The path planner developed for (DM)^2 is an extension of a wavefront expansion algorithm developed by Latombe. The wavefront expansion method relies on the initialization of a grid-based model of the robot's workspace with respect to a particular goal location. Each location in the grid that is occupied by an object is designated as off-limits. The goal-region is assigned the value 1, any cell which neighbors the goal cell and is not an object is given the value 2, any cell which neighbor a cell with value 2 and has not already been assigned a value is given the value 3. This process is repeated until every cell in the grid has been assigned a value. A path from any given starting location to the goal location can be found by iteratively moving from the current location to the neighboring cell with the lowest value. This algorithm generates paths of minimum distances, with is no possibility of generation of local minima.
The major problem faced during the implementation of the wavefront path planner for (DM)^2 is the nonholonomic kinematic constraint on the motion of the wheeled base. This nonholonomic constraint restricts the geometry of the feasible free paths between the start and the goal configurations. To solve this problem, movement of the base is restricted to straight-line motion, and the grid resolution is set to 2' by 2'. The mobile base is divided into a head and tail section, each of which occupy one cell in the workspace. The path planner uses the size of the workspace, the location of all of the objects, and the starting and ending locations for the head and the tail of the mobile base. Turns are accomplished by rotations using the center of the tail-section as a pivot point. In addition, turns are currently restricted to 90 or 180 degrees.
The process of motion planning for the base is divided into three parts; initial rotation, path following, and final rotation. This division of movement planning assures that the base will always travel forward and never backwards. Preference is given to long horizontal or vertical movements over diagonal movements so that robot motion is smooth and efficient.
Christopher Lee | chrislee@ri.cmu.edu