Abstract
This paper introduces a formal framework for updating beliefs in probabilistic spatio-temporal (PST) databases. Such systems track moving objects under uncertainty, often encountering conflicts between existing data and new observations. We analyze four revision strategies—subset selection, spatial, temporal, and probabilistic—against the AGM postulates for rational belief update. Our results demonstrate that while spatial and temporal revisions are either logically inconsistent or computationally intractable (coNP-hard), probabilistic revision via interval widening provides a mathematically sound, polynomial-time solution that satisfies all basic AGM axioms.
1. Introduction
Tracking systems for logistics and autonomous navigation rely on probabilistic spatio-temporal (PST) logic to manage uncertainty. A core challenge in these systems is "belief revision": how to rationally update the database when new sensor data contradicts existing records. For example, if a database expects a vehicle in one region but a sensor places it elsewhere, the system must resolve the conflict while maintaining physical realism (e.g., speed limits).
2. Problem Formulation
The AGM postulates (Alchourrón, Gärdenfors, and Makinson) define the requirements for a rational belief update. In PST databases, facts are represented as atoms: (Object, Region, Time, [Lower Bound, Upper Bound] Probability). To resolve inconsistencies, four "knobs" can be adjusted:
- Subsets: Removing conflicting historical facts.
- Space: Modifying the recorded region.
- Time: Adjusting the timestamp of events.
- Probability: Expanding the probability intervals to reduce certainty.
3. Methodology and the $K_{Beijing}$ Case Study
The authors employ Linear Programming (LP) to check consistency by modeling probability flow across possible worlds, constrained by reachability (speed) limits. To validate these methods, the paper uses a simulated environment called $K_{Beijing}$.
As shown in Figure 1, the $K_{Beijing}$ model tracks a delivery agent across ten regions. The spatial relationships between these regions define the reachability constraints that the revision algorithms must respect.
4. Analysis of Revision Strategies
The study evaluates the four strategies based on logical rationality and computational efficiency:
- Spatial Revision: This method is logically flawed, as it can fail to produce a consistent knowledge base even when one is theoretically possible.
- Temporal and Subset Revision: These strategies are logically sound but coNP-hard, making them impractical for large-scale or real-time tracking.
- Probabilistic Revision: This is the "sweet spot." By widening probability intervals (e.g., from $[0.7, 0.8]$ to $[0.6, 0.9]$), the system can accommodate new data efficiently.
5. Key Results
The primary contribution is the Probabilistic Revision Linear Program (PRLP). This algorithm finds the minimal expansion of probability intervals required to restore consistency. The authors prove that PRLP:
- Satisfies all six basic AGM postulates.
- Operates in polynomial time.
- Correctly handles reachability constraints.
6. Conclusion
Probabilistic revision offers a robust, computationally efficient method for maintaining consistency in PST databases. While current results are promising for bounded time horizons, future work will focus on high-velocity data streams ("the firehose problem") and extending the logic to handle complex structures like negations and disjunctions.
Summary updated