The mapping from workspace to configuration space (C-space) plays a major role in the field of kinematics, with applications including robotics path planning, packing and nesting, automated assembly, and mechanism analysis. Over the past 20 years, research into the problem has resulted in many techniques that can be combined to suit a specific application. This survey aims to provide the developer of a C-space-based system with an overview of those techniques that map the global C-space of a single robot in a static environment. We discuss issues concerning how the robot and its environment are modeled (including how approximations can be used to make C-space mapping easier) and describe a range of schemes used to represent a C-space map. We then discuss the key techniques used to generate a C-space map for mobile robots and manipulators. The survey of literature is summarized by tables that list some 50 individual mapmaking papers, classifying each according to criteria identified in earlier sections. Finally, we draw conclusions from the findings of the survey. Note that, although reference is made throughout to robots, the controlled objects may equivalently be components or assemblies. In particular, results for mobile robots are fundamental to all C-space mapmaking problems.
Get full access to this article
View all access options for this article.
References
1.
Adamowicz, M., and Albano, A. 1976. Nesting twodimensional shapes in rectangular modules . Computer Aided Design8(1): 27-27 .
2.
Adolphs, P., and Nafziger, D. 1990. A method for fast computation of collision-free robot movements in configuration space . IEEE International Workshop on Intelligent Robots and Systems, Tokyo, Japan, July 4–6, pp. 5–12 .
3.
Avnaim, F., and Boissonnat, J. D. 1988. Polygon placement under translation and rotation . Springer’s Lecture Notes in Computer Science Series294: 323–333 .
4.
Avnaim, F., Boissonnat, J. D., and Faverjon, B. 1988. A practical exact motion planning algorithm for polygonal objects amidst polygonal obstacles . Springer’s Lecture Notes in Computer Science Series391: 67–86 .
5.
Bajaj, C., and Kim, M. S. 1988. Generation of configuration space obstacles—the case of a moving sphere . IEEE Journal of Robotics and Automation4(1): 94–99 .
6.
Bajaj, C., and Kim, M. S. 1990. Generation of configuration space obstacles: Moving algebraic surfaces . International Journal of Robotics Research9(1): 92–112 .
7.
Bellier, C., Laugier, C., Mazer, E., and Troccaz, J. 1992. Planning/executing six DOF robot motions in complex environments . Proc. 91 IEEE RSJ International Workshop Intelligence Robots Systems IROS 91, Osaka, Japan, pp. 91–96 .
8.
Branicky, M. S., and Newman, W. S. 1990. Rapid computation of configuration space obstacles . Proc. 1990 IEEE International Conference Robotics Automation, Cincinnati, OH, pp. 304–310 .
9.
Brooks, R. A., and Lozano-Pérez, T. 1985. A subdivision algorithm in configuration space for findpath with rotation . IEEE Transactions on Systems Man and Cybernetics15(2): 224–233 .
10.
Brost, R. C. 1989. Computing metric and topological properties of configuration-space obstacles . International Conference Robotics Automation 19891: 170–176 .
11.
Canny, J. F. 1988. The Complexity of Robot Motion Planning. Cambridge, MA: MIT Press .
12.
Cesati, M., and Wareham, H. T. 1995. Parameterized complexity analysis in robot motion planning . Proceedings of the 1995 IEEE International Conference on Systems, Man and Cybernetics. Part 1 (Of 5), Vancouver, B.C., October 22–25 (Conf. Code 44222), vol. 1, pp. 880–885 . IEEE, Piscataway, NJ.
13.
Chan, R.H.T., Tam, P.K.S., and Leung, D.N.K. 1994. Solving the motion planning problem by using neural networks . Robotica12(4): 323–333 .
14.
Chen, P. C., and Hwang, Y. K. 1992. SANDROS: A motion planner with performance proportional to task difficulty . Proceedings—IEEE International Conference on Robotics and Automation3: 2346–2353 .
15.
Cheng, H., and Cheng, H. D. 1996. Feasible map algorithm for path planning . Robotics and Autonomous Systems17(3): 149–170 .
16.
Curto, B., and Moreno, V. 1997. Mathematical formalism for the fast evaluation of the configuration space . Proceedings of the 1997 IEEE International Symposium on Computational Intelligence in Robotics and Automation, Cira, Monterey, CA, July 10–11 (Conf. Code 46973), Record 85, pp. 194–199 . IEEE, Piscataway, NJ.
17.
Dehne, F., Hassenklover, A. L., and Sack, J. R. 1989. Computing the configuration space for a robot on a mesh-ofprocessors . Parallel Computing12(2): 221–231 .
18.
De Pedro, M. T., and Rosa, R. G. 1992. Robot path planning in the configuration space with automatic obstacle transformation . Cybernetics and Systems23(3–4): 367–378 .
19.
Donald, B. R. 1985. On motion planning with 6 degrees of freedom: Solving the intersection problems in configuration space . Proc. IEEE International Conference on Robotics and Automation, St. Louis, MO, pp. 536–541 .
20.
Donald, B. R. 1987. A search algorithm for motion planning with 6–degrees of freedom . Artificial Intelligence31(3): 295–353 .
21.
Duelen, G., and Willnow, C. 1991. Path planning of transfer motions for industrial robots by heuristically controlled decomposition of the configuration space. In Robotic Systems: Proceedings of the 1991 EURISCON Conference, Korfu, ed. S. G. Tzafestas, 217–224. Boston: Kluwer Academic .
22.
Efrat, A., and Sharir, M. 1997. On the complexity of the union of fat objects in the plane . Proceedings of the ACM Symposium on Computational Geometry ’97, Nice, France, pp. 104–112 .
23.
Faltings, B. 1987. Qualitative kinematics in mechanisms . Proceedings of IJCAI-87, Milan, Italy, pp. 436–442 .
24.
Faverjon, B. 1984. Obstacle avoidance using an octree in the configuration space of a manipulator . Proceedings of the IEEE Int. Conf. Robotics, Atlanta, GA, March, pp. 504–512 .
25.
Faverjon, B., and Tournassoud, P. 1988. Motion planning for manipulators in complex environments . Geometry & Robotics, in Springers’ Lecture Notes in Computer Science Series391: 87-87 .
26.
Fujimura, K. 1993. Motion planning amidst dynamic obstacles in three dimensions . 1993 International Conference on Intelligent Robots and Systems, Yokohama, Japan, p. 1387-1387 .
27.
Ge, Q., and McCarthy, J. M. 1989. Equations for boundaries of joint obstacles for planar robots . International Conference Robotics Automation1: 164–169 .
28.
Ge, Q. J., and McCarthy, J. M. 1990. An algebraic formulation of configuration-space obstacles for spatial robots . Proc. 1990 IEEE International Conference Robotics Automation, Cincinnati, OH, pp. 1542–1547 .
29.
Gouzènes, L. 1984. Strategies for solving collision-free trajectories problems for mobile and manipulator robots . International Journal of Robotics Research3(4): 51-51 .
30.
Halperin, D., Overmars, M. H., and Sharir, M. 1992. Efficient motion planning for an L-shaped object . SIAM Journal on Computing21(1): 1–23 .
31.
Hart, P. E., Nilsson, N. J., and Raphael, B. 1968. A formal basis for the heuristic determination of minimum cost paths . IEEE Transactions Systems, Science and CyberneticsSSC-4(2): 100-100 .
32.
Hasegawa, T., and Terasaki, H. 1988. Collision avoidance—A divide-and-conquer approach by space characterization and intermediate goals . IEEE Transactions on Systems Man and Cybernetics18(3): 337–347 .
33.
Heegaard, J. H. 1996. Efficient parameterization of the configuration space for rigid multi-body contact and impact . Proceedings of the 1996 ASME International Mechanical Engineering Congress and Exposition, Atlanta, GA, November 17–22 (Conf. Code 45867), vol. 33, pp. 431–432 . ASME, New York.
34.
Hopcroft, J. E., Schwartz, J. T., and Sharir, M. 1984. On the complexity of motion planning for multiple independent objects: P-space-hardness of the “warehouseman’s problem.” International Journal of Robotics Research3(4): 76-76 .
35.
Hwang, Y. K. 1990. Boundary equations of configuration obstacles for manipulators . Proc. 1990 IEEE International Conference Robotics Automation, Sacramento, CA, p. 298-298 .
36.
Hwang, Y. K. 1995. Current status and future research in motion planning . Proceedings, IEEE International Symposium on Assembly and Task Planning, Pittsburgh, PA, August 10–11, pp. 431–432 .
37.
Hwang, Y. K., and Ahuja, N. 1992. Gross motion planning—A survey . ACM Computing Surveys24(3): 219–291 .
38.
Jarvis, R. A. 1983. Growing polyhedral obstacles for planning collision-free paths . Australian Computer Journal15(3): 103–110 .
39.
Kavraki, L. 1993. Computation of configuration-space obstacles using the fast Fourier transform . Proceedings IEEE International Conference on Robotics and Automation3: 255–261 .
40.
Kavraki, L. E., Kolountzakis, M. N., and Latombe, J. C. 1996. Analysis of probabilistic roadmaps for path planning . Proceedings of the 1996 IEEE 13th International Conference on Robotics and Automation. Part 4 (Of 4), Minneapolis, MN, April 22–28 (Conf. Code 44943), vol. 4, pp. 3020–3025 . IEEE, Piscataway, NJ.
41.
Kohler, M., and Spreng, M. 1995. Fast computation of the C-space of convex 2-d algebraic objects . International Journal of Robotics Research14(6): 590–608 .
42.
Latombe, J. C. 1993. Robot Motion Planning. Boston: Kluwer Academic .
43.
Laugier, C., and Germain, F. 1985. An adaptative collision-free trajectory planner . International Conference Advanced Robotics, Tokyo, Japan, pp. 33–41 .
44.
Laumond, J. P. 1987. Obstacle growing in a nonpolygonal world . Information Processing Letters25(1): 41–50 .
45.
Laumond, J. P., Simeon, T., Chatila, R., and Giralt, G. 1988. Trajectory planning and motion control for mobile robots . Geometry & Robotics, in Springer’s Lecture Notes in Computer Science Series391: 133-133 .
46.
Lengyel, J., Reichert, M., Donald, B. R., and Greenberg, D. P. 1990. Real-time robot motion planning using rasterizing computer graphics hardware . Computer Graphics (ACM)24(4): 327–335 .
47.
Lin, P. L., and Chang, S. H. 1993. A shortest path algorithm for a nonrotating object among obstacles of arbitrary shapes . IEEE Transactions Systems, Man and Cybernetics23(3): 825-825 .
48.
Liu, Y. H., and Onda, H. 1993. Constructing an approximate representation of a configuration space without using an intersection check . 1993 International Conference on Intelligent Robots and Systems, pp. 644–651 .
49.
Lozano-Pérez, T. 1981. Automatic planning of manipulator transfer movements . IEEE Transactions on Systems, Man and Cybernetics11(10): 681-681 .
50.
Lozano-Pérez, T. 1983. Spatial planning: A configuration space approach . IEEE Transactions on Computers32(2): 108–119 .
51.
Lozano-Pérez, T. 1987. A simple motion-planning algorithm for general robot manipulators . IEEE Journal of Robotics and Automation3(3): 224–238 .
52.
Lozano-Pérez, T., and Wesley, M. A. 1979. An algorithm for planning collision-free paths among polyhedral obstacles . Communications of the ACM22(10): 560-560 .
53.
Ma, C., Li, W., Yang, Y., and Chang, L. 1995. Robot motion planning with many degrees of freedom . Proceedings of the 1995 IEEE International Conference on Systems, Man and Cybernetics. Part 1 (Of 5), Vancouver, B.C., October 22–25 (Conf. Code 44222), vol. 1, pp. 892–897 . IEEE, Piscataway, NJ.
54.
Maciejewski, A. A., and Fox, J. J. 1993. Path planning and the topology of configuration-space . IEEE Transactions on Robotics and Automation9(4): 444–456 .
55.
Marr, D., and Nishihara, H. K. 1977. Representation and recognition of the spatial organization of three-dimensional shapes. Technical Report AIM-416, Artificial Intell. Lab, MIT, Cambridge, MA , May.
56.
Murakami, T., and Gossard, D. C. 1992. Mechanism concept retrieval by behavioral specification using configuration space . ASME Design Engineering Division (Publication): Design Theory and Methodology42: 343–350 .
57.
Newman, W. S., and Branicky, M. S. 1991. Real-time configuration space transforms for obstacle avoidance . International Journal of Robotics Research10(6): 650–667 .
58.
Paden, B., Mees, A., and Fisher, M. 1989. Path planning using a Jacobian-based freespace generation algorithm . Proceedings IEEE International Conference on Robotics and Automation, Scottsdale, AZ, pp. 1732–1737 .
59.
Parry-Barwick, S., and Bowyer, A. 1995. Multidimensional set-theoretic feature recognition . Computer-Aided Design27(10): 731–740 .
60.
Parsons, D., and Canny, J. 1990. A motion planner for multiple mobile robots . Proc. 1990 IEEE International Conference Robotics Automation1: 8-8 .
61.
Ralli, E., and Hirzinger, G. 1996. Global and resolution complete path planner for up to 6dof robot manipulators . Proceedings of the 1996 IEEE 13th International Conference on Robotics and Automation. Part 4 (Of 4), Minneapolis, MN, April 22–28 (Conf. Code 44943), Record - 26, vol. 4, pp. 3295–3302 . IEEE, Piscataway, NJ.
62.
Ralli, E., and Hirzinger, G. 1997. Efficient c-space modelling using kohonen maps . Proceedings of the 1997 8th International Conference on Advanced Robotics, Icar’97, Monterey, CA, July 7–9 (Conf. Code 46955), Record - 74, pp. 433–438 . IEEE, Piscataway, NJ.
63.
Red, W. E., and Truong-Cao, H. V. 1985. Configuration maps for robot path planning in two dimensions . ASME Journal of Dynamic Systems, Measurement and Control107(4): 292–298 .
64.
Reif, J. H. 1979. Complexity of the mover’s problem and generalizations . Proceedings of the 20th Symposium on the Foundations of Computer Science, San Juan, Puerto Rico, pp. 421–427 .
65.
Requicha, A., and Voelcker, H. 1983. Solid modeling: Current status and research directions . IEEE Computer Graphics Applications, 3(7): 25–37 .
66.
Sacks, E., and Joskowicz, L. 1993. Automated modeling and kinematic simulation of mechanisms . Computer Aided Design25(2): 106–118 .
67.
Schwartz, J. T., and Sharir, M. 1983. On the piano movers’ problem I: The case of a two-dimensional rigid polygonal body moving amidst polygonal barriers . Comm. on Pure & Applied Maths36: 345-345 .
68.
Schweikard, A., and Wilson, R. H. 1995. Assembly sequences for polyhedra . Algorithmica13: 539–552 .
69.
Shiller, Z., and Gwo, Y. R. 1993. Collision-free path planning of articulated manipulators . Journal of Mechanical Design115(4): 901–908 .
70.
Siméon, T. 1988. Planning collision-free trajectories by a configuration space approach . Geometry & Robotics, in Springers Lecture Notes in Computer Science Series391: 116–132 .
71.
Solano González, J., and Jones, D. I. 1996. Parallel computation of configuration space . Robotica14(2): 205–212 .
72.
Subramanian, D., and Wang, C.S.E. 1995. Kinematic synthesis with configuration-spaces . Research in Engineering Design-Theory Applications and Concurrent Engineering7(3): 193–213 .
73.
Tso, S. K., and Liu, K. P. 1993. Fast motion planner based on configuration space . 1993 International Conference Intelligence Robotics Systems, Yokohama, Japan, pp. 1401–1408 .
74.
Udupa, S. M. 1977. Collision detection and avoidance in computer controlled manipulators . Proceedings of the 5th International Joint Conference on Artificial Intelligence, Cambridge, MA, pp. 737–748 .
75.
van der Stappen, A. F., Halperin, D., and Overmars, M. H. 1993. The complexity of the free-space for a robot moving amidst fat obstacles . Computational Geometry—Theory and Applications3(6): 353–373 .
76.
van der Stappen, A. F., and Overmars, M. H. 1994. Motion planning amidst fat obstacles . Proc. 10th ACM Symposium on Computational Geometry, Stony Brook, NY, pp. 31–40 .
77.
Verwer, B.J.H. 1990. A multiresolution work space, multiresolution configuration space approach to solve the path planning problem . Proc. 1990 IEEE International Conference Robotics Automation, Cincinnati, OH, pp. 2107–2112 .
78.
Warren, C. W., Danos, J. C., and Mooring, B. W. 1989. An approach to manipulator path planning . International Journal of Robotics Research8(5): 87–95 .
79.
Wise, K. D. 1998. Exact configuration-space maps using constructive solid geometry. Technical Report 08/98, Dept. of Mechanical Engineering, University of Bath , February.
80.
Wise, K. D., and Bowyer, A. 1996. Using CSG models in many dimensions to map where things can and cannot go . Proceedings from CSG 96 Set-theoretic Solid Modelling: Techniques and Applications, Winchester, UK, pp. 359–376 .
81.
Wise, K. D., and Bowyer, A. 1998. Configuration-space mapping for multiple moving objects: A survey of techniques and applications. Technical Report 09/98, Dept. of Mechanical Engineering, University of Bath , February.
82.
Wise, K. D., Eisenthal, D., and Bowyer, A. 1997. Design optimization of rigid-body mechanisms via multidimensional CSG, 1998 . Presented at the 1997 ASME Design for Manufacturing Symposium, published in the 1998 ASME Design For Manufacturing Symposium.
83.
Woodwark, J. R. 1986. Computing Shape. London, UK: Butterworths .
84.
Zhao, C. S., Farooq, M., and Bayoumi, M. M. 1995. Analytical solution for configuration space obstacle computation and representation . Proceedings of the 1995 IEEE 21st International Conference on Industrial Electronics, Control, and Instrumentation2: 1278–1283 . IEEE, Los Alamitos, CA .
85.
Zhu, D. J., and Latombe, J. C. 1991. New heuristic algorithms for efficient hierarchical path planning . IEEE Transactions on Robotics and Automation7(1): 9–20 .
