A divide-and-merge approach is introduced for automatic generation of high-level, discrete contact state space, represented as contact state graphs, between two contacting polyhedral solids from their geometric models. Based on the fact that a contact state graph is the union of the subgraphs called a goal-contact relaxation (GCR) graph, the approach consists of algorithms (1) to generate a complete GCR graph automatically given the most constrained contact state in the GCR graph and (2) to merge GCR graphs automatically. The algorithms arplemented for cases in which the most constrained contact state in a GCR graph consists of up to three principal contacts. The ability to capture and represent contact state information effectively and efficiently is essential for robotic operations involving compliant motions, for simulation of contact motions, and for haptic interactions.
Get full access to this article
View all access options for this article.
References
1.
Avnaim, F., Boissonnat, J. D., and Faverjon, B. 1988. A practical exact motion planning algorithm for polygonal objects amidst polygonal obstacles . Proceedings of the IEEE International Conference on Robotics and Automation, April, pp. 1656–1661 .
2.
Brost, R. 1989. Computing metric and topological properties of configuration-space obstacles . Proceedings of the IEEE International Conference on Robotics and Automation, May, pp. 170–176 .
3.
Bruyninckx, H., and Schutter, J. 1998. Modeling and specification of compliant motions with two and three contact points . Proceedings of the IEEE International Conference on Robotics and Automation, pp. 1938–1943 .
4.
Buckley, S. J. 1989. Planning compliant motion strategies . International Journal of Robotics Research8(5): 28–44 .
5.
Dakin, G., and Popplestone, R. 1992. Simplified fine-motion planning in generalized contact space . IEEE International Symposium on Intelligent Control, pp. 281–287 .
6.
Desai, R. 1989. On fine motion in mechanical assembly in presence of uncertainty. Ph.D. thesis, University of Michigan.
7.
Desai, R., Xiao, J., and Volz, R. 1988. Contact formations and design constraints: A new basis for the automatic generation of robot programs. In NATO ARW: CAD Based Programming for Sensor Based Robots, ed. B. Ravani, 361–395. New York: Springer-Verlag .
8.
De Schutter, J., Bruyninckx, H., Dutré, S., De Geeter, J., Katupitiya, J., Demey, S., and Lefebvre, T. 1999. Estimating first order geometric parameters and monitoring contact transitions during force controlled compliant motion . International Journal of Robotics Research18(12): 1161-1184 –
9.
Donald, B. R. 1985. On motion planning with six degree of freedoms: Solving the intersection problems in configuration space . Proceedings of the IEEE International Conference on Robotics and Automation, pp. 536–541 .
10.
Hirukawa, H. 1997. On motion planning of polyhedra in contact. Algorithms for Robotic Motion and Manipulation: Workshop on the Algorithmic Foundations of Robotics, Boston: A. K. Peters , pp. 381–392.
11.
Hirukawa, H., Papegay, Y., and Matsui, T. 1994. A motion planning algorithm for convex polyhedra in contact under translation and rotation . Proceedings of the IEEE International Conference on Robotics and Automation, May, pp. 3020–3027 .
12.
Hocaoglu, C., and Sanderson, A. 1998. Evolutionary path planning using multiresolution path representation . Proceedings of the IEEE International Conferenceon Robotics and Automation, May, pp. 318–323 .
13.
Hopcroft, J., and Wilfong, G. 1986. Motion of objects in contact . International Journal of Robotics Research4(4): 32–46 .
14.
Inoue, H. 1974. Force feedback in precise assembly tasks. Report No. AIM-308, AI Lab, Massachusetts Institute of Technology .
15.
Ji, X. 2000. On generation of contact state space and contact motion planning. Ph.D. thesis, University of North Carolina at Charlotte.
16.
Ji, X., and Xiao, J. 2001a. On random sampling in contact configuration space. In New Directions in Algorithmic and Computational Robotics, ed. B. R. Donald, K. Lynch, and D. Rus. Boston: A. K. Peters .
17.
Ji, X., and Xiao, J. 2001b. Planning motion compliant to complex contact states . International Journal of Robotics Research, forthcoming.
18.
Johnston, D., and Xiao, J. 2000. On relating the disconnectedness of a topological contact state to the geometric properties of its constituent objects . Proceedings of the IEEE International Conference on Robotics and Automation, April, pp. 2284–2289 .
19.
Joskowicz, L., and Taylor, R. H. 1996. Interference-free insertion of a solid body into a cavity: An algorithm and a medical application . International Journal of Robotics Research15(3): 211–229 .
20.
Kang, S. C., et al. 1997. A compliant motion control for insertion of complex shaped objects using contact . Proceedings of the IEEE International Conferenceon Robotics and Automation, pp. 841–846 .
21.
Kavraki, L. E., and Latombe, J. C. 1998. Probabilistic roadmaps for robot path planning. In Practical Motion Planning in Robotics: Current Approaches and Future Directions, ed. Gupta, K., and del Pobil, A. P., New York: John Wiley & Sons , pp. 33–53.
22.
Kavraki, L. E., Svestka, P., Latombe, L. C., and Overmars, M. 1996. Probabilistic roadmaps for path planning in high-dimensional configuration spaces . IEEE Transactions on Robotics and Automation12: 566–580 .
23.
Latombe, J. C. 1991. Robot Motion Planning. Norwell, MA: Kluwer Academic .
24.
Lin, M. C., Manocha, D., Cohen, J., and Gottschalk, S. 1996. Collision detection: Algorithms and applications . Proceedings of the Workshop on Algorithmic Foundations of Robotics, March.
25.
Lozano-Pérez, T. 1983. Spatial planning: A configuration space approach . IEEE Transactions on ComputingC-32: 108–120 .
26.
Lozano-Pérez, T., Mason, M. T., and Taylor, R. H. 1984. Automatic synthesis of fine-motion strategies for robot . International Journal of Robotics Research3(1): 3–24 .
27.
Mason, M. T. 1982. Compliant motion. In Robot Motion: Planning and Control, ed. M. Brady et al., 305–322. Cambridge, MA: MIT Press .
28.
McCarragher, B. J. 1996. Task primitives for the discrete event modeling and control of 6-DOF assembly tasks . IEEE Transactions on Robotics and Automation12(2): 280–289 .
29.
Rosell, J., Basañez, L., and Suárez, R. 1997. Determining compliant motions for planar assembly tasks in the presence of friction . Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 946–951 .
30.
Sacks, E., and Bajaj, C. 1998. Sliced configuration spaces for curved planar bodies . International Journal of Robotics Research17(6): 639–651 .
31.
Shekhar, S., and Khatib, O. 1987. Force strategies in real-time fine motion assembly . Proceedings of the ASME Winter Annual Meeting, Boston, MA.
32.
Sturges, R. H., and Laowattana, S. 1995. Fine motion planning through constraint network analysis . IEEE International Conference on Assembly and Task Planning, Pittsburgh, PA, August, pp. 160–170 .
33.
Whitney, D. E. 1985. Historical perspective and state of the art in robot force control . Proceedings of the IEEE International Conference on Robotics and Automation, pp. 262–268 .
34.
Xiao, J. 1993. Automatic determination of topological contacts in the presence of sensing uncertainties . Proceedings of the IEEE International Conference on Robotics and Automation, Atlanta, May, pp. 65–70 .
35.
Xiao, J. 1997. Goal-contact relaxation graphs for contact-based fine motion planning . 1997 IEEE International Conference on Assembly and Task Planning, Marina Del Rey, CA, August, pp. 25–30 .
36.
Xiao, J., Michalewicz, Z., Zhang, L., and Trojanowski, K. 1997. Adaptive evolutionary planner/navigator for mobile robots . IEEE Transactions on Evolutionary Computation1: 18–28 .
37.
Xiao, J., and Volz, R. 1989. On replanning for assembly tasks using robots in the presence of uncertainties . Proceedings of the IEEE International Conference on Robotics and Automation, May, pp. 638–645 .
38.
Xiao, J., and Zhang, L. 1997. Contact constraint analysis and determination of geometrically valid contact formations from possible contact primitives . IEEE Transactions on Robotics and Automation13(3): 456–466 .
