A Motion Closed World Asumption

Fusun Yaman, Dana S. Nau, V. S. SubrahmanianIJCAI 2005

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.

Figure 1: Visualization of go-theories and flight paths between cities, illustrating the "Planes" example.

The core of MCWA lies in Coherent Models. An interpretation is considered coherent if:

  1. The object moves in a straight line between source and destination at a valid speed.
  2. 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.

Figure 3: Query execution time (in seconds) relative to the number of atoms per object for different query types.

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

BibTeX
@inproceedings{yaman2005motion,
  author = {Fusun Yaman and Dana S. Nau and V. S. Subrahmanian},
  title = {{A Motion Closed World Asumption}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2005},
}
Figure