Name: Brandon Rozek
Advisor: Selmer Bringsjord
Title: Towards Automated Planning and Goal Recognition under Qualitative Uncertainty
Abstract: Humans and automated agents encounter a wide range of epistemic uncertainty when it comes to planning. Sometimes, an agent has access to probabilities concerning their initial state and the effects of their actions. Other times, the agent only knows that they are within a collection of possible situations or states. The intermediate case, where an agent can compare the relative qualitative likelihood of states or effects, is often under-investigated. In this thesis, we examine computational techniques for finding and recognizing the goals of agents under qualitative uncertainty. A state is a collection of predicates, each of which is true, false, or unknown. Prior research focuses on when an agent is able to compare the relative likelihood of such states, but humans often instead focus on individual predicates. This is common, for example, when assessing evidence during intelligence gathering or when making judicial decisions. To better handle this distinction, we extend the ideas stemming from Chisholm's epistemological theory and prior work on cognitive likelihoods to present our new framework QUGAF. This framework introduces qualitative levels of belief about predicates and presents a sound compilation to classical STRIPS.
In addition to finding plans, we investigate recognizing the goals of other agents. We revisit goal recognition in the context of qualitative possibilistic planning where agents are able to compare which initial state and action effects are more surprising than another. Assuming the agent does not compromise their goal, our algorithm filters out hypotheses in which the observed action sequence is incompatible with necessity-optimal behavior. We achieve this by introducing a novel compilation that casts the recognition problem as a qualitative possibilistic planning problem and formally prove its soundness. Our goal recognition approach relies on having an efficient algorithm for computing necessity-optimal plans. We conclude our investigation by presenting a new algorithm that is inspired by recent techniques from conformant planning. This new algorithm generates candidate plans from a classical instance where a single most-likely scenario is considered. Then, if not at the highest necessity, we find a counterexample. We use this counterexample to further refine our classical instance. We prove that this approach leads to finding a necessity-optimal plan and our experiments demonstrate that this approach outperforms the simpler baseline of iteratively finding a gamma-acceptable plan.
