Introduction
In real-world tracking scenarios—ranging from maritime surveillance to urban traffic planning—we often lack a vehicle's exact itinerary. We might know a vessel's last seen position and its maximum speed, but its future path remains a mystery. Traditional "go theories" or "logics of motion" typically require a pre-defined plan, making them ill-suited for handling the inherent temporal indeterminacy and probabilistic nature of tracking unknown entities. This paper introduces Probabilistic Go (pgo) Theories, a formal framework designed to reason about moving objects when their intentions are unknown.
The Framework: Bridging Spatio-Temporal Logic and Probability
The core of the pgo framework lies in its ability to represent motion through probabilistic constraints. The authors define pgo atoms (e.g., "Vehicle $v$ is at location $L$ at time $t$ with probability $p$") and in atoms (describing the probability of a vehicle being within a specific convex region).
A "world" in this context is a valid trajectory that respects physical constraints like maximum velocity. An "interpretation" is then a probability distribution over these possible worlds. While checking the consistency of such theories initially appears to be an exponential problem due to the vast number of possible trajectories, the authors introduce a breakthrough optimization.
Computational Efficiency through Linear Programming
The transition from exponential to polynomial complexity is achieved by shifting focus from entire trajectories to Partial Path Probabilities (PLP). Instead of modeling every full path, the system tracks the probability of moving between adjacent points in a single time step. This ensures "flow" conservation—the probability entering a location must equal the probability leaving it—reducing the problem to a manageable linear programming (LP) task.
Further refinement is provided by the Alternate Linear Program (ALP), which prunes variables by ignoring time points not explicitly mentioned in the theory. This is particularly effective for sparse datasets where observations are infrequent.
Experimental Evaluation and Key Insights
The system was evaluated using synthetic theories on a $50 \times 50$ grid, simulating various dynamics (e.g., car vs. plane speeds) and data densities. As shown in Figure 1, the prototype (implemented in MATLAB) can process 100 time points in just a few seconds on standard hardware.
One of the most significant findings is the relationship between data density and performance. Counter-intuitively, as a theory becomes more "complete"—meaning we have more certain data points—the computation time can actually decrease. These data points act as "anchors" that significantly prune the search space of possible interpretations.
Figure 3 illustrates this "more data is faster" phenomenon: as the temporal density of the theory increases, the log-time for computation drops exponentially. This confirms that a more informed model is not only more accurate but also more efficient to solve.
Conclusion and Future Directions
The introduction of Probabilistic Go Theories proves that reasoning about uncertain motion is polynomially solvable, making real-time tracking and prediction feasible. While the current model assumes independent vehicle movement, future work aims to incorporate vehicle interactions (e.g., collision avoidance) and handle queries over time intervals rather than just discrete points. These advancements will further enhance the utility of pgo theories in complex, real-world surveillance and planning applications.
Summary updated