Improving Continuous-time Conflict Based Search

Andreychuk A.; K. Yakovlev; Boyarski E.; Stern R.

?

Improving Continuous-time Conflict Based Search

P. 11220–11227.

Andreychuk A., Yakovlev K., Boyarski E., Stern R.

Conflict-Based Search (CBS) is a powerful algorithmic framework for optimally solving classical multi-agent path finding (MAPF) problems, where time is discretized into the time steps. Continuous-time CBS (CCBS) is a recently proposed version of CBS that guarantees optimal solutions without the need to discretize time. However, the scalability of CCBS is limited because it does not include any known improvements of CBS. In this paper, we begin to close this gap and explore how to adapt successful CBS improvements, namely, prioritizing conflicts (PC), disjoint splitting (DS), and high-level heuristics, to the continuous time setting of CCBS. These adaptions are not trivial, and require careful handling of different types of constraints, applying a generalized version of the Safe interval path planning (SIPP) algorithm, and extending the notion of cardinal conflicts. We evaluate the effect of the suggested enhancements by running experiments both on general graphs and 2 k -neighborhood grids. CCBS with these improvements significantly outperforms vanilla CCBS, solving problems with almost twice as many agents in some cases and pushing the limits of multiagent path finding in continuous-time domains.

Language: English

Full text

Text on another site

Keywords: multi-agent path finding

In book

The Thirty-Fifth AAAI Conference on Artificial Intelligence. Technical Tracks 13

Vol. 35. , AAAI Press, 2021.

Decentralized Unlabeled Multi-agent Pathfinding Via Target And Priority Swapping

Dergachev S., Yakovlev K., , in: ECAI 2024. 27th European Conference on Artificial Intelligence, October 19 – 24 October 2024, Santiago de Compostela, Spain – Including 13th Conference on Prestigious Applications of Intelligent Systems (PAIS 2024).: IOS Press, 2024. P. 4344–4351.

Added: September 11, 2024

Decentralized Unlabeled Multi-agent Navigation in Continuous Space

Dergachev S., Yakovlev K., , in: Interactive Collaborative Robotics. 9th International Conference, ICR 2024, Mexico City, Mexico, October 14–18, 2024, Proceedings.: Cham: Springer, 2024. P. 186–200.

Added: September 11, 2024

Towards a Complete Multi-agent Pathfinding Algorithm for Large Agents

Dergachev S., Yakovlev K., , in: Advances in Computational Intelligence. 21st Mexican International Conference on Artificial Intelligence, MICAI 2022, Monterrey, Mexico, October 24–29, 2022, Proceedings* 1.: Cham: Springer, 2022. P. 355–367.

Multi-agent pathfinding (MAPF) is a challenging problem which is hard to solve optimally even when simplifying assumptions are adopted, e.g. planar graphs (typically – grids), discretized time, uniform duration of move and wait actions etc. On the other hand, MAPF under such restrictive assumptions (also known as the Classical MAPF) is equivalent to the so-called ...

Added: May 16, 2023

Multi-agent Pathfinding With Continuous Time

Andreychuk A., Yakovlev K., Surynek P. et al., Artificial Intelligence 2022 Vol. 305 Article 103662

Multi-Agent Pathfinding (MAPF) is the problem of finding paths for multiple agents such that each agent reaches its goal and the agents do not collide. In recent years, variants of MAPF have risen in a wide range of real-world applications such as warehouse management and autonomous vehicles. Optimizing common MAPF objectives, such as minimizing sum-of-costs ...

Added: August 26, 2022

Flatland Competition 2020: MAPF and MARL for Efficient Train Coordination on a Grid World

Laurent F., Schneider M., Scheller C. et al., , in: Proceedings of Machine Learning ResearchVol. 133: Proceedings of the NeurIPS 2020: Competition and Demonstration Track.: PMLR, 2021. P. 275–301.

The Flatland competition aimed at finding novel approaches to solve the vehicle re-scheduling problem (VRSP). The VRSP is concerned with scheduling trips in traffic networks and the re-scheduling of vehicles when disruptions occur, for example the breakdown of a vehicle. While solving the VRSP in various settings has been an active area in operations research ...

Added: September 6, 2021

Prioritized Multi-Agent Path Finding for Differential Drive Robots

Yakovlev K., Andreychuk A., Vorobyev V., , in: Proceedings of the 2019 European Conference on Mobile Robotics (ECMR 2019).: Prague: IEEE, 2019. P. 1–6.

Methods for centralized planning of the collision-free trajectories for a fleet of mobile robots typically solve the discretized version of the problem and rely on numerous simplifying assumptions, e.g. moves of uniform duration, cardinal only translations, equal speed and size of the robots etc., thus the resultant plans can not always be directly executed by ...

Added: January 15, 2020

Multi-Agent Pathfinding with Continuous Time

Andreychuk A., Yakovlev K., Atzmon D. et al., , in: Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI 2019).: International Joint Conferences on Artificial Intelligence, 2019. P. 39–45.

Multi-Agent Pathfinding (MAPF) is the problem offinding paths for multiple agents such that everyagent reaches its goal and the agents do not col-lide. Most prior work on MAPF was on grids, as-sumed agents’ actions have uniform duration, andthat time is discretized into timesteps. We proposea MAPF algorithm that does not rely on these as-sumptions, is ...

Added: August 21, 2019

Two Techniques That Enhance the Performance of Multi-robot Prioritized Path Planning

Andreychuk A., Yakovlev K., , in: Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2018).: IFAAMAS, 2018. P. 2177–2179.

We introduce and empirically evaluate two techniques aimed at enhancing the performance of multi-robot prioritized path planning.The first technique is the deterministic procedure for re-scheduling(as opposed to well-known approach based on random restarts), the second one is the heuristic procedure that modifies the search-spaceof the individual planner involved in the prioritized path findin ...

Added: August 14, 2019

Applying MAPP Algorithm for Cooperative Path Finding in Urban Environments

Andreychuk A., Yakovlev K., , in: Interactive Collaborative Robotics: Second International Conference, ICR 2017, Hatfield, UK, September 12-16, 2017, Proceedings.: Springer, 2017. P. 1–10.

The paper considers the problem of planning a set of non-conflict trajectories for the coalition of intelligent agents (mobile robots). Two divergent approaches, e.g. centralized and decentralized, are surveyed and analyzed. Decentralized planner – MAPP is described and applied to the task of finding trajectories for dozens UAVs performing nap-of-the-earth flight in urban environments. Results ...

Added: November 6, 2017

Any-Angle Pathfinding for Multiple Agents Based on SIPP Algorithm

Yakovlev K., Andreychuk A., , in: Proceedings of the 27th International Conference on Automated Planning and Scheduling (ICAPS 2017).: Palo Alto: AAAI Press, 2017. P. 586–593.

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 any-angle moves are allowed, e.g. each agent can move into an ...

Added: July 17, 2017