Research Abstracts - 2007

Introduction

During human-robot collaborative tasks, it is useful for the robot, or agent, to understand what the human user is doing, and to anticipate what the user is likely to do in the future. The agent should gain this understanding based on observations of the user and contextual knowledge of the activity the user is trying to perform. To enable this, the agent has some set of observation capabilities, is given a priori a plan of the user and surrounding objects, and is also given the system's initial and goal states. The agent can make time-dependent observations of the system state. The purpose of this research is to best estimate which set of choices the user has made based on the sequence of observed states. As shown in Fig. 1, the output is given by a set of all possible trajectories that could have been taken to produce the observed state sequence.

Figure 1. The recognizer accepts a known plan and real-time observed states as input, and outputs all the possible plan trajectories that the user or surrounding objects have taken.

Qualitative State Plan Network

The qualitative state plan network combines concepts from qualitative state plans as described in [1] and temporal plan networks as described in [2]. A qualitative state plan is a temporally flexible plan [3], with activities that specify qualitative constraints on the state of the system. A qualitative state plan network encompasses all possible qualitative state plans for the system that can be determined a priori.

A qualitative state plan network specifies a network of possible evolutions of the system state over time. As shown in Fig. 2, a qualitative state plan network is diagrammatically illustrated by an acyclic directed graph.

Figure 2. In the graphical representation of a qualitative state plan network, discrete events are represented by nodes drawn as circles, and activities are represented by multi-dimensional constraint state regions. Choice events are noted by double circles, and resolution events are noted by circles with two cross-through lines.

The Recognizer

A constraint checking tree tracking algorithm has been developed for the recognizer. The algorithm recursively progresses the fringe of the tree of possible trajectories at every discrete time step and performs activity constraint and temporal constraint checking at each step. When an activity's goal region is reached while maintaining temporal consistency, the tree branches to possible new activities. If an activity's state or temporal constraints are unsatisfied, the trajectory branch containing said activity is destroyed rootward until a choice event branching. The progression continues until there exists no more observations. Figure 3 illustrates an example recognition progression.

Figure 3. The tree tracking algorithm recognizes all possible trajectories given the current observed state sequence at every time step. When an inconsistency is reached, the trajectory branch is destroyed.

Results

The recognizer algorithm has been run on toy problems and produces correct results. Current work is on demonstrating the capabilities of this recognizer on real-world human activities. This is still work in progress; results have not yet been captured. The scenario is a building task with multiple end states. For example, a human subject is given the task of building either one of two possible structures, as shown in Figure 4, which I call "bridge," and "boat," from two steel blocks and one wooden plank. Initially, all objects are outside of a certain goal region, marked by a yellow square on the ground. The person can build whichever structure he or she chooses. The human's and surrounding objects' states are captured by a motion capture system ViconIQ 2.5. Data extraction and algorithm testing is still in progress.

Figure 4. The initial state (left) of a simple building task, with two possible end states: "bridge" (center), or "boat" (right).

References:

[1] Thomas Léauté, "Coordinating Agile Systems through the Model-based Execution of Temporal Plans," S. M. Thesis, Massachusetts Institute of Technology, August 2005.

[2] Robert Effinger, "Optimal Temporal Planning at Reactive Time Scales via Dynamic Backtracking Branch and Bound," S.M. Thesis, Massachusetts Institute of Technology, September 2006.

[3] Rina Dechter, Itay Meiri & Judea Pearl. Temporal Constraint Networks. Artificial Intelligence Journal, 1991.