Prioritized SIPP for Multi-Agent Path Finding With Kinematic Constraints
Multi-Agent Path Finding (MAPF) is a long-standing problem in Robotics and Artificial Intelligence in which one needs to find a set of collision-free paths for a group of mobile agents (robots) operating in the shared workspace. Due to its importance, the problem is well-studied and multiple optimal and approximate algorithms are known. However, many of them abstract away from the kinematic constraints and assume that the agents can accelerate/decelerate instantaneously. This complicates the application of the algorithms on the real robots. In this paper, we present a method that mitigates this issue to a certain extent. The suggested solver is essentially, a prioritized planner based on the well-known Safe Interval Path Planning (SIPP) algorithm. Within SIPP we explicitly reason about the speed and the acceleration thus the constructed plans directly take kinematic constraints of agents into account. We suggest a range of heuristic functions for that setting and conduct a thorough empirical evaluation of the suggested algorithm.
Code (0)
등록된 구현이 없습니다.
Tasks
Multi-Agent Path FindingSimilar Papers 제목 키워드 기반
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 t…
Prioritized Planning for Continuous-time Lifelong Multi-agent Pathfinding
Multi-agent Path Finding (MAPF) is the problem of planning collision-free movements of agents so that they get from where they are to where they need to be. Commonly, agents are located on a graph and can traverse edges.…
Multi-Agent Path FindingSafe Interval Path Planning With Kinodynamic Constraints
Safe Interval Path Planning (SIPP) is a powerful algorithm for solving single-agent pathfinding problem when the agent is confined to a graph and certain vertices/edges of this graph are blocked at certain time intervals…
Optimal and Bounded Suboptimal Any-Angle Multi-agent Pathfinding
Multi-agent pathfinding (MAPF) is the problem of finding a set of conflict-free paths for a set of agents. Typically, the agents' moves are limited to a pre-defined graph of possible locations and allowed transitions bet…
Multi-Agent Pathfinding with Continuous Time
Multi-Agent Pathfinding (MAPF) is the problem of finding paths for multiple agents such that every agent reaches its goal and the agents do not collide. Most prior work on MAPF was on grids, assumed agents' actions have …