Informed and probabilistically complete search for motion planning under differential constraints
Kostas E. Bekris, Lydia E. Kavraki · 2008
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 con-trolled car that cannot move sideways. Methods that ex-pand trajectory trees in the state space produce feasible so-lutions 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 neces-sary 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 prob-abilistic completeness guarantees for a very general class of planning problems. Experiments on dynamic systems sim-ulated with a physics engine show that the technique outper-forms uninformed planners and existing informed variants. In many cases, it also produces better quality paths. I.