Iterative Motion Planning

Kimberly Chung, Thientu Ho, Tichakorn Wongpiromsarn, Dr. Venkatesh Rao, Prof. Raffaelo D'Andrea

This project studies a hierarchical motion planning scheme for a vehicle to navigate in a complex environment while satisfying its dynamic constraints. The approach is to decompose the problem into three layers: abstract, geometric, and dynamic, each solving its sub-problem independently. The abstract layer plans a coarse path as a tolerance region in the map within which a refined trajectory must be found. The geometric layer plans a geometrically feasible path to the destination within the band. The dynamic layer refines the geometrically feasible path by adapting it to incorporate internal constraints of the vehicle, such as minimum turning radius, arising from its dynamics. This layer also reports inexecutable path segments back to the geometric planner when the vehicle's constraints are not met. The geometric planner and the dynamic planner then interatively repairs these failed segments, by avoiding the broken ones as it attempts to stay close to the original path.

In addition, the planning of the velocity profile of the vehicle is being studied with a constraint that it has to stay within a predetermined polygon which follows the path generated by the three planning layers at a predetermined speed. The challenge lies in the fact that the path of the vehicle is independent of the path of the polygon as the vehicle needs to avoid small obstacles that are invisible to the polygon. The goal is to generate the smoothest velocity profile as possible.

This multi-layered approach reduces the complexity of robot motion planning, as each layer has to maintain only a certain level of details needed to carry out its goals.

This project introduces a portfolio approach for geometric path repair and refinement. This portfolio algorithm switches between the high-cost but optimal A* planner and the low-cost and acceptable "hopper" planner to achieve, on average, low-cost, high quality repairs.

Our two solutions to the dynamic refinement problem are based on fitting circular-arc motion primitives and minimum-time motion primitives respectively, to a polygonal line computed by the geometric planner. The first method, path refinement using tangential circular arcs, is conceptually simple and easier to implement, and has been implemented with simple cell decompositions and Voronoi diagrams. Minimum-time segments are geometrically more complex entities and have not been used in refinement of paths from cell decomposition to our knowledge, though they have been used in the maneuver automaton approach in conjunction with randomized road-map techniques. The shortcoming of this approach to using minimum-time primitives is that it does not offer as much top-down control over motion as the refinement approach (an important capability in multiagent domains where vehicles must move in precisely coordinated ways). Implementing dynamic refinement with minimum-time primitives for geometric paths computed from cell-decomposition is of interest because they are potentially capable of supporting better performance than simpler refinement primitives such as circular arcs.