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