Kinodynamic Motion Planning with Space-Time Exploration Guided Heuristic Search for Car-Like Robots in Dynamic Environments

abstract

The Space Exploration Guided Heuristic Search (SEHS) method solves the motion planning problem, especially for car-like robots, in two steps: a circle-based space exploration in the workspace followed by a circle-guided heuristic search in the configuration space. This paper extends this approach for kinodynamic planning in dynamic environments by performing the exploration in both space and time domains. Thus, a time-dependent heuristic is constructed to guide the search algorithm applying a kinodynamic vehicle model. Furthermore, the search step-size and state resolution are adapted incrementally to guarantee resolution completeness with a trade-off for efficiency. The performance of Space-Time Exploration Guided Heuristic Search (STEHS) approach is verified in two scenarios and compared with several search-based and sampling-based methods.