TL;DR
This paper tackles the challenge of accurately tracking the state of autonomous systems in real-time, even with limited memory. They introduce a method to synthesize "single-state trackable" estimators that guarantee no dead-ends, meaning the estimated state never diverges irrecoverably from the true system state. This is achieved by framing the problem as a simulation relation between automata and leveraging SMT solvers for synthesis.
What Problem Does This Paper Address?
Autonomous systems, from robots to industrial controllers, rely heavily on knowing their current state to make informed decisions. When systems are complex and their internal states aren't directly observable (partially observable systems), estimating the state becomes difficult. The number of possible states can explode, overwhelming memory and computational resources, especially in embedded systems. Traditional approaches might try to keep track of a limited set of "best guess" states, but this can lead to "dead-ends" where the estimated trajectory diverges so much from the true system trajectory that it becomes impossible to recover. This paper addresses the need for estimators that are not only efficient (using minimal memory by tracking only one state at a time) but also guaranteed to avoid these dead-ends, ensuring a reliable input for the system's decision-making.
Methods
The core of this work lies in defining and synthesizing "single-state trackable" estimators. A system is single-state trackable if a dead-end-free estimator can be constructed for it. The authors first formalize this property by showing it's equivalent to a simulation relation between the system's automaton and the estimator's automaton. This simulation relation, which captures the idea that the estimator's state "follows" the system's state without diverging, is key.
To synthesize these estimators, they translate the problem into a Satisfiability Modulo Theories (SMT) problem. They define Boolean variables to represent the states and transitions of the estimator, as well as the simulation relation itself. Constraints are then formulated to enforce:
- Estimator structure: The estimator must be a deterministic Moore machine.
- Reachability: The estimator's states must be reachable from its initial state.
- Simulation relation: The core constraints ensure that the estimator's states simulate the system's states, preventing dead-ends.
- Correctness (optional): They also introduce mechanisms to incorporate correctness criteria, either as hard constraints (e.g., ensuring specific fault states are always estimated correctly) or as a cost function to minimize estimation errors.
The SMT solver MONOSAT is used to find a solution that satisfies these constraints, effectively synthesizing a dead-end-free estimator.
Datasets
Not discussed in the paper. The authors use benchmark systems from existing literature (valve controller, valve driver, baggage transfer) and generate random systems for evaluation.
Key Insights and Ideas
- Simulation as a Dead-End Prevention Mechanism: The paper elegantly connects the abstract concept of avoiding dead-ends in estimation to the well-established formal verification concept of simulation relations between automata. This provides a powerful theoretical foundation.
- SMT for Synthesis: Framing the synthesis of dead-end-free estimators as an SMT problem is a practical and scalable approach, allowing for the integration of complex correctness criteria.
- Trackability is about Estimator Existence: The definition of single-state trackability hinges on the existence of a dead-end-free estimator, not necessarily finding the "best" one initially.
- Correctness as a Tunable Property: The paper moves beyond just avoiding dead-ends to offer ways to define and synthesize estimators that are "more correct" based on user-defined criteria, either through hard constraints or cost minimization.
Key Results
The paper demonstrates that the TRACKABILITY problem is in NP. Their SMT-based approach successfully synthesizes dead-end-free estimators for various benchmark systems. Experiments show that their encoding scales with the number of system states, with computation time growing logarithmically. They also show that incorporating correctness criteria doesn't drastically increase computation time in their experiments.
Limitations and Future Work
- NP-Completeness: While the TRACKABILITY problem is shown to be in NP, further investigation into NP-completeness with and without correctness constraints is suggested.
- Scalability with Correctness: The impact of complex correctness criteria on solving time needs further assessment.
- Extensions: Future work includes exploring delayed estimation, using a bounded number of memorized states, and symbolic representation of estimators with preferences. These extensions aim to apply the approach to a wider range of real-world systems.
Summary updated