Differentially Constrained Motion Planning with State Lattice Motion Primitives

Abstract

Robot motion planning with differential constraints has received a great deal of attention in the last few decades, yet it still remains a challenging problem. Among a number of reasons, three stand out. First, the differential constraints that most physical robots exhibit render the coupling between the control and state spaces quite complicated. Second, it is commonly accepted that robots must be able to operate in environments that are partially or entirely unknown; classical motion planning techniques that assume known structure of the world frequently encounter difficulties when applied in this setting. Third, such robots are typically expected to operate with speed that is commensurate with that of humans. This poses stringent limitations on available runtime and often hard real-time requirements on the motion planner. The impressive advances in computing capacity in recent years have been unable, by themselves, to meet the computational challenge of this problem. New algorithmic approaches to tackle its difficulties continue to be developed to this day. The approach advocated in this thesis is based on encapsulating some of the complexity of satisfying the differential constraints in pre-computed controls that serve as motion primitives, elementary motions that are combined to form the solution trajectory for the system. The contribution of this work is in developing a general approach to constructing such motion primitives given a model of robot mobility. Moreover, the approach allows an unprecedented amount of pre-computation in this domain, which yields a dramatic increase in planning efficiency even for systems with complex kinematics and dynamics. Lastly, the proposed motion primitives are fully compatible with a wide range of planning algorithms and allow such useful techniques as incremental planning and multi-directional search to be used in the context of planning with differential constraints. These ideas are demonstrated and validated on a number of relevant systems, both in simulation and in real experiments. This work promises to enable capable and reliable motion planners with differential constraints, as encountered in many realistic robot systems with practical utility, operating efficiently in cluttered, partially known environments.