# Explanation Generation for Multi-Modal Multi-Agent Path Finding with Optimal Resource Utilization using Answer Set Programming

@article{Bogatarkan2020ExplanationGF, title={Explanation Generation for Multi-Modal Multi-Agent Path Finding with Optimal Resource Utilization using Answer Set Programming}, author={Aysu Bogatarkan and Esra Erdem}, journal={Theory and Practice of Logic Programming}, year={2020}, volume={20}, pages={974 - 989} }

Abstract The multi-agent path finding (MAPF) problem is a combinatorial search problem that aims at finding paths for multiple agents (e.g., robots) in an environment (e.g., an autonomous warehouse) such that no two agents collide with each other, and subject to some constraints on the lengths of paths. We consider a general version of MAPF, called mMAPF, that involves multi-modal transportation modes (e.g., due to velocity constraints) and consumption of different types of resources (e.g… Expand

#### Topics from this paper

#### 2 Citations

Flexible and Explainable Solutions for Multi-Agent Path Finding Problems

- Computer Science
- Electronic Proceedings in Theoretical Computer Science
- 2021

This study introduces some flexible and explainable solutions for MAPF and its variants and addresses the challenges of flexibility as well as explainability. Expand

DPLL(MAPF): an Integration of Multi-Agent Path Finding and SAT Solving Technologies

- Computer Science
- SOCS
- 2021

A novel compilation scheme called DPLL(MAPF) is presented in this short paper in which the consistency checking of partial assignments of decision variables with respect to the MAPF rules is integrated directly into the SAT solver. Expand

#### References

SHOWING 1-10 OF 41 REFERENCES

Multi-modal Multi-agent Path Finding with Optimal Resource Utilization

- Computer Science
- 2020

This work introduces a declarative method to solve multi-agent path finding, called mMAPF, using answer set programming that provides a flexible formal framework to address all these challenges while optimizing multiple objectives. Expand

A Declarative Method for Dynamic Multi-Agent Path Finding

- Computer Science
- GCAI
- 2019

A dynamic variant of MAPF is studied, called D-MAPF, which allows changes in the environment and in the team at different times, and a new method is introduced to solve D- MAPF, using answer set programming. Expand

Explainable Multi Agent Path Finding

- Computer Science
- AAMAS
- 2020

An explanation scheme for Multi Agent Path Finding is proposed, which bases explanations on simplicity of visual verification by human’s cognitive process and decomposes a plan into segments such that within each segment, the paths of the agents are disjoint. Expand

Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks

- Computer Science
- SOCS
- 2019

A new grid-based benchmark for MAPF is introduced, and it is demonstrated experimentally that it poses a challenge to contemporary MAPF algorithms. Expand

A General Formal Framework for Pathfinding Problems with Multiple Agents

- Computer Science
- AAAI
- 2013

This work introduces a formal framework that is general enough to address many real-life applications, and uses the expressive high-level representation formalism and efficient solvers of the declarative programming paradigm Answer Set Programming to improve the computational efficiency and/or solution quality. Expand

Conflict-based search for optimal multi-agent pathfinding

- Computer Science
- Artif. Intell.
- 2012

A new search algorithm called Conflict Based Search (CBS), which enables CBS to examine fewer states than A* while still maintaining optimality and shows a speedup of up to a full order of magnitude over previous approaches. Expand

Fast and Memory-Efficient Multi-Agent Pathfinding

- Computer Science
- ICAPS
- 2008

FAR (Flow Annotation Replanning), a method for multi-agent path planning on grid maps, is introduced and is shown to run significantly faster, use much less memory, and scale up to problems with more mobile units. Expand

Efficient and complete centralized multi-robot path planning

- Mathematics
- IROS 2011
- 2011

Multi-robot path planning is abstracted as the problem of computing a set of non-colliding paths on a graph for multiple robots. A naive search of the composite search space, although complete, has… Expand

Planning optimal paths for multiple robots on graphs

- Computer Science, Engineering
- 2013 IEEE International Conference on Robotics and Automation
- 2013

Two multiflow based integer linear programming models are proposed that compute minimum last arrival time and minimum total distance solutions for the authors' MPP formulation, respectively that are complete and guaranteed to yield true optimal solutions. Expand

Cooperative Pathfinding

- Computer Science
- AIIDE
- 2005

The results show that the new algorithms, especially WHCA*, are robust and efficient solutions to the Cooperative Pathfinding problem, finding more successful routes and following better paths than Local Repair A*. Expand