Improving User-Generated Paths

Figure 2: Pushing approximate paths to free space: (a) simple push ($k=1$), (b) shortest push, (c) workspace assisted push.

figure=FIGS/simplepush.eps,width=

(a)

figure=FIGS/shortestpush.eps,width=

(b)

figure=FIGS/obstaclepush.eps,width=

(c)

The planner's goal is to use the operator-generated paths to improve the connectivity of the roadmap. If an approximate path was collected, then the planner must attempt to `push' the colliding portions to the free space before adding them to the roadmap.

One approach might be to use the colliding configurations as milestones in the dilated freespace as in [11] or as seed nodes in OBPRM [2] (which attempts to `push' them to freespace).

However, in our scenario, more efficient methods are possible because the provided paths expected to be `close' to a valid path. Below, we first propose methods for pushing an approximate path to the free space, and then describe an iterated pushing technique, which coupled with the pushing methods, enables one to transform a solution for a much easier version of the problem (valid in the dilated freespace [11]) into a solution for the original version.