  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.
