Hard real-time motion planning for autonomous vehicles

Motion planning is the problem of finding a continuous collision free path from an initial configuration (or state) to a goal. On board an autonomous vehicle, the capability to prevent collisions also depends on the sensing and control. Critically, motion planning is a necessary component for the safe operation of an autonomous vehicles. This work focuses on the problem of embedding a motion planner into a software system in which all tasks are required to satisfy hard deadlines. The key contribution of this work is to present a framework that can be used as a basis for incorporating approximately complete motion planning algorithms within a hard real-time system. This framework ensures that deadlines can be satisfied, with only mild constraints on other software. Two motion planning algorithms are presented as a verification of the framework, and are applied to solving dynamic motion planning problems related to the safe and efficient navigation of autonomous systems.