Informed and Probabilistically Complete Search for Motion Planning under Differential Constraints

Contents

Sampling-based search has been shown effective in motion planning, a hard continuous state-space problem. Motion planning is especially challenging when the robotic system obeys differential constraints, such as an acceleration controlled car that cannot move sideways. Methods that expand trajectory trees in the state space produce feasible solutions for such systems. These planners can be viewed as continuous-space analogs of traditional uninformed search as their goal is to explore the entire state space. In many cases, the search can be focused on the part of the state-space necessary to solve a problem by employing heuristics. This paper proposes an informed framework for tree-based planning that successfully balances greedy with methodical search. The framework allows the use of a broad set of heuristics for goal-directed problem solving, while avoiding scaling issues that appear in continuous space heuristic search. It also employs an appropriate discretization technique for continuous state-space problems, based on an adaptive subdivision scheme. Although greedy in nature, the method provides with probabilistic completeness guarantees for a very general class of planning problems. Experiments on dynamic systems simulated with a physics engine show that the technique outperforms uninformed planners and existing informed variants. In many cases, it also produces better quality paths.