Approximating State-Space Obstacles for Non-Holonomic Motion Planning

Abstract

Classical forward search-based motion planning methods (i.e. A*) are often ill-suited to solve kinodynamic motion planning problems. Although such algorithms are often straightforward to implement, they do not always inherently exploit information about kinodynamic constraints to shape the search because they often only consider workspace or configuration space obstacles. In this project, I will look at some methods for approximating state space obstacles -- regions in state space which may correspond to collision with an obstacle, or which correspond to the situation in which no control action can prevent a future collision. Hence, the collection of all state space obstacles is sometimes referred to as the region of inevitable collision, as in LaValle and Kuffner [1]. By computing approximations of state space obstacles, it may be possible to make search-based planning both faster and safer.