The Multi-Agent Transportation Problem

Pascal Bachor, Rolf-David Bergdoll, Bernhard NebelAAAI 2023 · DOI

TL;DR

This paper introduces the Multi-Agent Transportation (MAT) problem, a more flexible generalization of multi-agent pathfinding and pickup/delivery problems. MAT allows agents to freely separate from containers and containers to collide, enabling solutions to previously unsolvable scenarios and potentially reducing planning time. The authors prove MAT is NP-complete and propose a SAT-based solver.

What Problem Does This Paper Address?

Existing multi-agent pathfinding (MAPF) and multi-agent pickup and delivery (MAPD) problems often make simplifying assumptions. MAPF focuses on agents avoiding each other, while MAPD typically involves fixed agent-container assignments and assumes containers are not obstacles once delivered. However, real-world scenarios like logistics or construction often require agents to temporarily move containers out of the way, or for containers to act as obstacles themselves. These situations can lead to unsolvable problems in standard MAPF/MAPD frameworks or require longer, less efficient plans. This paper addresses this gap by introducing the MAT problem, which relaxes these constraints to better model these complex, dynamic environments.

Methods

The authors formally define the MAT problem, highlighting its key differences from MAPF and MAPD: agents can separate from containers at any time, and containers can collide with each other. They establish the NP-completeness of MAT by reducing it to a series of SAT problems, a common technique for solving complex combinatorial problems. For planning, they employ an exponential search strategy, similar to SAT planning, to find the optimal makespan (minimum plan length). This involves building a propositional formula for a given makespan and using binary search to find the minimal makespan. They also introduce preprocessing steps to derive lower bounds for makespan and object distances.

Datasets

Not discussed in the paper. The authors generated their own instances for experiments.

Key Insights and Ideas

  • Container Collisions Matter: Allowing containers to collide significantly increases the problem's complexity and can lead to longer makespans compared to scenarios where containers are non-blocking. This highlights the importance of modeling realistic container interactions.
  • Agent-Container Separation is Crucial: The ability for agents to freely detach from containers is not just a convenience; it's essential for solving certain scenarios (e.g., when containers block each other or in tight spaces) and can lead to shorter plans.
  • MAT is Computationally Harder, but Tractable: While MAT is NP-complete, the authors demonstrate that it can be solved using SAT solvers, suggesting that practical solutions are achievable for many instances.
  • Agent-to-Container Ratio Impacts Difficulty: Instances with fewer agents than containers (a < c) are generally more difficult to solve, but increasing the number of agents can significantly reduce runtime. Conversely, when agents outnumber containers (a >= c), adding more agents can slightly increase difficulty.

Key Results

  • The MAT problem is proven to be NP-complete.
  • A SAT-based solver for MAT was implemented and evaluated.
  • Experiments showed that container collisions and the need for agents to cooperate in transportation (as opposed to fixed assignments) significantly increase runtime and makespan.
  • Instances with fewer agents than containers are generally harder.
  • The proposed MAT solver was compared to a modified CBS-based MAPD solver, with the latter showing faster runtimes on easier instances but the SAT-based MAT solver performing comparably on success rate, especially with more agents.

Limitations and Future Work

The authors acknowledge that their SAT-based solver's runtime can be high, especially for instances with many containers. They suggest that further optimizations are needed for scalability, particularly for scenarios with a large number of agents. Future work includes exploring CBS-based solvers for MAT, which might offer better performance, and investigating more efficient feasibility tests for MAT plans, aiming for a linear-time solution similar to some pebble motion problems. They also plan to address theoretical open problems.

Summary updated

BibTeX
@inproceedings{bachor2023multi,
  author = {Pascal Bachor and Rolf-David Bergdoll and Bernhard Nebel},
  title = {{The Multi-Agent Transportation Problem}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.1609/aaai.v37i10.26362},
}
Figure