Date Added: Jul 2011
The authors present a hybrid path planner that combines two common methods for robotic planning: a Dijkstra graph search for the minimum distance path through the configuration space and an optimization scheme to iteratively improve grid-based paths. Their formulation is novel because they first commit to the minimum distance path, then explicitly relax the path to maximize the clearance up to a user-specified bound. Notably, this formulation yields more predictable paths than potential field methods which try to trade increases in path length for greater clearance around obstacles. These potential field costs infer a trade off that can yield poor paths when the obstacle map is partially observable and has a finite history.