Combining Space Exploration and Heuristic Search in Online Motion Planning for Nonholonomic Vehicles

abstract

This paper presents an efficient motion planning method for nonholonomic vehicles, which combines space exploration and heuristic search to achieve online performance. The space exploration employs simple geometric shapes to investigate the collision-free space for the dimension and topology information. Then, the heuristic search is guided by this knowledge to generate vehicle motions under kinodynamic constraints. The overall performance of this framework greatly benefits from the cooperation of these two simple generic algorithms in suitable domains, which sequentially handles the free-space information and kinodynamic constraints. Experimental results show that this method is able to generate motions for nonholonomic vehicles in a time frame of less than 100 milliseconds for the given problem settings. The contribution of this work is the development of a Space Exploration Guided Heuristic Search with a circle-path based heuristics and adaptable search step size. The approach is grid-free and able to plan nonholonomic vehicle motions under kinodynamic constraints.