Skip to content
conftrace_
2018 IJCAI IJCAI 2018

Solving Multi-Agent Path Finding on Strongly Biconnected Digraphs (Extended Abstract)

Abstract

We present and evaluate diBOX, an algorithm for multi-agent path finding on strongly biconnected directed graphs. diBOX runs in polynomial time, computes suboptimal solutions and is complete for instances on strongly biconnected digraphs with at least two unoccupied positions. A detailed empirical analysis shows a good scalability for diBOX.

🐣 Hot Topic Early Bird - graph algorithm

Authors

Adi Botea, Davide Bonusi, Pavel Surynek

Topics

Mathematics & Optimization > Mathematics > Graph Theory Mathematics & Optimization > Optimization > Combinatorial Optimization

Keywords

directed graph polynomial time graph algorithm path finding multi-agent system
Download PDF

More from IJCAI 2018

All IJCAI 2018 papers →
MCTS-Minimax Hybrids with State Evaluations (Extended Abstract)
A COP Model for Graph-Constrained Coalition Formation (Extended Abstract)
On the Logical Properties of the Description Logic DL^N (Extended abstract)
Enhancing Context Knowledge Repositories with Justifiable Exceptions (Extended Abstract)
Revisiting the Arcade Learning Environment: Evaluation Protocols and Open Problems for General Agents (Extended Abstract)
On the Equivalence between Assumption-Based Argumentation and Logic Programming (Extended Abstract)