02/02/2021

Improving Continuous-time Conflict Based Search

Anton Andreychuk, Konstantin Yakovlev, Eli Boyarski, Roni Stern

Keywords:

Abstract Paper Similar Papers

Abstract: Conflict-Based Search (CBS) is a powerful algorithmic framework for optimally solving classical multi-agent path finding (MAPF) problems, where time is discretized into the time steps. Continuous-time CBS (CCBS) is a recently proposed version of CBS that guarantees optimal solutions without the need to discretize time. However, the scalability of CCBS is limited because it does not include any known improvements of CBS. In this paper, we begin to close this gap and explore how to adapt successful CBS improvements, namely, prioritizing conflicts (PC), disjoint splitting (DS), and high-level heuristics, to the continuous time setting of CCBS. These adaptions are not trivial, and require careful handling of different types of constraints, applying a generalized version of the Safe interval path planning (SIPP) algorithm, and extending the notion of cardinal conflicts. We evaluate the effect of the suggested enhancements by running experiments both on general graphs and 2^k-neighborhood grids. CCBS with these improvements significantly outperforms vanilla CCBS, solving problems with almost twice as many agents in some cases and pushing the limits of multi-agent path finding in continuous-time domains.

The video of this talk cannot be embedded. You can watch it here:
https://slideslive.com/38948757
(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
 24:58 
 0
 0
 0
 0
 14:19 
 0
 0
 0
 0
 14:58 
 0
 0
 0
 0
 12:37 
 0
 0
 0
 0
 25:01 
 0
 0
 0
 0
 3:10 
 0
 0
 0
 1
 12:45 
 0
 0
 0
 0
 13:50 
 0
 0
 0
 1
 12:59 
 0
 0
 0
 0
 7:46 
 0
 0
 0
 0
 3:21 
 0
 0
 0
 0
 14:57 
 0
 0
 0
 0
 13:46 
 0
 0
 0
 0
 13:27 
 0
 0
 0
 0
 5:30 
 0
 0
 0
 0
 15:01 
 0
 0
 0
 0
 15:07 
 0
 0
 0
 0
 27:41 
 0
 0
 0
 0
 11:48 
 0
 0
 0
 0
 3:03 
 0
 0
 0
 0
 3:34 
 0
 0
 0
 0
 3:16 
 0
 0
 0
 0
 3:05 
 0
 0
 0
 0
 15:11 
 0
 0
 0
 0
 4:49 
 0
 0
 0
 0
 15:25 
 0
 0
 0
 0
 13:25 
 1
 0
 1
 1
 13:26 
 0
 0
 0
 0
 19:34 
 0
 0
 0
 0
 2:01 
 0
 0
 0
 0
 3:19 
 0
 0
 0
 0
 20:24 
 0
 0
 0
 0
 16:22 
 0
 0
 0
 0
 18:12 
 0
 0
 0
 0
 7:27 
 0
 0
 0
 0
 5:17 
 0
 0
 0
 2
 4:57 
 0
 0
 0
 0
 9:56 
 0
 0
 0
 0
 3:23 
 0
 0
 0
 0
 3:20