Deterministic annealing with Potts neurons for multi-robot routing

Summary, in English

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.

• Författare: Jennifer David; Thorsteinn Rögnvaldsson; Bo Söderberg; Mattias Ohlsson
• Avdelning/ar: Beräkningsbiologi och biologisk fysik - Har omorganiserats; eSSENCE: The e-Science Collaboration
• Publiceringsår: 2022-07
• Språk: Engelska
• Sidor: 321-334
• Publikation/Tidskrift/Serie: Intelligent Service Robotics
• Volym: 15
• Issue: 3
• Länkar: http://dx.doi.org/10.1007/s11370-022-00424-8
• Dokumenttyp: Artikel i tidskrift
• Förlag: Springer
• Ämne: Computational Mathematics
• Nyckelord: Approximation method; Deterministic annealing; Multiple robots; Task allocation; Task-ordering
• Status: Published
• ISBN/ISSN/Övrigt: ISSN: 1861-2776