Fig. 1: Motion
Interpolation between two configurations q0 and q1
(a) There is collision at the intermediate configuration qt if we use a linear
interpolation; (b) Using our constrained interpolation algorithm, we obtain
a collision-free trajectory for this case. (c) We take into account
multiple closest feature pairs (V0,
F0) and (V1, F1) in this case) at the two configurations, and
guarantee no collisions among these feature pairs along the trajectory. The
use of multiple feature pairs increases the probability of finding a
collision-free path for the local planner.
If the sign of the distance function for a
feature pair (V, F), (F, V) or (E,E) between the robot and obstacles does
not change when the robot moves, then there is no collision in this feature
In order to guarantee that the sign of the
distance function does not change, a simple but sufficient way is to
perform a linear interpolation on the signed distances if initially both d0
and d1 have the same sign. Other more complex polynomial
interpolation functions can have been used.
Multiple distance constraints are considered in our formulation. We compute
the locally closest feature pairs between the robot and obstacles (Fig.
1(c)). We derive closed forms for our constrained interpolation which can
consider up to three locally closest feature pairs. By taking into account
multiple constraints, the resulting interpolating motion conforms better to
the local geometry of c-obstacles in the configuration space.
Motion Interpolation with Distance Constraints
Two distance constraints
Three distance constraints.
A video clip compares different motion interoplation schemes.
Local Planning in Sample-based Planners
The following video clips highligths the
collision-free paths computed using our new constrained motion
interpolation algorithm. We integrate our local planner into a
retraction-based RRT planner and compare its performance with the original
planner that used straight-line linear interpolation algorithm. We report
the time taken and the samples generated by our new planner as compared to
the earlier planner.
Alpha Puzzle Video