On the Topology of Discrete Strategies

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 ho