Any-Angle Pathfinding for Multiple Agents Based on SIPP Algorithm

The problem of finding conflict-free trajectories for multiple agents of identical circular shape, operating in shared 2D workspace, is addressed in the paper and decoupled, e.g., prioritized, approach is used to solve this problem. Agents' workspace is tessellated into the square grid on which anyangle moves are allowed, e.g. each agent can move into an arbitrary direction as long as this move follows the straight line segment whose endpoints are tied to the distinct grid elements. A novel any-angle planner based on Safe Interval Path Planning (SIPP) algorithm is proposed to find trajectories for an agent moving amidst dynamic obstacles (other agents) on a grid. This algorithm is then used as part of a prioritized multi-agent planner AA-SIPP(m). On the theoretical side, we show that AA-SIPP(m) is complete under well-defined conditions. On the experimental side, in simulation tests with up to 250 agents involved, we show that our planner finds much better solutions in terms of cost (up to 20%) compared to the planners relying on cardinal moves only. Copyright © 2017, Association for the Advancement of Artificial Intelligence (www.aaai.org).

Авторы
Yakovlev K.1, 2 , Andreychuk A. 1, 3
Редакторы
-
Сборник материалов конференции
Издательство
AAAI press
Номер выпуска
-
Язык
Английский
Страницы
586-593
Статус
Опубликовано
Подразделение
-
Ссылка
-
DOI
-
Номер
-
Том
-
Год
2017
Организации
  • 1 Federal Research Center Computer Science and Control, Russian Academy of Sciences, Moscow, Russian Federation
  • 2 National Research University, Higher School of Economics, Moscow, Russian Federation
  • 3 RUDN University, Moscow, Russian Federation
Ключевые слова
Motion planning; Multi agent systems; Scheduling; Arbitrary direction; Circular shape; Conflict-free trajectory; Dynamic obstacles; Multiple agents; Safe intervals; Simulation tests; Straight-line segments; Software agents
Дата создания
19.10.2018
Дата изменения
19.10.2018
Постоянная ссылка
https://repository.rudn.ru/ru/records/article/record/6075/