Title: Toward a language-theoretic foundation for planning and filtering,
Abstract: We address problems underlying the algorithmic question of automating the
co-design of robot hardware in tandem with its apposite software. Specifically,
we consider the impact that degradations of a robot's sensor and actuation
suites may have on the ability of that robot to complete its tasks. We
introduce a new formal structure that generalizes and consolidates a variety of
well-known structures including many forms of plans, planning problems, and
filters, into a single data structure called a procrustean graph, and give
these graph structures semantics in terms of ideas based in formal language
theory. We describe a collection of operations on procrustean graphs (both
semantics-preserving and semantics-mutating), and show how a family of
questions about the destructiveness of a change to the robot hardware can be
answered by applying these operations. We also highlight the connections
between this new approach and existing threads of research, including
combinatorial filtering, Erdmann's strategy complexes, and hybrid automata.