hh.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Deterministic annealing with Potts neurons for multi-robot routing
Halmstad University, School of Information Technology.ORCID iD: 0000-0001-6119-6615
Halmstad University, School of Information Technology.ORCID iD: 0000-0001-5163-2997
Lund University, Lund, Sweden.
Halmstad University, School of Information Technology. Lund University, Lund, Sweden.ORCID iD: 0000-0003-1145-4297
2022 (English)In: Intelligent Service Robotics, ISSN 1861-2776, Vol. 15, no 3, p. 321-334Article in journal (Refereed) Published
Abstract [en]

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. © The Author(s) 2022

Place, publisher, year, edition, pages
Heidelberg: Springer, 2022. Vol. 15, no 3, p. 321-334
Keywords [en]
Task allocation, Multiple robots, Task-ordering, Deterministic annealing, Approximation method
National Category
Robotics
Identifiers
URN: urn:nbn:se:hh:diva-46801DOI: 10.1007/s11370-022-00424-8ISI: 000798147000001Scopus ID: 2-s2.0-85130304007OAI: oai:DiVA.org:hh-46801DiVA, id: diva2:1659762
Funder
Halmstad University
Note

Funding: Open access funding provided by Halmstad University. 

Available from: 2022-05-21 Created: 2022-05-21 Last updated: 2022-08-23Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

David, JenniferRögnvaldsson, ThorsteinnOhlsson, Mattias

Search in DiVA

By author/editor
David, JenniferRögnvaldsson, ThorsteinnOhlsson, Mattias
By organisation
School of Information Technology
Robotics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 60 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf