Probabilistic Go Theories

Austin Parker, Fusun Yaman, Dana Nau, VS Subrahmanian

There are numerous cases where we need to reason about vehicles whose intentions and itineraries are not known in advance to us. For example, Coast Guard agents tracking boats don't always know where they are headed. Likewise, in drug enforcement applications, it is not always clear where drug-carrying airplanes (which do often show up on radar) are headed, and how legitimate planes with an approved flight manifest can avoid them. Likewise, traffic planners may want to understand how many vehicles will be on a given road at a given time. Past work on reasoning about vehicles (such as the "logic of motion" by Yaman et. al.) only deals with vehicles whose plans are known in advance and don't capture such situations. In this paper, we develop a formal probabilistic extension of their work and show that it captures both vehicles whose itineraries are known, and those whose itineraries are not known. We show how to correctly answer certain queries against a set of statements about such vehicles. A prototype implementation shows our system to work efficiently in practice.