Event Location: NSH 3305

Abstract: Robotic motion planning is known to be an NP Hard problem. Many real-world applications employ hierarchical planning to decompose a complex problem into a set of sub-problems, each addressed by a sub-planner that makes different trade-offs and assumptions. To achieve scalability, long-range planners such as D* simplify the robot’s motion model, often to a grid. Such a global planner is aware of the topology of freespace–thus avoiding cul- de-sacs–but grid paths are not feasible for direct execution on real robots because sharp angles neglect dynamic constraints.

A model-predictive local planner converts a collection of control inputs into a set of feasible paths (or simply a path set) via a forward motion model. After collision-testing these paths, the best control may be executed easily and safely on a real robot. To guarantee safety, such a local-area planner must replan frequently (on the order of 10 Hz) and so does not scale well (under 10 m planning horizon), hence the need for a global planner. A typical hierarchical planner consists of a control-sampling local planner paired with a global planner like D*. In such a scenario, the local planner often consumes in excess of 99% of total planning time. With naive, precomputed path sets the norm today, the local planner spends a significant fraction of this time testing paths that could be predicted to fail based on information available to the planner at runtime.

In this thesis proposal, I study the problem of online path set generation. With a modest amount of knowledge about the robots current situation, a custom path set may be generated at each replan cycle to maximize in situ performance. Contextual factors influencing path set performance include the direction to the goal and the location and density of obstacles. I introduce several approaches to theoretical analysis of the problem and propose several algorithms for online path set generation. Additionally, I study the performance issues surrounding path set collision-testing, which consumes greater than 90% of planning time in some applications. By considering path set testing in conjunction with path set generation, additional gains in performance and safety may be realized.

Committee:Matthew Mason, Chair

Alonzo Kelly

Siddhartha Srinivasa

Emilio Frazzoli, Massachusetts Institute of Technology