This article describes a framework for qualitatively represent ing and reasoning about spatial configurations. The framework contains interval/region-based formalisms for describing dis tances, angles, and locations. These representations lead to the formulation of inference rules, as well as search-heuristics that enable the derivation of spatial relationships and paths among objects. The qualitative framework can be used in two principal ways: to formulate solutions to spatial configuration problems where exact geometric knowledge is not available, and to provide guidance for the application of quantitative configuration analysis and planning methods. The applications of the proposed framework are demonstrated through simula tion examples that involve inferring constrained instantaneous configurations as well as coupler curves for compliant mo tion planning and deriving collision-free paths for open-chain mechanisms moving among static obstacles.
Get full access to this article
View all access options for this article.
References
1.
Ananthanarayanan, S., Goldenberg, A.A., and Mylopoulos, J.1992. Introducing robotic common sense in real-time dexterous manipulation. Proceedings of the 1992 IEEE International Conference on Robotics and Automation, pp. 2776-2781.
2.
Barraquand, J., and Latombe, J.-C.1990. A Monte-Carlo algorithm for path planning with many degrees of freedom. Proceedings of the IEEE International Conference on Robotics and Automation, pp. 1712-1717.
3.
Blackwell, A.1988. Qualitative geometric reasoning using a partial distance ordering. In Gero, J. S., and Stanton, R. (eds.): Artificial Intelligence Developments and Applications. New York: Elsevier Science Publishers, pp. 217-229.
4.
Bobrow, D.G.1985. Qualitative Reasoning About Physical Systems. Cambridge, MA: The MIT Press.
5.
Bobrow, D.G.1993. Special volume on artificial intelligence in perspective . Artificial Intell. 59(1-2):5-20.
6.
Brady, M.1989. The problems of robotics. In Brady, M. (ed.): Robotics Science. System Development Foundation Benchmark Series. Cambridge, MA: The MIT Press, pp. 1-35.
7.
Brooks, R.A.1983. Solving the find-path problem by good representation of free space. IEEE Trans. Sys. Man Cybernet.13(3):190-197.
8.
Dague, P.1993 (August). Symbolic reasoning with relative orders of magnitude . Proceedings of IJCAI-93, pp. 1509-1514.
9.
Davis, E.1986. Representing and Acquiring Geographic Knowledge. London: Pitman Publishing.
10.
Faltings, B.1992. A symbolic approach to qualitative kinematics. Artificial Intell.56(2-3):139-170.
11.
Faltings, B., and Pu, P.1991. Applying means-ends analysis to spatial planning. Proceedings of the 1991 IEEE/RSJ International Workshop on Intelligent Robots and Systems (IROS '91), pp. 80-85.
12.
Faverjon, B., and Tournassoud, P.1987. A local based approach for path planning of manipulators with a high number of degrees of freedom. Proceedings of the 1987 IEEE International Conference on Robotics and Automation, pp. 1152-1159.
13.
Forbus, K.D., Nielsen, P., and Faltings, B.1987. Qualitative kinematics: A framework. Proceedings of the International Joint Conference on Artificial Intelligence , pp. 430-435.
14.
Glavina, B.1990. Solving findpath by combination of goal-directed and randomized search. Proceedings of the 1990 IEEE International Conference on Robotics and Automation, pp. 1718-1723.
15.
Hopcroft, J.E., Kearney, J.K., and Krafft, D.B.1991. A case study of flexible object manipulation. Int. J. Robot. Res.10(1):41-50.
16.
Hunt, K.H.1978. Kinematic Geometry of Mechanisms. Oxford Engineering Science Series. Oxford: Oxford University Press.
17.
Joskowicz, L., and Sacks, E.1991. Incremental configuration space construction for mechanism analysis. Proceedings of AAAI-91, pp. 888-893.
Kuipers, B., and Byun, Y.-T.1991. A robot exploration and mapping strategy based on a semantic hierarchy of spatial representations. Robot. Autonomous Sys.8:47-63.
20.
Latecki, L., and Rohrig, R.1993 (August). Orientation and qualitative angle for spatial reasoning. Proceedings of IJCAI-93, pp. 1544-1549.
Liu, J.1994. Qualitative spatial reasoning with applications to planar mechanism analysis and motion planning. PhD dissertation. McGill University, Department ofElectrical Engineering.
23.
Liu, J., and Daneshmend, L.K.1991a (April). Qualitative analysis of task kinematics for compliant motion planning. Proceedings of the 1991 IEEE International Conference on Robotics and Automation , pp. 1258-1265.
24.
Liu, J., and Daneshmend, L.K.1991b. Qualitative physics for robot task planning: Part II, kinematics of mechanical devices. Proceedings of the 1991 IEEE/RSJ International Workshop on Intelligent Robots and Systems (IROS '91).
25.
Lozano-Pérez, T.1983. Spatial planning: A configuration space approach. IEEE Trans. ComputersC-32(2):108-109.
26.
Lozano-Pérez, T.1987. A simple motion planning algorithm for general robot manipulators . IEEE J. Robot. Automation3(3):224-238.
27.
Lozano-Pérez, T., Jones, J.L., Mazer, E., O'Donnell, P.A., and Grimson, E.L.1988. Handey: A task-level robot system. In Bolles, R. C. (ed.): Robotics Research: The Fourth International Symposium. Cambridge, MA: The MIT Press, pp. 29-36.
28.
Mason, M.T.1981. Compliance and force control for computer controlled manipulators . IEEE Trans. Sys. Man Cybernet.11(6):418-432.
29.
Mavrovouniotis, M.L., and Stephanopoulos, G.1987. Reasoning with order of magnitude and approximate relations. Proceedings of AAAI-87. Cambridge, MA: AAAI Press/The MIT Press, pp. 626-630.
30.
Mazer, E., Pertin-Troccaz, J., and Lefevre, J.-M.1991. Act: A robot programming environment. Proceedings of the 1991 IEEE International Conference on Robotics and Automation , pp. 1427-1432.
31.
Metropolis, N., Rosenbluth, A., Rosenbluth, M., Teller, A., and Teller, E.1953. Equations of state calculations by fast computing machines. Journal ofChem. Phys.21:1087-1091.
32.
Oduńlaing, C., Sharir, M., and Yap, C.-K.1983. Retraction: A new approach to motion planning. Proceedings of the 15th FOCS, pp. 207-220.
33.
Peters, S.F., Hirai, S., Omata, T., and Sato, T.1991 (Aug. 24-30). Planning robot control parameter values with qualitative reasoning. Proceedings of IJCAI-91 .
34.
Raiman, O.1986. Order of magnitude reasoning. Proceedings of AAAI-86, pp. 100-104.
35.
Randell, D.1991. Analyzing the familiar: A logical representation of space and time. Proceedings of the Third International Workshop on Semantics of Time, Space, and Movement.
36.
Uicker, J., Denavit, J., and Hartenberg, R.1964. An iterative method for the displacement analysis of spatial mechanisms. J. Appl. Math. Trans. ASME.
37.
Wilson, R.H., and Latombe, J.-C.1992 (July). On the qualitative structure of a mechanical assembly . Proceedings of AAAI-92. Cambridge, MA: AAAI Press/The MIT Press , pp. 697-702.
