New Metrics and Algorithms for Stochastic Goal Recognition Design Problems

New Metrics and Algorithms for Stochastic Goal Recognition Design Problems

Christabel Wayllace, Ping Hou, William Yeoh

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence
Main track. Pages 4455-4462. https://doi.org/10.24963/ijcai.2017/622

Goal Recognition Design (GRD) problems involve identifying the best ways to modify the underlying environment that agents operate in, typically by making a subset of feasible actions infeasible, in such a way that agents are forced to reveal their goals as early as possible. The Stochastic GRD (S-GRD) model is an important extension that introduced stochasticity to the outcome of agent actions. Unfortunately, the worst-case distinctiveness (wcd) metric proposed for S-GRDs has a formal definition that is inconsistent with its intuitive definition, which is the maximal number of actions an agent can take, in the expectation, before its goal is revealed. In this paper, we make the following contributions: (1) We propose a new wcd metric, called all-goals wcd (wcdag), that remedies this inconsistency; (2) We introduce a new metric, called expected-case distinctiveness (ecd), that weighs the possible goals based on their importance; (3) We provide theoretical results comparing these different metrics as well as the complexity of computing them optimally; and (4) We describe new efficient algorithms to compute the wcdag and ecd values.
Keywords:
Planning and Scheduling: Activity and Plan Recognition
Planning and Scheduling: Markov Decisions Processes