Yong K. Hwang
Skip Abstract Section
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.
- AHUJA, N., AND SCHACHTER, B. 1983. Pattern Models. Wiley, New York.Google Scholar
- ALAML R., SIMEON, T., AND LAUMOND, J.P. 1989. A geometric approach to planning manipulation tasks. The case of discrete placements and grasps. In Proceedings of the 5th International Symposium of Robotics Research (Tokyo, Aug. 28-31), MIT Press, Cambridge, Mass. pp. 453-463. Google Scholar
- ALT, H., FLEISCHER, R., KAUFMANN, M., MEHLHORN, K., N'AHER, S., SCHIRRA, S., AND UHRIG, C. 1990. Approximate motion planning and the complexity of the boundary of the union of simple geometric figures. In Proceedings of the 5th Annual ACM Symposium on Compzltational Geometry (Berkeley, Calif., June 6-8). ACM, New York, pp. 281-289. Google Scholar
- 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.Google Scholar
- ATALLAH, M. J., AND CHEN, D.Z. 1989. Optimal parallel algorithms for visibility of a simple polygon from a point. In Proceedings of the 5th Annual ACM Symposium on Computational Geometry (Berkeley, Calif., June 6-8). ACM, New York, pp. 114 123 Google Scholar
- ATALLAH, M. J., COLE, R., AND GOODRICH, M. T. 1989. Cascading divide-and-conquer: A technique for designing parallel algorithms. SIAM J. Comput. 18, 3 (June), 499-532. Google Scholar
- ATHENS, M., AND FALBS, P. L. 1966 Optimal Control. McGraw-Hill, New York.Google Scholar
- AURENHAMMER, F. 1991. Voronol diagrams--A survey of fundamental geometric data structure. ACM Comput. Surv. 23, 3 (Sept.), 345-405. Google Scholar
- 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.Google Scholar
- BARR, A., AND FEIGENBAUM, E. A. 1981. The Handbook of Arhl%ial Intelligence. William Kaufmann, Los Altos, Calif. Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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-310Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- BRYSON, A. E., JR., AND HO, Y.C. 1975. Appltcd Opttmal Control. Hemisphere Publishing, Washington, D.C.Google Scholar
- 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.Google Scholar
- CANNY, J. F. 1988. The Complexity of Robot Motion Plan~zing. The MIT Press, Cambridge, Mass. Google Scholar
- 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.Google Scholar
- CANNY, J. F., AND DONALD, B. 1987. Simplified Voronoi diagram. In Proceedings of the 3rd Annual ACM Symposium on Computational Geometry (Waterloo, Ontario, June 8 10). ACM Press, New York, pp 153 161 Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- CANNY, J. F., REOE, A., AND REIF, J. 1990. An exact algorithm for klnodynamic planning in the plane. In Proceedings of the 6th Annual ACM Symposium on Computational Geometry (Berkeley, Calif, June 6 8). ACM~ New York, pp. 271 280. Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- C}~ATTERGY, R. 1985. Some heuristics for the navigation of a robot. Int. J. Robotics Res. 4, 1 (Spring), 59-66.Google Scholar
- CimN, J., AND HAN, Y. 1990. Shortest paths on a polyhedron. In Proceedings of the 6th Annual ACM Symposium on Computational Geometry (Berkeley, Ca}if., June 6-8). ACM, New York, pp. 36O 369. Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- CHEW, L.P. 1985. Planning the shortest path for a disc in O(n2 log n) time. In Proceedings of the 18t Annual ACM Symposium on Computational Geometry tBaltimore, June 5-7). ACM, New York, pp. 214 220. Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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).Google Scholar
- CLARKSON, K. L., KAPOOR, S., AND VAIDYA, P. M. 1987. Rectilinear shortest paths through polygonal obstacles in O(n(logn)~) time. In Proceedings of the 3rd Annual ACM Symposium on Computational Geometry (Waterloo, Ontario, June 8 10). ACM, New York, pp. 251 257. Google Scholar
- COLLINS, G. 1975. Quantifier elimination for real closed fields by cylindrical algebraic decomposition. In The 2nd G! Conference on Automata Theory and Formal Languages, vol. 33. Springer-Verlag, New York, pp. 134-183. Google Scholar
- CORMEN, T. H., LEISERSON, C. E., AND RIVEST, R. L. 1990. Introduction to Algorithms. McGraw- Hill, New York, pp. 916 963. Google Scholar
- DE REZENDE, P. J., LEE, D. T., AND WU, Y.F. 1985. Rectilinear shortest paths with rectangular barriers. In Proceedings of the 1st Annual ACM Symposium on Computational Geometry (Baltimore, June 5-7). ACM, New York, pp. 204 213. Google Scholar
- DIJKSTRA, E.W. 1959. A note on two problems in connection with graphs. Numerlsche Mathemat~k 1,269 271. In English.Google Scholar
- DONALD, B. 1984. Motion planning with six degrees of freedom, Tech. Rep. AI-TR-791, Artificial Intelligence Lab., Massachusetts Inst. of Technology, Cambridge, Mass. Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- DRYSDALE, R.L. 1979. Generalized Voronoi diagrams and geometric searching. Tech. Rep. STAN-CS-79-705, Stanford Univ., Stanford, Calif.Google Scholar
- 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.Google Scholar
- ELGINDY, H., AND GOODRICH, M.T. 1988. A linear algorithm for computing the visibility polygon from a point. J. Alg. 2, 186-197.Google Scholar
- 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. {Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- FORTUNE, S., AND WILFONG, G. 1988. Planning constrained motion. In The Symposium on the Theory of Computer Science (Chicago). pp. 445 459. Google Scholar
- 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.Google Scholar
- FREUND, E., AND HOYER, H. 1988. Real-time pathfinding in multirobot systems including obstacle avoidance. Int. J. Robotics Res. 7, 1 (Feb.), 42-70. Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- GEWALI, L., MENG, A., MITCHELL, J. S. B., AND NTAFOS, S. 1988. Path planning in 0/1/2 weighted regions with applications. In Proceedings' of the 4th Annual ACM Symposium on Computational Geometry (Urbana, Ill., June 6-8). ACM, New York, pp. 266-278. Google Scholar
- 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-61Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- GOODRICH, M. T., SHAUCK, S. B., AND GUHA, S. 1990. Parallel method for visibility and shortest path problems in a simple polygons. In Proceedtngs of the 6th Annual ACM Symposium on Computatmnal Geometry (Berkeley, Calif., June 6-8). ACM, New York, pp. 73 82. Google Scholar
- GumAs, L. J., S~tARIR, M., AND SIFRONY, S. 1988. On the general motion planning problem with two degrees of freedom. In Proceedings of the 4th Annual ACM Symposium on Computational Geometry (Urbana, Ill., June 6-8). ACM, New York, pp. 289-298. Google Scholar
- 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.Google Scholar
- HOGAN, N. 1985. Impedance control: An approach to manipulation: Part III-- Application. ASME J. Dynamtc Syst. Meas. Control. 107 (Mar.), 17-24.Google Scholar
- HOPCROFT, J., ANDULLMAN, J.D. 1979. Introduction to Automata Theory, Languages and Computations. Addison-Wesley, Reading, Mass. Google Scholar
- HOPCROFT, J., AND WILFONG, G T. 1986. Reducing multiple object motion planning to graph searching. SlAM J. Comput. 15, 3 (Aug.), 768-785. Google Scholar
- 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.Google Scholar
- HOPCROFT, J., JOSEPH, D., AND WHITESIDE, S. 1984a. Movement problems for 2-dimensional linkages. SlAM J. Comput. 13, 3 (Aug.), 610 629. Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- HUTCHINSON, S. A., AND KAK, A.C. 1990. Spar: A planner that satisfies operational and geometric goals in uncertain environments. A/Mag. 11, I (Spring), 31 61. Google Scholar
- 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.Google Scholar
- HWANG, Y. K., AND AHUJA, N. 1992. Potentml field approach to path planning. IEEE Trans. Robotics Auto. 8, I (Feb.), 23-32.Google Scholar
- 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.Google Scholar
- HWAN% Y. H., CHANG, R. C., AND TU, H.Y. 1989. Finding all shortest path edge sequences on a convex polyhedron. In Lecture Notes in Computer Science, Algorithms and Data Structures Workshop, vol. 332, Springer-Verlag, New York. Google Scholar
- HWANG, Y. K., CHEN, P. C., AND XAVIER, P. G. 1992. Test states for motion planning. Internal Rep., Sandia National Laboratories, Albuquerque, New Mex.Google Scholar
- 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.Google Scholar
- JONES, S. T. 1980. Solving problems involving variable terrain. Part 1: A general algorithm. Byte 5, 2.Google Scholar
- 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.Google Scholar
- KAMBHAMPATI, S., AND DAVIS, L. S. 1986. Multiresolution path planning for mobile robots. IEEE J. Robotics Auto. RA-2, 3 (June), 135-145.Google Scholar
- 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.Google Scholar
- KANT, K., AND ZUCKER, S.W. 1986. Toward efficient trajectory planning: The path-velocity decomposition. Int. J. Robottcs Res. 5, 1 (Spring), 72-89. Google Scholar
- KE, Y. 1989. An efficient algorithm for link distance problems. In Proceedzngs of the 5th Annual ACM Symposium on Computational Geometry (Saarbruchen, West Germany, June 5-7). ACM, New York, pp. 69-78. Google Scholar
- KE, Y., AND O'ROURKE, J. 1988. Lower bounds on moving a ladder in two and three dimensions. In Discrete and Computational Geometry, vol. 3. Springer-Verlag, New York, pp. 197-217. Google Scholar
- Ku, Y., AND O'RoURKE, J. 1987. Moving a ladder in three dimensions: Upper and lower bounds. In Proceedings of the 3rd Ann ual ACM Symposium on Computational Geometry (Waterloo, Ontario. June 8-10). ACM, New York, pp. 136-145. Google Scholar
- KEDEM, K., AND SHARIR, M. 1988. An automatic motion planning system for a convex polygonal mobile robot in 2-D polygonal space. In Proceedmgs of the 4th Annual ACM Symposium on Computational Geometry (Urbana, Ill., June 6-8). ACM, New York, pp. 329-340. Google Scholar
- KEDEM, K., AND SHARIR, M. 1985. An efficient algorithm for planning collision-free motion of a convex polygonal object in 2-dimensional space amidst polygonal obstacles. In Proceedmgs of the 1st Annual ACM Symposium on Computatzonal Geometry (Baltimore, June 5-7). ACM, New York, pp. 75-80. Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- KHATIB, O., AND MAMPEY, L.M. 1978. Fonction decision-commande d'un robot manipulateur. Rep. 2/7156. DERA/CERT, Toulouse, France.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- KODtTSCHEK, D. E. 1989. Robot planning and control via potential functions. In Robotzcs Review, vol. 1, O. Khatib, J. Graig, and T. Lozano-P~rez, Eds. MIT Press, Cambridge, Mass. Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- LATOMBE, J C. 1991. Robot Motion Planning Kluwer Academic Publishers, Boston/ Dordrecht/London. Google Scholar
- LEE, D.T. 1978. Proximity and reachability in the plane. Ph.D. dissertation, Univ. of Ilhnois, Urbana-Champaign, Ill. Google Scholar
- LEE, D. T, AND DRYSDALE, R.L. 1981. Generalization of Voronoi diagram in the plane. SIAM J. Comput. 10, 73-83.Google Scholar
- 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.Google Scholar
- LEE, D. T., CHEN, T. H., AND YANO, C. D. 1990. Shortest rectilinear paths among weighted obstacles. In Proceedings of the 6th Annual ACM Symposium on Computational Geometry (Berkeley, Calif., June 6-8). ACM, New York, pp. 301-310. Google Scholar
- LENGYEL, J., REICHERT, M., DONALD, B. R, AND GREENBERG, D. P. 1990. Real-time robot motion planning using rasterizing computer graphics hardware. Cornput. Graph. 24, 4 (Aug.), 327 335 Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- LOZANO-P~REZ, T. 1987. A simple motionplanning algorithm for general robot manipulators. IEEE J. Robotics Auto. RA-3, 3 (June), 224-238Google Scholar
- 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.Google Scholar
- LOZANO-PiREZ, T, AND WESLEY, M.A. 1979 An algorithm for planning collision-free paths among polyhedral obstacles. Coraraun. ACM 22, 10 (Oct.), 560 570. Google Scholar
- LOZANO-P~REZ, T., JONES, J. L., MAZER, E., O'DONNELL, P.A. 1989. Task-level planning of pick-and-place robot motmns. IEEE Comput. 22, 3 (Mar.), 21 29. Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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-1055Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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 ResGoogle Scholar
- MITCHELL, J. S. B., AND PAPADIMrTRIOU, C.H. 1987. he weighted region problem. In Proceedings f the 3rd Annual ACM Symposium on Compuational Geometry (Waterloo, Ontario, June -10). ACM, New York, pp. 30 38. Google Scholar
- MITCHELL, J. S. B., MOUNT, D. M., AND APADIMITRIOU, C. H. 1987. The discrete eodesic problem. SIAM J. Comput. 16, 4 Aug.), 647-668. Google Scholar
- MITCHELL, J. S. B., ROTE, G., AND WOEGINGER, G. 990. Minimum-link paths among obstacles n the plane. In Proceedings of the 6th Annual CM Symposium on Computatwnal Geometry Berkeley, Calif., June 6 8). ACM, New York, p. 63 72. Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- MOUNT, D. M. 1985. On finding shortest paths n convex polyhedra. Tech. Rep. 1495, Dept. of omputer Science, Univ. of Maryland, altimore.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- NGUYEN, V. D. 1984. The Findpath problem in he plane. AI Memo 760, Artificial Intelligence ab., Massachusetts Inst. of Technology, ambridge, Mass.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- O'DI~NLAING, C. 1987. Motion planning with nertial constraints. Algorithmica 2, 4, 431- 75.Google Scholar
- O'DfJNLAINC, C., AND YAP, C. K. 1985. A retracion method for planning the motion of a disc. . Alger. 6, 1(Mar.), 104-111.Google Scholar
- 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.Google Scholar
- O'RouRKE, J., SURI, S., ANv BOOTH, H. 1984. hortest paths on polyhedral surfaces. Tech. ep. The Johns Hopkins Univ. Baltimore.Google Scholar
- 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.Google Scholar
- PAPADIMITRIOU, C. H. 1985. An algorithm for hortest-path motion in three dimensions. Inf. rocess. Lett. 20, 5 (June), 259-263.Google Scholar
- 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.Google Scholar
- PREPARATA, F. P., AND Sm~MOS, M.I. 1985. Comutational Geometry. An Introductzon. pringer-Verlag, New York. Google Scholar
- 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).Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- REIF, J. H., AND STORER, J. A. 1988. 3- imensional shortest paths in the presence of olyhedral obstacles. In Proceedings of the EEE Symposium on Foundations of Computer cience. (White Plains. New York. Oct. 24-26). EEE, New York, pp 85-92. Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- RUEB, K. D., ANn WONG, A. K.C. 1987. Structur~ g free space as a hypergraph for roving robot ath planning and navigation. IEEE Trans. art. Anal. Machzne Intell. PAMI 9, 2 (Feb.), 63-273. Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- SCHWARTZ, J. T., AND YAP, C.K. 1987. Advances n Robotics, Vol. I, Algorithmic and Geometric spects of Robotics. Erlbaum, Hiltsdale, New ersey. Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- SHARIR, M. AND SCHORR, A. 1986. On shortest aths in polyhedral spaces. SIAM J. Comput. 5, l(Feb.), 193 215. Google Scholar
- SHARiR, M., AND SCHORR, A. 1984. On shortest aths in polyhedral spaces. In Proceedings of he 16th Symposium on the Theory of Computng. American Computing Machinery, pp. 44-153. Google Scholar
- SHARn~, M., AND SIFRONY, S. 1988. Coordinated otion planning for two independent robots. In roceedings of the 4th Annual ACM Sympozum on Computational Geometry (Urbane, Ill., une 6-8). ACM, New York, pp. 319 328. Google Scholar
- 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 375Google Scholar
- 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-1236Google Scholar
- SINGH, S., AND WAGH, M. D. 1987. Robot path lanning using intersecting convex shapes. EEE J. Robotics Auto. RA-3, 2 (Apr.), 101-108.Google Scholar
- 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.Google Scholar
- SUm, S. 1986. A linear time algorithm for minium link paths reside a rumple polygon. Cornut. Vision, Graph. Image Proc. 35, 99 110. Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- TARsKI, A. 1951. A Decision Method for Elemenary Algebra and Geometry, 2nd ed. University f California Press. Berkeley, Calif.Google Scholar
- 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-321Google Scholar
- 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.Google Scholar
- WELZL, E 1985. Constructing the visibility raph for n line segments in O(n2) time. Inf. rocess Lett. 20, 4(May), 167-171.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- WmFONG, G 1988b. Motion planningin the presnce of movable obstacles. In Proceedings of he 4th Annual ACM Symposium on Computaional Geometry (Urbana, Ill., June 6-8). ACM~ ew York, pp. 279 288. Google Scholar
- WmSON, R. H. 1992. On geometric assembly lanning. Tech. Rep. STAN-CS-92-1416, Dept. f Computer Science, Stanford Univ., Stanford, alif.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
Index Terms
- Gross motion planning—a survey
Recommendations
Multiple Mobile Robot Task and Motion Planning: A Survey
With recent advances in mobile robotics, autonomous systems, and artificial intelligence, there is a growing expectation that robots are able to solve complex problems. Many of these problems require multiple robots working cooperatively in a multi-robot ...
On responsiveness, safety, and completeness in real-time motion planning
Replanning is a powerful mechanism for controlling robot motion under hard constraints and unpredictable disturbances, but it involves an inherent tradeoff between the planner's power (e.g., a planning horizon or time cutoff) and its responsiveness to ...
A novel collaborative path planning algorithm for 3-wheel omnidirectional Autonomous Mobile Robot
AbstractCollaboration of multiple mobile robots becomes important in situations where collaborative tasks are required. For this purpose, a method including obstacle detection based on collaborative path planning of multiple Autonomous Mobile Robots (...
Graphical abstractDisplay Omitted
Highlights- The most efficient collision-free trajectory planning for collaborative mobile robots.
- Path planning and obstacle avoidance algorithm at the safe following distance.
- Path planning of collaborative autonomous omnidirectional mobile ...
Reviews
Paolo Fiorini
The authors take on the difficult task of presenting, in a concise and detailed form, a central aspect of the motion planning problem, that is, the computation of movements away from the boundaries of obstacles and environment, which goes under the name of gross motion planning. This area has traditionally been the domain of motion planning from an AI perspective, whereas fine motion planning, which deals with movements that have a dynamic interaction with the environment, is mostly studied from the point of view of real-time control, because of its strong dependency on sensing and control. This paper is a comprehensive summary of most of the available algorithms for gross motion planning. The good organization of the abundant material makes it particularly worthwhile reading for people who want to quickly learn the concepts, terminology, and tools of gross motion planning, before undertaking the study of a specific research area. The paper is organized in four major sections. The first presents the basic aspects of the motion planning problem. The authors then discuss general methods for solving it. Next, they present how these methods have been implemented by different researchers for specific cases. The conclusion gives helpful suggestions on how to develop efficient algorithms. An important feature of this paper is the description, within the limits of the available data, of the complete development of a solution to a gross motion planning problem, from its formulation, through the choice of problem representation, to its performance data. Overall, the quality of the paper is good, and the level of the presentation is accessible to most readers. Each section is structured according to a taxonomy of the problem, which helps the authors make correspondences and identify analogies among the various algorithms, although, at times, it tends to slow down the presentation. The authors cover most of the issues in gross motion planning, with the exception of a few missing references, particularly in the areas of planning under uncertainty and constructive geometry methods for motion planning. Of the four sections composing the paper, the first is a brief introduction followed by a presentation of the nature of the motion planning problem. The authors explain the terminology of the problem and review the relevant concepts of computer science. Section 2 summarizes the different tools that can be used in solving a motion planning problem. Section 3 is the main part of the paper, where the authors list and discuss the main approaches presented in the literature on motion planning. The presentation is summarized at the end by a set of tables listing each paper discussed in terms of the approach used and of its applicability to a specific motion planning problem. In the conclusion, the authors emphasize the importance of developing more practical algorithms for motion planning. In general, the authors' writing style is clear and easy to follow. Good explanations are given of the main features of the various algorithms, although references to a particular approach are mainly provided when that approach is discussed, and not in the introductory sections. The bibliography at the end of the paper, covering most of the significant work in gross motion planning, is particularly useful.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments