mihailp @ seas.upenn.edu   +1-412-805-0210            Curriculum Vitae


Kinodynamic Motion Planning


Differentially constrained (e.g. nonholonomic) motion planning and incremental replanning (e.g. D*) have been independently developed for nearly two decades. In this work, we introduced an approach to unify these two methodologies and demonstrated new capability that results. The crux of the method is the development of state lattice motion primitives that satisfy differential constraints by construction, yet admit many types of efficient search previously under-exploited in this domain, including D* and bi-directional RRT.

Acknowledgements: DARPA PerceptOR, NASA GSRP Fellowship, JPL Mars Technology Program
DARPA logo   NASA logo JPL logo

See Maxim Likhachev's webpage for application of state lattice motion primitives to the parking lot planner of the Boss robot, the CMU entry to the DARPA Urban Challenge.
Boss

Planning with Dynamics

dynamics
We successfully applied the standard state lattice techniques to planning with dynamics constraints using a "car on ice" system simulated with ODE. A set of primitives was developed by analyzing the reachability of the system and applying gradient descent optimization to improve its sampling qualities. Standard D* was applied for time-optimal planning. The planner automatically produced efficient maneuvers, such as a sliding U-turn.

Field Validation

Field Validation
A state lattice motion planner was validated in field experimentation. It considered car-like mobility constraints explicitly and featured 10Hz average replanning frequency with limited perception (radius of two robot lengths),  in rough terrain environment (sensor noise and uncertainty). A single CPU was shared by all processes of the robot.

Multi-Resolution Planning

Grad fidelity
We introduced graduated fidelity: a method of improving efficiency by gradually varying the fidelity of representation of the motion planning problem. The method frees up the designer to specify any number of regions of fidelity, of any size or location; moreover, the regions move or change shape arbitrarily. By masquerading topology changes as perception updates, D* maintains the connectivity of this "dynamic" search space automatically.

Search Space Design

lattice
We proposed state lattice motion primitives as a way of leveraging our related work in trajectory generation for car-like robots (boundary value problem) for efficient motion planning. A method of generating such primitives is developed based on detecting and pruning redundant motions from a large set of primitives.



See publications on this topic.