AAAI

Association for the Advancement of Artificial Intelligence

Home > Proceedings / Proceedings of the International Symposium on Combinatorial Search, 14

Towards Narrowing the Search in Bounded-Suboptimal Safe Interval Path Planning

Authors

Tomas Rybecky,Miroslav Kulich,Anton Andreychuk,Konstantin Yakovlev

Department of Cybernetics, Faculty of Electrical Engineering, Czech Technical University Czech Institute for Informatics, Robotics and Cybernetics, Czech Technical University,Czech Institute for Informatics, Robotics and Cybernetics, Czech Technical University,Federal Research Center for Computer Science and Control of Russian Academy of Sciences Peoples Friendship University of Russia (RUDN University),Federal Research Center for Computer Science and Control of Russian Academy of Sciences National Research University Higher School of Economics


Proceedings:

Proceedings of the International Symposium on Combinatorial Search, 14

Volume

Issue:

Vol. 14 No. 1 (2021): Fourteenth International Symposium on Combinatorial Search

Track:

Short Papers

Downloads:

Download PDF

Abstract:

Path planning in the presence of dynamic obstacles is challenging as the time dimension has to be considered. A prominent approach to tackle this problem known to be complete and optimal is the A*-based Safe-interval Path Planning (SIPP). Bounded-suboptimal variants of SIPP employing the ideas of Weighted A* (WSIPP) and Focal Search (FocalSIPP) have been introduced recently, trading-off optimality for decreased planning time. In this paper, we revisit FocalSIPP and design several secondary heuristics for Focal Search with the intention to narrow the search in the direction of a preplanned optimal single-agent path not considering dynamic obstacles. The experimental results on various maps show that the designed heuristics generally outperform the hops-to-the-goal heuristic used in the original FocalSIPP and successfully compete with WSIPP as well.

DOI:

10.1609/socs.v12i1.18562


SOCS

Vol. 14 No. 1 (2021): Fourteenth International Symposium on Combinatorial Search