On the topological structure of configuration spaces
Tóm tắt
We investigate the topological structure of configuration spaces of kinematic scenes, i.e., mechanisms consisting of rigid, independently movable objects in a 2- or 3-dimensional environment. We demonstrate the practical importance of the considered questions by giving a motivation from the viewpoint of qualitative reasoning. Especially, we investigate topological invariants of the configuration space as a means for characterizing and classifying mechanisms. This paper focuses on the topological invariants homeomorphy, homotopy equivalence and fundamental group. We describe a procedure for computing a finite representation of the fundamental group of a given kinematic scene, and investigate its possible structure and complexity for simple classes of scenes. We show that for any finitely represented group one can construct a kinematic scene in the plane such that the fundamental group of its configuration space is isomorphic to the given group. This construction shows the undecidability of a variety of problems concerning the topological structure of configuration spaces, and reveals that the considered invariants in their general form do not provide an algorithmic method for characterizing or classifying arbitrary mechanisms.
Tài liệu tham khảo
D.G. Bobrow and P.J. Hayes, Special volume on qualitative reasoning about physical systems, Artificial Intelligence 24(1–3) (1984).
L. Joskowicz and E.P. Sacks, Computational kinematics, Artificial Intelligence 51(1–3) (1991).
K.D. Forbus, P. Nielsen and B. Faltings, Qualitative spatial reasoning, Artificial Intelligence 51(1–3) (1991).
L. Joskowicz, Simplification and abstraction of kinematic behaviours, in: Proceedings of IJCAI (1989) pp. 1337–1342.
B. Faltings, E. Baechler and J. Primus, Reasoning about kinematic topology, in: Proceedings of IJCAI (1989) pp. 1331–1336.
J.T. Schwartz and M. Sharir, Algorithmic motion planning in robotics, in: Handbook of Theoretical Computer Science, Vol. A, ed. Jan van Leeuwen (Elsevier, 1990).
C.-K. Yap, Algorithmic motion planning, in: Algorithmic and Geometric Aspects of Robotics, Vol. 1, eds. J.T. Schwartz and C.-K. Yap (Lawrence Erlbaum Associates, 1987).
J. Sellen, Durch kinematische Szenen erzeugte topologische Räume, Technical Report 05/1992 of Sonderforschungsbereich 124, Saarbrücken/Kaiserslautern (1992).
A.A. Markov, The problem of homeomorphy, in: Proceedings of International Congress of Mathematicians (1958) pp. 300–306.
W. Boone, W. Haken and V. Poénaru, On recursively unsolvable problems in topology and their classification, in: Contributions to Mathematical Logic, eds. H. Schmidt, K. Schutte and H.-J. Thiele (North-Holland, 1968) pp. 37–74.
M.O. Rabin, Recursive unsolvability of group theoretic problems, Annals of Mathematics 67(1) (1958) 172–194.
R.C. Lyndon and P.E. Schupp, Combinatorial Group Theory (Springer, New York, Heidelberg, Berlin, 1980).
H. Hironaka, Triangulations of algebraic sets, in: Proceedings, Symposia in Pure Math, Vol. 29 (American Mathematical Society, 1975) pp. 165–185.