In this paper we explore a topological perspective of planning in the presence of uncertainty, focusing on tasks specified by goal states in discrete spaces. We introduce strategy complexes. A strategy complex is the collection of all plans for attaining all goals in a given space. Plans are like jigsaw pieces. Understanding how the pieces fit together in a strategy complex reveals structure. That structure characterizes the inherent capabilities of an uncertain system. By adjusting the jigsaw pieces in a design loop, one can build systems with desired competencies. The paper draws on representations from combinatorial topology, Markov chains, and polyhedral cones. Triangulating between these three perspectives produces a topological language for describing concisely the capabilities of uncertain systems, analogous to the concepts of reachability and controllability in other disciplines. The major nouns in this language are topological spaces. Three key theorems illustrate the sentences in this language. (a) Goal attain-ability: There exists a strategy for attaining a particular goal from anywhere in a system if and only if the strategy complex of a slightly modified system is homotopic to a sphere. (b) Full controllability : A system can move between any two states despite control uncertainty precisely when its strategy complex is homotopic to a sphere of dimension two less than the number of states. (c) General structure: Any system’s strategy complex is homotopic to the product of a spherical part, modeling full controllability on subspaces, and a general part, modeling adversarial capabilities. This paper contains a number of additional results required as stepping stones, along with many examples. We provide algorithms for computing the key structures described. Finally, we show that some interesting questions are hard. For instance, it is NP-complete to determine the most precisely attainable goal of a system with perfect sensing, but uncertain control.
Aho, A.V., Hopcroft, J.E. and Ullman, J.D. ( 1974). The Design and Analysis of Computer Algorithms . Reading, MA, Addison-Wesley .
2.
Akella, S. and Mason, M.T. ( 1992). Posing polygonal objects in the plane by pushing . Proceedings IEEE International Conference on Robotics and Automation , pp. 2255-2262.
3.
Barr, A., Cohen, P. and Feigenbaum, E., eds ( 1981-1989). The Handbook of Artificial Intelligence . Los Altos, CA, William Kaufmann .
4.
Bellman, R. ( 1957). Dynamic Programming. Princeton, NJ , Princeton University Press.
Björner, A. ( 1995). Topological methods. Handbook of Combinatorics , Vol. II, Graham, R., Grötschel, M. and Lovász, L. (eds). Amsterdam, North-Holland, pp. 1819-1872.
7.
Björner, A. and Tancer, M. ( 2009). Note: Combinatorial Alexander Duality-A Short and Elementary Proof. Discrete and Computational Geometry , 42(4): 586-593.
8.
Björner, A. and Welker, V. ( 1999). Complexes of directed graphs. SIAM Journal of Discrete Mathematics, 12(4): 413-424.
9.
Brady, M., Hollerbach, J.M., Johnson, T., Lozano-Pérez, T. and Mason, M.T. ( 1982). Robot Motion: Planning and Control. Cambridge, MA, MIT Press.
10.
Brost, R.C. ( 1988). Automatic grasp planning in the presence of uncertainty . The International Journal of Robotics Research, 7(1): 3-17.
11.
Brost, R.C. and Goldberg, K.Y. ( 1996). A complete algorithm for designing planar fixtures using modular components. IEEE Transactions on Robotics and Automation , 12(1): 31- 46.
12.
Canny, J.F. ( 1988). The Complexity of Robot Motion Planning. Cambridge, MA, MIT Press.
13.
de Silva, V. and Ghrist, R. ( 2006). Coordinate-free coverage in sensor networks with controlled boundaries via homology. The International Journal of Robotics Research, 25(12): 1205-1222.
Donald, B.R. ( 1989). Error Detection and Recovery in Robotics (Lecture Notes in Computer Science, Vol. 336). Berlin, Springer.
16.
Donald, B.R. ( 1990). Planning multi-step error detection and recovery strategies . The International Journal of Robotics Research , 9(1): 3-60.
17.
Donald, B.R. ( 1995). On information invariants in robotics. Artificial Intelligence, 72: 217-304.
18.
Donald, B.R. and Jennings, J. ( 1992). Constructive recognizability for task-directed robot programming. Robotics and Autonomous Systems, 9: 41-74.
19.
Donald, B.R., Jennings, J. and Rus, D. ( 1993). Towards a theory of information invariants for cooperating autonomous mobile robots. Sixth International Symposium onRobotics Research, pp. 29-48.
20.
Dugundji, J. ( 1966). Topology. Boston, MA,Allyn and Bacon.
21.
Durrant-Whyte, H.F. ( 1988). Sensor models and multisensor integration. The International Journal of Robotics Research, 7(6): 97-113.
22.
Erdmann, M.A. ( 1986). Using backprojections for fine motion planning with uncertainty . The International Journal of Robotics Research, 5(1): 19-45.
23.
Erdmann, M.A. ( 1989). On Probabilistic Strategies for Robot Tasks. PhD thesis (Technical Report AI-TR-1155), EECS, MIT, Cambridge, MA.
24.
Erdmann, M.A. ( 1992). Randomization in robot tasks. The International Journal of Robotics Research, 11(5): 399- 436.
25.
Erdmann, M.A. ( 1993). Randomization for robot tasks: Using dynamic programming in the space of knowledge states. Algorithmica, 10(2-4): 248-291.
26.
Erdmann, M.A. ( 1995). Understanding action and sensing by designing action-based sensors. The International Journal of Robotics Research, 14(5): 483-509.
27.
Erdmann, M.A. ( 1998). An exploration of nonprehensile two-palm manipulation . The International Journal of Robotics Research, 17(5): 485-503.
28.
Erdmann, M.A. ( 2008). On the topology of plans. Eighth International Workshop on the Algorithmic Foundations of Robotics, Guanajuato, Mexico, December 2008.
29.
Erdmann, M.A. and Mason, M.T. ( 1988). An exploration of sensorless manipulation. IEEE Journal of Robotics and Automation, 4(4): 369-379.
30.
Erdmann, M.A., Mason, M.T. and Vaněček, G., Jr (1993). Mechanical parts orienting: The case of a polyhedron on a table. Algorithmica, 10(2-4): 226-247.
31.
Farber, M. ( 2003). Topological complexity of motion planning. Discrete and Computational Geometry, 29(2): 211- 221.
32.
Feller, W. ( 1968). An Introduction to Probability Theory and Its Applications. Volume I (3rd edn). New York , John Wiley and Sons.
33.
Fox, A. and Hutchinson, S. ( 1995). Exploiting visual constraints in the synthesis of uncertainty-tolerant motion plans. IEEE Transactions on Robotics and Automation , 11(1): 56-71.
34.
Ghrist, R. and LaValle, S. ( 2006). Nonpositive curvature and Pareto-optimal coordination of robots. SIAM Journal of Control and Optimization, 45(5): 1697-1713.
35.
Ghrist, R., O’Kane, J. and LaValle, S. ( 2005). Computing Pareto optimal coordinations on roadmaps . The International Journal of Robotics Research, 24(11): 997-1010.
36.
Ghrist, R. and Peterson, V. ( 2007). The geometry and topology of reconfiguration. Advances in Applied Mathematics, 38: 302-323.
37.
Goldberg, K.Y. ( 1993). Orienting polygonal parts without sensors. Algorithmica, 10(2-4): 201-225.
38.
Guilamo, L., Tovar, B. and LaValle, S. ( 2004). Pursuit-evasion in an unknown environment using gap navigation trees. Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 3456-3462.
39.
Hatcher, A. ( 2002). Algebraic Topology. Cambridge , Cambridge University Press.
40.
Herlihy, M. and Shavit, N. ( 1999). The topological structure of asynchronous computability . Journal of the ACM, 46(6): 858-923.
41.
Hopcroft, J. and Wilfong, G. ( 1986). Motion of objects in contact. The International Journal of Robotics Research, 4(4): 32-46.
42.
Hsiao, K., Kaelbling, L. and Lozano-Pérez, T. ( 2007). Grasping POMDPs. Proceedings IEEE International Conference on Robotics and Automation, pp. 4685-4692.
43.
Hsiao, K., Kaelbling, L., and Lozano-Pérez, T. (2008). Robust belief-based execution of manipulation programs. Eighth International Workshop on the Algorithmic Foundations of Robotics, Guanajuato , Mexico, December 2008.
44.
Hultman, A. ( 2004). Directed subgraph complexes. Electronic Journal of Combinatorics, 11(1): R75.
45.
Jia, Y.-B. and Erdmann, M.A. ( 1996). Geometric sensing of known planar shapes. The International Journal of Robotics Research, 15(4): 365-392.
46.
Jia, Y.-B. and Erdmann, M.A. ( 1999). Pose and motion from contact. The International Journal of Robotics Research, 18(5): 466-490.
47.
Jonsson, J. ( 2005). Simplicial Complexes of Graphs. PhD thesis, Department of Mathematics, KTH, Stockholm , Sweden.
48.
Karlin, S. and Taylor, H.M. ( 1981). A Second Course in Stochastic Processes. New York, Academic Press.
49.
Karp, R.M. ( 1972). Reducibility among combinatorial problems. Complexity of Computer Computations, Miller, R. E. and Thatcher, J. W. (eds). New York, Plenum Press, pp. 85- 103.
50.
Kelley, J.L. ( 1955). General Topology. New York , Springer.
51.
Kerr, J. and Roth, B. ( 1986). Analysis of multifingered hands. The International Journal of Robotics Research, 4(4): 3-17.
52.
Koditschek, D.E. ( 1994). An approach to autonomous robot assembly. Robotica, 12(2): 137-155.
LaValle, S.M. ( 2006). Planning Algorithms. New York , Cambridge University Press.
55.
Lazanas, A. and Latombe, J.-C. ( 1995). Motion planning with uncertainty: A landmark approach . Artificial Intelligence, 76(1-2): 285-317.
56.
Lozano-Pérez, T., Mason, M. and Taylor, R. ( 1984). Automatic synthesis of fine-motion strategies for robots . The International Journal of Robotics Research , 3(1): 3-24.
57.
Mackenzie, D. ( 2003). ROBOTICS: Topologists and Roboticists Explore an ‘Inchoate World’. Science, 301(5634): 756.
58.
Madani, O., Hanks, S. and Condon, A. ( 2003). On the undecidability of probabilistic planning and related stochastic optimization problems. Artificial Intelligence , 147(1-2): 5-34.
59.
Mason, M.T. ( 1984). Automatic planning of fine motions: Correctness and completeness . Proceedings IEEE International Conference on Robotics and Automation, pp. 492- 503.
60.
Mason, M.T. ( 1986). Mechanics and planning of manipulator pushing operations . The International Journal of Robotics Research , 5(3): 53-71.
61.
Munkres, J.R. ( 1984). Elements of Algebraic Topology. Menlo Park, CA, Addison-Wesley.
62.
Nevins, J., Whitney, D., Drake, S., Killoran, D., Lynch, M., Seltzer, D., Simunovic, S., Spencer, R., Watson, P. and Woodin, A. ( 1975). Exploratory Research in Industrial Modular Assembly. Technical Report R-921, The Charles Stark Draper Laboratory .
63.
Novikov, P.S. ( 1955). On the algorithmic unsolvability of the word problem in group theory. Trudy Mat. Inst. Steklov, 44: 1-143.
64.
Novikov, S.P. ( 1974). Appendix to: The problem of the algorithmic discrimination of the standard three-dimensional sphere, byI. A. Volodin, V. E. Kuznetsov, and A. T. Fomenko. Uspekhi Mat. Nauk, 29(5): 71-168.
65.
O’Kane, J.M. and LaValle, S.M. ( 2008). Comparing the power of robots. The International Journal of Robotics Research, 27(1): 5-23.
66.
Papadimitriou, C.H. and Steiglitz, K. ( 1982). Combinatorial Optimization: Algorithms and Complexity . Englewood Cliffs, NJ, Prentice-Hall .
67.
Papadimitriou, C.H. and Tsitsiklis, J.N. ( 1987). The complexity of Markov decision processes. Mathematics of Operations Research, 12(3): 441-450.
68.
Quillen, D. ( 1978). Homotopy properties of the poset of non-trivial p-subgroups of a group. Advances in Mathematics, 28: 101-128.
69.
Rotman, J.J. ( 1988). An Introduction to Algebraic Topology. New York, Springer.
70.
Smith, R.C. and Cheeseman, P. ( 1986). On the representation and estimation of spatial uncertainty . The International Journal of Robotics Research , 5(4): 56-68.
71.
Spanier, E.H. ( 1966). Algebraic Topology. San Francisco, CA, McGraw-Hill.
72.
Taylor, R.H., Mason, M.T., and Goldberg, K.Y. ( 1988). Sensor-based manipulation planning as a game with nature . Robotics Research, Vol. IV, Bolles, R. and Roth, B. (eds). Cambridge, MA, MIT Press, pp. 421-429.
73.
Tovar, B., Murrieta, R. and LaValle, S. ( 2007). Distance-optimal navigation in an unknown environment without sensing distances. IEEE Transactions on Robotics, 23(3): 506-518.
74.
Tovar, B., Yershova, A., O’Kane, J. and LaValle, S. ( 2005). Information spaces for mobile robots. Proceedings International Workshop on Robot Motion and Control .
75.
Wachs, M.L. ( 2004). Poset Topology: Tools and Applications. Technical Report, IAS/Park City Mathematics Institute.
76.
Weinberger, S. ( 2004). Computers, Rigidity, and Moduli: The Large-Scale Fractal Geometry of Riemannian Moduli Space. (M. B. Porter Lectures). Princeton, NJ, Princeton University Press .
77.
Whitney, D.E. ( 1982). Quasi-static assembly of compliantly supported rigid parts. Journal of Dynamic Systems, Measurement, and Control , 104(1): 65-77.
