Symbolic Behavior Recognition

Abstract

It is important for robots to model other robots’ unobserved plans, goals and behaviors, based on their observable actions. This process of modeling others based on observations is known as behavior- or plan-recognition. Behavior-recognition algorithms work by first matching observed actions to a template model (called the plan- or behavior-library), and then propagating the implications of matching actions to determine possible hypotheses that explain the observed behavior.
However, classic plan recognition algorithms are ill-suited to modeling robots in state-of-the-art applications: (i) they assume that only a single atomic feature (i.e., the action of the observed robot) is observable at any given point; and (ii) they assume that all such actions are always observable (i.e., the observer never loses an observation). As a result, existing behavior-recognition algorithms are often
inefficient, and may fail catastrophically in face of lossy observation streams.
This thesis presents a set of behavior-recognition algorithms that are specifically suited for modeling behavior-based robots. First, the algorithms use a decision-tree structure to efficiently match complex (multi-feature) observations to behaviors, reducing the run-time complexity of the observation-matching phase from O(F L) to O(F + L) in the worst case. Second, the algorithms are able
to handle lossy observations gracefully. The algorithms are correct (in that all matching hypotheses are produced), and symbolic (in that they do not provide an ordering over hypotheses). The algorithms’ run-time is linear in the size of the behavior-library. We provide an extensive empirical evaluation of the algorithms in scaled-up simulation experiments.

Date of Award	13 Oct 2004
Original language	English
Awarding Institution	Department of Computer Science and Artificial Intelligence
Supervisor	Gal Kaminka (Supervisor)