Introduction: The Wandering Interpretation Problem
In standard logical frameworks, describing an object's movement (e.g., "a plane travels from Paris to Boston") often fails to exclude unintended behaviors. Without explicit constraints, logic allows for "wandering interpretations"—where the plane might take an unmentioned detour to Detroit before arriving at its destination. While existing "go-theories" handle positive entailment well (e.g., "Is the plane at location X?"), they struggle with negative entailment. Proving an object was not in a specific region is nearly impossible because the logic permits any theoretically possible path.
The Motion Closed World Assumption (MCWA)
To bridge this gap, this paper introduces the Motion Closed World Assumption (MCWA). This framework formalizes the intuition that if a theory does not require an object to be somewhere else, it should be assumed to stay on its prescribed path.
The core of MCWA lies in Coherent Models. An interpretation is considered coherent if:
- The object moves in a straight line between source and destination at a valid speed.
- The object remains at its destination until its next scheduled movement (the "Stay Put" rule).
A spatial literal is entailed via MCWA if it holds true in every coherent model of the theory. This allows systems to conclude, for instance, that a plane was not in Detroit if Detroit was not part of its coherent path.
Algorithmic Implementation
The authors translate go-theories into linear programming constraints involving start times, end times, and velocities. They developed two primary algorithms: CheckCoherentIn and CheckCoherentNotIn. These algorithms utilize "Entry-Exit" logic to identify time windows where an object enters and leaves a rectangular region, verifying if the object must be there or cannot be there.
While checking MCWA-entailment is theoretically co-NP complete, the authors note that real-world constraints—such as "spatially continuous orderings" where a destination must match the next origin—significantly prune the search space, making the problem tractable in practice.
Experimental Evaluation
The approach was evaluated using synthetic datasets and the "Planes" example. To test scalability, the authors generated theories with up to 1,000 go-atoms per object and multiple potential movement sequences.
As shown in Figure 3, the implementation (built in Matlab) remained highly responsive. Most queries executed in less than 0.3 seconds, and even at the 1,000-atom limit, processing times typically stayed under 1 second. This demonstrates that the MCWA framework is computationally feasible for dynamic tracking environments like air traffic control.
Conclusion and Future Work
The MCWA provides a robust logical foundation for negative spatial reasoning. Future research directions include extending the logic to complex non-rectangular polygons, handling 3D space, and optimizing for real-time dynamic updates as new movement data arrives.
Summary updated