Designing Planning Domains: A Case Study Version 0.7b

The purpose of this document is to describe the process by which a real planning domain can be represented in the Cyc KB. It is assumed that the reader already has some experience with knowledge entry and some knowledge of the issues involved in ontological design.

The domain in question, computer programming, has been selected for several reasons. Firstly, it is relatively easy to implement this domain up to the execution level. The programs produced by the planner in this domain should be amenable to being compiled, interpreted, and run. Secondly, computers in general are already a fairly discrete world that lends itself well to near complete representation in predicate logic. Thirdly, this domain effectively demonstrates in action several key Cyc technologies for knowledge representation and reasoning.

Our purpose here is to describe the process of creating the domain and exploring how that domain can interact with the rest of the KB and be used for interesting applications. In the process, we will show how to make best use the inference engine and the SHOP planner.

This problem domain was an interesting exercise in ontological engineering, since much of the vocabulary we needed for preconditions did not exist. This allowed the KB representation of the program model to grow and be influenced by the parallel development of the planning domain. Since domain-specific knowledge is scarce in the KB, this will likely be the normal state of affairs.

Go to Appendix A for some example plan tasks to try, and for a discussion of the programming domain as it is represented in the Cyc KB. Appendix B is a list of some possible extensions to the domain that would make interesting projects for the interested ontological engineer.

General

A Planner is by its very nature a general purpose problem solver. As an extension to the Cyc inference engine, its power is harnessed via rules and assertions in the KB. Applications using the planner may have special code for processing, displaying, or even executing plans, but the heart of the application will be the planner rules themselves.

Creating a planning domain is a very similar act to programming. Often rules when first conceived will not work as expected. This is because the rules are inherently linked together, and a failure anywhere might break the entire plan. Thus, it is normal to spend a period of debugging whenever a planning domain is extended with new rules, or when a new world model representation requires editing rule preconditions.

A rough algorithm for designing a planning domain:

1. Design the world representation
2. Design the primitive action layer
3. Design the hierarchy of complex actions

This algorithm is very rough. In fact, it may be true that no planning domain is ever designed this way. In reality, it seems more likely that design will become an iterative process, during which mistakes are made and lessons learned. But this algorithm is still valuable, since it also communicates the inherent dependencies of the various parts of the planning domain. It is guaranteed that a change in your world model representation will force changes to your planner rules. However, there may be many possible networks of complex actions that reasonably represent the abstract activities of the plan. Also, the steps are written in increasing order of the expected amount of revision each will likely require.

An important consideration early on is determining how all of the relevant information is going to be made available to the planner during its execution. The SHOP planner is given one (1) microtheory as a parameter that defines the context in which the planning is done. However, for real (non-toy) domains it will make sense to fragment the domain into modular chunks. The reason is that typically there will actually be several interesting and well defined contexts that you will be interesting in planning in, and these contexts will share a lot of their knowledge.

There are two types of simple action rules, preconditions and effects. Preconditions can be considered to be a specialization of method rules so we discuss them further in the section on complex action rules. Cyc current uses two different effect predicates: #$effectOfAction-Props, and #$effectOfActionIf-Props.

Good planner rules allow the right information to be available at each step of the planner's decision-making. There are two ways for this information to flow: Primarily, it can flow down the hierarchy, through the variable bindings of matching complex action preconditions, applied to the actions of their associated decompositions. Secondarily, it can flow through the preconditions of later actions matching the effects of previous actions.

It turns out that in some domains that the effects of actions play a relatively small part in the planning process. The primary purpose of effect rules in a planning domain is that they allow the signalling of information to later steps in the planning process. The SHOP planner plans for tasks in the same order they are to be executed; this means that in some cases decisions made when expanding earlier complex tasks in the plan will constrain the planning for later tasks. For example, consider a domain for traveling to work. At the beginning of the journey, one may have the option of riding the bus or driving a car. But once the plan involves a phase of bus riding, the planner should prune away all successive actions that involve driving, since riding the bus means leaving the car behind.

A planning domain is only as good as its rules. Unfortunately, planning domains are inherently interdependent structures. One bad rule can totally ruin the performance of the planner on many problems. Sometimes the preconditions of the rule can be incredible expensive.

It is helpful when design method rules to consider the nature of the information flow during the planning process. Each method rule encapsulates a point of decision making for the planner. The decision is always whether the rule should fire; i.e. whether the search space should include a node with this rule's decomposition pushed onto its stack. It makes this decision based on information from two sources: variable bindings from the world state, and variable bindings for the action predicates arguments passed to the rule from successful method rules encounter previously during planning.

Since the information flow into the rule from these two sources can change as the design evolves, it should be expected that these rules will change as well, and even the argument constraints and arity of the action predicate itself may change.

Some heuristics:

