Resolving Spatial-Time Conflicts In A Set Of Any-angle Or Angle-constrained Grid Paths
This addresses path planning conflicts for multiple agents in grid environments, though it appears incremental as it builds on existing MAPF approaches.
The paper tackles the multi-agent path finding problem on a 2D grid by developing a centralized algorithm that resolves conflicts in independently computed plans through local re-planning and time offsets. Experimental results demonstrate the algorithm finds high-quality conflict-free solutions with low computational cost.
We study the multi-agent path finding problem (MAPF) for a group of agents which are allowed to move into arbitrary directions on a 2D square grid. We focus on centralized conflict resolution for independently computed plans. We propose an algorithm that eliminates conflicts by using local re-planning and introducing time offsets to the execution of paths by different agents. Experimental results show that the algorithm can find high quality conflict-free solutions at low computational cost.