Abstract
This paper presents a novel approach to stream reasoning using Metric Temporal Logic (MTL) in environments characterized by incomplete or uncertain sensor data. By modeling logical formulas as progression graphs and implementing a "leaky" approximation algorithm, the proposed method enables autonomous systems to maintain real-time performance with quantifiable trade-offs between mathematical certainty and computational efficiency.
Introduction
In robotics and runtime verification, Metric Temporal Logic (MTL) is a standard for defining complex temporal constraints. For instance, a safety rule might require a robot to reach a charging station within a specific timeframe upon detecting a low battery. Traditional stream reasoning via "progression" involves rewriting formulas as new states arrive. However, this approach typically assumes complete state information—a luxury rarely available in real-world scenarios with noisy sensors. Furthermore, tracking all possible truth values leads to an exponential explosion in formula size, exceeding the memory limits of embedded systems.
Methodology: Stochastic Progression and Graphs
To address these challenges, the authors introduce a stochastic extension to MTL progression. The world is modeled as a probability distribution over possible states rather than a single deterministic state.
Progression Graphs
The reasoning process is formalized as a directed graph. In this graph, vertices represent MTL formulas, and edges denote transitions triggered by observed states. Probability mass flows through this graph as the stream progresses.
The PPROGRESS Algorithm
The core contribution is the PPROGRESS algorithm, an approximate procedure designed to manage graph size through two primary parameters:
- MAX_NODES: Constrains the total number of tracked formulas.
- MAX_TTL (Time-To-Live): Prunes formulas that have not been updated within a specified window.
When a node is deleted to conserve memory, its associated probability mass is "leaked." This "leaky probability" serves as a quantifiable metric for the uncertainty introduced by the approximation.
Experimental Evaluation
The approach was evaluated using a synthetic stream generator simulating robotics scenarios. The test formula followed a response pattern: $\square (\neg p \to \diamond_{[0,100]} \square_{[0,10]} p)$, requiring that a recovery state $p$ be reached and maintained after a condition $\neg p$. The input stream contained 20% unknown samples to simulate sensor uncertainty.
Performance and Efficiency
The empirical results highlight a significant improvement in both speed and memory usage when using the approximate procedure.
As shown in the table, setting MAX_NODES = 175 and MAX_TTL = 1 reduced the average task duration from 143.9 seconds to 89.1 seconds. Concurrently, the maximum size of the formula representation was reduced by nearly 83%, from 15,706 to 2,653 units. Crucially, the authors observed that with MAX_NODES at 175, the leaked probability mass remained below 1%, ensuring high accuracy despite the significant performance gains.
Discussion and Key Insights
A central insight of this work is the conceptualization of logic as a flow problem. By treating reasoning as the movement of probability mass, the authors transform a discrete logic problem into a continuous tracking task. This allows for "graceful degradation": instead of failing when resources are exhausted, the system provides a probabilistic answer (e.g., "99% True"), which is often sufficient for practical decision-making.
Interestingly, higher uncertainty in the input stream can lead to faster falsification of formulas, potentially reducing the number of active hypotheses the system must track.
Conclusion and Future Work
While the current model assumes a known probability distribution for states, future research will focus on learning these probabilities from observations. Additionally, the authors aim to automate the tuning of parameters like MAX_NODES to minimize leakage dynamically. Integration with Answer Set Programming (ASP) is also planned to incorporate complex spatial reasoning into the temporal framework.
Summary updated