TL;DR
This paper introduces Livingstone, a kernel for reactive, self-configuring autonomous systems. It tackles the challenge of building robust spacecraft that can autonomously reconfigure themselves in response to failures, using a unified model for various diagnostic and control tasks. This approach promises significant progress towards the long-held vision of model-based reasoning for complex engineering systems.
What Problem Does This Paper Address?
NASA's ambitious goal of establishing a "virtual presence" in space with intelligent probes presents a significant AI challenge. These probes must operate autonomously for years in harsh environments, requiring them to radically reconfigure themselves in response to failures. Furthermore, the need for rapid deployment and low cost necessitates a component-based approach to software development, where systems can be "plugged together" quickly. Crucially, the vast number of potential failure scenarios means that pre-programmed responses are infeasible. Instead, spacecraft must reactively reason about the consequences of their reconfiguration options. This paper addresses the need for a system that can achieve this reactive, model-based self-configuration, unifying deduction and reactivity in a single framework.
Methods
The core of this work is the Livingstone kernel, which implements a model-based reactive configuration manager. Key methodological contributions include:
- Unified Deduction and Reactivity: Livingstone achieves reactivity by performing significant deduction within the sense/response loop. This is accomplished by leveraging experience with propositional conflict-based diagnosis algorithms and framing the configuration manager as a propositional feedback controller.
- Novel Modeling Formalism: Moving away from traditional first-order logic, Livingstone uses a formalism that couples transition system models (common in concurrent reactive languages) with qualitative representations from model-based reasoning. This allows for broad coverage of hybrid hardware/software systems.
- Single Model, Single Algorithm: A central goal is to use a single model to support diverse engineering tasks. Livingstone automates tasks like tracking goals, confirming modes, reconfiguring hardware, detecting anomalies, isolating faults, diagnosis, fault recovery, and safing using one model and one core algorithm.
- Synchronous Transition Systems: The system models components as synchronous transition systems. This abstraction simplifies reasoning by assuming that each component performs a state transition simultaneously, even if the underlying hardware interleaves operations.
- Conflict-Directed Best-First Search (CBFS): Both mode identification (MI) and mode reconfiguration (MR) are cast as combinatorial optimization problems. CBFS is used to efficiently solve these problems by focusing the search on likely trajectories and optimal control actions, using conflicts to prune infeasible solutions.
Datasets
Not discussed in the paper. The paper focuses on a simulated spacecraft (Newmaap) and combinational circuits for testing.
Key Insights and Ideas
- Bridging the Deduction-Reactivity Gap: The paper demonstrates a successful unification of deductive reasoning (model-based diagnosis) with reactive control, a long-standing challenge in AI.
- Qualitative Models for Robustness: Using qualitative representations for system behaviors makes the models more robust to changes in underlying details, which is crucial for long-duration space missions.
- The Power of Conflict-Directed Search: CBFS significantly focuses the search space for complex optimization problems, making reactive inference feasible even for large, intricate systems. This is a key enabler for real-time autonomy.
- Synchrony as a Practical Abstraction: While components might operate asynchronously, modeling them as synchronous simplifies reasoning and inference, provided the abstraction is valid (i.e., different interleavings produce the same final result).
Key Results
- NewMaap Spacecraft Demonstration: Livingstone, integrated with HSTS and RAPS, was successfully demonstrated on the simulated NewMaap spacecraft. It navigated a complex scenario, recovering from multiple failures during a Saturn orbit insertion.
- Efficiency of CBFS: The experiments show that CBFS dramatically focuses the search. For the Newmaap scenarios, the number of solutions checked was significantly reduced, and the processing times were on the order of seconds on a Sparc 5.
- Combinational Circuit Testing: MI was tested on ten combinational circuits, demonstrating comparable results to ATMS-based implementations without using ATMS, highlighting the efficiency of the propositional approach.
- Selection for Deep Space 1: The success of this work led to Livingstone, HSTS, and RAPS being selected as the core autonomy architecture for NASA's Deep Space 1 mission, the first flight of the New Millennium program.
Limitations and Future Work
- Estimating Transition Probabilities: The paper notes that estimating the probability of transitions is difficult and requires further research.
- Completeness of Characterizations: The paper acknowledges that the state-formula characterizations of $S_{i+1}$ and $M_i$ are sound but potentially incomplete, meaning they might not capture all possible states or actions. Generating complete characterizations can be computationally expensive.
- Partial LTMS: Initial experiments with a partial LTMS showed an order of magnitude speed-up, suggesting that further exploration of such techniques could enhance performance.
- Bioreactor Application: Livingstone is being applied to the autonomous control of a Bioreactor, with final results still forthcoming. This represents ongoing work and potential future applications.
Summary updated