Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Deterministic annealing with Potts neurons for multi-robot routing

David, Jennifer ; Rögnvaldsson, Thorsteinn ; Söderberg, Bo LU and Ohlsson, Mattias LU orcid (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)
Please use this url to cite or link to this publication:
author
; ; and
organization
publishing date
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}},
}