[OpenCyc.org Homepage] The OpenCyc Planner
Version 0.7
E-Mail Comments to: opencyc-doc@cyc.com

The OpenCyc Planner

1. Actions

2. Planner Rule Vocabulary
.2.1. #$PlanningDomainMicrotheory
.2.2. Preconditions
.2.3. Effects
.2.4. Complex Actions and Methods

3. Running The Planner

4. Further Reading on Planning

The OpenCyc Planner

The OpenCyc Planner is a reimplementation of the SHOP planner designed to directly access the Cyc Inference Engine. A planner is an inference engine optimized for reasoning about actions, events, and other activities in a dynamic world.

1. Actions

Actions are represented as formulas with instances of #$ActionPredicate as their operators. For example, if it is asserted that: 

(#$cleans #$Bob #$BobsRoomFloor)

this represents the fact that Bob is cleaning the floor of his room in the current context.

One uses the planner by giving it a high-level, possibly abstract action sentence as a goal. For example, 

(#$transport #$Bob #$AustinBergstromAirport)

given to the planner as a goal means that it should find a sequence of simple actions for getting Bob to the Austin Bergstrom International Airport.

For any context we shall consider instances of #$SimpleActionPredicate, a subcollection of #$ActionPredicate, to define the extent of primitive actions in that context. These are actions for which there are no decompositions. Every context should have a set of simple actions, since they give the vocabulary with which to express complete plans. If the plans generated are meant to be executed, then it makes sense for the simple actions in the domain to correspond with the simplest actions of the effector.

A plan consists of a linear sequence of sentences, whose operators are instances of #$SimpleActionPredicate. It is important to stress that context should be important in determining whether or not an action should be represented with a simple action predicate. Suppose we wanted to create a planning domain that could power a user application that would give driving directions between locations in Austin, TX. It would be inappropriate to have simple actions like #$turnKeyInIgnition, #$shiftGears, and #$changeLanes, since we can assume that most users of the application already know how to drive. Probably a better vocabulary would have simple action sentences like: 

(#$turnLeftAtIntersection (#$RoadIntersectionFn #$SanJacinto #$SixthStreet))
(#$followHighwayRouteUntilExit #$MopacExpressway #$MopacExit43)

2. Planner Rule Vocabulary

2.1. #$PlanningDomainMicrotheory

The planner takes as one of its inputs a microtheory that sets the context for the search. Planner rules using the vocabulary described above should be asserted in a microtheory that is an instance of #$PlanningDomainMicrotheory. Every #$genlMt of the context mt that is also an instance of #$PlanningDomainMicrotheory is relevant when the planner looks for applicable rules.

2.2. Preconditions

Simple actions can have preconditions. Preconditions are facts that must be true in the world in order for the particular action to be executable or applicable. In order to mop the floor of a room, you must be holding the mop, you must be in or standing next to the room, the floor can't be covered with carpeting, etc. These facts can all be represented with preconditions.

Usage: 

(#$preconditionFor-Props CONDITION ACTION)

Comment for #$preconditionFor-Props:

"A binary predicate which relates instances of ELSentence-Assertible to instances of ELSentence-Assertible, and which is used to state that one formula expresses a necessary precondition for the truth of another. (preconditionFor-Props COND PROP) means that PROP isn't true unless COND is true. Preconditions of various types are distinguished by the more specialized predicates legalPreconditionFor and causalPreconditionFor. See also sufficientFor-Props."

Example: 

       (#$preconditionFor-Props 
             (#$and (#$isa ?CLEANSER #$CleaningSubstance)
                    (#$possesses ?AGT ?CLEANSER)
                    (#$possesses ?AGT ?OBJECT))
             (#$cleans ?AGT ?OBJECT))

2.3. Effects

Simple actions are unique in a domain, since they are permitted to have effects. Effects are facts that are true in the world after an action occurs. We use positive literals to represent facts that are true in the world after the action is executed. We use negative literals to represent facts that are made untrue by the execution of the action.

We use the binary predicate #$effectOfAction-Props to represent literals.

Usage:

(#$effectOfAction-Props ACTION EFFECTS)

Comment for #$effectOfAction-Props:

"A binary predicate which relates instances of ELSentence-Assertible to instances of ELSentence-Assertible. (effectOfAction-Props ACTION-PROP PROP) means that the effect of ACTION-PROP, where ACTION-PROP is a proposition of the form (PRED . ARGS) and PRED is an instance of ActionPredicate, is PROP, where PROP is any proposition that describes the effect(s) of ACTION-PROP. Thus, effectOfAction-Props should be used only when the first argument is a proposition in which an ActionPredicate is used in the arg0 place."

Example: 

(#$effectOfAction-Props (#$cleans ?AGT ?OBJ) (#$not (#$dirtinessOfObject ?OBJ #$ALittleDirty))

Effects can also be conditional, meaning that the facts that are true after the action occurs may be dependent on what is already true. For rules like these, we use #$effectOfActionIf-Props.

Usage:

(#$effectOfActionIf-Props ACTION CONDITION EFFECTS)

Comment for #$effectOfActionIf-Props:

"A ternary predicate which relates three instances of ELSentence-Assertible. (effectOfActionIf-Props ACTION COND EFFECT) means that if COND is true in the context in which ACTION occurs, then ACTION makes EFFECT true. This predicate was designed to be used in the specification of planning domains (see PlanningDomainMicrotheory). ACTION should be an atomic sentence with an ActionPredicate as the formula operator (i.e. in the arg0 position). See also the binary predicate effectOfAction-Props."

Example: A more subtle notion of cleaning:

(#$effectOfActionIf-Props (#$cleans ?AGT ?OBJ) 
    (#$and (#$dirtinessOfObject ?OBJ ?OLD-DIRTINESS) 
           (#$followingValue ?NEW-DIRTYNESS ?OLD-DIRTYNESS))
    (#$and (#$not (#$dirtynessOfObject ?OBJ ?OLD-DIRTYNESS))
                  (#$dirtynessOfObject ?OBJ ?NEW-DIRTYNESS)))

In this example the dirtyness of an object is an instance of #$Dirtiness which can range from #$ReallyDirty to #$Sterile. Each execution of the cleaning action on the same object will raise its cleaniness one step.

2.4. Complex Actions and Methods

SHOP is an example of a Hierarchical Task Network planner. Most of the knowledge it uses is in the form of method decompositions. Methods encapsulate the approach of solving problems by breaking them down into smaller subproblems. For example, cleaning the floor can be achieved, if it is not carpeted, by mopping the floor . Mopping the floor can be achieved by acquiring a mop and a pail of soapy water, mopping each square meter of the floor separately, and then cleaning the mop and emptying the pail. Mopping each square meter involves wetting the mop, wringing out the mop, swabbing the square meter section, checking to see if it is still dirty, and repeating if necessary. Each of these can be represented as a single method rule in the Cyc KB.

#$methodForAction rules associate a complex action with its decomposition.

      (#$implies FORMULA 
         (#$methodForAction (COMPLEXACTIONPRED . ARGS)
         (#$actionSequence 
           (#$TheList 
              (SUBACTION1 ) 
              (SUBACTION2 ) 
              (SUBACTION3 )))))

#$sufficientFor-Props rules specify the conditions under which a complex action has a trivial decomposition. Sometimes it is not necessary to add the decomposed primitive actions of a complex action to a plan, when the purpose of that complex action has already been achieved by steps taken earlier in the plan. These kinds of rules aid in representing a domain since we can then specify method decomposition rules in their most general form, without enumerating all the possible exceptions when part of the decomposition could be redundant.

Usage:

(#$sufficientFor-Props CONDITION-FORMULA ACTION-SENTENCE)

Comment for #$sufficientFor-Props:

"A binary predicate which relates instances of ELSentence-Assertible to instances of ELSentence-Assertible, and which is used to state that one formula expresses a sufficient condition for the truth of another. (sufficientFor-Props PROP1 PROP2) means that PROP1's being satisfied is sufficient for PROP2's being satisfied. See also preconditionFor-Props."

Example:

         (#$sufficientFor-Props 
              (#$dirtynessOfObject ?OBJECT #$Sterile)
              (#$cleans ?AGT ?OBJECT))

3. Running The Planner

The OpenCyc Planner is easy to use, it can be accessed with one function: SHOP-FIND-PLANS.

function SHOP-FIND-PLANS: (task mt &optional (verbose 0) number time depth backchain)

Returns a list of action sequences each of which are a plan for TASK in the context of MT.

TASK
a formula with an instance of #$ActionSequence as its first argument.
MT
a microtheory that gives context to the planning problem.
VERBOSE
an integer between 0 and 9, that controls how much logging information shop should send to standard output.
NUMBER
the maximum number of plans to return.
TIME
the maximum amount of time allocated to the planner.
DEPTH
the maximum depth the planner can reach searching for plans.
BACKCHAIN
the maximum number of backchains allowed when querying the KB when matching rule conditions.

4. Further Reading on Planning

Last update: 06/21/2002    |    Copyright © 2002 Cycorp All rights reserved.