Plan Recognition Using A Hypothesize and Revise Paradigm
Proceedings of the Fifth International Joint Conference on Artificial Intelligence. Problem-solving and Search. Pages 480-485.
© 1977 International Joint Conferences on Artificial Intelligence
Abstract
- Bobrow, D. and Winograd, T. An Overview of KRL, A Knowledge Representation Language. Cognitive Science, vol 1, January 1977, p3-46.
- Sacerdoti, E.A. A Structure for Plans and Behavior. Ph.D. Thesis, Computer Science Department, Stanford University, 1975.
- Schank, R.C. The structure of episodes in memory. In D.G. Bobrow and A. Collins (Eds.), Representation and Understanding. New York: AcademiC Press, 1975. p237-272.
- Schmidt, C.F. and D'Addamio, J. A model of the common-sense theory of intention and personal causation. Prohlem-Solvlng-4: Schml~t In Third International Joint Conference on Artificia_l __ __ Intelllgence7 Advance Papers of the Conference. Stanford Univ~rsity, Stanford, Calif., 1973, p465-471.
- Schmidt, C.F. Understanding human action: Recognizing the plans and m9tives of other persons. In J. Carroll & J. Payne (Eds.), Cognition and Social Behavior. H1llsdale, New Jersey: Lawrence Erlbaum Associates, 1976. p47-67.
- Schmidt, C.F., Sridharan, N.S., & Goodson, J.L. Recognizing plans and summar1zing actions. Proceedings of .the Conference on Artificial Irltelligence andthe Simulation of Behavior. Edinburgh, Scotland: University of Edinbugh, 1976. p291-306.
- Schmidt, C.F. & Goodson, J.L. Recalling and Summarizing Action Sequences: Some Empirical Tests of the BELIEVER Thoery. Technical Report CBM-TR-81, Department of Computer Science, Rutgers University, June, 1977.
- ti.
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
PLAN RECOGN I'riON USING A HYPOTHESIZE AND REVISE PARADIGM:
An Example
Charles F. Schm1dt and N.S. Sridharan
Departments of Psychology and Computer Science Rutgers University, New Brunswick, NJ 08903
A great deal of resea.tch has focused on the problem of how to generate a plan that satifies a given goal [2]. The problem of plan recognition is to take as input the sequence of actions performed by an actor and to identify the goal pursued by th€ actor and also to organize the act1on sequence in terms of a plan structure. This plan structure explicitly describes the goal-subgoal relations among its component units. Our concern with plan recognition has ar1sen from our research [4,5,6,7] in the development of a theory of how persons understand the observed actions of others. A variety of experiments [7] have demonstrated that the summary as well as the recall protocols of an action sequence can be predicted if it is assumed that the observer is actively reconstructing from the observations the plan or plans that the actor is executing.
The psychological theory of plan recogn1tion, BELIEVER, consists of a set of knowledge structures and processes defined within the AIMDS system [11]. The specification of the knowledge sources for the BELIEVER model arose from considerations of the properties of the problem domain and do not rest on any particular psychological assumptions about properties of the human information processing system. For example, the observed sequence of actions that serve as input to a plan recognition system do not provide information that identifies which of the set of outcomes associated with an action sequence corresponds to the goal or goals of the actor. In fact, the actor's plan may have failed or been abandoned or interrupted 1n which case the goal outcome would not be represented at all in the action sequence. If cases such as these are to be recognized, then a plan recognition process must be capable of counterfactual reasoning that shows . how a hypothesized goal could have been achieved had some aspect of the physical world been
otherwise. Further, actions are linearly ordered and unbounded in time. Plans are bounded, hierarchical, and nonlinearly ordered based on the logical connection be twe en an enduring outcome of one action and the precondition of some subsequent act ion. Further, a plan is well-formed with reference to the ~lanner's beli e fs about the world rathe r than with respect to the actual state of the world. For the se and simil a r reasons, we have argued that any process of plan recognition must use meta-knowledge about plans and the psychological constraints which define a well-formed plan. Knowledge of only the physical constraints on ac tion does not provide sufficient information to recognize plans [8].
In this paper we present, by means of an example, those aspects of a plan recognition process that have been implemented in BELIEVER. The properties of this process have been motivated primarily by our desire to incorporate within this proce ss certain psychological assumptions about characteristics of the human plan recognition process. The two major assumptions are that the human process is: (1) a general non-specialized process; and (2) is based on a hypothesize and revise strategy. The remainder of this paper is concerned with conveying the meaning of these labels. However, it will be useful to first explicate these idea~ in an informal way.
Because of interest in application or for methodological reasons, much of the recent work in AI has been concerned with the representation of expert knowledge within a relatively narrow domain. Chess, restaurants, flush toilets and particular electronic circuits are well-known examples of this approach. An expert's knowledge is, by definition, highly specialized and customized to a particular domain. This has led researchers to encode this knowledge in similarly specialized and customized forms which are often generically referred to as scripts [3]. The use of script-like knowledge is an important aspect of the human information processing capability.
However, very few of us are expert in everything and none of us are born that way. Spec1al1zed, customized knowledge must be acquired using quite general and schematic knowledge [9]. Accordingly, the system we have des1gned and implemented uses multiple communica ting knowledge sources to customize and specialize the general knowledge about acts and plans to speci fic observational input.
The knowledge needed by a process of plan recognition has been decomposed into three major knowl edge sources. These knowledge sources toge the r With some of the major l1nes of communication between them arc shown in Figure 1. In this f1gure the knowledge sources are referred to as the Person, Plan, and World Domains. Each knowledge domain defines the concepts, relations, and logical dependencies between concepts that govern the representation of particular instances of objects within that domain. The boxes labeled Person Model (Pr-1 ), Expectation Structure (ES), and World Model (WM) graphically represent the different contexts within which particular assertions are maintained. The WM consists of the assert1ons that the system believes to be true of the current physical situation. This set of assertions is constantly changing and being updated as a new description of an observed action is input to the system. In Figure 1 the beginning of such an input stream is shown and referred to as Input Action Sequence. The PM contains assertions about what the syte~ believes the actor believes, wants, and likes, etc.
The ES represents the plan structure that the system currently believes the actor is executing. This attribution of a plan to the actor requires that: (1) the 1ncoming act sequence match the partial order of the plan structure; (2) the actor have certain beliefs and wants (the Person Model Requirements); and (3) that certain assertions about the physical world be true (the World Hodel Requirements). We will show that by def1ning the ES appropriately and using this knowledge decomposition, the ES can be used by the plan recognition process to compute the PM and WM requirements. Further, by matching the plan units of the ES to the incoming actions the schema variables of the ES can be bound and used to further customize and specialize the ES to the observatinal context. In this way the
basic process of plan recognition is reduced to various types of matching processe s.
The requirements derived from the current ES a re log1ca l requirements that must be met 1f the actions are to be interpreted using that particular ES. Consequently, a mismatch signals the violation of an expect a tion and indica tes tha t the ES must be revised. ~fter presenting the operatin of this basic matching process we will show how the results of this misma tch can be used to trigger and guide a strategy of ES revision. This hypothesize and revise strategy is congruent with our goa l of using knowledge stated at a general level in plan r ecognition. The revision rules are anchored on classes of mismatche s between ES r equi rements and the observations. Consequently, w2 have been able to avoid anchoring these revision rules to particular ES structures.
This hypothesize and revise strategy is further motivated by our assumption that human observers do not use a strategy of heuristic sea rch to explore a large space of possible interpretations of a sequence of actions. Rather the observer is assumed to explore only a few, usually only one , hypotheses at a time. This hypothesis is adapted to the rea lities of the observations by a process of refinement and revision. This str a tegy does not insure correctness nor completeness. However, this is not our goal. Rather, we hope that this strategy will allow us to predict the conditions under which the human observer will succeed or fail in the task of plan recognition.
The Process of Interpretation
The process we define below takes a sequence of act descriptions and by re-representing them as 9lan units, produces a plan structure that is supported by and is consistent with the world model and the person model.
Hypothesize and Revise
The three main steps of the process are: (1) [SETUPES] An appropriate ES is set up and this ES is customized for use in the current context. The ES may be simply summoned from memory, constructed by a plan generator from knowing the goal of the planner, or may be postdictively assembled unit by unit from the incoming observations. (2) [ACTINPUT] The input act description is used to update the world model and is then matched against an expected plan unit 1n the ES. A proper match produces bindings for the variables in the ES thus making the further expectations more spec1f1c . The details of this expectation guided matching process a re reported in [10) . (3) [REVISE) Conflicts that arise between the expectat1ons and observations trigger rules for hypothesis revision.
The structure of ES schemata
The ES consists of a number of plan units with specified " inorderto" relat1ons among them which constitutes a partial order. The starting plan units and the final unit are identified. The goal of the final unit iS also the goal assigned to the ES. The set of triples [Pl S P2) called the "inordertoprops" is formed from those plans Pl and P2 such that the goal proposition S of Pl iS among the preconditions of P2. For th1s it should also be the case tha t no other plan unit occuring in between Pl and P2 undoes the proposition S. The "modelregu1rements" are pairs [S PI with ~ropositions S, which are opportunities for a plan unit P in the ES, such that there iS no other plan Q set up to accomplish s. Each such proposition is required to be satisfied in the 1nit1al world model.
Monitoring these propositions aids the interpretation process in developing further expectations and in the recognition of conflicts and failed plans. As input actions are matched against expected plan units, they are shifted into the Hypothesis set H, to designate that they are supported by observations and are no longer "expected" to occur. Th1s distinction between H and E is represented graphically in Figure 1 where those units in H are l1nked to input actions that have been taken up by the system. As a plan unit is shifted from the set E to the set H, other members of E are considered to be "next expected" plan un1ts. A next expected member has its modelrequ1rements checked against the world model. If such a modelreguirement proposition is true in the person model and false in the world model, then this plan unit is flagged as "expected to fail". If a modelrequirement proposition is false in both the person model and world model, then a plan to accomplish the proposition iS generated and inserted into the ES. If the modelrequirements are satisfied in both these models, the inordertoprops are checked. If the proposition me ntioned in an inordertoprops was in fact accomplished by an earlier plan but is no longer true then the assumption of "inorder to" between the two plans is not supportable.
The diagnosis and analysis of the currently attributed plan is performed by a decision tree [8) us 1ng information maintained in a structur e called INTERPRETATION . Each terminal node of this decision tree calls for a corresponding revision rule. The revision rules perform actions that could range from accommodating the next observed action a s being optional, or including it as part of the present plan, or generating and inserting plans to accompl1sh failed modelrequirements, or claiming that the planner failed in successfully carrying out his plan, or as drastic as abandoning the current assumptions and developing a different plan structure using whatever information can be meaningfully carried over from the present plan structure. We illustrate below the actions of the three components of the hypothesize-revise procedure.
Example of Basic Match Process and Conflict ResoiUtTOn
An example expectation structure is presented below using KRL-like [1) conventions. The notation [refer: V) introduces a variable name and all subsequent uses of the vari able designate the same entity. This ES is constructed by SETUPES from eight plan units that use variables to make references to objects and locations in the world mode l. The eight plan units form a connected partially orde red structure shown in Figure 1.
(a EXPECTATION STRUCTURE Assemble/and/Eat with
[Variables
(LIST ALl L2 L3 01 02 03 04)) [agent (a PERSON [refer: A))])
The actions embedded within the ES are listed below. DESCRIPTION of Assemble/and/Eat Expectation Structure:
- (a \'iALK with
[toloc (a LOCATION [refer: Ll))))
- (a TAKE With
[object (a OBJECT [refer: 01]
with [loc Ll) which IsEdible))
[inordertoof (the last WALK)))
- (a CARRY with
[object Ol] [toloc (a LOCATION [refer: L3])] [inordertoof (the last TAKE)])
- (a \'VALK with [toloc (a LOCATION (refer: L2])J)
- (il TAKE W.i..th [object (a OBJECT [refer: 02] with [loc L2] Wh.i.Ch IsEdible [ASSEMBLYPARTS 01 02])]
[inordertoof (the last WALK)])
- (a CARRY Wlth [object 02] [toloc L3] [1nordertoof (the last TAKE)])
- (a 11AKE with
[components 01]
[components 02]
[instrument (a OBJECT [refer: 03]
with (loc L3))]
[assembly (a Object [refer: 04] which IsEdible (ASSE~\BLYOF
Oland 02 using 03))]
[1nordertoof (the last CARRY)]
[inordertoof (the prev CARRY)])
- (a EA'r with [object 04] [inordertoof (the last MAKE)]))
The Assemble/and/Eat assembles two objects 01 and 02 to produce another object 04 which is then eaten. The 1nstrument used 1n making 04 is 03. The two sequences of Walk->Take->Carry sat1sfy the subgoal of the Make that require the components to be at the
location of the Make.
'rhe Des1gn of an Expectation Structure
The types of 1n1ormat1on that go 1nto defining the ES have been carefully chosen and it is worthwhile to consider here the reasons for the cho1ces made. (1) All references to objects in the world model are through variables, so that the ES is not spec1f1c to the part1cular situation but is generally applicable to a variety of situations. For example, 04 is not bound, and could be a peanut butter sandwich, an ice cream cone, or anyth1ng else. Similarly, there is no ident1fication of the location L3 to wh1ch 01 will be carried. If the person goes over to the cabinet and picks up an inedible object, there is sufficient information in the ES to know that this ES is no longer supportable in its present form. This information 1s reflected in the predicates [Assemblyparts .. ] [ IsEdiblel and [Assemblyof .. ] (2) The ES reflects no explicit world knowledge and thus no assumptions about the ed1bility or desirability of eating
1ce-cream are made in setting up the ES. (3) Knowledge that ice-cream will melt if left on the counter, that liquids need containers to carry, and that a cabinet door must be open to access its contents are factored out and do not ~ implicitly influence the structure of the plan 1n the ES. Thus, although a door might have to be opened to Take 02, and a container might be needed to Carry 02, these context dependent aspects of the plan are left out of the ES and the goal-subgoal structure is described in a context independent fashion. (4) There are only implicit alternatives and optional plans included 1n the ES. None of these alternatives and options are explicitly given in the structure. A dish might substitute for cone in eating ice-cream. If the scoop is not already on the counter the person might have to fetch one. The person might optionally sit down before eating. Such alternatives and options, including ways to take care of interruptions and accidents are factored out into the revision rules. This allows a single sketchy ES to be used and adapted to a number of action sequences. (5) Similarly, no explicit assumptions about the planner, his belief state, knowledge state or motivations are introduced into the ES. The statement of goals and inorderto relations certainly have 1mplications about what the planner wants and believes but these will be derived and accounted for as the interpretation proceeds by matching actions against
the plan units 1n the ES.
The ES is set up to reflect only the causal and intentional structure of the plan. The objects entering the ~lan are defined by their role in the plan. The ES leaves out as much world knowledge, person knowledge, and listing of alternatives and options as possible. This factoring is done to achieve generality in the structure of the plans used and also because it is impossible to anticipate all revisions, options, and world knowledge contexts in which a general kind of goal may be pursued.
Sett1ng ~ and customizing the ES
The SETUPES component customizes the ES to the context of a given initial World Model, WM, and an initial Person Model, PM, which it compares with ES. This gives rise to an initial set of bindings and the calculation of
the next expected action.
Inltial World Mode l WM : (Tom loc Kitchen) (Cabinet in Kitchen) (Cone loc Cabinet) (PeanutButte r loc Cabinet) (Ref r1gerator 1n Kitchen) (Br ead loc Refrigerator) (Ref riger a tor 1n K1tchen) Not-(IceCream loc Refrigerator) (Counter in Kitchen) (Scoop loc Counter) accompanied w1th the general world knowledge: (Assemblyparts IceCr eam Cone ) (Assemblyparts Bread PeanutButter) (Assemblyof IceCr eam Cone Scoop ICC) (Assemblyof Bread PeanutButter Knife PBS ) (IceCream IsEdible) (Cone IsEdible)
No t-(Knife IsEd1ble) etc.
In1t1al Person Model PM: (Tom bel1eves (Scoop loc Counter)) (Tom believes (IceCream loc Refrigerator ) ) (Tom believes (Cone loc Cabinet)) and so on, conforming to the model WM. (Tom like s (Tom ate ICC)) (Tom likes (Tom a t e PBS))
In setting up the ES the modelrequ1rement propositions are matched against the Per son Model PM a nd the World Model WM. Each proposit1on falls into one of three classes with respect to each model: (l) It is known to be true in the model; the requirement iS satisfied. (2) It is unknown 1n the model; it will be presumed true until explicitly denied. (3) It iS known to be false in the mod e l. If the proposition is false in the person model, that is, if the planner has a belief that contradicts one of the requirements then the attribution of the plan structure to the planner cannot be made and the ES will have to be revoked. On the other hand, 1f it is the world model that contrad1cts the proposition while the person model supports it, the divergence between the two models allows the plan but requires that the proposition be flagged "expected to fa1l during execution".
Hodeling and 1·1atching Actions
We shall follow the basic matching process, especially the actions of ACTINPUT, for an episode whose first four acts are:
l. Tom walks to the cabinet. (Mwalkl)
2. Tom takes out a cone. (Mtakel)
3. Tom carries the cone to the counter. (11carryl)
4. Tom walks to the Refrigerator. (11walk2)
The first act, Mwalkl, is taken in and the updated WM now shows the proposition (John loc Cabinet). Mwa lkl is then matched to Wa lkl from the ES yielding the following bindings: Walkl-> (Hwa lkl), A-> ('rom), Ll->(Cabinet), 01->(PeanutButter, Cone, .· ), L2->(Cabine t, Counter, Re frigera tor, .. ) and so on. The matching process pursues unique bindings such as Ll->(Cabine t) deeply to make sure that what is required about Ll by the ES is in fact ma tched by the properties and relations of Cabine t. Vari ables such as 03 and L2 have a set of candidate bindings and the procedure does not generate and analyze the various combinations of assignments that are possible. However, as soon as the actor takes out the cone in the second act, Mtakel , the binding of 01-> (Cone) causes an investigation of what objects 02 can be assembled with the binding for 01. The specifications in 'the world knowl edge constrains 02 to have the unique binding 02->(IceCream), which then yields the unique binding L2->(Refrige rator) and also 03->(Scoop) and 04->(Counter) since the scoop is on the counter. Thus after the second act all the variables are bound uniquely: A->(Tom), Ll->(Cabinet ), L2->(Refrigera tor), L3->(Counter), 01-> (Cone), 02-> (IceCream), 03-> (Scoop) and 04->(ICC).
There iS a modelrequirement (02 loc L2) associated with the plan unit Take2 and th is proposition is now tested since 02 is unique ly bound. This process of verification recognizes that it 1s false in the world model and thus flags Take2 a s being "expected to f ai l". Thus later on at the time of revision either the goal of the ES is considered abandoned, or Take2 is replaced with another plan to accomplish its goal, or a plan is inserted to accomplish the proposition (02 loc L2) or 02 is bound to some other object which will st1ll allow the final goal to be pursued. ~t this point in the processing none of these alternatives a re enumerated. Instead a "wait and see" strategy is followed and the next input act is taken up.
Generation and explanation of conflict
~fter the four acts shown above are input and matched the matching generates the following bindings: Walkl->(Mwalkl), Takel->(Mtakel), Carryl-> (r1carryl), Halk2-> (Mwalk2), A-> (Tom), 01-> (Cone), 02-> (IceCream), 03-> (Scoop) , 04-> (ICC) , Ll-> (Cabinet) , L2-> (Refrigerator), L3-> (Counter). The next expected unit is Take2, which translated using the current bindings 1s "Tom takes out the ice cream."
The next input act, call it Xwalk, is "Tom walked to the counter," and th1s observation requires a revision of the current interpretation. Since Xwalk does not correspond to the expected next act1on, Take2, the system recognizes a violation of expectation. The report of the mismatch has two parts: (1) Xwalk does not match the next expected unit of ES; and (2) In the inordertoprop [Walk2 (A loc L2) Take2], the Walk2 is already matched to an action, (A loc L2) is now false, thus signalling a violation of the alleged [Walk2 inorderto Take2]
relat1on.
The observed action is to be explained either as an attempt to satisfy the goal of Take2 by a d1fferent sequence of actions (Tom is doing something to get ice cream) or to treat it as part of a sequence reversing the consequences after failing in the plan (Tom is putting away the cone). There is also the option that the actor may be attempting to reachieve his original goal (to eat some object, not necessarily ice cream cone). The maintenance of such explanat1ons at different levels of general1ty is aided by the generality w1th which the ES is designed. When alternative revisions are forthcoming, the revisions will have to await further conf1rmation from subsequent observations. Agajn, as in the matching of input acts, a "walt and see" strategy that delays the analysis of alternatives is used in the case of ES revision since subsequent inputs will provide guidance in selecting an
alternative.
Conclusion
The principal tenet of the hypothes1ze and revise paradigm is that when the hypothesis revision rules are robust enough to set the process back on the right track and to fill missing details whenever appropriate, there is no pressure to set up the "correct" or the most detailed expectation at the start. It is characteristic of most recognition problems, including vision, speech and in our case plan recognition, that there is little information at the start to set up strong expectations. Yet, generating hypotheses and conducting "best first"
or backtracking search demands strong expectations in the beginning and lays heavy penalties of effort on the process when the expectations are either partially inappropriate or when they lack adequate detail. Further investigation of the robustness of the hypothesize and revise procedure and further characterizations of revision rules will be the focus of , our continuing research.
Status of implementations
The representational structures described above, the consistency checking, action modeling have been in operation for about _ a year now. The basic match process, conflict analysis and reporting was working in February 1977. The case analysis and interpretation revision is being programmed and is expected to be working in the summer and will be demonstrated at the Third Annual Workshop on AI in Medicine and the Sciences, to be held at Rutgers University in July 1977. BELIEVER is developed in the AIMDS system, which is a smaller version of MDS customized to the task of reasoning about actions. AIMDS has taken from the MDS formalism the concepts of Templates, Consistency Conditions and Residues and components of the MDS architecture [12) providing a framework for representing knowledge in terms of frames and transition frames.
This research was supported by Grant RR-643 to the Rutgers Research Resource on Computers in Biomedicine from the BRP, Division of Research Resources, NIH.
@inproceedings{ijcai1977p108,
title = {Plan Recognition Using A Hypothesize and Revise Paradigm},
author = {Schmidt, Charles F. and Sridharan, N. S.},
booktitle = {Proceedings of the Fifth International Joint Conference on
Artificial Intelligence, {IJCAI-77}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Raj Reddy},
pages = {480--485},
year = {1977},
note = {Problem-solving and Search},
url = {https://ijcai.org/proceedings/1977/108},
}
TY - CPAPER TI - Plan Recognition Using A Hypothesize and Revise Paradigm AU - Schmidt, Charles F. AU - Sridharan, N. S. T2 - Proceedings of the Fifth International Joint Conference on Artificial Intelligence, IJCAI-77 PB - International Joint Conferences on Artificial Intelligence PY - 1977 SP - 480 EP - 485 UR - https://ijcai.org/proceedings/1977/108 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
Welcome
Future Conferences
AI Journal Division
IJCAI Proceedings
About IJCAI
IJCAI Awards