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

Authors

  • Tomas Rybecky Department of Cybernetics, Faculty of Electrical Engineering, Czech Technical University Czech Institute for Informatics, Robotics and Cybernetics, Czech Technical University
  • Miroslav Kulich Czech Institute for Informatics, Robotics and Cybernetics, Czech Technical University
  • Anton Andreychuk Federal Research Center for Computer Science and Control of Russian Academy of Sciences Peoples Friendship University of Russia (RUDN University)
  • Konstantin Yakovlev Federal Research Center for Computer Science and Control of Russian Academy of Sciences National Research University Higher School of Economics

Keywords:

Search In Robotics, Combinatorial Optimization, Bounding And Pruning Techniques, Time, Memory, And Solution Quality Trade-offs

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.

Downloads

Published

2021-07-21