Source-linked AI summary
Optimal Target Assignment and Path Finding for Teams of Agents
Hang Ma, Sven Koenig
TL;DR
TAPF asks how teams of agents can be assigned to team-specific targets and routed without collisions while minimizing makespan. The paper introduces CBM, which combines within-team min-cost flow with high-level conflict-based search. CBM is proven correct, complete, and optimal, and experiments report scalability to dozens of teams and hundreds of agents, including a simulated warehouse system.
Problem
TAPF addresses target assignment and collision-free path planning for teams of agents, an intermediate case between anonymous and non-anonymous MAPF.
Method
CBM combines within-team min-cost max-flow on a time-expanded network with high-level conflict-based search across teams.
Results
CBM is correct, complete, and optimal, and outperforms non-anonymous MAPF algorithms in scalability and solution quality in the experiments.
Takeaways & Limitations
CBM generalizes to TAPF instances with dozens of teams and hundreds of agents and is adapted to a simulated warehouse system.
Takeaways & Limitations
The collision model forbids vertex collisions and opposite-direction edge collisions between agents.
Abstract
from arXiv · showhide
We study the TAPF (combined target-assignment and path-finding) problem for teams of agents in known terrain, which generalizes both the anonymous and non-anonymous multi-agent path-finding problems. Each of the teams is given the same number of targets as there are agents in the team. Each agent has to move to exactly one target given to its team such that all targets are visited. The TAPF problem is to first assign agents to targets and then plan collision-free paths for the agents to their targets in a way such that the makespan is minimized. We present the CBM (Conflict-Based Min-Cost-Flow) algorithm, a hierarchical algorithm that solves TAPF instances optimally by combining ideas from anonymous and non-anonymous multi-agent path-finding algorithms. On the low level, CBM uses a min-cost max-flow algorithm on a time-expanded network to assign all agents in a single team to targets and plan their paths. On the high level, CBM uses conflict-based search to resolve collisions among agents in different teams. Theoretically, we prove that CBM is correct, complete and optimal. Experimentally, we show the scalability of CBM to TAPF instances with dozens of teams and hundreds of agents and adapt it to a simulated warehouse system.
1. INTRODUCTION
TAPF addresses team-based target assignment and collision-free path planning between anonymous and non-anonymous MAPF, motivated by applications such as warehouses and towing vehicles. CBM combines flow-based within-team planning with conflict-based coordination across teams, with theoretical and experimental support.
- Motivation: Many applications, including autonomous towing vehicles and warehouse robots, require agents to assign targets and plan collision-free paths.The motivating systems include aircraft towing and inventory-pod transport.
- Problem: TAPF assigns each team’s agents to its unique targets and plans collision-free paths while minimizing makespan.Agents within a team are exchangeable, whereas agents across teams are not.
- Related Problems: TAPF lies between anonymous MAPF, where agents are exchangeable, and non-anonymous MAPF, where agent-target assignments are fixed.The paper notes that real-world applications often have more than one team but fewer teams than agents.
- Contribution: CBM combines conflict-based search with min-cost max-flow on a time-expanded network to assign within-team targets and coordinate different teams.This structure is intended to retain polynomial-time within-team planning while addressing cross-team collisions.
- Contribution: The paper proves CBM correct, complete, and optimal and evaluates its scalability on TAPF instances with dozens of teams and hundreds of agents.CBM is also adapted to a simulated warehouse system.
2. TAPF
TAPF formalizes assigning team agents to unique targets and finding collision-free paths of minimum makespan. The paper reduces bounded-horizon TAPF to integer multi-commodity flow and uses this characterization to establish tractable special cases.
- Definition: A TAPF instance places teams of agents on a connected graph, with each team receiving as many unique targets as it has agents.Each agent must reach one unique target belonging to its team.
- Feasibility: A solution gives every agent a valid path from its start to its assigned target while allowing waits and forbidding vertex and edge collisions.Vertex collisions share a location at the same time; edge collisions traverse one edge in opposite directions simultaneously.
- Objective: The makespan is the earliest time when all agents have reached their targets and stopped, and the objective is to minimize it.Team cost is the latest arrival time among agents in that team.
- Flow Reduction: A T-step time-expanded network represents starts, goals, waits, movements, vertex capacities, and edge gadgets that prevent simultaneous opposing traversals.Unit-capacity flow encodes feasible agent paths over the time horizon.
- Flow Reduction: The reduction establishes a correspondence between feasible integer multi-commodity flows carrying one unit per agent and TAPF solutions with makespans at most T.An optimal solution can be found by checking increasing horizons, although the resulting flow problem is NP-hard.
- Special Case: If only one team exists, TAPF is solvable optimally in polynomial time.This follows because the instance becomes anonymous MAPF, which admits polynomial-time flow-based solution methods.
3. CONFLICT-BASED MIN-COST FLOW
CBM combines high-level conflict-based search across teams with low-level min-cost flow within each team. This hierarchy assigns targets, plans paths, biases solutions away from inter-team collisions, and is proved correct, complete, and optimal.
- High-Level Search: CBM treats each team as a meta-agent, using CBS to resolve collisions between agents in different teams.The high level searches a binary tree of constraint-and-path nodes and branches on detected collisions.
- Low-Level Search: The low level uses min-cost max-flow on a time-expanded network to assign a team’s agents to unique targets and plan collision-free paths.The network encodes vertex and edge constraints by removing corresponding edges.
- Low-Level Search: The low-level search iteratively increases the time horizon T until a feasible flow for all agents in the team is found or an upper bound is exhausted.It can begin at the parent node’s key, which provides a lower bound on the child key.
- Low-Level Search: CBM biases low-level flow toward paths that avoid vertex and edge collisions with agents from other teams.Edge weights penalize shared vertices at the same time and opposing traversal of the same edge simultaneously.
- Low-Level Search: The min-cost flow procedure finds a minimum-weight feasible maximal flow using the successive shortest path algorithm.Its stated complexity is O(U(|E′| + |V′| log |V′|)).
- Correctness and Optimality: CBM is proved correct, complete, and optimal.The proof uses correspondence between feasible integer flows and valid within-team paths, together with properties of the high-level search keys.
4. EXPERIMENTS
The experiments evaluate CBM against alternative solvers, vary team size and total agents, and test a simulated warehouse system. CBM solves TAPF instances optimally and scales to hundreds of agents, while performance depends on low-level assignment quality and the number of inter-team collisions.
- 4.1 Alternative Solvers: CBM is compared with optimal CBS, ILP-based MAPF, unweighted CBM, and ILP-based TAPF solvers on randomly generated grid instances.Experiment 1 uses 30×30 4-neighbor grids with 10% randomly blocked cells, varying from 10 to 50 agents in teams of five.
- 4.1 Alternative Solvers: CBM solves all TAPF instances within the 5-minute time limit, while the comparison records success rates, makespans, and running times.The reported means are computed over instances solved within the time limit.
- 4.1 Alternative Solvers: Optimal TAPF solutions have smaller makespans than optimal MAPF solutions because TAPF permits assigning agents to targets rather than fixing random assignments.CBM and CBS have similar running times because their single-team and single-agent low-level searches are fast.
- 4.1 Alternative Solvers: Unweighted CBM solves less than half of TAPF instances above 10 agents because low-level max-flow paths create many inter-team collisions and high-level CBS expansions.The experiments conclude that biasing the low-level search with min-cost flow is important for solving all instances within the time limit.
- 4.1 Alternative Solvers: The ILP-based TAPF solver solves less than half of instances above 30 agents and runs much longer than CBM.Although its formulation has fewer variables than corresponding MAPF formulations, TAPF uses integer rather than Boolean variables and a different starting value for T.
- 4.2 Team Size: With 100 agents, CBM solves all instances across team sizes from 50 to 2 agents; larger teams yield smaller makespans and running times.Larger teams provide more freedom for agent-to-target assignment, while fewer teams reduce high-level collision resolution.
- 4.3 Number of Agents: For 250 agents or fewer, CBM's success rate exceeds 85%; as the agent count rises to 450, success rates decrease while makespans and running times increase.The authors attribute the degradation to more inter-team collisions, including heavily occupied grids at 450 agents.
- 4.4 Warehouse System: In the simulated Kiva warehouse, CBM solves 40 of 50 instances, achieving an 80% success rate with mean makespan 63.73 and mean running time 91.61 seconds.The warehouse instances contain 420 drive units and use randomly selected storage-location starts to create difficult cases.
5. CONCLUSIONS
The paper establishes CBM as an optimal TAPF solver and reports scalability from dozens of teams to hundreds of agents, including a simulated warehouse application.
- CBM is correct, complete and optimal for solving the TAPF problem.
- CBM outperforms non-anonymous MAPF algorithms in scalability and solution quality.
- CBM generalizes to instances with dozens of teams and hundreds of agents.
- The algorithm demonstrates promise for applications requiring TAPF, including simulated warehouse systems.