# Toward a language-theoretic foundation for planning and filtering

arXiv: https://arxiv.org/abs/1807.08856 · HTML: https://mlsanity.com/paper/1807.08856/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Jul 2018.

## Built on by (most cited first, 3 of 3)

- [A Mathematical Characterization of Minimally Sufficient Robot Brains](https://mlsanity.com/paper/2308.09041/) (2023)
- [Fundamental Limits for Sensor-Based Robot Control](https://mlsanity.com/paper/2202.00129/) (2022)
- [CODEI: Resource-Efficient Task-Driven Co-Design of Perception and Decision Making for Mobile Robots Applied to Autonomous Vehicles](https://mlsanity.com/paper/2503.10296/) (2025)

## Abstract (arXiv)

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.