Space Adaptive Search for Nonholonomic Mobile Robots Path Planning

Path planning for a nonholonomic mobile robot is a challenging problem. This paper proposes a novel space adaptive search (SAS) approach that greatly reduces the computation cost of nonholonomic mobile robot path planning. The classic search-based path planning only updates the state on the current location in each step, which is very inefficient, and, therefore, can easily be trapped by local minimum. The SAS updates not only the state of the current location, but also all states in the neighborhood, and the size of the neighborhood is adaptively varied based on the clearance around the current location at each step. Since a great deal of states can be immediately updated, the search can explore the local minimum and get rid of it very fast. As a result, the proposed approach can effectively deal with clustered environments with a large number of local minima. The SAS also utilizes a set of predefined motion primitives, and dynamically scales them into different sizes during the search to create various new primitives with differing sizes and curvatures. This greatly promotes the flexibility of the search of path planning in more complex environments. Unlike the A* family, which uses heuristic to accelerate the search, the experiments shows that the SAS requires much less computation time and memory cost even without heuristic than the weighted A* algorithm, while still preserving the optimality of the produced path. However, the SAS can also be applied together with heuristic or other path planning algorithms.
Comment: 12 pages, 62 figures