An Algorithm for Planning Collision-Free
Paths Among Polyhedral Obstacles

This paper describes a collision avoidance algorithm
for planning a safe path for a polyhedral object moving among
known polyhedral objects.  The algorithm transforms the obstacles
so that they represent the locus of forbidden positions for an arbitrary
reference point on the moving object.  A trajectory of this
reference point which avoids all forbidden regions is free of collisions.
Trajectories are found by searching a network which indicates, for each vertex 
in the transformed obstacles, which other vertices can be reached safely.

CACM October, 1979

Lozano-Perez, T.
Wesley, M.

Path finding, collision-free paths, polyhedral objects,
polyhedral obstacles, graph searching, growing objects

3.15 3.64 3.66 8.1

CA791005 DB January 17, 1980  10:13 AM

3172	4	3172
3116	5	3172
3172	5	3172
3172	5	3172
3172	5	3172