Optimal Multi-Agent Path Finding for Precedence Constrained Planning Tasks
Multi-Agent Path Finding (MAPF) is the problem of finding collision-free paths for multiple agents from their start locations to end locations. We consider an extension to this problem, Precedence Constrained Multi-Agent Path Finding (PC-MAPF), wherein agents are assigned a sequence of planning tasks that contain precedence constraints between them. PC-MAPF has various applications, for example in multi-agent pickup and delivery problems where some objects might require multiple agents to collaboratively pickup and move them in unison. Precedence constraints also arise in warehouse assembly problems where before a manufacturing task can begin, its input resources must be manufactured and delivered. We propose a novel algorithm, Precedence Constrained Conflict Based Search (PC-CBS), which finds makespan-optimal solutions for this class of problems. PC-CBS utilizes a Precedence-Constrained Task-Graph to define valid intervals for each planning task and updates them when precedence conflicts are encountered. We benchmark the performance of this algorithm over various warehouse assembly, and multi-agent pickup and delivery tasks, and use it to evaluate the sub-optimality of a recently proposed efficient baseline.
Code (0)
등록된 구현이 없습니다.
Tasks
Multi-Agent Path FindingvalidSimilar Papers 제목 키워드 기반
Optimal Task Assignment and Path Planning using Conflict-Based Search with Precedence and Temporal Constraints
The Multi-Agent Path Finding (MAPF) problem entails finding collision-free paths for a set of agents, guiding them from their start to goal locations. However, MAPF does not account for several practical task-related con…
Multi-Agent Path FindingReinforcement Learning (RL)Large Neighborhood Search for Multi-Agent Task Assignment and Path Finding with Precedence Constraints
Many multi-robot applications require tasks to be completed efficiently and in the correct order, so that downstream operations can proceed at the right time. Multi-agent path finding with precedence constraints (MAPF-PC…
Neural Pathways to Program Success: Hopfield Networks for PERT Analysis
Project and task scheduling under uncertainty remains a fundamental challenge in program and project management, where accurate estimation of task durations and dependencies is critical for delivering complex, multi proj…
SchedulingOptimal Sequential Task Assignment and Path Finding for Multi-Agent Robotic Assembly Planning
We study the problem of sequential task assignment and collision-free routing for large teams of robots in applications with inter-task precedence constraints (e.g., task $A$ and task $B$ must both be completed before ta…
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…