A Conflict Avoidance Table for Continuous Conflict-Based Search

Coppé, Vianney;Schaus, Pierre
(2022) Fifteenth International Symposium on Combinatorial Search — Location: Vienna, Austria

Files

CCBS_CAT_SOCS.pdf
  • Open Access
  • Adobe PDF
  • 460.03 KB
Download

Details

Authors
Abstract
Conflict-Based Search is a state-of-the-art algorithm solving the Multi-Agent Path Finding problem. Given multiple agents with start and goal locations, the problem is to find a set of collision-free paths of minimal cost. Continuous Conflict-Based Search is a recent adaptation of this algorithm for continuous time and agents with physical shapes. However, an important ingredient has not been adapted to this continuous version: the Conflict Avoidance Table. It is used as a tie-breaking strategy in single-agent search phases to favor paths causing fewer conflicts with the other agents. This paper explains how the R-Tree can be used as a Conflict Avoidance Table for Continuous Conflict-Based Search. The experiments show that using the Conflict Avoidance Table can reduce the number of nodes expanded by the algorithm by a large margin. As a result, the solving time is improved proportionally and especially when using the implementation based on R-Trees as opposed to a naive implementation.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Coppé, V., & Schaus, P. (2022). A Conflict Avoidance Table for Continuous Conflict-Based Search. Proceedings of the International Symposium on Combinatorial Search, 15(1), 264-266. https://hdl.handle.net/2078.5/103027 (Original work published 2022)