On the Topology of Discrete Strategies

Abstract

This paper explores a topological perspective of planning in the presence of uncertainty focusing on tasks specified by goal states in discrete spaces. The paper introduces 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 concepts of reachability and controllability in other disciplines. The major nouns in this language are topological spaces. Three key theorems (numbered 1, 11, 20 in the paper) illustrate the sentences in this language: (a) Goal Attainability: 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. The paper contains a number of additional results required as stepping stones, along with many examples. The paper provides algorithms for computing the key structures described.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Dec 01, 2009
Accession Number
ADA543617

Entities

People

  • Michael Erdmann

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Autonomy
  • Materials and Manufacturing Processes
  • Sensors

DTIC Thesaurus Topics

  • Algebraic Topology
  • Algorithms
  • Autonomous Systems
  • Computer Languages
  • Computer Science
  • Coordinate Systems
  • Geometry
  • Language
  • Markov Chains
  • Motion Planning
  • Notation
  • Probability
  • Robotics
  • Standards
  • Topology
  • Two Dimensional
  • Uncertainty

Readers

  • Control Systems Engineering.
  • Graph Algorithms and Convex Optimization.
  • Systems Analysis and Design

Technology Areas

  • Space
  • Space - Spacecraft Maneuvers