Kinematic feasibility guarantees in geometric path planning using history-based transition costs over cell decompositions

The hierarchical decomposition of motion planning tasks into geometric path planning, followed by kinodynamic motion planning is useful for designing efficient algorithms, but it entails the possibility of inconsistency between the two layers of planning. In an earlier paper, we proposed a general framework, based on rectangular cell decompositions, for incorporating information about the kinodynamic behavior of the vehicle in the geometric planning layer itself. In this paper, we use this framework to design a geometric path planning scheme which simultaneously finds an obstacle-free channel of cells from the initial point to the goal, as well as a vehicle state trajectory lying within that channel.