With PQDT Open, you can read the full text of open access dissertations and theses free of charge.
About PQDT Open
Search
There are many applications where we wish to reason about spatio-temporal aspects of an agent’s behavior. This dissertation examines several facets of this type of reasoning.
First, given a model of past agent behavior, we wish to reason about the probability that an agent takes a given action at a certain time. Previous work combining temporal and probabilistic reasoning has made either independence or Markov assumptions. This work introduces Annotated Probabilistic Temporal (APT) logic which makes neither assumption. Statements in APT logic consist of rules of the form “Formula G becomes true with a probability [L,U] within T time units after formula F becomes true” and can be written by experts or extracted automatically from historical data. In this dissertation, we explore the problem of entailment, specifically what is the probability that an agent performs a given action at a certain time based on a set of such rules. We show this problem to be coNP-hard (in the complexity class coNP under some natural assumptions) and present several sets of linear constraints for solving this problem exactly. We then develop a sound, but incomplete fixpoint operator as a heuristic for such queries. This approach was implemented and tested on 23 different models automatically generated from several datasets. The operator quickly converged to produce tight probability bounds for the queries.
Second, agent behavior often results in “observations” at geospatial locations that imply the existence of other, unobserved, locations we wish to find (“partners”). In this dissertation, we formalize this notion with “geospatial abduction problems” (GAPs). GAPs try to infer a set of partner locations for a set of observations and a model representing the relationship between observations and partners for a given agent. This dissertation presents exact and approximate algorithms for solving GAPs as well as an implemented software package for addressing these problems called SCARE (the Spatio-Cultural Abductive Reasoning Engine). We tested SCARE on counter-insurgency data from Iraq, attempting to locate enemy weapons caches (partners) based on attacks (observations). On average, SCARE was able to locate weapons caches within 690 meters of actual sites. Additionally, we have considered a variant of the problem where the agent wishes to abduce regions that contain partner points. This problem is also NP-hard. To address this issue, we develop and implement a greedy approximation algorithm that finds small regions which contain partner points - on average containing 4 times as many partners as the overall area.
We then provide an adversarial extension to GAPs as follows: given a fixed set of observations, if an adversary has probabilistic knowledge of how an agent were to find a corresponding set of partners, he would place the partners in locations that minimize the expected number of partners found by the agent. In a complementary problem, the agent has probabilistic knowledge of how an adversary locates his partners and wishes to maximize the expected number partners found. We show that both of these problems are NP-hard and design schemes to find approximate solutions - often with theoretical guarantees. With our implementation, we demonstrate that these algorithms often obtain excellent solutions.
We also introduce a class of problems called geospatial optimization problems (GOPs). Here the agent has a set of actions that modify attributes of a geospatial region and he wishes to select a limited number of such actions (with respect to some budget) in a manner that either causes some goal to be true (goal-based GOPs) and/or maximizes a benefit function (benefit-maximizing GOPs). Additionally, there are certain combinations of actions that cannot be combined. We show NP-hardness (membership in NP under reasonable assumptions) as well as provide limits of approximation for these problems. We then develop sets of integer constraints that provide an exact solution and provide an approximation algorithm with a guarantee. (Abstract shortened by UMI.)
Advisor: | Subrahmanian, V.S. |
Commitee: | Antman, Stuart S., Khuller, Samir, Nau, Dana, Reggia, James A. |
School: | University of Maryland, College Park |
Department: | Computer Science |
School Location: | United States -- Maryland |
Source: | DAI-B 72/10, Dissertation Abstracts International |
Source Type: | DISSERTATION |
Subjects: | Computer science |
Keywords: | Abductive inference, Agent behavior, Geospatial reasoning, Logic programming, Probabilistic reasoning |
Publication Number: | 3461587 |
ISBN: | 978-1-124-75054-5 |