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

Chao Chen, Markus Rickert and Alois Knoll

Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 2666–2671

September 2015 · Hamburg, Germany · doi: 10.1109/IROS.2015.7353741


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.

subject terms: autonomous driving, robotics