Procedural Knowledge

MICHAEL P. GEORGEFF AND AMY L. LANSKY

Much of commonsense knowledge about the in natural-language understandingconcernedwiththe

real world is in the
form of p r d u r e s or sequences of actions for achieving particular
meaning of actionsentences. Someattempts have alsobeen
goals. In this paper, a formalism is presented for representing suchmade to indicate how these theories could used be for gen-
knowledge using the notion ofprocess. A declarative semantics for
the representationis given, which allows auser to state facts about eral reasoning about actions[2], [IA. Second, there is work
the effects of doing things in the problem domain interest.of on planning-that is, the problem of constructing
An a plan by
operational semantics is also provided,whichshows how this
searching for a sequenceof actions that will yielda partic-
knowledge can be used to achieve particular goals or to form in-
ulargoal P I , [q,V91,
1211, W I , P51, [281.
tentions regarding their achievement. Given both semantics, our
formalism additionally serves as an executable specification lan- Surprisingly, almost no work has been done in AI con-
guage suitable for constructing complex systems. A system based cerning the execution of preformed plansprocedures-or
on this formalism is described, and examples involving control of yet this is the almost universal way in which humans go
an autonomous robot and fault diagnosis for NASA’s space shuttle about their day-to-day tasks, and probably the only way
are provided.
other creatures do so. Actually searching the space of pos-
sible futurecourses of action, which is the basis of mostAI
I. INTRODUCTION planning systems, is relatively rare.
There is an increasing demand for systems or artificial For example, consider the task of driving to workeach
agents that can interact with a dynamic environment to day. For most of us, our plan of action has been worked out
achieve particular goals. Common applications of this type in advance. Once we establish agoal for ourselves to leave
include robotic functions, construction and assemblytasks, home andget to work, we followsome internal procedure
navigation and exploration by autonomousvehicles, con- or pattern of getting to thecar, getting in, driving a certain
trol and monitoring of systems, and servicing and main- route, searchingthe parkinglot in aparticular fashion once
tenance of equipment. Agents capable of operating effec- weget there, parking, and then walkingto theoffice. Rarely
tivelyinthesekindsofdomainsmustbeabletoreasonabout do weever derive this plan from first principles. In fact, we
their tasks and determine how toact in given situations- often seem to perform these actionswithout even thinking!
i.e., they must be capable of practicalreasoning [6].To build This pattern appliesto many of thetasks we performevery-
such systems we need to be able to represent knowledge day.
about the effects of actions and how these actions can be Of course, there are often situations in which our normal
combined to achieve specific goals. procedures or plans must be modified or reconsidered.
Within artificial intelligence(AI), there have been two ap- Rather than derive completely new plans, we usually adjust
proaches to this problem, with a somewhat poor connec- to situations by operating in a piecemeal fashion;we keep
tion between them. In thefirst category, there i s work on an overall plan in mind and elaborate it as we proceed and
theories of action,i.e., on what constitutesan action perse acquire more knowledge of the world. For example, if we
[I], [12], [ I q . This research hasfocused mainlyo n problems run intoan obstacle on theroad to work, a new routemay
need to be found for part of the journey. Although the top
Manuscript received April 26, 1985; revised May 14, 1986. This
level plan of actionmay remain the same, different means
research has been made possible inpart by a gift from the System of realizing pieces of the plan would beused, depending
Development Foundation, by the Officeof Naval Research under on the particular situation. For instance, one might beable
Contracts N00014-80-C-0296 and N00014-85-C-0251,and by the Na- to avoid the obstacle simply by driving around it. On the
tional Aeronautics and Space Administration (NASA) under Con- other hand, if theobstacle werelarge, one may haveto use
tract NAS2-11864. The viewsand conclusions contained in this pa-
per are those of the authors and should not be interpreted as more complex avoidance procedures that involved turning
representative of the official policies, eitherexpressed or implied, onto side streets,continuing in the same general direction,
of the Office of Naval Research, NASA, or the United States gov- and the like.
ernment. This strategy of operation might be called partial hier-
The authors are with the Artificial Intelligence Center, SRI In-
ternational, Menlo Park, CA 94025, and the Center for the Study
archical planning. The idea is simply to intermix the for-
of Language and Information, Stanford University, Stanford, CA mation ofplans andtheir execution; i.e., form a partial over-
94025, USA. all plan, figure outnear-term means, execute them,further

0018-9219/86/1000-133$01.00 0 1986 I E E E

PROCEEDINGS OF THE IEEE, VOL. 74, NO. 10, OCTOBER 1986 1383
Authorized licensed use limited to: UNIVERSITY OF ESSEX. Downloaded on January 12,2023 at 18:12:35 UTC from IEEE Xplore. Restrictions apply.
 expand the near-term plan of action some more, execute, mediate pointsin the recipe. Work Lansky[14] by has taken
and so on. This approach has many advantages. First of all, veryseriouslythenotionofencodingdomain requirements
systems generally lack sufficient knowledge to expand a primarily in terms of actions and their interrelationships
plan of action to the lowestlevels of detail-at least if the and deriving knowledge from past activity. Such an ap-
plan is expected to operate effectively in a real-world sit- proach appears particularly advantageous for describing
uation. The world around us is simply too dynamic to an- the properties of multiagent domains.
ticipate all circumstances. By finding and executing rele- Another advantage of representing knowledge as pro-
vant procedures when they are truly needed, a system may cedures is that we are able to reason about those proce-
stand a better chance of achieving its goals. dures as wholeentities. For example, giventwo procedures
Acombined planninglexecution architecturecan alsobe for fixing a broken pipe, we can evaluate those procedures
reactive. By reactive, we mean more than a capability of in their entirety and decide which has the best codbenefit
modifymgcurrent plans in orderto accomplish goals; given properties in a particular situation. Thistypeof “metalevel
a reactive system should also be able to completely change or reflective reasoning about our own internal procedures
its focus and pursue new goals when the situation warrants enables us to perform effectively and wouldbe intractible
it. This is essential for domains in whichemergencies can if the steps of the procedure had been broken down into
occur andis an integral component of human practical rea- seemingly unrelated rules.
soning. In asystem that expands plans dynamically and in- The primaryaim of this paper is t o provide abasis for rep-
crementally, there are frequent opportunities to react to resenting and reasoning about procedural forms of knowl-
new situations and changing goals. Such a system is there- edge in away that allows an agent to deal effectively with
fore able to rapidly modify its intentions (plans of action) a dynamicallychangingworld. It is importantthatthe
on the basis of what it currently perceives as well as upon agent be able to use these procedures to form intentions
what it already believes, intends, and desires. to achieve givengoals, t o react t o particular events, to mod-
Of course, how we represent knowledge is just as im- ify intentions in the light of new beliefs goals,or
and t o rea-
portant as how we use it. Representing knowledge of dy- son about these things in a timelyway.
namic environments as procedures, rather than as sets of To do this, we first introduce the notions of action and
rules about individual atomic actions, has many advan- process. We then provide means a for describing these and
tages. Most obviousis the computational efficiency gained define a declarative and operational semantics for our for-
in nothaving to reconstruct particular plans of action over malism. Together, theseprovide a way of both stating pro-
and over again from knowledge of individual actions. cedural facts about the problem domain anda method of
Second, much expert knowledge is already procedural practical reasoning about how t o use this knowledge to
in nature: for example, consider the knowledge one might achieve given goals.
have about kicking a football, performing a certain dance More generally, the formalism may also beviewed as the
movement, cooking a roast dinner, solving Rubik’s cube, basis for an executable specification language. Justas for
or diagnosing an engine malfunction. In such cases, it is Prolog [5],the declarative semantics provides ameans for
highly disadvantageous to ”deproceduralize” this knowl- stating facts about the problem domain, and the opera-
edge into disjoint rules or descriptions of individual ac- tional semantics yields a means of using these facts t o
tions. To do so invariably involves encoding the control achieve given goals.
structureofthe procedureinsomeway. Usuallythis isdone A system basedon theproposed representationhas been
by linking individual actions with “control conditions,” implemented andis currently beingused for the control of
whose sole purpose is t o ensure that the rules or actions an intelligent robot and for fault isolation and diagnosison
are executed in the correct order. This approachcan be very NASA‘s space shuttle. An early version of an implemented
tedious and confusing, destroys extensibility, lacks and any system is described in Georgeff and Bonollo[8] and the lat-
natural semantics. est work in Georgeff and Lansky [ I l l .
By having direct access to theparticular behavior that a
procedure has or will follow, we can alsomake muchmore
II. PROCESSES AND ACTIONS
effective use of procedural knowledge. For example, s u p
pose that an agent knows that in order toachieve G it will We assume that, at any given instant, the world is in a
follow a course of action of the form: X + Y + Z. When particular worldstate. Thisstate embodies not only the ex-
performing X, the agent will know that itis setting up a sit- ternal environment, but also the world insidean agent-its
uation for later performance of Z. When the agent finally internal cognitive world. As time progresses, the worldstate
does getaround toZ, itwilllikewise knowthatxand Y have changes through the occurrence ofactions (or events).’
been performed, thereby allowing it to make various as- Most early work in AI represented actions as mappings
sumptions-for instance, that certain environmental con- from world states to world states [A, [16], [19].However,
ditions willbe in place because X andY tend tomake them these models can describe only a limited class of actions
that way. and are too weak to be used in dealing with multiagent
Having access to one‘s history of actions can alsofree an ordynamicworlds. Some attempts have recentlybeen
agent from stringent reliance on its sensors-the agent can made to provide a better underlying theory for actions.
derive much information about the state of the worldsim- McDermott [I7considers an action or eventto be a set of
ply from knowledge of its previous activities (see also [4], sequences of states, and describesa temporal logic forrea-
[20], [26]). Forexample, if cooks follow the steps of a recipe soning about such actions and events. Allen [I] also con-
exactly, they can usually assume the food will turn out
right-they do not have to perpetually taste it. They might ’Although some authors make a distinction between actions and
not even know whatit should taste like, especiallyat inter- events, in this paper we treat the two terms synonymously.

1384 PROCEEDINGS OF THE IEEE, VOL. 74, NO. IO, OCTOBER 1986
Authorized licensed use limited to: UNIVERSITY OF ESSEX. Downloaded on January 12,2023 at 18:12:35 UTC from IEEE Xplore. Restrictions apply.
siders anaction t o be aset of sequences of states and spec- sible modesof failure. And thiscan only be done with a no-
ifies an action by describing the relationships among the tion of process-an intrinsic part of deducing a failed be-
intervals overwhich theaction’s conditions and effectsare havior is knowing exactly how that behavior was generated
assumed to hold. However, although it is possible to state in the first place.
arbitrary properties of actions and events, it is not obvious The need for representing failed behaviors also arises in
how these logics can be used effectively for practical rea- natural-language understanding. For example, it is impor-
soning2 tant to have a denotation for action sentences (such as “she
Our notion of action is essentially the same as that of was painting a picture”) that allows for action failure, even
McDermott and Allen; namely, we consider actions to be in midperformance(”she was painting a picture when her
sets of sequences of worldstates. However, t o reason about paints ran out”). The action referred to in thesecond sen-
how toachieve givengoals or test certain properties of the tence must be one of the failed behaviors of the picture-
world, the concept of actionalone is not sufficient. In par- painting process, and there is no way to derive this solely
ticular, we needto know how the actions are actually gen- from a set of successful picture-painting behavior^.^
erated. Finally, the notion ofprocess failure also allows us t o rep-
To do this, we introduce a notion ofprocess. Informally, resent tests on world states in a particularly simple way
a process can be viewedas an abstract mechanism thatcan without the introduction of knowledge or belief structures
be executedto generate a sequenceof worldstates, called (cf. [18]).To do this, we let certain successful process be-
a behaviorof theprocess. The set of all behaviors of a pro- haviors stand as tests for a given condition. This can only
cess constitutes the action (or action type) generated bythe be done if are we guaranteed thatthe process will onlysuc-
pro~ess.~ ceed when the condition is indeed true. (If theprocess fails,
Having a notion process
of allows us to make adistinction we can, of course, assume nothing about the condition. Al-
that is critical for practical reasoning-we can distinguish though we might usually behappyto equate process failure
between behaviors that are successful executions of the with thenegation of the condition being tested, we may not
process (i.e., successful instances of the action) and those always wish to doso. In such cases, we might need one pro-
that are unsuccessful (thosethat have failed). Theability to cess to test for a givencondition and another process to test
represent both successful and failed behaviors is very im- for its negation.)
portant in commonsense reasoning and is critical in mul-
tiagent and dynamic environments (e.g., see [13]). Ill. PROCESSDESCRIPTIONS
The need for representing both failedand successful be-
Abstractly, a process can be modeled by twosets of be-
haviors is most clearly seen in problems that involve mul-
haviors, one set representing the successful behaviors of
tiple agents. In such worlds, the potential side effects of an
the process and the other the failed behaviors. However,
agent’s activities can havea dramatic influence upon other
to reason about these behaviors we need some means for
agents. In a system that uses a combined planninglexe-
describing them; moreover, whatever descriptions weuse
cution frameworkas described earlier, and in which knowl-
need to be amenable to efficient reasoning techniques.
edge of the world is incomplete or uncertain, it is usually
In this section we present a means of describing pro-
not possible to predict whether a process will succeed or
cesses as sequences of particular subgoals or behaviors to
fail. (Of course, even if we were fully planning everything
be achieved. Each process is represented by a labeled tran-
out in advance, we still could notrealistically anticipate all
sition networkwith distinguished start and finish nodes and
of theconsequences of executing aprocess.) Given this, it
arcs labeled with subgoal descriptions (see Fig. 1). Any re-
is clear that both failed andsuccessful process executions
alizable behavior that achieves each of the subgoals la-
will occur, and thus both must be available for reasoning
beling some paththrough the network from the start node
about potential process interactions.
to a final node constitutessuccessful
a behavior ofthe pro-
Using a notion of process is particularly important for
cess; a failed behavioris one which terminates with failure
reasoning about failed attemptsto accomplish givengoals.
to achieve a subgoal on the path.
For example, suppose that we have two ways to get to the
Operationally, we may view a process description as
airport to catch a plane; one involving making a bus con-
being executed in the following manner. At any moment
nection and the other, although less convenient, by car
during execution, control is at a given noden. An outgoing
along a busy route frequented by numerous taxis. Clearly,
arc a may be transitted by successfully executingprocessa
the successful behaviors of both methods(processes) will
that achieves the subgoal (behavior) labeling a. I f no out-
result in catching the plane. However, failure tomake the
going arc from n can be transitted, process execution fails.
bus connection could leave us in a state from which we
Execution begins with control at the start node and suc-
could not recover (because next available means of trans-
ceeds if control reaches the finish node.
port to the airport will arrive too late), whereas failure of
We nowgive amore formal definition of our process de-
the other method, given the availabilitytaxis, of would not
be so catastrophic. We might, therefore, decideto use the
4The reason is that different processes or procedures can gen-
second, less convenient method, if we compare theirpos- eratethesamesetofsuccessful behaviorsyet havedifferentfailure
modes. For example, consider two procedures for jumping across
a stream. In the first procedure, we check that the stream is suf-
*Allen [2]does, however, propose a methodof forming plans that ficiently narrow to jump and, if so, jump it; otherwise, we do not
is based on a restricted form of his interval logic. even attempt to cross. In the second procedure we perform the
’In this paper we restrict our attention to sequential, noncon- same test but attempt the jumpirrespective of the outcomeof the
current processes. Our work on implementing system a based on test. Assuming the test accurately determines whether or not the
this theory, however, has incorporated the notionof concurrently stream can be jumped, both procedures yield the same set of suc-
active, communicating processes. cessful behaviors, but the failed behaviors are quite different!

CEORCEFF AND LANSKY:PROCEDURALKNOWLEDGE 1385

Authorized licensed use limited to: UNIVERSITY OF ESSEX. Downloaded on January 12,2023 at 18:12:35 UTC from IEEE Xplore. Restrictions apply.
 Having ameans for describing processes, we now need
a way to state properties about them.In thispaper, we are
interested primarily in describing theeffects of successful
behaviors of a process; that is, we wantto be ableto express
the fact that, under certain conditions, successful execu-
tion of the process will result in a certain behavior being
wbgoal3
achieved. We will call such facts process assertions.
A process assertion consists of a process description, PI
describing a process; a precondition, c, denoting a set of

b world states in which the process is applicable; and an ef-

fect, g, characterizing the set of successful behaviors the
process can actually generate when commenced ina state
subgoal5 satisfying c. We will write such an assertion as c ( P)g.
The intent or meaning of this assertion is that any suc-
cessful behavior of process Pwhose firststate satisfiespre-
condition cwill alsosatisfytheeffectg. From an operational
viewpoint, if c holds at the commencement of execution of
Fig. 1. A process description. process P, g will be realized by a successful execution of
the process.
Process assertionsmay also use variables. Such variables
scription language. First, we assume a fixed set S, possibly
may appear in the preconditionc, in the process descrip-
set A, also possibly
infinite, ofstate descriptions and a fixed
tion P,as well as in theeffect g. We make adistinction be-
infinite, of action descriptions. A process description can
tween local variables (prefixed by %) and global variables
thenberepresentedasatupleP= (N,E,6,n,,NF,a,),where
(prefixed by$1. All global variables must have a fixed inter-
N is a set of nodes pretation over the entireassertion andare taken to be uni-
E is a set of arcs versally quantified. In contrast, local variables must have
6: N X E + N is the process control function
a fixed intepretation in theinterval of states during which
n, N is the start node agiven arc istransitted, butcanotherwisevary.Theycannot
appear in thepreconditions or the effect of a process as-
N F C N is a set of final nodes
sertion, and are existentially quantified over the scope of
a: E + A associates anaction description witheach arc;
these action descriptionsare called goaldescriptions. the arc on which they appear. (Local variables are often
needed in loops where it is necessary to identify different
Rather than represent process descriptions in this formal elements from one iteration to then e ~ t . 1 ~
mathematical way, we use a graphical form as typified in A typical process assertion is shown in Fig. 2.
Fig. 1.
Both the state and action description languages are based
on predicate calculus. Each state description is a first-order Precondition: TRUE
predicate-calculus formula and can be viewedas denoting Effect: (I (DEFEATED WANT)

a set of states; namely,those in whichit is true. For example,

a formula of the form((on a b) A (on b c)) could beused
todenotetheworldstatesinwhichblockaisontopofblock
b, which in turn is on top of blockc.
An action descriptionconsists of an action predicate ap-
(FIND $GIANT) P
plied to an n-tuple of terms. Each action description de-
notes an action type or set of behaviors. For example, an
expression like (walk a, b) could be taken to denote the
set of behaviors in which an agent walks from point a to
point b.
It is also desirable to allowa class of action descriptions
that relate directly to worldstates. We thus extend the ac-
tion description language to include actions that achieve
a given state condition p (represented by an action de-
scription of the form (! p)),actions totestforp (represented
as (? p)), andactions that preserve p (represented as
(# p)).We call these temporalaction descriptions. In each
of these, p is a state description-Le., a description of the
type of state to be achieved, tested for, or preserved. For
example, an action that achieves a state in which block a
is on block b might be described by a temporal actionde- Fig. 2. DavidandGoliath.
scriptionoftheform (! (on a b)).
Action descriptions may also be combined into action
expressions. These are composed in the usual way using ’In fact, because we want to allow localvariables to denote dif-
ferent objects on different transitions of the same arc, we strictly
conjunctiveanddisjunctive operators. Thusan action have to interpret variables with respect to the underlying tree
expression of the form (! p) A (? 9)denotes an action that structure of a process obtained by “unwinding” all loops ap-
both tests for q and achieves p. pearing in the process description.

1386 PROCEEDINGS OF THEIEEE, VOL. 74, NO. 10, OCTOBER 1986

Authorized licensed use limited to: UNIVERSITY OF ESSEX. Downloaded on January 12,2023 at 18:12:35 UTC from IEEE Xplore. Restrictions apply.
IV. DECLARATIVE
SEMANTICS work must allow behaviors that explicitly include failed at-
tempts at realizing tests and actions as well as successful
The declarative semantics of process assertions is in- ones.
tended to describewhat is trueabout the underlying system Moreover, it is important to realize that the goal descrip-
of processes and the world in which they operate. Such a tions labeling process arcs actually referto otherprocesses;
semantics says nothing about how such knowledge can be namely, those whose successful behaviors realize the de-
used t o achieve particular goals-rather, it simply allows scribed goals. If this were not thecase, we could not talk
one to state facts about certain behaviors.In the preceding sensiblyabout failed attempts achievegoals-failurescan
to
section we provided a preliminary, intuitive meaning for only be understood relative to the processes or methods
process assertions. In this section we present a more formal used t o generate actions, and not with respect to actions
declarativesemantics. First, however,we beginwithacloser alone. Second, from a practical point ofview, it would be
examination of the process assertion depicted in Fig. 2. very difficult to say anything useful about process asser-
The “David and Goliath” procedure can be viewed as a tions that were not grounded in performable actions-the
plan for defeating a giant with a slingshot.The procedure resulting processes would be too unconstrained.
involves gathering stones, placing them in a pile, getting We now give a more formal definition of the semantics
a slingshot, and then repeatedly taking up a stone and of process assertions. We first need to specify the inter-
shooting it until the giant is hit on the
head. In this particular pretation for thesymbols appearingin our description lan-
domain, hitting a giant on the head with a stone hurled by guage. We will assume a fixed domain D of objects and a
a slingshot always results in the giant’s defeat. The pro- possibly infiniteset of states. Given a particular state, astate
cedure is nondeterministic and allowsagents t o gather as interpretation associates with each constant symbol and
many stones as they wish, limited only by their ability to variable an object from D, with each predicate symbol a
continue gathering them.The procedure is not guaranteed relation over D, and with each function symbol a function
to be successful-it may fail if any one of the actions la- on D. The meaning of a givenstate description is then de-
belingthearcsofthenetworkcannotbeaccomplished(and fined under the usual semantics for first-order predicate
no other alternative path can be taken). calculus.
It is important to note howthe processassertion captures Similarly, wecan define a behavior interpretation that as-
implicit knowledge of the problem domain. This knowl- sociates a set of behaviors with each action predicate. The
edge is of two kinds: one concerning the validity of the pro- meaning ofan action predicate is then taken to be the cor-
cedure, the other heuristic. For example, hitting giants on responding set of behaviors in the interpretation of that
the headwith an object propelled from a slingshot will not predicate. We also need to specify the meaning of temporal
always defeat them (e+, if it is a cotton ball), but will if it action descriptions. If p is a state description, then
is a stone. Thus the validity of the effects of the procedure
depends critically on the structure of the procedure itself, (! p) denotesthosebehaviorswhose laststatesat-
which ensures theonly stones are placedinthepile. isfies p.
(Strictly, the procedure should also ensure that the pile is (? p ) denotes those behaviors whose first statesat-
initially empty or contains nothing butstones.) isfies p.
The procedure also captures heuristic knowledge in that (# p) denotes those behaviors all of whose states sat-
earlier actions may make subsequent actions more likely isfy p.
tosucceed.Forexample,theslingshotmayrequireacertain
sizeand weight of stone; however, instead of this being rep Conjunction and disjunction of action descriptions denote
resented as an explicit test that precedes the shooting ac- behavior-set intersection and union, respectively.
tion, it is represented implicitly by the context established Finally,weareinthepositiontogiveameaningtoprocess
by the procedure. In this case, the assumption is that any descriptions. Each process description will be takento de-
stone thatcan possibly be gathered will most likelypossess note a set of successful behaviors and a set of failed be-
the appropriate characteristics. Note that thisdoes not af- haviors. To build a description of these behaviors, we first
fect the validity of the procedure;if a stone does nothave introduce the notion ofprocess applicability. A processP
the necessary properties, the action of shooting the sling- is said to be applicable to a goal (i.e., an action type) B for
shot will fail. a set of states S, if every behaviorin thesuccess setof Pthat
At first glance, it seems that the semantics of a process begins in a state s E S is also in B.
descrjption couldbe determined solely on the basis of suc- Now let n be a node in a process description P. An allowed
cessful behaviors which satisfy each of its subgoals. On behavior startingat node n is a sequence composed of be-
closer examination, however,it becomes clear that this will haviors of processes applicable to the goals labeling the
not quite do.For example, if a nodehas multiple outgoing arcs emanating from n. Each allowed behavior represents
arcs (such as nodes N1 and N4 in Fig. 2) we need t o allow a series of attempts by applicable processes to transit an arc
several of these arcs to be tried until one is found suc- leaving n, until one succeeds or they all fail. Thus the set
cessful. This is exactly the sort of behavior required of any of allowed behaviors starting at a noden can be partitioned
useful conditional plan or program; iftest a on one branch into two sets: those representing successful transits to a
ofaconditionalfails(returnsfalse),itisnecessarytotryother succeeding node, and those that represent failures to leave
branches of the conditional. Similarly, in many real-world the node. The first set is denoted by succ(n,a). Each of its
situations, it is often desirable to allow multiple attempts behaviors must be a sequence of unsuccessful attempts by
to achieve a goal before relinquishing that goal (for ex- processes applicable to goals on arcs emanating from n,
ample, if a stone i s accidently dropped when tryingto pick followed by a behavior of an applicable process that suc-
it from the pile). The problem with failed attempts, how- ceeds for some arc a. The secondset, fail(n), consists of the
ever, i s that they may change the state of the world.Thus null behavior along with those behaviors composed only
to obtain a propersemantics, pathsthrough a process net- of failed attempts of applicableprocesses.

CEORCEFFANDIANSKY:PROC.EDURALKNOWLEDGE 1387
Authorized licensed use limited to: UNIVERSITY OF ESSEX. Downloaded on January 12,2023 at 18:12:35 UTC from IEEE Xplore. Restrictions apply.
 Given thesetwo types of allowedbehaviors, we can then Noticethat,whilethesemanticsgivenaboveallowsformul-
recursively define thesuccess and failuresets for a node n, tiple attempts to achieve the goals exiting any given mode,
denoted S(n)and F(n), respectively, as follows:6 it does not allow for backtracking t o previous nodesin the
net.
1) If n is a final node, thenS(n)and F(n) are both empty.
Now that we have given an interpretation forprocess de-
2) I f n has arcs a; to nodes mi, 1 5 i 5 k, then
scriptions, we arefinally in a position tospecify the mean-
S(n) = U;succ(n, ai).S(mi)
ing of a set of process assertions. Consider a process as-
and
sertion c ( P)g. This assertion is actually a requirement of
F(n) = U { fai/(n), U;succ(n, a;).F(m;)}.
the following form: foreach behavior b in thesuccess set
The success and failure sets of a process description Pare denoted byP, if thefirst state of b satisfies c, then b satisfies
then taken to be the success and failure sets, respectively, g. This requirement must be met by all process assertions.
of the initial node ofP.
As an example, consider theprocess networks shownin
V. OPERATIONAL
SEMANTICS
Fig. 3 where thearcs are labeledwith applicable processes.
Processassertions provideawayof describingtheeffects
of actions in some dynamic problem domain. Buthow can
A
a system or "agent" use this knowledge to achieve its goals?
That is, we currentlyhave a knowledge representation that
allows us to state certain properties about actions and what
behaviors constitute whatactions. We have not explained,
P 1: however, how an agent's wanting something can provide
a rationale for or cause an agent to act in a certain way.
One way to view the causal connection between rea-
soning and action is as an interpreterthat takes goalsas well
as knowledge about thestate of the worldas input and, as
a result, forms intentions to perform certain actions and
n
then acts accordingly. An abstract representation of such
an interpreter may be consideredto be the operationalse-
mantics ofthe knowledge representationlanguage. In this
section we provide a description of such an interpreter.
To ground our interpreter in some executable frame-
work, we must make certain assumptions. First of all, if a
P2: system is to be able to achieve its goals, it must be ableto
bring about certainactions, and thus beable t o affect the
course of behavior. Thus we assume a system containing
certain primitiveprocesses capable of activating various ex-
ternal effectors. Thesystem must also be ablet o sense the
world to theextent of determining the success or failure
of primitive processes-indeed, this is the onlyway it can
sense the state of the world.
Given these capabilities, the system tries to achieve i t s
Fig. 3. Sample process networks. goals by applying the following interpreter to applicable
processes.'The interpreter works by exploring paths from
a given node n in a process description P in a depth-first
For a process A, let A denote the set of i t s successful be- manner. To transit an arc, the interpreter unifies the cor-
haviors, andAFthe set of its failed behaviors. Thenthe suc-
responding arc assertion with the effects of the set of all
cess and failure sets for each of theprocess networks in Fig. process descriptions, andexecutes a set of the unifying pro-
3 may be described as follows:' cesses, one at a time, until oneterminates satisfactorily. I f
PI: there are no matchingprocesses, or none of the matching
processes on any of the outgoingarcs are successful, the
execution ofP fails. Note that the preconditioneach of pro-
cess must be satisfied when it is applied, in order for it to
P2: be truly applicable.
function successful (P n)
if (is-end-node n) then
return true
?f w, = 51, * . . , sk and w, = sk, . . , s,, then w, . w, =
*
else
s,, . . ,s ~ - sk, . . . ,s,. This operation is extended to sets
~ ,s k + , ,
of sequences in the usual way. Note that this formulation allows
a single state to satisfy a sequence of goals.
'The notation used is that for standard regular expressions. The qhis interpreter is very similar to theparsers and generators used
+
symbols * and denote zeroor more and one or more repetitions, for Augmented Transition Networks [29]. It differs in the amount
respectively. The symbol 1 is used to denote a choice between al- of backtracking allowed and in theuse of unification to matcharc
ternatives, e.g., (AIS) denotes a behavior of form A or 6. labels and networks.

1388 PROCEEDINGS OF THEIEEE, VOL. 74, NO. 10, OCTOBER 1986

Authorized licensed use limited to: UNIVERSITY OF ESSEX. Downloaded on January 12,2023 at 18:12:35 UTC from IEEE Xplore. Restrictions apply.
 arc-set := (outgoing-arcs n) Note that wehave made no assumptions about whether
pr-aset := (processes-that-unify arc-set) a process will succeed or fail-this is determined solely by
do until (empty pr-a-set) theenvironment. As discussed earlier,in thereal world, the
pr-a := (select pr-a-set) success or failure of processes simplycannot always be pre-
pr := (process pr-a) dicted. Thus the above interpreter must be embedded in
a := (arc pr-a) an environment in order to be truly useful. Without this,
if (satisfied (precondition pr)) then the operational semantics given above would be of little
if (successful pr (start-node pr))then interest: it would produce just one possible success-setfor
return (successful P (terminating-node a)) a given process or goal without any expectation that this
pr-a-set := (procesethat-unify arc-set) behavior could be realized. However, because the inter-
enddo preter is actually operating using a mixed planning/exe-
return false cution strategy, the environmentitself determinesprocess
end-function success or failure. This is quite different from standard AI
planning systems, where success of primitiveactions is as-
The function processes-that-unify takes a set of arcs and
sumed. It is also quite different from the operational se-
returns the set of processes that unify with some arc in the
mantics of pure Prolog, though would be similar to a se-
set, along with thespecific arc with whicheach unifies. The
mantics for Prolog with input and outputstreams.
functions process and arc select out the process instance
Of course, if wedid have additional knowledge about the
and corresponding arc from each element of this set. The
state of the environment and the success or failure of the
function select selects an element from a set. The order in
primitive actions, we could use the above interpreter in a
which selections are made is called the selection rule. We
pure planning mode. However, the inclusion of Po,R,A in
call the rule governing the number of times a process may
PDwould be, in general, strict. That is, the interpreter may
be tried the application rule (for this particular interpreter,
not achieve some given goal even when, according to the
the application ruleis embodied in the functionprocesses-
declarative semantics, there exists a way t o achieve it. This
that-~nify).~The function return returns from the enclosing
is partly because the interpreterfixes the selection rule and
function, not just the enclosing do. The system starts by ex-
application rule.Even by allowingall possible selection and
ecuting a process description witha singlearc labeled with
application rules, however, we would still not attain com-
the initial goal.
pleteness.The problem isthatthe interpreter does not have
Of course, it i s important that the operational and de-
the machinery to deduce facts about world state that can
clarative semantics be consistent with each other. The de-
be inferred using the declarative semantics. If an inter-
clarative semantics definesa set of behaviors for each
preter were capableof deducing all possible behaviors of
process. Theoperational semantics also defines aset of be-
a process from its description, andif it could also arbitrarily
haviors for each process, but this set depends on the se-
combine processes to generate any achievable behavior,
lection and application rules used in the above algorithm.
that interpreterwould also be ableto generate any behavior
Let Po be theset of successful behaviors for a process Pas
in PD. It i s clear that suchan interpreter wouldbe extremely
given by thedeclarative semantics, and letPo,R,Abe theset
difficult (if not impossible) to construct. However, in the
of successful behaviors for P as given by the operational
next section we provide a limited set of proof rules for de-
semantics for selection rule R and application rule A. It is
ducing facts about process behaviors as well as for com-
not difficult to show thatPO,R,AC Po. This means that any
bining processes to achieve particular effects.
behavior generated bythe interpreter givenabove will sat-
isfy the declarative semantics. The proof involves showing
that both thesuccess set and failureset of aprocess under VI. ACTION DECOMPOSITION RULES
the operationalsemantics are eacha subset of the success
As described above, the operational semantics we have
set and failure set, respectively, of the process under the
provided is actually not as strong as it could be. For ex-
declarative semantics. This can be done using double in-
ample, if an arc is labeled with a goal of the form(! ( p v q)),
duction, first, on the number of processes that are applied
wecandeterminefromthedeclarativesemanticsthatapro-
at a node, and second, on the length of a particular path
cess with effect p (or effect q) will be applicable (assuming
through theprocess (where lengthis measured in number
its preconditions are satisfied). The interpreter given above,
of nodes in thepath). The proof is straightforward once it
however, cannot make this determination.
is recognized thatany path resulting from use of a selection
One way of strengthening our interpreter is to provide
rule R and an application rule A will automatically be one
it with additional proof rules about the behavior of pro-
of the paths covered by the declarative semantics, and that
cesses. For example, we might use standard rules of logic
any sequence of process attempts (as well as primitive ac-
along with proof rules such as the following:
tions) will be considered successful (or a failure) both de-
claratively and operationally. c l ( P ) g l A c2(P)g2 = ( c l A c2)(P)(gl A 82)
cl(P)gl V c2(P)g2 3 (cl A cZ)(p)(gl V g2).
'In a practical implementation of the operational semantics, it
is usually best to use an application rule that tries each matching We can also devise additional rules for combining pro-
process exactly once. This allows the realizationof all the control cesses. As before, we use the notation c(P)g to mean that
constructs of standard programming languages while meetingrea- every successful behavior of P whose first state satisfies c
sonable bounds on time resources. However, variations in which
each process i s tried multipletimes could be incorporated without also satisfiesthe temporalassertion g. However, we extend
conflicting with the declarative semantics of process character- the notation to failed
behaviors as well, using assertions of
izations. the formc(P),g to describe theeffects of failed behaviors.

SEORCEFF AND IANSKY: PROCEDURALKNOWLEDGE 1389

Authorized licensed use limited to: UNIVERSITY OF ESSEX. Downloaded on January 12,2023 at 18:12:35 UTC from IEEE Xplore. Restrictions apply.
The symbols”;”and ’‘I” represent sequential composition wayprocedurescan beinvoked.Theseadditionsenablethe
and [nondeterministic] branching, respectively. system to exhibit not only goal-directedbehavior, but be-
Conjunctive Testing havior that is reactive to particular situations.
The PRS system also makesextensive use of worldstates
c(Pl)(?pA!C’A(#QV#(~9)))
and actions that referto an agent’s internal cognitive com-
c’( P2) (? 9) ponents. These “metalevel” states and actions are manip-
C(P1 ;p2) (? ( p A 9)) ulated by thesystem in thesame way it handles states and
actions thatdeal solely with the outside world. They enable
Conjunctive Achievement
the system to formgoals or react t o situations thatdeal with
c(P1) (! p A ! C’) the system’s internal workings-for example, t o figure out
c’(P2>(! 9 A # p ) how to choose between multiple applicable procedures fo
a particular task, how to establish new desires, beliefs, or
C(P1 ; P 2 ) (! ( p A 9))
intentions based o n particular situations, and so on. All of
Disjunctive Testing this metalevel reasoning, however, is donewithin thesame
c(P,)(? p ) formal contextin which reasoning about external the world
C(P2) (? 9) is done-i.e., in the context of the formalism presented in
C(Pl)F((# 9 V (19)) A C)
this paper.
c ( P ~ ) F ( ( p# V A ! c)
The overall structure of a procedural reasoning system
is shown in Fig. 4. The system consists of a database con-
C(PlIP2)(? ( p v 9)) taining currently knownfacts (or beliefs) about the world,
Disjunctive Achievement a set of current goals (tasks) to be accomplished, a set of
process assertions (plans) that described procedures for
C(P1) (! p ) achieving given goals or reacting to particular situations,
C(P2) (! 9) and an interpreter(inference mechanism) for manipulating
C(Pl)F(# c) these components. Atany moment in time, the system will
C(P2)FW c) also have a process stack that contains all currently active
C(PlIP2) (! ( p v 9)) processes. This stack can be viewedas the system‘s current
intentions. We now lookat these components in morede-
The aboverule for disjunctive achievement, for example, tail.
can be readas follows: if process Pl achievesp when begun The databaseis intended to describe the state of the world
in state c, and ifprocess P2achieves 9 when begun instate at the currentinstant, andthus contains onlystate descrip-
c, and if, in addition, failures of processes P1 and P2 leave tions. Its primaryfunction is t o keep track of facts about the
c intact, then processes Pl and P2can be combined intoa world state that can be inferredas consequences of process
disjunctive process that generates a behavior of the form executions. We also usethe database to provide thesystem
(! ( p v q))when begun in state c. with knowledge ofthe initial world state. A STRIPS-like rule
To obtain a new operationalsemantics that incorporates is used for determining the full effects of processes; that
these proof rules, the interpreter providedin the previous is, facts are assumed to remain unchanged throughout a
section would have to be modified to allow application of processunless we can infer otherwise. Updates to the
the proof rules when necessary. database require theuse of consistency maintenance pro-
cedures.
VII. SYSTEM DESCRIPTION As in the preceding sections, goals are represented by
We now describe a procedural reasoning system (PRS) action descriptions, andcan be viewedas specifying ade-
based on the theory describedin the previous sections. It sired behaviorof thesystem. This viewof goals as behaviors
goes beyond the theory inseveral ways, including thead- is unlike thatused by most planning systems. In such sys-
dition of a database of beliefs and an enhancement of the tems, goals can only be representedas descriptions of state

SystemlUvr Interpreter Shuttle

Interfaces (Reasoner) Subsystems
1
Controllen

Fig. 4. System structure.

1390 PROCEEDINGS OF THE IEEE, VOL. 74, NO. 10, OCTOBER 1986
Authorized licensed use limited to: UNIVERSITY OF ESSEX. Downloaded on January 12,2023 at 18:12:35 UTC from IEEE Xplore. Restrictions apply.
conditionstobeachieved.Theschemeadopted hereallows programming languages, this means that it is not necessary
us to express a much wider class of goals, including goals to decide before execution whichprocess variables are to
of maintenance(e.g., “achievep while maintaining q true”) count as input variables and which are to countas output
and goals with resource constraints (e.g., “achieve p with- variables.This isimportantfor providingflexibilityandease
out using more than one tool”). of verification. It also means that variables will not be un-
As indicated earlier, wehave alsoenhanced theway pro- necessarily bound, whichcan often beadvantageous in al-
cedures supplied to PRS may be invoked. Rather than just lowing difficultdecisions to be avoided or deferred. For ex-
being applicableto given goals, some procedures become ample, if we had a goal of the form (P $x) (where $x i s not
applicable when certain facts become known to the sys- bound), and a procedure for achieving (P $x) for all objects
tem-i.e., they are fact invoked. Fact-invoked procedures $x,we coulduse this procedure for achieving goal the with-
are particularly useful for creating a reactive system-i.e., out having to select a particular object to apply it to.
one that can change focus in reaction to particular situa- PRS also differsfromconventionalprogramming lan-
tions. Such procedures are usually associated with some guages in its more flexiblemeans of representingand using
implicit goal. For example, a fact-invoked procedure for procedural information. For example, procedures are not
putting out a fire might become applicablewhenever the “called” as in standard programming languages. Instead,
system notices that there i s a fire.Although this procedure they are invoked whenever they can contribute toaccom-
does not respond to any explicit goal per se, it actually plishing some goal or reacting to some situation. Just as
achieves an underlying implicit goal of all organisms-to procedurescannot becalled, neithercan theycall anyother
stay alive. Within the context of the formalism presented procedure;they can only specify what goalsare to be
in the precedingsections, a process assertion for a fact-in- achieved and in what order. This makes PRS procedures
voked procedure hasaprecondition that describesthecon- much more amenable to modular verification techniques.
dition under which it is applicable and an effect part that Another difference that sets PRS apart from standard pro-
matches all implicit goals of the system. This guarantees gramming languages is that it is not deterministic. For ex-
that each fact-invokedprocedurebecomesapplicable ample, several procedures may be relevant to a goal at any
whenever its precondition becomes true. one time, and the order in which they are chosen for ex-
The PRS interpreter runs the entiresystem. From a con- ecution may, in general, be nondeterministic.
ceptual viewpoint, it operates in a relatively simpleway. At We have implemented an experimental system basedon
any particular point in time, certain goals are active in the the ideas presented above. Theimplemented system iswrit-
system, and certain facts or beliefs are held in the system ten in LISP and runs on a Symbolics 3600 machine. User
database. Given these goals and facts, a subset of the pro- interactionoccursviaagraphicalpackagethatallowsdirect
cedures in the system (both fact-invoked and goal-invoked) entry and manipulation of process networks.
will be applicable. One of these procedures will then be
chosen for execution. In the course of transitting the body
VIII. SAMPLE PROBLEMDOMAINS
of the chosen procedure, new goals will be formulatedand
new facts will be derived. When new goals areadded to the A. Space Shuttle
goal stack, the interpreter checks to see if any new pro-
cedures are relevant, selects one,and executes it. Likewise, One area in which advanced automation can be of par-
whenever a new fact is added to the database, the inter- ticular practical benefit is fault isolation and diagnosis in
preter will perform appropriate consistency-maintenance complex systems. PRS is particularly suited to this kind of
operations on thedatabase and possibly activate newly ap- application not only because a diagnostic domain is dy-
plicable procedures. namic, requiring quickresponse to faults, but also because
Because the system is repeatedly assessing its current set much of diagnostic knowledge is specifically procedural in
of goals, beliefs, and the applicability of procedures, the nature. In this section we describe onesuch application-
system exhi bits avery reactive form of behavior, ratherthan diagnosis of the Reaction Control System (RCS) of NASA‘s
being merely goal-driven. For example, when a new fact space shuttle. The structure of the RCS module i s depicted
enters the system database, execution of the current pro- in Fig. 5. Sample malfunction procedures from the NASA
cess network might be suspended, with a new relevant pro- diagnostic manuals are shown in Fig. 6.
cess network taking over. One of theways the system re- The manner in which we have represented procedures
solves which procedures to execute at any given timeis by for our RCS application reflects what we have said in the
using other metalevel process networks. These metalevel preceding sections-i.e., that actions andtests must be rep-
procedures are manipulated and invoked by the system in resented by whatever condition they achieve or test for,
the same way as any other procedure. However, they re- rather than by some arbitrary name. For example, there
spond to facts and goals pertaining to the system itself, exist severalmalfunction procedures for lowering the pres-
rather than just those of the application domain. For ex- sure in tanks that have high pressure readings, and like-
ample, one typical metalevel procedure might respond to wise, raising the pressure in tanks with low pressure. Cur-
a goal of the form: (CHOOSE-BEST-PROCESS $goal $list-ofpro- rently,theNASAdiagnosticproceduresforthesetasksmake
cedures). Besides the task of process selection, metalevel explicit calls to particular procedures that raise and lower
procedures can also be usedto combine process networks tank pressure. Whenever the desired methods for altering
in order to achieve composite goals. For example, metalevel tank pressure change, these procedure calls also have to
procedures are used in the current system to apply some be explicitlychanged.
of the proof rules described in Section VI. Our methodology for invoking proceduresobviates the
As in the interpreterof Section V, unification is used to need for such changes; goals t o lower orraise tank pressure
determine whether or not a givenprocess matches a given may be postedas such-any applicable procedure maythen
goal or database fact. Justas in Prolog, and unlikestandard respond. In fact, for this particular example, the goal un-

CEORGEFF AND LANSKY: PROCEDURAL KNOWLEDGE 1391

Authorized licensed use limited to: UNIVERSITY OF ESSEX. Downloaded on January 12,2023 at 18:12:35 UTC from IEEE Xplore. Restrictions apply.
 FWD RCS

AFT RCS
n
meter +
IGNC 23 RCS GNC SYS SUMM 2 I + G E l

+ EFS. GNC SYS SUMM 2

8
METER +
TK ISOL TK ISOL
GNC 23 RCS 1 I2 3/4/5

EFS. GNC SYS SUMM 2 TKp;y L R L R L

U U U D R
D D D
F F F

XFEED Y Y Y Y Y
U U D U D XFEED
1 I2 A 0 A D 31415

Fig. 5. Thereaction control system.

derlying the pressure alterations may simply be to "nor- (TYPEHE-TANK HET.I.I.I)

ma1ize"the pressure of thetank. Invoking procedureso n (PART-OFHET.~.I HEP.~.~)
the basis of desiredeffects resultsin a much more modular (TYPE HE-TANK HET.l.2.1)
and useful way of constructing large systems. Given a set (PART-OF HET.l.l.l HEP.l.2)
of procedures associated with the actual goal that they
Two types of structural facts have been used for thisa p
achieve, the procedures may be reused in other circum-
plication-TYPEfacts, which declare specific components or
stances in which they might beuseful, or easily replaced
subsystems and assign tothem uniqueidentifiers, andPART-
by other procedures that achieve their particular goal in a
OF facts, which state which components are part of which
better way.
subsystems.Forexample, (TYPE RCS F RCS.I) declares the
7) RCS Database: Our first task in encoding theRCS a p
entire frontRCS and assigns it the identifierRcs.1. Each RCS
plication was to capture the structure of thephysical RCS
containstwo helium pressurization subsystems,oneforthe
system (depicted in Fig. 5) as a set of database facts. Once
oxidant partof thesystem, theother for the fuel subsystem.
inserted into thesystem database,these facts are useddur-
For the system Rcs.1 these are labeledasHEP.1.1 and HEP.~.~,
ing fault diagnosis to identify particular components of the
respectively.Finally,each heliumpressurization system
system and their properties. For example, a sample set of
contains its own helium tank.
structural facts are given below.
Once we encode the structure ofRCS thein this fashion,
(TYPE RCS F RCS.l) the diagnostic procedurescan make useof this information
(TYPE HE-PRESSURIZATION ox H E P . ~ . ~ ) to perform what might be considered simple common-
(TYPE HE-PRESSURIZATION FUEL HEP.1.2) sense tasks for anastronaut. For example, if a malfunction
(PART-OF HEP.l.l
RCS.l) procedurehasthetest"lstheoxidanthe1iumtankpressure
(PART-OF HEP.1.2
RCS.l) greater than the fuel helium tank pressure for the front

1392 PROCEEDINGS OF THE IEEE, VOL. 74, NO. 10, OCTOBER 1986

Authorized licensed use limited to: UNIVERSITY OF ESSEX. Downloaded on January 12,2023 at 18:12:35 UTC from IEEE Xplore. Restrictions apply.
 I RCS JET @ I t GNC SYS
ll GNC 23 RCS SUMM 2 and meter
RCS JET FAIL (ON) disagree, He Pin-
I BACKUP Ciul
ALARM 1 Affected MANF ISOL - CLkb-CL),
then GPC il MANF 5
sbumentation

2. GO to MALF. LS. 10.la

F RCS D JET
or
F RCS F JET
12
1-
or RCS JET FAIL (LEAK)
F RCS L JET If GNC SYS
1. Check RCS FU and OXlD quantity diverging: SUMM 2 and meter
or If diverging affected, MANF ISOL- CL(tb-CL).
F RCS R JET agree but no1 dew,
then GPC if MANF 5 qty input inslrumenl
or z GO to MALF,&s, 10.ta 1231
F RCS U JET
or
L RCS A JET
A 1I failure Do not use
[GNC 23 RCS] to
crosscheck meter
U RCS JET FAIL (OFF)
L RCS D JET
or 1 GO to MALF. LS, 10 l a m
L RCS L JET
or 4
l
J
GNC SYS SUMM 2
L RCS U JET
U RCS LEAK ISOL
R RCS A JET
or
II FU or OXlD TK P high, go lo RCS TK PRESS (FU or OX) HIGH, 1171
R RCS D JET \I FU and OXlD TK P low, check FU (OXID) He P (CRT 8 meler) 0
or
R RCS R JET
U
R RCS U JET
I' If decreasing, go to slep 1
II not decreasing go IO RCS TK PRESS (FU or OX) LOW,
If FU or OXID TK P normal.
Check FU(0XID) He P (CRT 8 meter) decr: @@
[161step 2

1. DAP. hee &in

If Secure RCS
Primary Jel OX 11
jeclor Temp < 30 2 Perform affected RCS SECURE, , then.
3. If affected RCS receiving XFEEDA'CNECT, go lo step 6
Primary Jet FU Ir
jectorTemp < 20 Check Single MANF.
Vernier Jet In- 4 . Check only one MANF P decr
jector Temp < 13 If decr, relurn to normal m f g except leave leaking MANF dosed >>
Flre Command Check PRPLT TK Leg (check two MANF P):
and no PC 5. Check MANF 1.2 or MANF 3,4 P decr
Discrete II two MANF P decr, relurn lo noma1 config except leave aflected TK
No Fire Comman ISOL (112 u 3415). MANFs. and mrrespmding XFEED valves dosed
with Jet Drlver 11346, go lo LOSS OF VERNIERS (ORB OPS. L S ) >>
output
Check He TK:
W OF0801 6 Check He P decr
If decr, call MCC for use of LEAKING He RCS BURN, MALF. L S .
SSR-5. When an mnbd required:
If Aft RCS, I'CNECT horn OMS or 119]
then open all MANFs. Prior to deorbil TIG return lo sba' ht RCS feed.

I BACKUP ChV
ALARM d
When He TK P < 556 perform I'CNECT f r o m OMS, 1.8 or
AI EI perform XFEED from g w d RCS. (1111 or 1.12 >>
If Fwd RCS. relum to normal m f
1-1
When He P < 556, owMe FWD MANFs STAT
1191

clcsed,perform LOSS OF VERNIERS. (ORB OPS. K S ) then

ovenide open Mor to deorbil. When PRPLT TK P < 190,
II. perlom RCS SECURE (FWD) >>
F(L,R) RCS A
OX-FU > 12.6%

Fig. 6. Some RCS malfunctionprocedures.

RCS?" the test can be represented in a way that is imper- 2) RCS Process: We will now concentrate on the pro-
vious to system reconfiguration, is not hard-wired to par- cedure called RCS JET FAIL (ON), which can be seen as Step
ticular identifiers, andcan be usedfor any RCS.Thisis done 1.1of ProcedurelO.1, aswell as IO.la(a portion of the entire
using unification-matching database facts againstqueries malfunction procedure is shown in Fig. 7).Notice how di-
composed as logical combinations of atomic formulas. In agnosticconclusions(such as"JETDRIVER FAILED-ON
this case, the query wouldhave the following form: ELECTRICALLY") are displayed in highlighted boxes.
PRS uses several processes to implement this diagnostic
(? ((TYPE RCS F srcs-id) A
procedure. The main top-levelprocess for dealing with the
(TYPE HE-PRESSURIZATION o x ghep-ox) A
"JET FAIL (ON)" failure is called JET-FAIL-ON and is shown in
(PART-OF shep-ox
srcs-id) A
Fig. 8.This processis fact invoked-that is, it respondswhen
(TYPE HE-PRESSURIZATION shep-fuel) A
FUEL
the system notices that certainlights, alarms, and computer
(PART-OF shep-fuel grcs-id) A
monitor readings appear. Its precondition has the form:
(TYPE HE-TANK $he-ox-tank) A
(PART-OF $he-ox-tank shep-ox) A
(LIGHT RCS-JET) A (ALARM BACKUP-CW) A
(TYPE HE-TANK she-fuel-tank) A
(FAULT srcs-id RCS sjet-id JET) A
(PART-OF $he-fuel-tankshep-fuel) A (JETFAIL-INDICATOR ON smanf-id).
(PRESSURE she-ox-tanksox-press) A
(PRESSURE $he-fuel-tank$fuel-press) A In order to get JET-FAIL-ON running, these four facts (with in-
( > sox-press
sfuel-press))). stantiations of the three variables wcs-id, sjet-id, srnanf-

CEORGEFF A N D LANSKY:PROCEDURALKNOWLEDGE 1393

Authorized licensed use limited to: UNIVERSITY OF ESSEX. Downloaded on January 12,2023 at 18:12:35 UTC from IEEE Xplore. Restrictions apply.
 11 1. Affected MANF ISOL CLItb-CL),
~

p
then GPC if MANF 5
BACKUP C m 2 GO to MAG, RCS. 10.1a

10.la

I RCS Jet FAIL-ON

1YES

ELECTRICALLY
t
I
I

(ORB OPS)

DRIVER
FAILED-ON
VERNIERS
(ORB OPS)
ELECTRICALLY

Override to CL status
affected M a n f and all
o(her Mank which
share same RID
e RCS FWD(L.R) I E M
r)
~

l(2.3) EXEC
MANF VLV OVRD -
!?(LR) RCS MANF ITEM 42(43.44,45)
1(2.3,4) ISOL-

Affected Jet R I D
DRIVER - OFF

Fig. 7. RCS IET-FAIL-(ON)malfunctionprocedure.

id) must be addedto the system database. For example,

we in Fig. 7,which reads: “Affected MANF ISOL-CL(tb-CL),then
might add the following facts: GPC if MANF 5.” Notice how we have abstracted the overall
goalor intentof this step (to close the manifold) from a par-
(LIGHT RCS-JET) ticular instruction inthemalfunction bookwhich onlystates
(ALARM BACKUP-CW) how t o achieve the goal.
(FAULT
RCS.1
RCS THR.l.l JET) In this case, there are actually two different ways of
(JETFAIL-INDICATOR ON MIV.l.l.l). achieving a closed manifold: for allmanifolds, a talk-back
switch is set to the closed position, but for vernier mani-
This tells the system that there is an actual malfunction in folds (type5 manifolds), a setting must also be madeon the
a specificRCS subsystem, jet, and manifold. The system will computer console. These two ways of achieving a behavior
then react and apply the JET-FAIL-ON process. of form (! (CLosED-MANIFoLD smanf-id)) are reflected in the
Starting at its START node, JET-FAIL-ON will proceed and try two proceduresshown in Fig. 9, CLOSED-MANIFOLD and
to traverse its first edge, labeled with the goal expression CLOSED-MANIFOLD-VERNIER. Each responds to a goalof the form
(1 (CLOSED-MANIFOLD smanf-id)). In otherwords, the sys- (I (CLOSED-MANIFOLDsmanf-id)). However, their precondi-
tem must find some way to close the given manifold.This tionsconstrain theirappliCabilityfUrther-CLOSED-MANlFOLD
corresponds to the firststep of the malfunction procedure will only be truly applicablei f the manifold in question is

1394 PROCEEDINGS OF THEIEEE,VOL. 74, NO. 10, OCTOBER 1986

Authorized licensed use limited to: UNIVERSITY OF ESSEX. Downloaded on January 12,2023 at 18:12:35 UTC from IEEE Xplore. Restrictions apply.
Precondition: (LIGHT a c c l n j h (AL" EACKUPCW) h
(FAULT % C U D RCS SIET-ID
JET) h
(JETFAIL-INDIUTOR ON WNF-ID) JET-FAIL-ON
Effect:

(7 (- (> SP-ox 130)))

(UOU-INRIT-PAR*U-FAIL FAIL-HIW SET-ID))

Fig. 8. JET-FAIL-ON process.

not of type 5, and CLOSED-MANIFOLD-VERNIER will only bea p could have realized that its goal to close the manifold had
plicable if the manifoldis of type 5. In situations in which already been achieved.
more than oneprocess i s truly applicable t o a given goal, We continue now with one more step in the execution
metalevel processes are usedto resolve which is most use- of theJET-FAIL-ON process. If thegoal t o close the manifold
ful. actually succeeds, the system will then move on tonext the
Of course, given the semantics of process assertions, node and choose anew outgoingarc to traverse. One pos-
there is yet another way to achieve (! (CLOSED-MANIFOLD sible choice might be the arc labeled (7 (7 (HIGH-USAGE
smanf-id)). In particular, a goal of the form (! P) will auto- sRcsid)))-i.e., our goal is to determine whether there is not
matically be achieved if the system already believes that P high usage in theaffected RCS. To handle a goal of this form
is true. for this case, if thesystem already has in its database the system will first check to see if thereare any database
a fact of the form(CLOSED-MANIFOLD MIv.1.1.1), a goal of the facts or processes that match this goal precisely. Because
form (1 (CLOSED-MANIFOLD MIv.I.1.1)) will automatically suc- we can have negated factsin the system database, it is pos-
ceed-no executions of theprocesses CLOSED-MANIFOLD and sible that a fact of form (7 (HIGH-USAGE Rcs.1)) is present
CLOSED-MANIFOLD-VERNIER need be undertaken. in thedatabase (for thesake of argumentwe have assumed
It is precisely the lack of this kind ofgoal semantics and that srcs-id is bound toRcs.1). Similarly, there may be a pro-
reasoning ability that caused a recent space shuttle flight cess with an invocation part that indicates it i s useful for
to abort. Although the shuttle system knew thata particular precisely a goal of the form (? (1 (HIGH-USAGE srcs-id))).
manifold was closed, it found itself unable to proceed when If a matching database fact or a successful matching pro-
an instruction of the form"close the manifold" was given cessisfound,thenthesystemwillattempttosatisfythegoal
to it. This is because all of the manifold-closing procedures in these ways. However, if nosuch factor matchingprocess
availablepresumedan openmanifold-they could notclose is present, the system will try to achieve the goal using any
a manifold that was already closed! If the procedures had other means at i t s disposal.
beenwrittenintermsofthegoalstobeaccomplished,rather Forgoals composedofcertainnegated predicates, a
than as fixed hard-wired procedure calls, the shuttlesystem metalevel processis availablewhich triesto achieve the goal

GEORCEFF AND LANSKY: PROCEDURAL KNOWLEDGE 1395

Authorized licensed use limited to: UNIVERSITY OF ESSEX. Downloaded on January 12,2023 at 18:12:35 UTC from IEEE Xplore. Restrictions apply.
 Precondition: (NE MANF.ISOL-VALVE s WF-IO)
Effect: (! (CLOSEDMANIFOLDIMANF.ID))

CLOSED-MANIFOLD

(I (ISOLATED-UANIFOLDSWITCH CLOSED --ID))

4
Q
Precondition: (TYPE WF-ISOL-VALVE w WNF-ID) A (+ w 5)
Effect: (! ( C L O K B M 4 N I K X D IMANF-IO))

CLOSED-MANIFOLD-VERNIER

6 (=> ((CLOSECI-MANIFOLD --ID) -

(- (OPEKD-UANIFOUI $MAW-ID))))

Fig. 9. Process for closing a manifold.

using the “negationas failure” rule[IS].In other words, for could not be retrieved. In another scenario, the robotmay
a goal of form (! (1 P)) or (? ( 1 P)), the metalevel pro- be in theprocess of retrieving the wrench when it notices
cess will try toachieve (! p) (or (? p)), and if it fails to doso, a malfunction light for one of the jets in an RCS module of
will assume that the original negated goal has succeeded. the space station. It reasons that this is of higher priority
Inourcurrent system, this is preciselyhowthe goal than retrievingawrenchandsetsaboutdiagnosingthefault
( I (1 (HIGH-USAGE srcs-id)) is handled.Othermetalevel and correcting it. After having done this, it continues with
processes also exist for achieving a conjunct ofgoals or a its original task, finally telling the astronaut what has h a p
disjunct of goals. pened.
To accomplish these tasks the robot must notonly beable
B. Autonomous Robot to create and executeplans, but must bewilling to interrupt
A second interesting applicationof PRS is i n the control or abandon a plan when circumstances demand it. Since
of autonomous robots. Ourexperimentationin this domain other agents can move obstacles andissue demands even
is being done usingSRI International’s new robot, Flakey. as the robotis planning, andsince its view of the world can
To effectively tackle this problem,we had to use multiple, change as fast as the robot itself is moving, performance
concurrentlyactivePRSmodules,eachconsistingof itsown of thetask requires a robot whichis perceptive and highly
database, goal stack, and processes that monitor and con- reactive as well as goal directed.
trol different aspects of the robot‘s activity. The way we have structured the processes for this do-
As our objective, we envisaged the robotin aspace sta- main has actually conformed somewhat t o Brooks’ notion
tion acting as an astronaut’s assistant. When asked to get [3] of a vertical decomposition of robot functions (in con-
a wrench, for example, the robot works out where the trast to the traditional horizontal decomposition into func-
wrench is kept, plansa route to get it, and goes there. If the tional modules).The top-level robot module is used to per-
wrench is not there the robot reasons further about how form higher level cognitive functions: overall route plannin
to obtain information on its whereabouts, and finally re- and high-level guidance.The lower the level of a module,
turns to the astronaut with the wrench or explains why it the more primitivei t s function. Below the highest levelare

1396 PROCEEDINGS OF THE IEEE, VOL. 74, NO. 10, O C T O B E R 1986

Authorized licensed use limited to: UNIVERSITY OF ESSEX. Downloaded on January 12,2023 at 18:12:35 UTC from IEEE Xplore. Restrictions apply.
modules which put together sonar sensory dataand figure on synchronizing theactivities of multipleagents hasbeen
out where“walls” and “doors” are. Even lower level mod- done by Lansky [I41 and Stuart [24].
ulesreactivelymonitorthemorerudimentaryaspectsofthe
navigation process-reacting t o obstacles, maintaining a ACKNOWLEDGMENT
parallel bearing to the wall, getting back on course when
There have been a number of people involved in thede-
veering takes place, etc.
sign, implementation, and testing of PRS, including P. Bes-
Our present version of the robot application system is
siere, M. Schoppers, 1. Singer, and M.Tyson. We are most
more fully describedelsewhere [22]. Currently, the robot’s
grateful for their contributions.
model of theexternal world is particularlysimple: apart from
topological knowledge about hallways and rooms, thebe-
liefs of the robot
consist solelyof i t s most recentsonar read- REFERENCES
ings, various velocities and accelerations, and some indi- J. F. Allen, “A general model of action and time,” Computer
cators regarding the status of simulated external systems Science Rep. TR 97,Univ. of Rochester, Rochester, NY, 1981.
-, “Maintaining knowledge about temporal intervals,”
(such as the RCS module). Of course, any realistic appli-
Commun. ACM, vol. 26, pp. 832-843,1983.
cation of the system would require that the robot be ca- R. A. Brooks, “A robust layered control system for a mobile
pable of building and storing much more complex models robot,” A.I. Memo864, MITArtificial Intell.Lab., Cambridge,
of the world around it. MA, 1985.
K. M. Chandy and J. Misra, “How processes learn,” in Proc.
4th ACMSymp. on Principles o f Distributed Computing,1985.
IX. CONCLUSIONS W. F. Clocksin and C. S. Mellish,Programming in Prolog.
Berlin, FRC: Springer-Verlag, 1984.
We have presented a model for action and a means for D. Davidson,Actions and Events. Oxford, England: Clar-
representingknowledgeaboutprocedures.Theimpor- endon, 1980.
tance of reasoning aboutprocesses rather than simplehis- R. E. Fikes and N. J. Nilsson, “STRIPS: A new approachto the
application of theorem proving to problem solving,”Artificial
tories or state sequences was stressed. In particular, wehave
lntell., vol. 2, pp. 189-208, 1971.
indicated the role that process failure plays in practical rea- M. P. Ceorgeff and U. Bonollo, “Procedural expert systems,”
soning. in Proc. 8th lnt. joint Conf. on Artificial lntelligence (Karls-
A declarative semantics for the representation was pro- ruhe, West Germany, 1983).
vided that allowsuser a to specify facts about processes and M. P. Ceorgeff, “A theoryof action for multiagent planning,”
in Proc. 4th Nat. Conf. on Artificial Intelligence (Austin, TX,
their behaviors. This semantics is important for providing 1984).
a model-theoretic basis to the knowledgerepresentation. M. P. Ceorgeff, A. L. Lansky, and P. Bessiere, “A procedural
We have also given an operational semantics that shows logic,” in Proc. 9th lnt. joint Conf. on Artificial Intelligence
how these facts canbe usedby an agent to achieve (or form (Los Angeles, CA, 1985).
M. P. Ceorgeff and A. L. Lansky, “A system for reasoning in
intentions toachieve) its goals. A critical feature of the in-
dynamicdomains: FauItdiagnosisonthespaceshuttle,”Tech.
terpreter, and one that distinguishes it in kind from most Note 375,Artificial Intelligence Center, SRI Int., Menlo Park,
existing AI planners, is that it is situated in an environment CA, 1985.
with which it interacts during the reasoning process. We C. C. Hendrix, “Modeling simultaneous actions and contin-
consider the partial hierarchical planning that results to be uous processes,” Artificial Intell., vol. 4, pp. 145-180, 1973.
C . A. R. Hoare, S. D. Brookes, and A. W. Roscoe, “A theory
an essential component of effective practical reasoning. of communicatingsequential processes,”Tech. Monograph
The knowledge representation we have described can PRC-16, Computing Lab., Oxford Univ., Oxford, England,
also be used for symbolic planning in the traditional sense, May 1981.
although we would need to provide additionalaxioms stat- A. L. Lansky, “Behavioral specification and planning for mul-
ing under what conditions primitive processes would be tiagent domains,”Tech. Note 360,Artificial Intelligence Cen-
ter, SRI Int., Menlo Park, CA, 1985.
successful. Indeed, the operators of many standard plan- J. W. Lloyd, Foundations o f Logic Programming (Symbolic
ning systems (such as NOAH [21], DEVISER [27], and SlPE Computation Series). Berlin, FRC: Springer-Verlag, 1984.
[281)can be viewedas restricted formsofprocess assertions. 1. McCarthy, “Programs with common sense,” in Semantic
Our formalism can alsobe viewedas an executable spec- Information Processing, M. Minsky, Ed. Cambridge, MA: MIT
Press, 1968.
ification language-that is, as a programming language that D. McDermott, “A temporal logic for reasoning about plans
allows a user to directly describe thebehaviors desired of and processes,” Computer Science Res. Rep. I%, Yale Univ.,
the system being constructed. The fact that the language New Haven, CT, 1981.
has a declarativesemantics allows facts about thebehavior R. C. Moore,”Reasoningabout knowledgeandaction,”Tech.
of thesystem to be stated and verified independently. The Note 191,Artificial Intelligence Center, SRI Int., Menlo Park,
CA, 1980.
operational semantics provides a means for directly exe- S. J.Rosenschein, “Plan synthesis: A logical perspective,” in
cuting these specifications to obtain the desired behavior. Proc. 7th lnt. Joint Conf. on Artificial Intelligence, pp. 331-
In this sense, the language has much in common with 337,1981.
-,“Formal theoriesof knowledge in AI and robotics,”Tech.
Prolog, except that is applies to dynamic domains instead
Note 362,Artificial Intelligence Center, SRI Int., Menlo Park,
of static domains. CA, 1985.
We have described a practical implementation of a sys- E. D. Sacerdoti, A Structure for PlansandBehavior. New York,
tem based on this model, and have shown how it can be NY: Elsevier-North Holland, 1977.
applied for fault diagnosis and in the control of autono- M. P. Ceorgeff, A. L. Lansky, and M. Schoppers, “Reasoning
mous robotsin highlydynamic situations.Althoughwe have and planning in dynamic domains: An experiment with an
autonomous robot,” Tech. Note 380, Artificial Intelligence
used parallel instances of PRSs within ourimplementation, Center, SRI Int., Menlo Park, CA, 1986.
we have yet to extend our formal model to deal with it. Some M. Stefik, “Planning with constraints,” Artificial lntell., vol.
work in this directionis descri bed byGeorgeff [9], and work 16,pp. 111-140, 1981.

GEORGEFF AND LANSKY: PROCEDURAL KNOWLEDGE 1397

Authorized licensed use limited to: UNIVERSITY OF ESSEX. Downloaded on January 12,2023 at 18:12:35 UTC from IEEE Xplore. Restrictions apply.
[24] C. Stuart, “An implementationofamulti-agentplan syn- Heights, NY, 1986.
chronizer using a temporal logic theorem prover,” in Proc. [27] S. Vere, “Planning i n time: Windows and durations for ac-
9th lnt. joint Conf. on Artificial lntelligence (Los Angeles, CA, tivities andgoals,” Tech. Rep., Jet PropulsionLab., Pasadena,
1985). CA, 1981.
[25] A. Tate, “Goal structure-Capturing the intent of plans,” in [28] D. E. Wilkins,“Domainindependentplanning: Represen-
Proc. 6th European Conf. on Artificial Intelligence, pp. 273- tation and plan generation,” Artificial Intell., vol.
22, pp. 269-
276,1984. 301, 1984.
[26] V. Nguyen and K. J. Perry, “Do we really know what knowl- [29] A.T. Woods, “Transition network grammar for natural lan-
edge is,” Tech. Note, IBM T.J. Watson Res. Cen., Yorktown guage analysis,” Commun. ACM, vol. 13, pp. 591-606, 1970.

1398 PROCEEDINGS OF THE IEEE, VOL. 74, NO. 10, OCTOBER 1986
Authorized licensed use limited to: UNIVERSITY OF ESSEX. Downloaded on January 12,2023 at 18:12:35 UTC from IEEE Xplore. Restrictions apply.