Learning to Resolve Conflicts for Multi-Agent Path Finding with Conflict-Based Search

Authors

  • Taoan Huang University of Southern California
  • Sven Koenig University of Southern California
  • Bistra Dilkina University of Southern California

Keywords:

Multiagent Planning, Planning/Scheduling and Learning, Heuristic Search, Optimization

Abstract

Conflict-Based Search (CBS) is a state-of-the-art algorithm for multi-agent path finding. On the high level, CBS repeatedly detects conflicts and resolves one of them by splitting the current problem into two subproblems. Previous work chooses the conflict to resolve by categorizing conflicts into three classes and always picking one from the highest-priority class. In this work, we propose an oracle for conflict selection that results in smaller search tree sizes than the one used in previous work. However, the computation of the oracle is slow. Thus, we propose a machine-learning (ML) framework for conflict selection that observes the decisions made by the oracle and learns a conflict-selection strategy represented by a linear ranking function that imitates the oracle's decisions accurately and quickly. Experiments on benchmark maps indicate that our approach, ML-guided CBS, significantly improves the success rates, search tree sizes and runtimes of the current state-of-the-art CBS solver.

Downloads

Published

2021-05-18

How to Cite

Huang, T., Koenig, S., & Dilkina, B. (2021). Learning to Resolve Conflicts for Multi-Agent Path Finding with Conflict-Based Search. Proceedings of the AAAI Conference on Artificial Intelligence, 35(13), 11246-11253. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/17341

Issue

Section

AAAI Technical Track on Multiagent Systems