Multi-Agent Path Finding as Planning

Description

Multi-Agent Path Finding (MAPF) is the problem of deciding whether a set of agents on a 2D grid (or graph, which is equivalent) can reach their desired goals from their initial positions. A special variant of this problem is (probably) computationally harder, since we require optimal plans, i.e., solutions where the overall number of steps taken is minimal. This problem is proved to be in PSPACE, as well as being NP-hard. Due to PSPACE-membership it's possible to model this problem as a classical planning problem, which is known to be PSPACE-complete.

Thus, the task in this project is to find an adequate translation of MAPF problems into a classical planning problem (or possibly with multiple different translations with different properties) and to evaluate the respective problem with domain-independent planning systems. These results should be compared with specialized MAPF solvers.

Depending on the strengths of the respective student and the time available (i.e., the number of units of the project), we could also look into the computational complexity of this problem, as bounds are still not tight. (I.e., it is yet an open question whether MAPF is NP-complete or PSPACE-complete).

Goals

  • Find a classical planning model (or multiple) that encodes a given Multi-Agent Path Finding (MAPF) problem
  • Conduct an empirical evaluation of the model comparing performance of domain-independent planners with specialized MAPF solvers

Requirements

  • None required, though having prior knowledge in AI planning will be highly beneficial.

Background Literature

At SoCS 2019 (https://aaai.org/Library/SOCS/socs19contents.php) there was a challenge paper on MAPF, which essentially serves as survey:

Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks by Stern et al.

Gain

You'll become an expert in

  • multi-agent pathfinding -- an important problem in robotics
  • classical planning, an important sub discipline in Artificial Intelligence for autonomous problem solving

Keywords

  • Robotics
  • Multi-Agent Path Finding (MAPF)
  • AI Planning
  • Complexity Studies

Updated:  10 August 2021/Responsible Officer:  Dean, CECS/Page Contact:  CECS Marketing