TR#456: Fast Constraint Propagation on Specialized Allen Networks and its Application to Action Recognition and Control

Claudio S. Pinhanez & Aaron F. Bobick

Submitted to AAAI'98

In this paper we present a specialization of Allen interval networks that permits the rapid determination as to whether a given interval must be occurring at the current point in time. The Allen-closure of the interval network is projected into a 3-valued (PAST,NOW,FUT) constraint network called a PNF-network. We show that the minimal domain of a PNF-network can be approximately computed in linear time by using arc-consistency. This computation is the key factor in the PNF propagation method of determining, for each instant of time and given information from perceptual sensors, the PNF-state of each interval, that is, happening (NOW), already happened (PAST), or has not happened (FUT). We show how the computation of PNF-states can support both action recognition and the control of real-time interactive environments in which the actions are described by Allen interval networks.