1. While there is no hard constraint limiting the size of method rules, historically our planner rules have usually around half a dozen preconditions and no more than half a dozen subtasks in their decomposition.
2. We enforce modularity by being selective about the preconditions. At each stage we should include in the preconditions only that information necessary for ensuring the legality of its associated decomposition.
3. While in an ideal world, the planner would be able to handle any representation, we find that sometimes we must tailor our representation to facilitate its querying by the planner.
4. CycL has a sophisticated array of evaluatable functions available. Often will want to pass variables to the decomposition action formulas with that require something beyond the mere binding against GAFs in the KB.

We now will consider some different problems that arose during the development of the programming domain, and their solutions.

(#$SqrtFn 
   (#$PlusFn
      (#$TimesFn (#$ParameterValueFn XSide)
		 (#$ParameterValueFn XSide))
      (#$TimesFn (#$ParameterValueFn YSide)
		 (#$ParameterValueFn YSide))))

(#$implies 
       (#$programFunctionOperator ?RELN ?OPERATOR) 
       (#$methodForAction 
           (#$doOutputProgramExpression ?HACKER ?FILE 
               (?RELN ?ARG1 ?ARG2)) 
           (#$actionSequence 
               (#$TheList 
                   (#$outputProgramToken ?HACKER ?FILE "(") 
                   (#$doOutputProgramOperator ?HACKER ?FILE ?OPERATOR) 
                   (#$doOutputProgramExpression ?HACKER ?FILE ?ARG1) 
                   (#$doOutputProgramExpression ?HACKER ?FILE ?ARG2) 
                   (#$outputProgramToken ?HACKER ?FILE ")"))))) 

(#$implies 
   (#$and 
    (#$programAlgorithmInternals ?ALGORITHM . ?INTERNALS) 
    (#$algorithmStartStep ?ALGORITHM ?STEP) 
    (#$programAlgorithmOutputs ?ALGORITHM ?OUTVARS) 
    (#$programStrings ?ALGORITHM ?ALG-NAME) 
    (#$equals ?JOINLISTSFN 
    (#$TheList . ?LOCALS)) 
    (#$evaluate ?JOINLISTSFN 
    (#$JoinListsFn 
      (#$TheList ?OUTVARS) 
      (#$TheList . ?INTERNALS))) 
    (#$termOfUnit ?PARAMETERVALUEFN 
      (#$ParameterValueFn ?OUTVARS))) 
   (#$methodForAction 
    (#$doDefineProgramFunctionFromAlgorithm ?HACKER ?FILE ?ALGORITHM)
      (#$actionSequence 
       (#$TheList 
        (#$doOutputProgramFunctionHeader ?HACKER ?FILE ?ALGORITHM) 
        (#$doOpenLocalVariablesScope ?HACKER ?FILE . ?LOCALS) 
        (#$doProgramStep ?HACKER ?FILE ?STEP) 
        (#$doOutputFunctionReturn ?HACKER ?FILE ?ALGORITHM ?PARAMETERVALUEFN) 
        (#$doCloseLocalVariablesScope ?HACKER ?FILE . ?LOCALS) 
        (#$doCloseFunctionDefinition ?HACKER ?FILE 
          (#$AlgorithmFunctionFn ?ALGORITHM ?ALG-NAME))))))

Debugging Tricks

Do not be surprised when you carefully designed planning domain fails to return plans right away. The rule interactions are complicated and it is very hard to assert the rules correctly the first time. Here are some pointers that might help the debugging process:

1. Use the verbose mode. Setting the verbosity of the planner, either throw the parameter of shop-find-plans or otherwise, will give you more information about where in the planning process the error occurred. A verbosity of 0 means no extra output, and a value of 9 means the highest level of extra information.
2. It will sometimes be the case, especially when designing domains with recursive method rules, or when preconditions are extremely expensive to compute, that the planner will run of into the weeds trying its best to find a solution. Since we do not currently have a method for interrupting the planning process, it is usually a good idea to set the depth and time cutoffs to reasonable values. The time cutoff does the obvious thing. Every time a method rule is successfully applied to a node, the children of that node have their depth value incremented by one. Depth is therefore a rough guide of the progress of the planner on a particular task. If the planner tries to expand nodes of a depth greater than your predefined limit, it will halt immediately.
3. Work backwards. It is much more efficient to make the complex rules that are closer to the primitive level work properly, and then more up to the more abstract actions. By working backwards you can build the domain one level at a time, with each level debugged against a known-to-be stable base of action rules. The planner can be called on any action predicate formula, and will plan for even the smallest subactions in a larger conceived plan. There is nothing that forces plan tests to be executed at the highest possible level.

Example Plan Tasks

1. Try the plan: (#$doDefineProgramFunctionFromAlgorithm #$Thing #$Thing #$AbsoluteValueComputation)
   in either #$CProgrammingTestMt or #$CommonLispProgrammingTestMt.
2. Try the plan: (#$doDefineProgramFunctionFromAlgorithm #$Thing #$Thing #$MaxElementComputation)
   in either #$CProgrammingTestMt or #$CommonLispProgrammingTestMt.

For example,

CYC(1): (csetq plans (shop-find-plans '(#$doDefineProgramFunctionFromAlgorithm #$Thing #$Thing #$MaxElementComputation) #$CProgrammingTestMt)
CYC(2): (punless (null plans) (csetq actions (shop-plan-simple-actions (first plans))))

Algorithm Representation

While it is important that the programs produced by the planner be valid, we would like further to analyze the algorithms involved abstracted away as much as possible from their implementation in the syntax of the programming languages themselves.

Program Steps

We currently support the representation of functional algorithms, i.e. functions which compute only one data object. This collection is denoted by the term #$FunctionalAlgorithm. We represent an algorithm as a mapping between program steps. It is conceptually very similar to the old style logic flowcharts.

Program steps are always instances of #$ProgramStep. We associate an algorithm with its first step with the predicate #$algorithmStartStep. Individual program steps of an algorithm can be denoted with the function #$AlgorithmStepFn. Other program steps can be denoted with special purpose functions like #$ProgramAssignmentFn and #$MakeFunctionCallInProgramFn.

There are several predicates that can be used to define the relationships between the program steps:

#$programIfConditionThenElse
#$programWhileConditionDo
#$hasSequentialProgramSteps

Tokens

Most named entities in a program, such as parameters and functions, will have a #$programStrings assertion on them, that will indicate (within the current context) what the string should be used in the program for that entity.

Variables

Variables are crucial to algorithm representation. We use instances of #$SoftwareParameter as variables or, as we call them here, parameters. Initial values for parameters are represented with #$initialParameterValue GAFs. The value of a parameter can be denoted via the unary function #$ParameterValueFn. In practice, this is similar to the '$' prefix used in bash shell scripting when accessing the value of an environment variable. This function maps a parameter to the information that its actual interal value is meant to represent. For example, in a C program where #$Counter is has type int, then (#$ParameterValueFn #$Counter) would denote an instance #$Integer, not some bitfield that is the actual representation of that integer in memory.

Expressions

The CycKB already has extensive knowledge about many of the mathematical functions we would be interested in using in program expressions. We use these functions as much as possible in the CycL representation of program steps, thereby establishing the semantic roots of the expression within pre-existing CycL. We use the binary predicate #$programFunctionOperator to represent the mapping between the CycL functions and their programming language counterparts.

Statement Parts

Many programming languages have very similar kinds of statements. For example, usually an if/then/else statement is almost standard, as is some kind looping construct. Since these forms are so common we can abstract them out to a language independent level, and have merely a mapping between parts of the statement and tokens in the language. This is the main reason for the action predicate #$doOutputStatementPart and the represented instances of #$ProgramSyntaxObject, such as #$IfStatement-StartIf and #$IfStatement-Then.

Domain Extent

At the current stage the domain represents only the programming of individual functions. To really useful, we need to extend the domain to include complete programs that meet specified requirements; use more of the existing #$Algorithm ontology to represent how different algorithms are combined to form complex programs; and look for ways of automating a link between program specifications and programs themselves.

The domain is currently only a small prototype. There are many ways it could be easily extended to cover more of the programming domain space. We now give some suggestions for projects that the interested student may wish to work on:

1. Extend the representation to pointer referencing/dereferencing. Allow a capability for pointer arithmetic.
2. Extend the representation to gracefully handle C-style bitwise operations.
3. Create a framework for software modules/packages. Allow the automatic mapping of functions like #$TangentFn and #$SineFn to functions in a mathematics subroutine library only when that library is available.
4. Extend existing vocabulary to handle object oriented programming, specifically the manipulation of class definitions, method declarations, and method invocation.
5. Namespaces and identifiers are currently given a very cursory treatment. Ideally we would like to automatically generate meaningful identifier strings for variables such that there are no collisions in the namespace. Presumably assertions in the KB (perhaps something involving #$programStrings, or perhaps some more complicated scheme) would be used to give "hints" to the planner.
6. Develop a framework for doing software verification in CycL. Extend CycL to enable the application (or implementation) of software engineering tools upon the CycL representation.
7. Extend existing functionality to include bash shell scripting. With the representation of the typical tool set of the average Linux user, develop a methodology that allows the planner to usefully chain together commands like grep and find, using piping and i/o indirection, like grep and find, to extract information from both the user environment, and from text file based knowledge sources with known formats. Simple queries for information by the user could serve as the high level goals for plans to actively process those files and extract their information as an answer to the query.