SA-reCBS: Multi-robot task assignment with integrated reactive path generation

• In this paper, we study the multi-robot task assignment and path-finding problem (MRTAPF), where a number of robots are required to visit all given tasks while avoiding collisions with each other. We propose a novel two-layer algorithm SA-reCBS that cascades the simulated annealing algorithm and conflict-based search to solve this problem. Compared to other approaches in the field of MRTAPF, the advantage of SA-reCBS is that without requiring a pre-bundle of tasks to groups with the same number of groups as the number of robots, it enables a part of robots needed to visit all tasks in collision-free paths. We test the algorithm in various simulation instances and compare it with state-of-the-art algorithms. The result shows that SA-reCBS has a better performance with a higher success rate, less computational time, and better objective values.

Ämnesord

NATURVETENSKAP  -- Data- och informationsvetenskap -- Datorseende och robotik (hsv//swe)

NATURAL SCIENCES  -- Computer and Information Sciences -- Computer Vision and Robotics (hsv//eng)

TEKNIK OCH TEKNOLOGIER  -- Elektroteknik och elektronik -- Robotteknik och automation (hsv//swe)

ENGINEERING AND TECHNOLOGY  -- Electrical Engineering, Electronic Engineering, Information Engineering -- Robotics (hsv//eng)

Nyckelord

task assignment

multi-robot path-finding

multi-depot vehicle routing problem

Robotics and Artificial Intelligence

Robotik och artificiell intelligens

Publikations- och innehållstyp

ref (ämneskategori)

kon (ämneskategori)