IEEE Robotics and Automation Letters · 2022 · 29 citations · 25 references
ComputingAutonomous SystemsComputational GeometryMotion PlanningPath PlanningCollision DetectionRobot Motion PlanningAutonomous Vehicle Path PlanningCollision CheckingMulti-agent Collision AvoidanceMulti-agent Path PlanningPath Planning For Collision AvoidancePathfinding AlgorithmsScalable Planning AlgorithmsTrajectory Planning For Collision Avoidance
We address a challenging multi-agent pathfinding (MAPF) problem for hundreds of agents moving on a 2D roadmap with continuous time. Despite its known potential for producing better solutions compared to typical grid and discrete-time cases, few approaches have been established to solve this problem due to the intractability of collision checks on a large scale. In this work, we propose Prioritized Safe-Interval Path Planning with Continuous-Time Conflicts (PSIPP/CTC) that extends a scalable prioritized planning algorithm to work on the 2D roadmap and continuous-time setup by alleviating intensive collision checks. Our approach involves a novel concept named Continuous-Time Conflict (CTC), which describes a pair among vertices and edges associated with continuous-time intervals within which collisions can happen between agents. We pre-compute CTCs using geometric neighbor-search and sweeping techniques and annotate roadmaps with the CTCs just once before planning starts. Doing so allows us to efficiently enumerate collision-free time intervals for all vertices and edges and find each agent's path with continuous time in prioritized planning. Extensive experimental evaluations demonstrate that PSIPP/CTC significantly outperforms existing methods in terms of planning success rate and runtime while maintaining an acceptable solution quality. As a proof of concept, we also confirmed the effectiveness of the proposed approach on a physics simulation with differential wheeled robots.
25
Conflict-based search for optimal multi-agent pathfinding
Guni Sharon, Roni Stern, Ariel Felner et al. · Artificial Intelligence · 2014 · 1.2K citations
Algorithms for Reporting and Counting Geometric Intersections
Bentley, Ottmann · IEEE Transactions on Computers · 1979 · 999 citations
Michael Erdmann, Tomás Lozano‐Pérez · Algorithmica · 1987 · 743 citations