Deterministic annealing with Potts neurons for multi-robot routing

Jennifer David, Thorsteinn Rögnvaldsson, Bo Söderberg, Mattias Ohlsson

Research output: Contribution to journalArticlepeer-review

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 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.

Original languageEnglish
Pages (from-to)321-334
Number of pages14
JournalIntelligent Service Robotics
Volume15
Issue number3
DOIs
Publication statusPublished - 2022 Jul

Subject classification (UKÄ)

  • Computational Mathematics

Free keywords

  • Approximation method
  • Deterministic annealing
  • Multiple robots
  • Task allocation
  • Task-ordering

Fingerprint

Dive into the research topics of 'Deterministic annealing with Potts neurons for multi-robot routing'. Together they form a unique fingerprint.

Cite this