02/02/2021

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

Taoan Huang, Sven Koenig, Bistra Dilkina

Keywords:

Abstract Paper Similar Papers

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.

The video of this talk cannot be embedded. You can watch it here:
https://slideslive.com/38948038
(Link will open in new window)
 0
 0
 0
 0
  Share    
This is an embedded video. Talk and the respective paper are published at AAAI 2021 virtual conference. If you are one of the authors of the paper and want to manage your upload, see the question "My papertalk has been externally embedded..." in the FAQ section.

Comments

Post Comment
no comments yet
code of conduct: tbd Characters remaining: 140

Similar Papers

 0
 0
 0
 0
 13:27 
 0
 0
 0
 0
 18:25 
 0
 0
 0
 0
 15:23 
 0
 0
 0
 0
 16:07 
 0
 0
 0
 0
 4:49 
 0
 0
 0
 0
 5:16 
 0
 0
 0
 0
 17:34 
 0
 0
 0
 0
 21:43 
 0
 0
 0
 0
 9:27 
 0
 0
 0
 0
 3:08 
 0
 0
 0
 0
 15:07 
 0
 0
 0
 0
 4:52 
 0
 0
 0
 0
 8:13 
 0
 0
 0
 0
 13:25 
 0
 0
 0
 0
 15:01 
 0
 0
 0
 0
 3:21 
 0
 0
 0
 0
 19:28 
 0
 0
 0
 0
 12:01 
 0
 0
 0
 0
 14:31 
 0
 0
 0
 0
 6:58 
 0
 0
 0
 0
 19:58 
 0
 0
 0
 0
 2:40 
 0
 0
 0
 0
 9:59 
 0
 0
 0
 0
 3:16 
 0
 0
 0
 0
 14:46 
 0
 0
 0
 0
 5:07 
 0
 0
 0
 0
 9:34 
 0
 0
 0
 0
 3:12 
 0
 0
 0
 0
 7:27 
 0
 0
 0
 0
 11:52 
 0
 0
 0
 1
 5:49 
 0
 0
 0
 0
 11:43 
 0
 0
 0
 0
 11:40 
 0
 0
 0
 0
 6:13 
 0
 0
 0
 0
 15:02 
 0
 0
 0
 0
 14:42 
 0
 0
 0
 0
 14:06 
 0
 0
 0
 0
 15:08 
 0
 0
 0
 0
 1:01 
 0
 0
 0
 0
 11:49