Gross motion planning—a survey

ABSTRACT

Motion planning is one of the most important areas of robotics research. The complexity of the motion-planning problem has hindered the development of practical algorithms. This paper surveys the work on gross-motion planning, including motion planners for point robots, rigid robots, and manipulators in stationary, time-varying, constrained, and movable-object environments. The general issues in motion planning are explained. Recent approaches and their performances are briefly described, and possible future research directions are discussed.

REFERENCES

• 1: AHUJA, N., AND SCHACHTER, B. 1983. Pattern Models. Wiley, New York.
• 2: Rachid Alami , Thierry Simeon , Jean-Paul Laumond, A geometrical approach to planning manipulation tasks. The case of discrete placements and grasps, The fifth international symposium on Robotics research, p.453-463, February 1991
• 3: Helmut Alt , Rudolf Fleischer , Michael Kaufmann , Kurt Mehlhorn , Stefan Näher , Stefan Schirra , Christian Uhrig, Approximate motion planning and the complexity of the boundary of the union of simple geometric figures, Proceedings of the sixth annual symposium on Computational geometry, p.281-289, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98592]
• 4: ASANO, T., ASANO, T., GUIBAS, L., HERSHBERGER, J., AND IMAI, H. 1985. Visibility-polygon search and Euclidean shortest path. In The 26th Symposlum on Foundations of Computer Science (Portland, Oreg., Oct. 21 23) pp. 155 164.
• 5: M. J. Atallah , D. Z. Chen, Optimal parallel algorithm for visibility of a simple polygon from a point, Proceedings of the fifth annual symposium on Computational geometry, p.114-123, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73846]
• 6: M. J. Atallah , R. Cole , M. T. Goodrich, Cascading divide-and-conquer: a technique for designing parallel algorithms, SIAM Journal on Computing, v.18 n.3, p.499-532, June 1989 [doi>10.1137/0218035]
• 7: ATHENS, M., AND FALBS, P. L. 1966 Optimal Control. McGraw-Hill, New York.
• 8: Franz Aurenhammer, Voronoi diagrams—a survey of a fundamental geometric data structure, ACM Computing Surveys (CSUR), v.23 n.3, p.345-405, Sept. 1991 [doi>10.1145/116873.116880]
• 9: AVNAIM, F., BOISSONNAT, J. D., AND FAVERJON, B. 1988 A practical exact motion planning' algorithm for polygonal objects amidst polygonal obstacles. In Procee&ngs o/the IEEE Internatmnal Conference on Robotics and Automation (Philadelphia, Apr. 24-29). IEEE, New York, pp. 1656 1661.
• 10: Avron Barr , Edward A. Feigenbaum, Handbook of AI, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 11: BARRAQUAND, J., AND LATOMBE, J. C 1990 A Monte-Carlo algorithm for path planning with many degrees of freedom. In Proceedings of the IEEE International Co,ference on Robotics and Automation (Cincinnati, May 13 18). IEEE. New York, pp. 1712 1717.
• 12: BOBROW, J. E., DUBOWSKY, S., AND GIBSON, J. S. 1985. Time-optimal control of robotic manipulators along' specified paths. Int. J. Robotics Res. 4, 3 (Fall), 3-17.
• 13: BOISSIERE, P. T., AND HARRJGAN, R. W. 1988. Telerobotic operation of conventional robot manipulators. In Proceedings of the IEEE International Conference on Robotics and Automation (Philadelphia, Apr. 24-29). IEEE, New York, pp. 576 583.
• 14: Br~NICKY, M., ANt) NEWMAN, W. 1990. Rapid computation of configuration obstacles. In Proceedings of the IEEE International Conference on Robottcs and Automation (Cincinnati, May 13 18). pp. 304-310
• 15: BROOKS, R.A. 1983. Solving the Findpath problem by good representation of free space. IEEE Trans. Syst., Man, and Cybernetics SMC-13, 3 (Mar./Apr.), 190 197.
• 16: BROOKS, R. A., AND LOZANO-PI~REZ, T. 1983. A subdivision algorithm in configuration space for Findpath with rotation. In The International Joint Conference on Artificial Intelligence (Karlsruhe, Germany, Aug 8-12). William Kaufmann, Inc., Los Altos, Calif, pp. 799-806.
• 17: BRYSON, A. E., JR., AND HO, Y.C. 1975. Appltcd Opttmal Control. Hemisphere Publishing, Washington, D.C.
• 18: BUCKLEY, S. J. 1989. Fast motion planning for multiple moving robots. In Proceedings of the IEEE International Conference on Robotics and Automation (Scottsdale, Ariz., May 14 19). pp. 322 326.
• 19: John F. Canny, The complexity of robot motion planning, MIT Press, Cambridge, MA, 1988
• 20: C^NNY, J. F 1987. A new algebraic method for robot motion planning and real geometry In Proceedings of the 28th Annual Symposium on Foundations of Computer Sctence (Los Angeles, Oct 12 14). IEEE, Washington, D.C., pp 39-48.
• 21: J. Canny , B. Donald, Simplified Voronoi diagrams, Proceedings of the third annual symposium on Computational geometry, p.153-161, June 08-10, 1987, Waterloo, Ontario, Canada [doi>10.1145/41958.41974]
• 22: CANNY, J. F., AND LIN, M. C. 1900. An opportunistic global path planner. In Proceedings of the IEEE Internattonal Con/erence on Robotics and Automation (Cincinnati, May 13-18). IEEE, New York, pp. 1554-1561.
• 23: CANNY, J. F., ANt) REIF, J. 1987. New lower bound techniques for robot motion planning problems. In Proceedings of the 28th Annual Symposium on Foundations of Computer Science (Los Angeles, Oct. 12-14). IEEE, New York, pp. 49 60.
• 24: CANNY, J. F., DONALD, B., REIF, J., AND XAVIER, P. 1988. On the complexity ofkinodynamic planning. In Proceedzngs of the 29th Annual Sympos'ium on Foundatio,s of Computer Science (White Plains, New York, Oct. 24 26). IEEE, New York, pp. 306 315.
• 25: John Canny , Ashutosh Rege , John Reif, An exact algorithm for kinodynamic planning in the plane, Proceedings of the sixth annual symposium on Computational geometry, p.271-280, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98584]
• 26: CHATILA, R. 1982. Path planmng and environment learning in a mobile robot system. In Procee&ngs of the European Conference on Artzfictal Intelligence (Orsay, France, July 12 14). pp. 211-215.
• 27: CHATILA, R., AND LAUMOND, J. P. 1985. Position referencing and consistent world modeling for mobile robots. In Proceedings of the IEEE Internatmnal Conference on Robotics and Automation (St Louis). IEEE, New York, pp. 138-145.
• 28: C}~ATTERGY, R. 1985. Some heuristics for the navigation of a robot. Int. J. Robotics Res. 4, 1 (Spring), 59-66.
• 29: Jindong Chen , Yijie Han, Shortest paths on a polyhedron, Proceedings of the sixth annual symposium on Computational geometry, p.360-369, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98601]
• 30: CHEN, P. C., AND HWANG, Y.K. 1992. SANDROS: A motion planner with performance proportional to task difficulty. In Proceedings of the IEEE International Conference on Robotics and Automation (Nice, France, May 12 14). IEEE, New York, pp. 2346-2353.
• 31: C~EN, P. C., AND HWAN% Y. K. 1991. Practical path planning among movable obstacles. In Proceedings of the IEEE International Conference on Robotics and Automation (Sacramento, Apr. 7 12). ACM, New York, pp. 444-449.
• 32: CHEN, Y. C., AND VIDYASAGAR, M. 1988. Optimal trajectory planning for planner n-link revolute manipulators in the presence of obstacles. In Proceedings of the IEEE International Conference on Robotics and Automatwn (Philadelphia, Apr. 24-29). IEEE, New York, pp. 202-208.
• 33: CHEUNG, E., AND LUMELSKY, V. 1988. Motion planning for robot arm manipulators with proximity sensing. In Proceedings of the IEEE International Conference on Robotics and Automatwn (Philadelphia, Apr. 24-29). IEEE, New York, pp. 740-745.
• 34: L. Paul Chew, Planning the shortest path for a disc in O(n²log n) time, Proceedings of the first annual symposium on Computational geometry, p.214-220, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323261]
• 35: CmEN, Y. P., Ko~vo, A. J., AND LEE, B.H. 1988. On-line generation of collision free trajectories for multiple robots. In Proceedings of the IEEE Internatwnal Conference on Robottcs and Automation (Philadelphia, Apr. 24-29). IEEE, New York, pp. 209-211.
• 36: CtiUANC,, J., AND AUUJA, N. 1991a. Path planning using the Newtonian potential. In Proceedings of the IEEE International Conference on Robotics and Automation (Sacramento, Apr. 7-12). IEEE, New York, pp. 558 563.
• 37: C~UANG, J., AND AHUJA, N. 1991b. Skeletonization using a generalized potential field model. In The 8th Israeh Symposium on Artificial Intelligence and Computer V~sion (Dec. 30-31).
• 38: K. Clarkson , S. Kapoor , P. Vaidya, Rectilinear shortest paths through polygonal obstacles in O(n(logn)²) time, Proceedings of the third annual symposium on Computational geometry, p.251-257, June 08-10, 1987, Waterloo, Ontario, Canada [doi>10.1145/41958.41985]
• 39: George E. Collins, Hauptvortrag: Quantifier elimination for real closed fields by cylindrical algebraic decomposition, Proceedings of the 2nd GI Conference on Automata Theory and Formal Languages, p.134-183, May 20-23, 1975
• 40: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 41: P. J. de Rezende , D. T. Lee , Y. F. Wu, Rectilinear shortest paths with rectangular barriers, Proceedings of the first annual symposium on Computational geometry, p.204-213, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323260]
• 42: DIJKSTRA, E.W. 1959. A note on two problems in connection with graphs. Numerlsche Mathemat~k 1,269 271. In English.
• 43: Bruce R. Donald, Motion Planning with Six Degrees of Freedom, Massachusetts Institute of Technology, Cambridge, MA, 1984
• 44: DONALD, B., AND JENNINGS, J. 1991. Sensor interpretation and task-directed planning using perceptual equivalence class. In Proceedings of the IEEE Internatmnal Conference on Roboacs and Automatzon (Sacramento, Apr. 7-12). IEEE, New York, pp. 190-197.
• 45: DONALD, B.,ANDXAVIER, P. 1989. A provably good approximation algorithm for optimal time trajectory planning. In Proceedings of the IEEE Internatwnal Conference on Robottcs and Automatwn (Scottsdale, Ariz., May 14-19). IEEE, New York, pp. 958-963.
• 46: DRYSDALE, R.L. 1979. Generalized Voronoi diagrams and geometric searching. Tech. Rep. STAN-CS-79-705, Stanford Univ., Stanford, Calif.
• 47: DUBINS, L.E. 1957. On curves of minimal length with a constraint on average curvature and with prescribed initial and terminal positions and tangents. Amer. J. Math. 79, 497-516.
• 48: ELGINDY, H., AND GOODRICH, M.T. 1988. A linear algorithm for computing the visibility polygon from a point. J. Alg. 2, 186-197.
• 49: I~LTIMSAHY, A. H., AND YANG, W. S. 1988. Near Minimum-time control of robotic manipulator with obstacles in the workspaee. In Proceedings of the IEEE Internatwnal Conference on Robotics and Automation (Philadelphia, Apr. 24 29). IEEE, New York, pp. 358-363. {
• 50: ERDMANN, M., AND LOZANo-PgREZ, T. 1986. On multiple mowng objects. In Procee&ngs of the IEEE Internatwnal Conference on Robotics and Automatwn (San Francisco, Apr. 7 10). IEEE, New York, pp. 1419-1424.
• 51: FAVERJON, B. 1989. Hierarchical object models for efficient anti-collision algorithm. In Proceedings of the IEEE Intcrnatwnal Conference on Robotics and Automation (Scottsdale, Ariz., May 14 19). IEEE, New York, pp. 333-340.
• 52: FAVEP~JON, B. 1986. Object level programming of industrial robots. In The IEEE International Conference on Robotics and Automation (San Francisco, Apr. 7-10). IEEE, New York, pp 1406-1412.
• 53: FAVERJON, B., AND TOURNASSOUD, P. 1987. A local approach for path planning of manipulators with a high number of degrees of freedom. In Proceedings of the IEEE Internatzonal Conference on Robotics and Automation (Raleigh, N. Carol., Mar. 31-Apr. 3). IEEE, New York, pp. 1152-1159.
• 54: Steven Fortune , Gordon Wilfong, Planning constrained motion, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.445-459, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62256]
• 55: FORTUNE, S., WILFONG, G., AND YAP, C. 1986. Coordinated motion of two robot arms. In Proceedings of the IEEE International Conference on Robotics and Automation (San Francisco, Apr. 7 10). IEEE, New York, pp. 1215-1223.
• 56: E. Freund , H. Hoyer, Real-time pathfinding in multirobot systems including obstacle avoidance, International Journal of Robotics Research, v.7 n.1, p.42-70, Feb., 1988 [doi>10.1177/027836498800700104]
• 57: FUJIMURA, K., AND SAMET, H. 1989. Time minireal paths among moving obstacles. In Proceedings of the IEEE International Conference on Robotics and Automatton (Scottsdale, Ariz., May 14-19). IEEE, New York, pp. 1110-1115.
• 58: FUJIMURA, K., AND SAMET, H. 1988. Path planning among moving obstacles using spatial indexing. In Proceedings of the IEEE International Conference on Robotics and Automation (Philadelphia, Apr. 24-29). IEEE, New York, pp. 1662-1667.
• 59: GAW, D., AND MEYSTEL, A. 1986. Minimum-time navigation of an unmanned mobfie robot in a 2-1/2D world with obstacles. In Proceedtngs of the IEEE International Conference on Robotics and Automatton (San Francisco, Apr. 7-10). IEEE, New York, pp. 1670-1677.
• 60: GE, Q., AND McCARTHY, J. M. 1989. Equations for boundaries of joint obstacles for planar robots. In Proceedings of the IEEE {nternattonal Conference on Robottcs and Automatton ( Scottsdale, Ariz., May 14 19). IEEE, New York. pp. 164 169.
• 61: L. Gewali , A. Meng , J. S. Mitchell , S. Ntafos, Path planning in 0/1/ weighted regions with applications, Proceedings of the fourth annual symposium on Computational geometry, p.266-278, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73421]
• 62: GILBERT, E. G., AND FOO, C.P. 1990. Computing the distance between general convex objects in three-dimensional space. IEEE Trans. Robotics Auto. 6, I (Feb.), 53-61
• 63: GILBERT, E. G., AND JOHNSON, D.W. 1985. Distance functions and their applications to robot path planning in the presence of obstacles. IEEE J. Robotics Auto. RA-1, 1, 21-30.
• 64: GILBERT, E. G., JOHNSON, D. W., AND KEERTHI, S. S. 1988. A fast procedure for computing the distance between complex objects in threedimensional space. IEEE J. Robotics Auto. RA- 4, 2 (Apr.), 193-203.
• 65: Michael T. Goodrich , Steven B. Shauck , Sumanta Guha, Parallel methods for visibility and shortest path problems in simple polygons (preliminary version), Proceedings of the sixth annual symposium on Computational geometry, p.73-82, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98539]
• 66: L. J. Guibas , M. Sharir , S. Sifrony, On the general motion planning problem with two degrees of freedom, Proceedings of the fourth annual symposium on Computational geometry, p.289-298, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73423]
• 67: HERMAN, M. 1986. Fast, three-dimensional, collision-free motion planning. In Proceedings of the IEEE International Conference on Robotics and Automation (San Francisco, Apr. 7-10). IEEE, New York, pp. 1056-1063.
• 68: HOGAN, N. 1985. Impedance control: An approach to manipulation: Part III-- Application. ASME J. Dynamtc Syst. Meas. Control. 107 (Mar.), 17-24.
• 69: John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 70: J E Hopcroft , G T Wolfong, Reducing multiple object motion planning to graph searching, SIAM Journal on Computing, v.15 n.3, p.768-785, August 1986 [doi>10.1137/0215055]
• 71: HOPCROFT, J., JOSEPH D., AND WHITESIDE, S. 1985. On the movement of robot arms in 2- dimensional bounded regions. SIAM J. Cornput. 14, 2 (May), 315-333.
• 72: John Hopcroft , Deborah Joseph , Sue Whitesides, Movement problems for 2-dimensional linkages, SIAM Journal on Computing, v.13 n.3, p.610-629, August 1984 [doi>10.1137/0213038]
• 73: HOPCROF% J., SCHWARTZ, J. T., AND SHARIR, M. 1984b. On the complexity of motion planning for multiple independent objects; PSPACE- hardness of the "Warehouseman's Problem." Int J. Robottcs Res. 3, 4 (Winter), 76-88.
• 74: HUANG, Y. F., AND LEE. C. S.G. 1991. A framework of knowledge-based assembly planning. In Procee&ngs of the IEEE Internatzonal Conference on Robotzcs and Automation (Sacramento, Apr. 7-12). IEEE, New York, pp. 599-604.
• 75: Seth A. Hutchinson , Avinash C. Kak, SPAR: a planner that satisfies operational and geometric goals in uncertain environments, AI Magazine, v.11 n.1, p.30-61, Spring 1990
• 76: HWANG, Y. K 1990. Boundary equations of configuration obstacles for manipulators. In Proceedings of the IEEE Internatmnal Conference on Robotics azzd Automation (Cincinnati, May 13-18). IEEE, New York, pp. 298 303.
• 77: HWANG, Y. K., AND AHUJA, N. 1992. Potentml field approach to path planning. IEEE Trans. Robotics Auto. 8, I (Feb.), 23-32.
• 78: HWANG, Y. K., AND AHUJA, N. 1989. Robot path planning using a potential field representation. In The IEEE Computer Society Conference on Computer Vtsion and Pattern Recognition (San Diego, June 4 8). IEEE, New York, pp. 569 575.
• 79: Yie-Huei Hwang , Ruei-Chuan Chang , Hung-Yi Tu, Finding All Shortest Path Edge Sequences on a Convex Polyhedron, Proceedings of the Workshop on Algorithms and Data Structures, p.251-266, August 17-19, 1989
• 80: HWANG, Y. K., CHEN, P. C., AND XAVIER, P. G. 1992. Test states for motion planning. Internal Rep., Sandia National Laboratories, Albuquerque, New Mex.
• 81: JACOBS, P., AND CANNY, J. 1989. Planning smooth paths for mobile robots. In Proceedings of the IEEE International Conference on Robotics and Automation (Scottsdale, Ariz., May 14-19). IEEE, New York, pp. 2-7.
• 82: JONES, S. T. 1980. Solving problems involving variable terrain. Part 1: A general algorithm. Byte 5, 2.
• 83: JUN, S., AND SHIN, K. G. 1988. A probabilistic approach to collision-free robot path planning. In Proceedtngs of the IEEE International Conference on Robottcs and Automatton (Philadelphia, Apr. 24-29). IEEE, New York, pp. 220-227.
• 84: KAMBHAMPATI, S., AND DAVIS, L. S. 1986. Multiresolution path planning for mobile robots. IEEE J. Robotics Auto. RA-2, 3 (June), 135-145.
• 85: KANT, K., AND ZUCKER, S. W. 1988. Planning collision-free trajectories in time-varying environments: A two-level hierarchy. In Proceedings of the IEEE Internatzonal Conference on Robotics and Automation (Philadelphia, Apr. 24-29). IEEE, New York, pp. 1644-1649.
• 86: K Kant , S W Zucker, Toward efficient trajectory planning: the path-velocity decomposition, International Journal of Robotics Research, v.5 n.3, p.72-89, Fall 1986 [doi>10.1177/027836498600500304]
• 87: Y. Ke, An efficient algorithm for link-distance problems, Proceedings of the fifth annual symposium on Computational geometry, p.69-78, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73841]
• 88: Yan Ke , Joseph O'Rourke, Lower bounds on moving a ladder in two and three dimensions, Discrete & Computational Geometry, v.3 n.3, p.197-217, Jan., 1988 [doi>10.1007/BF02187908]
• 89: Y. Ke , J. O'Rourke, Moving a ladder in three dimensions: upper and lower bounds, Proceedings of the third annual symposium on Computational geometry, p.136-146, June 08-10, 1987, Waterloo, Ontario, Canada [doi>10.1145/41958.41972]
• 90: K. Kedem , M. Sharir, An automatic motion planning system for a convex polygonal mobile robot in 2-dimensional polygonal space, Proceedings of the fourth annual symposium on Computational geometry, p.329-340, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73427]
• 91: K. Kedem , M. Sharir, An efficient algorithm for planning collision-free translational motion of a convex polygonal object in 2-dimensional space amidst polygonal obstacles, Proceedings of the first annual symposium on Computational geometry, p.75-80, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323244]
• 92: KEHTARNAVAZ, N., AND LI, S. 1988. A collisionfree navigation scheme in the presence of moving obstacles. Ill The International Conference on Computer Vision. IEEE Computer Society, Los Angeles, pp. 808-813.
• 93: KErn, J. M., AND SACK, J. R. 1985. Minimum decomposition of polygonal objects. In Computational Geometry. Elsevier Science Publishers, North Holland, Amsterdam, pp. 197-216.
• 94: KHATIB, O. 1985. Real-time obstacle avoidance for manipulators and mobile robots. In Proceedings of the IEEE International Conference on Robottcs and Atomation (St. Lores, Missouri). IEEE, New York, pp. 500-505.
• 95: KHATIB, O., AND MAMPEY, L.M. 1978. Fonction decision-commande d'un robot manipulateur. Rep. 2/7156. DERA/CERT, Toulouse, France.
• 96: KItERADPIR, S., AND THORP, J.S. 1987. Real-time control of robot manipulators in the presence of obstacles. IEEE Int. J. Robottcs Auto. RA~4, 6 (Dec.), 687-698.
• 97: KHOSLA, P., AND VOLPE, R. 1988. Superquadric artificial potentials for obstacle avoidance and approach. In Proceedings of the IEEE International Conference on Robotics and Automation (Philadelphia, Apr. 24 29). IEEE, New York, pp. 1778 1784.
• 98: KEIRSEY, D. M., ANn MITCHELL, J. S. B. 1984. Planning strategic paths through variable terrain data. In Proceedings of SPIE Applications of Artificial Intelligence vol. 485, SPIE, Bellingham, Washington, pp. 172-179.
• 99: KIRKPATRICK, D. G. 1979. Efficient computation of continuous skeletons. In The 20th Symposium on the Foundations of Computer Sctence (San Juan, Puerto Rico, Oct. 29 31). pp. 18-27.
• 100: KOCH, E., YEN, C., HILLEL, G., MEYSTEL, A., AND ISIK, C. 1985. Simulation of path planning for a system with vision and map updating In Proceedings of the IEEE International Conference on Robottcs and Automation (St. Louis, Missouri). IEEE, New York, pp. 146 160.
• 101: Daniel E. Koditschek, Robot planning and control via potential functions, The robotics review 1, MIT Press, Cambridge, MA, 1989
• 102: KODITSCHEK, D.E. 1987. Exact robot navigation by means of potential functions: Some topological considerations. In Proceedings of the IEEE International Conference on Robotics and Automation (Raleigh, N. Carol, Mar. 31-Apr. 3). IEEE, New York, pp. I 6.
• 103: KONDO, K. 1991. Motion planning with six degrees of freedom by multistrategic, bidirectional heuristic free space enumeration. IEEE Trans. Robotics Auto. 7, 3 (June), 267-277.
• 104: KROGH, B. H., AND THORPE, C. E. 1986. Integrated path planning and dynamic steering control for autonomous vehicles. In Proceedings of the IEEE Internattonal Conference on Robotics and Automation (San Franmsco, Apr. 7-10) IEEE, New York, pp. 1664-1669.
• 105: KUAN, D. T., ZAMISKA, J C., AND BROOKS, R. A. 1985. Natural decomposition of free space for path planning. In Proceedings of the IEEE International Conference on Robottcs and Automatton (St. Louis, Missouri). IEEE, New York, pp. 168-173.
• 106: Jean-Claude Latombe, Robot Motion Planning, Kluwer Academic Publishers, Norwell, MA, 1991
• 107: Der-Tsai Lee, Proximity and reachability in the plane., 1978
• 108: LEE, D. T, AND DRYSDALE, R.L. 1981. Generalization of Voronoi diagram in the plane. SIAM J. Comput. 10, 73-83.
• 109: LEE, S., AND SHIN, Y.G. 1990. Disassembly planning based on subassembly extraction. In Proceedings of the IEEE Internattonal Conference on Robottcs and Automation (Cincinnati, May 13-18). IEEE, New York, pp. 1606-1613.
• 110: D. T. Lee , T. H. Chen , C. D. Yang, Shortest rectilinear paths among weighted obstacles, Proceedings of the sixth annual symposium on Computational geometry, p.301-310, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98595]
• 111: Jed Lengyel , Mark Reichert , Bruce R. Donald , Donald P. Greenberg, Real-time robot motion planning using rasterizing computer graphics hardware, ACM SIGGRAPH Computer Graphics, v.24 n.4, p.327-335, Aug. 1990
• 112: LIN, M. C., AND CANNY, J.F. 1991. A fast algorithm for incremental distance calculation. In Proceedings of the IEEE International Conference on Robotics and Automation (Sacramento, Apr. 7-12). IEEE, New York, pp. 1008-1014.
• 113: LIu, Y H., KURODA, S., NANIWA, T., NOBORIO, H., AND ARIMOTO, S 1989. A practical algorithm for planning collision-free coordinated motion of multiple mobile robots. In Proceedings of the IEEE International Conference on Robotics and Automatton (Scottsdale, Ariz., May 14-19) IEEE, New York, pp. 1427-1432.
• 114: LOZANO-P~REZ, T. 1987. A simple motionplanning algorithm for general robot manipulators. IEEE J. Robotics Auto. RA-3, 3 (June), 224-238
• 115: LOZANO-P~REZ, T., AND O'DONNELL, P. A. 1991. Parallel robot motion planning. In Proceedings of the IEEE International Conference on Robotics and Automatton (Sacramento, Apr. 7-12). IEEE, New York, pp. 1000 1007.
• 116: Tomás Lozano-Pérez , Michael A. Wesley, An algorithm for planning collision-free paths among polyhedral obstacles, Communications of the ACM, v.22 n.10, p.560-570, Oct. 1979 [doi>10.1145/359156.359164]
• 117: T. Lozano-Pérez , E. Mazer , J. L. Jones , P. A. O'Donnell, Task-Level Planning of Pick-and-Place Robot Motions, Computer, v.22 n.3, p.21-29, March 1989 [doi>10.1109/2.16222]
• 118: LOZANO-PI~REZ, T., JONES, J. L , MAZER, E., O'DONNELL, P. A., GRIMSON, E. L., TOURNAS- SOUD, P., AND LANUSSE, A. 1987 Handey: A robot system that recognizes, plans, and manipulates. In Proceedings of t/le IEEE International Conference on Robottcs and Automatton (Raleigh, N Carol, Mar 31 Apr. 3). IEEE, New York, pp. 843-849.
• 119: LUMELSKY, V. J. 1987. Effect of kinematms on otion planning for planar robot arms mowng midst unknown obstacles. IEEE J. Robottcs uto. RA-3, 3 (June), 207-223.
• 120: LUMELSKY, V. 1986. Continuous motion planmng unknown environment for a 3D cartesian obot arm. In Proceedings of the IEEE Internaional Conference on Robottcs arid Automation San Francisco, Apr. 7-10) IEEE, New York, p. 1050-1055
• 121: LUMELSK~~, V., AND SKEWIS, T 1988. A paradigm or incorporating vision in the robot navigation unction. In Proceedtngs of the IEEE Internalona! Conference on Robotics and Autornatton Philadelphia, Apr. 24 29). IEEE, New York, p 734 739.
• 122: LUMELSKY, V., AND SUN, K. 1987. Gross motion lanning for a simple 3D articulated robot arm oving amidst unknown arMtrarily shaped bstacles. In Proceedings of the IEEE Internatonal Con/erence on Robotics and Automation Raleigh, N. Carol., Mar. 31-Apr. 3). IEEE, ew York, pp. 1929-1934.
• 123: MACmJEWSICI, A. A., AND KLEIN, C. A. 1985 bstacle avoidance for kinematically redunant manipulators in dynamically varying nvironments. Int. J Robotics Res. 4, 3 (Fall), 09-117.
• 124: MADmLA, S. R. 1986 Decomposition algorithm or moving a ladder among rectangular obstales. In Proceedtags of the IEEE International onference on Robottcs and Automation (San rancisco, Apr. 7 10). IEEE, New York, pp. 413 1418.
• 125: McCARTHY, J. M., GE, Q., AND BODDULURI, R. M. C. 989. The analysis of cooperating planar robot rms in the image space of the workpiece. Int. . Robottcs Res
• 126: J. Mitchell , C. Papadimitriou, The weighted region problem, Proceedings of the third annual symposium on Computational geometry, p.30-38, June 08-10, 1987, Waterloo, Ontario, Canada [doi>10.1145/41958.41962]
• 127: Joseph S. B. Mitchell , David M. Mount , Christos H. Papadimitriou, The discrete geodesic problem, SIAM Journal on Computing, v.16 n.4, p.647-668, Aug. 1987 [doi>10.1137/0216045]
• 128: Joseph S. B. Mitchell , Günter Rote , Gerhard Woeginger, Minimum-link paths among obstacles in the plane, Proceedings of the sixth annual symposium on Computational geometry, p.63-72, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98537]
• 129: MIYAZAKI, F., AND ARIMOTO, S. 1984. Sensory eedback based on the artificial potential for obots. In Proceedings of the 9th Triannual orld Congress of International Factory Auomation (Budapest, July 2 6). Pergamon ress, New York, pp. 2381 2386.
• 130: MONTGOMERY, M., GAW, D., AND MEYSTEL~ h. 1987. avigation algorithm for a nested hierarchical ystem of robot path planning among polyheral obstacles. In Proceedings of the IEEE nternational Conference on Robotics and utomation (Raleigh, N. Carol., Mar. 31 Apr. ). IEEE, New York, pp. 1612-1622.
• 131: MOUNT, D. M. 1985. On finding shortest paths n convex polyhedra. Tech. Rep. 1495, Dept. of omputer Science, Univ. of Maryland, altimore.
• 132: NEWMAN, W. 1989, Automatic obstacle avmdance t high speeds via reflex control. In Proceedngs of the IEEE International Conference on obotics and Automation (Scottsdale, Ariz.). EEE, New York. pp. 1104 1109.
• 133: NEWMAN, W., AND HOGAN, N. 1987. High speed obot control and obstacle avoidance using ynamic potential function. In Proceedings of he IEEE International Conference on Robotics nd Automation (Raleigh, N. Carol., Mar. 1-Apr. 3). IEEE, New York, pp. 14 24.
• 134: NGUYEN, V. D. 1984. The Findpath problem in he plane. AI Memo 760, Artificial Intelligence ab., Massachusetts Inst. of Technology, ambridge, Mass.
• 135: NOBORIO, H., NANIWA, T., AND ARIMOTO, S. 1989. feasible motion planning algorithm for a obile robot on a quadtrce representation. In roceedings of the IEEE International Confernce on Robotics and Automation (Scottsdale, riz., May 14-19). IEEE, New York, pp. 27-332.
• 136: O'DONNELL, P. A., AND LOZANO-PI~REZ, T. 1989. eadlock-free and collision-free coordination of wo robot manipulators. In Proceedings of the EEE International Conference on Robotics and utomation (Scottsdale, Ariz., May 14 19). EEE, New York, pp. 484-489.
• 137: O'DI~NLAING, C. 1987. Motion planning with nertial constraints. Algorithmica 2, 4, 431- 75.
• 138: O'DfJNLAINC, C., AND YAP, C. K. 1985. A retracion method for planning the motion of a disc. . Alger. 6, 1(Mar.), 104-111.
• 139: OOMMEN, B. J., IYENGAR, S. S., RAO, N. S. V., AND ASHYAP, R. L. 1987. Robot navigation in nknown terrains using learned visibility raphs. Part I: The disjoint convex obstacle ase. IEEE Int. J. Robotzcs Auto. RA-3, 6 (Dec.), 72 680.
• 140: O'RouRKE, J., SURI, S., ANv BOOTH, H. 1984. hortest paths on polyhedral surfaces. Tech. ep. The Johns Hopkins Univ.. Baltimore.
• 141: PADEN, B., MEES, A., AND FISHER, M. 1989. Path lanning using a Jacobian-based freespace genration algorithm. In Proceedings of the IEEE nternational Conference on Robotics and utomation (Scottsdale, Ariz. May 14-19). EEE, New York, pp. 1732-1737.
• 142: PAPADIMITRIOU, C. H. 1985. An algorithm for hortest-path motion in three dimensions. Inf. rocess. Lett. 20, 5 (June), 259-263.
• 143: PArLOr, V. V., AND VORONIN, A. N. 1984. The ethod of potential functions for coding onstraints of the external space in an intellient mobile robot. Soviet Auto. Cont. 6.
• 144: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 145: QUEK, F. K. H., FRANKLIN, R. F., AND PONT, F. 985. A decision system for autonomous robot avigation over rough terrain. In Proceedings f SPIE Applicaaons of Artificial Intelligence Boston).
• 146: RAO, N., IYENGAR, S., AND DESAUSSURE, G. 1988. he visit problem: Visibility graph-based soluion. In Proceedings of the IEEE International onference on Robotics and Automation Philadelphia, Apr. 24-29). IEEE, New York, p. 1650 1655.
• 147: REIF, J. H. 1979. Complexity of the mover's roblem and generalizations, extended bstract. In Proceedings of the IEEE Sympoium on Foundations of Computer Science (San uan, Puerto Rico, Oct. 29-31), IEEE, New ork, pp. 421 427.
• 148: REIF, J. H., AND SHARm, M. 1985. Motion planing in the presence of moving obstacles In roceedings of the 26th Annual IEEE Sympoium on Foundations of Computer Science Portland, Oreg., Oct. 21-23). IEEE, New York, p. 144-154.
• 149: John H. Reif , James A. Storer, 3-Dimensional Shortest Paths in the Presence of Polyhedral Obstacles, Proceedings of the Mathematical Foundations of Computer Science 1988, p.85-92, August 29-September 02, 1988
• 150: REIF, J. H., AND STORER, J. A. 1985. Shortest aths in Euclidean space with polyhedral bstacles. Tech. Rep. CS-85-121, Computer Scince Dept., Brandeis Univ., Waltham, Mass.
• 151: RICHBOURG, R. F., RowE, N. C., ZYDA, M. J., AND CGHEE, R. B. 1987. Solving the global, wo-dimensional routing problem using Snell's aw and A~ search. In Proceedings of the IEEE nternattonal Conference on Robotics and utomation (Raleigh, N. Carol., Mar. 31-Apr. ). IEEE, New York, pp. 1631-1636.
• 152: RIMON, E., AND KODITSCHEK~ D. E 1989. The contruction of analytic diffeomorphism for exact obot navigation on star worlds. In Proceedings f the IEEE International Conference on obotics and Automation (Scottsdale, Ariz., ay 14-19). IEEE, New York, pp. 21-26.
• 153: RIMON, E., AND KODITSCHEK, D. E. 1988. Exact obot navigation using cost functions: The case f distinct spherical boundaries in En. In Proeedzngs of the IEEE International Conference n Robotics and Automation (Philadelphia, Apr. 4-29). IEEE, New York, pp. 1791 1796.
• 154: K. D. Rueb , A. K. C. Wong, Structuring free space as a hypergraph for roving robot path planning and navigation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.9 n.2, p.263-273, March 1987 [doi>10.1109/TPAMI.1987.4767900]
• 155: SCHWARTZ, J T., AND SHAreR, M. 1983a. On the iano movers' problem: I. The case of a twoimensional rigid polygonal body moving midst polygonal barriers. Commun. Pure Appl. ath. 3G, 3(May), 345 398.
• 156: SCHWARTZ, J. T., AND SHARm, M. 1983b. On the iano movers' problem: III. Coordinating he motion of several independent bodies midst polygonal barriers. Int. J. Robotics Res , 3 (Fall), 46-75.
• 157: SCHWARTZ, J. T., AND SHARIR, M. 1981. On the iano movers' problem: II: Techniques for comuting topological properties of real algebraic anifolds. Report No. 39, Courant Inst. of athematical Sciences. New York Univ.
• 158: Jacob T. Schwartz , C. K. Yap, Advances in Robotics: Algorithmic and Geometric Aspects of Robotics, Lawrence Erlbaum Associates, Inc., Mahwah, NJ, 1987
• 159: SHAMOS, M. I., AND HOEY, D. 1975. Closest point roblems. In Proceedings of the 16th IEEE ymposium on Foundations of Computer Science (Berkeley, Calif., Oct. 13 15), IEEE, New ork, pp. 151-162.
• 160: SHAreR, M. 1987. Efficient algorithms for planing purely translational collision-free motion n two and three dimensions. In Proceedings of he IEEE Internattonal Conference on Robotics nd Automation (Raleigh, N. Carol., Mar. 1-Apr. 3). IEEE, New York, pp. 1326-1331.
• 161: Micha Sharir , Amir Schorr, On shortest paths in polyhedral spaces, SIAM Journal on Computing, v.15 n.1, p.193-215, Feb. 1986 [doi>10.1137/0215014]
• 162: Micha Sharir( , Amir Schorr, On shortest paths in polyhedral spaces, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.144-153, December 1984 [doi>10.1145/800057.808676]
• 163: M. Sharir , S. Sifrony, Coordinated motion planning for two independent robots, Proceedings of the fourth annual symposium on Computational geometry, p.319-328, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73426]
• 164: SmLLER, Z., AND DUBOWSkW, S. 1988. Global time ptimal motions of robotic manipulators in the resence of obstacles In Proceedings of the EEE Internatzonal Conference on Robotics and utornatmn (Philadelphia, Apr. 24-29). IEEE, ew York, pp. 370 375
• 165: SHIN~ K. G., AND McKAY, N.D. 1984. Open-loop mmimum-t~me control of mechanical mampuators and its application. In Proceedings of the merican Control Conference (San Diego, June -8). IEEE, New York, pp. 1231-1236
• 166: SINGH, S., AND WAGH, M. D. 1987. Robot path lanning using intersecting convex shapes. EEE J. Robotics Auto. RA-3, 2 (Apr.), 101-108.
• 167: STRIP, D. R., AND MACIEJEWSKI, A. A. 1990. rchimedes An experiment in automating echanical assembly. In The 11th Internaional Conference on Assembly Automation Dearborn, Mmh.). pp. MS90-839.
• 168: Subhash Suri, A linear time algorithm with minimum link paths inside a simple polygon, Computer Vision, Graphics, and Image Processing, v.35 n.1, p.99-110, July 1986 [doi>10.1016/0734-189X(86)90127-1]
• 169: TANNENBAUM, A., AND YOMDIN, Y. 1987. Robotic anipulators and the geometry of real semialebraic sets. IEEE J. Robotics Auto. RA-3, 4 Aug.), 301 307.
• 170: TAP~BANIS, K., TSAI, R. Y., AND ALLEN, P.K. 1991. utomated sensor planning for robotic vision ask. In Procee&ngs of the IEEE International onference on Robotzcs and Automatzon Sacramento, Apr. 7-12). IEEE, New York, pp. 6-83.
• 171: TARsKI, A. 1951. A Decision Method for Elemenary Algebra and Geometry, 2nd ed. University f California Press. Berkeley, Calif.
• 172: THORPE, C.E. 1984. Path relaxation: Path planing for a mobile robot. In Procee&ngs of the A_A/(Austin, Tex., Aug. 6-10). Morgan Kaufann Publishers, Inc. Los Altos, Calif., pp. 18-321
• 173: WARREN, C. W 1989. Global path planning using rtificial potential fields. In Proceedings of the EEE International Conference on Robotics and utomation (Scottsdale, Ariz., May 14-19). EEE, New York, pp. 316-321.
• 174: WELZL, E 1985. Constructing the visibility raph for n line segments in O(n2) time. Inf. rocess Lett. 20, 4(May), 167-171.
• 175: WILFONG, G. 1989. Shortest path for autonomous ehicles. In Proceedings of the IEEE Internaional Conference on Robotics and Automation Scottsdale, Ariz., May 14 19). IEEE, New ork, pp. 15-20.
• 176: WILFONG, G. 1988a. Motion planning for an utonomous vehmle. In Proceedings of the IEEE nternatzonal Conference on Robotics and utomatzon (Philadelphia, Apr. 24-29). IEEE, ew York, pp. 529-533.
• 177: G. Wilfong, Motion planning in the presence of movable obstacles, Proceedings of the fourth annual symposium on Computational geometry, p.279-288, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73422]
• 178: WmSON, R. H. 1992. On geometric assembly lanning. Tech. Rep. STAN-CS-92-1416, Dept. f Computer Science, Stanford Univ., Stanford, alif.
• 179: YAP, C.K. 1985. An O(n log n) algorithm for the oronoi diagram of a set of simple curve segents. Rep. No. 43, Couront Inst. Robotics aboratory, New York Univ.
• 180: YEVNG, D. Y., ~D B~Y, G.A. 1987. A decenralized approach to the motion planning probem for multiple mobile robots. In Proceedings f the IEEE International Conference on obotics and Automation (Raleigh, N. Carol., ar. 31-Apr. 3). IEEE, New York, pp. 779-1784.
• 181: ZHu, D., A~D LATOMBE, J. C. 1990. Constraint eformulation in a hierarchical path planner. n Proceedings of the IEEE Internatwnal onference on Robotics and Automation Cincinnati, May 13- 18). IEEE, New York, pp. 918 1923.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.9 Robotics
          Subjects: Manipulators

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.10 Vision and Scene Understanding
            Subjects: Motion
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods; Graph and tree search strategies

General Terms:
Algorithms, Theory

Keywords:
collision detection, computational geometry, implementation, motion planning, obstacle avoidance, path planning, spatial representation