The browser you are using is not supported by this website. All versions of Internet Explorer are no longer supported, either by us or Microsoft (read more here: https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Please use a modern browser to fully experience our website, such as the newest versions of Edge, Chrome, Firefox or Safari etc.

Photo of Mattias Ohlsson

Mattias Ohlsson

Professor

Photo of Mattias Ohlsson

Deterministic annealing with Potts neurons for multi-robot routing

Author

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

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.

Department/s

  • Computational Biology and Biological Physics - Undergoing reorganization
  • eSSENCE: The e-Science Collaboration

Publishing year

2022-07

Language

English

Pages

321-334

Publication/Series

Intelligent Service Robotics

Volume

15

Issue

3

Document type

Journal article

Publisher

Springer

Topic

  • Computational Mathematics

Keywords

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

Status

Published

ISBN/ISSN/Other

  • ISSN: 1861-2776