Deterministic annealing with Potts neurons for multi-robot routing
(2022) In Intelligent Service Robotics 15(3). p.321-334- Abstract
A deterministic annealing (DA) method is presented for solving the multi-robot routing problem with min–max objective. This is an NP-hard problem belonging to the multi-robot task allocation set of problems where robots are assigned to a group of sequentially ordered tasks such that the cost of the slowest robot is minimized. The problem is first formulated in a matrix form where the optimal solution of the problem is the minimum-cost permutation matrix without any loops. The solution matrix is then found using the DA method is based on mean field theory applied to a Potts spin model which has been proven to yield near-optimal results for NP-hard problems. Our method is bench-marked against simulated annealing and a heuristic search... (More)
A deterministic annealing (DA) method is presented for solving the multi-robot routing problem with min–max objective. This is an NP-hard problem belonging to the multi-robot task allocation set of problems where robots are assigned to a group of sequentially ordered tasks such that the cost of the slowest robot is minimized. The problem is first formulated in a matrix form where the optimal solution of the problem is the minimum-cost permutation matrix without any loops. The solution matrix is then found using the DA method is based on mean field theory applied to a Potts spin model which has been proven to yield near-optimal results for NP-hard problems. Our method is bench-marked against simulated annealing and a heuristic search method. The results show that the proposed method is promising for small-medium sized problems in terms of computation time and solution quality compared to the other two methods.
(Less)
- author
- David, Jennifer
; Rögnvaldsson, Thorsteinn
; Söderberg, Bo
LU
and Ohlsson, Mattias
LU
- organization
- publishing date
- 2022-07
- type
- Contribution to journal
- publication status
- published
- subject
- keywords
- Approximation method, Deterministic annealing, Multiple robots, Task allocation, Task-ordering
- in
- Intelligent Service Robotics
- volume
- 15
- issue
- 3
- pages
- 14 pages
- publisher
- Springer
- external identifiers
-
- scopus:85130304007
- ISSN
- 1861-2776
- DOI
- 10.1007/s11370-022-00424-8
- language
- English
- LU publication?
- yes
- id
- 2a5038d6-8763-49bf-a252-f6a44d401e8f
- date added to LUP
- 2022-12-28 11:01:52
- date last changed
- 2024-04-18 17:10:34
@article{2a5038d6-8763-49bf-a252-f6a44d401e8f, abstract = {{<p>A deterministic annealing (DA) method is presented for solving the multi-robot routing problem with min–max objective. This is an NP-hard problem belonging to the multi-robot task allocation set of problems where robots are assigned to a group of sequentially ordered tasks such that the cost of the slowest robot is minimized. The problem is first formulated in a matrix form where the optimal solution of the problem is the minimum-cost permutation matrix without any loops. The solution matrix is then found using the DA method is based on mean field theory applied to a Potts spin model which has been proven to yield near-optimal results for NP-hard problems. Our method is bench-marked against simulated annealing and a heuristic search method. The results show that the proposed method is promising for small-medium sized problems in terms of computation time and solution quality compared to the other two methods.</p>}}, author = {{David, Jennifer and Rögnvaldsson, Thorsteinn and Söderberg, Bo and Ohlsson, Mattias}}, issn = {{1861-2776}}, keywords = {{Approximation method; Deterministic annealing; Multiple robots; Task allocation; Task-ordering}}, language = {{eng}}, number = {{3}}, pages = {{321--334}}, publisher = {{Springer}}, series = {{Intelligent Service Robotics}}, title = {{Deterministic annealing with Potts neurons for multi-robot routing}}, url = {{http://dx.doi.org/10.1007/s11370-022-00424-8}}, doi = {{10.1007/s11370-022-00424-8}}, volume = {{15}}, year = {{2022}}, }