[an error occurred while processing this directive]

TLPlan / HPlan-P

Disclaimers

Copyright (c) 1998, 2003, Fahiem Bacchus and Michael Ady. All rights reserved. Use of this software is permitted for non-commercial research purposes, and it may be copied only for that use. All copies must include this copyright message. This software and any documentation and/or information supplied with it is distributed on an as is basis. Fahiem Bacchus, Michael Ady and the University of Toronto make no warranties, express or implied, including but not limited to implied warranties of merchantability and fitness for a particular purpose, regarding the documentation, functions or performance of such software, documentation and/or information.

Acknowledgments

Microsoft, Windows 95, Windows 98, Windows NT, Windows 2000, Windows XP and MS-DOS are trademarks or trade names of Microsoft Corporation.

UNIX is a trademark of X/Open Company Ltd.

Intel and Pentium are trademarks or trade names of Intel Corporation.

Sun, Sun Microsystems, SunOS and Solaris are trademarks or trade names of Sun Microsystems Inc.

This software was developed with support from the Canadian Government through their NSERC and IRIS programs.

Installation.

The system is distributed as a tar file named tlplan.tar Follow the following sequence of steps.
  1. Place tlplan.tar in the directory you want to store tlplan. Then move to that directory (i.e., make it your current directory).
  2. tar -xvf tlplan.tar (note that the tar file will not create a new top level directory---it will create a subdirectory called Blocks).
  3. Either move libtl.so to a directory accessible to the loader, or change the environment variable LD_LIBRARY_PATH so that the loader can find libtl.so. (Remember that LD_LIBRARY_PATH must be accessible to all subproceses, so, e.g., cshrc it must be a setenv variable).
The README file gives a bit more detail, and there is also a “runtlplan” file that can be edited and used to invoke tlplan. To test, move to the sub-directory and invoke

tlplan runblockstest.tlp

This should result the creation of a file “tlplan.log” containing a plan for a random 1000 blocksworld problem (a random problem generated by the Slaney-Thiébaux generator, John Slaney and Sylvie Thiébaux Blocks World revisited Artificial Intelligence 125 (2001): 119-153). On a 2Gz this will take about 1/3 of a sec. The script file will also terminate tlplan with an (exit) command. Comment out (with a “;”) this command if you want to enter an interactive session after the plan has been completed.

Overview

The best place to start is to browse the paper Using Temporal Logics to Express Search Control Knowledge for Planning. In particular, look at the section that describes the design of Tlplan. The basic steps are
  1. Defining the planning domain. First one tells the planner about the predicate and function symbols to be used in the domain. You must have some described symbols (these are the basic predicates and function that get updated by actions), and you can have defined symbols (defined by first-order formulas) and external symbols (used to invoke external C routines). Once all of the symbols have been defined, you can talk about the domain using the first-order language generated by these predicate and function symbols. The symbols declared to be defined must subsequently be given definitions. Then one can define the domain's actions. These can be defined using standard STRIPS operators or using ADL operators. To fully understand ADL actions you must understand how formulas are evaluated (see the paper cited above). Both STRIPS and ADL operators generate first-order formulas that are evaluated in thee current world to generate the successor worlds. In particular, the adds and deletes of the ADL operators are activated if and only if the evaluator evaluates the add/del clause in the operator (this in turn is controlled by the evaluator's rules for early termination). Note that functions can be used and updated by including a function specification inside of an add clause, and ADL operators can specify a recursive set of updates by invoking recursive defined predicates in their set of clauses.
  2. Defining the search control for the domain. Unless you are dealing with a very simple domain you will need to specify domain specific search control. The main mechanism for doing so is to specify a temporal logic formula using set-tl-control. See the paper cited above to understand how temporal formulas allows one to control search. Also see the various domains that come with the planner for an extensive set of examples. In addition to temporal formulas the user may specify the planner's search strategy (depth-first, best-first, etc.) and may also specify a heuristic function for best-first search. See the file "tlplan/domains/Eight/EightWorld.tlp" for an example of searching Lloyd's sliding tile puzzle using the standard Manhattan distance heuristic.
  3. Specify the initial world and the goal. The initial world and goal are specified using a list of predicate and function specifications. If one sets the goal type to be "extended" then the goal can be an arbitrary temporal formula. If every initial world in this domain has some special features, or one wants to initially set up some additional described predicates and functions, the special commands set-initialization-sequence and set-initial-facts can be used.
  4. Running the Planner. To run the planner one loads the domain definition file sets the initial world and goal, and then invokes the planner with the command plan.
Notes:

Contents

Commands for Defining a Domain
Initializations and Declarations
Definitions
Syntax of Formulas
Commands for Defining Operators
Defining STRIPS Operators
Defining ADL Operators
Commands for Controlling the Planner
Search Cost and Priority Routines
Controlling information generated during planning
Commands for Running the Planner
Commands for Specifying and Manipulating Worlds
Specifying Initial Worlds
Commands for Handling Files and I/O
File Operations
Printing
Commands for Installing a Domain
Utility Routines
Routines for Interrogating the Current World
Routines for Retrieving Planning Statistics
Arithmetic Functions and Predicates
Random Number Generators
Generators
World Context Selectors
Miscellaneous Routines
User Libraries
CDF – Cumulative Distribution Functions
HPlan-P
Use
Configuring new heuristics

Commands for Defining a Domain

Initializations and Declarations

(clear-world-symbols)
Type: Pseudo-predicate returning true.
Description: Clear the previous domain's language definition. This command must be called first in a new domain definition file. This command also calls the reset-print-world-fn command and reset-tl-control. These commands reset the temporal control formula and the print world command to their defaults.
(declare-defined-symbols (function|predicate|generator name arity) ...)
Type: Pseudo-predicate returning false on error.
Description: Declare the defined predicate, function and generator symbols of the domain. The defined symbols must be declared after the described symbols. name is the name of the defined symbol (i.e. function, predicate or generator). arity specifies the number of parameters accepted by the defined symbol.
(declare-described-symbols (function|predicate name arity [no-cycle-check|rewritable]) ...)
Type: Pseudo-predicate returning false on error.
Description: Declare the described predicate and function symbols of the domain. The described symbols must be declared prior to any other symbols. name is the name of the described symbol (i.e. function or predicate). arity specifies the number of parameters accepted by the described symbol.
Optionally, either qualifier, no-cycle-check and/or rewritable may be specified. If no-cycle-check is specified, then the associated described symbol will be excluded from cycle-checking. The planner can spend a significant amount of time doing cycle-checking, and in some circumstances performance can be greatly improved by excluding certain described symbols from cycle checking. This option can be specified if a particular function/predicate value never changes, or if it does not affect any of the decisions made by the planner.
By default, TLPlan, complains whenever a described predicate is add’ed whenever it is already asserted or true. If rewritable is specified for a described predicate, then this warning is suppressed. The use of this option is not recommended unless you are trying to get someone else’s domain to work under TLPlan (i.e. the domain semantics are defined for some other planner). If TLPlan complains with “Rewriting predicate symbol…” for domains you have written yourself, then it is most likely that you have a logical error in you domain definition. Rather than specifying rewritable for a particular described predicate, first consider if you have failed to add or delete the symbol in some operator, and you will almost certainly discover a logical error.
(declare-external-symbols library (function|predicate|generator|macro name libref arity) ...)
Type: Pseudo-predicate returning false on error.
Description: Declare the externally defined predicate, function, generator and macro symbols of the domain. External symbols must be declared before they are used. library, is the location and name of the user library. A separate call to assign a value to the function's name. Note that formula may include a reference to the current function (thus recursive function definitions are allowed). To use this feature be sure you understand the evaluator's early termination rules. With early termination formula can be written so as to ensure any recursion terminates.
While parameters and local variables are "local" to the defined function, they are "global" to all formulas evaluated as a consequence of evaluating formula.
(def-defined-generator (name parameters) (local-vars declarations) formula)
Type: Pseudo-predicate returning false on error.
Description: Include a new generator, defined in the domain language. name is a symbol which names the new generator. parameters is a list of variables that are the arguments of the new generator. declarations is an optional list of local variables and arrays.
formula is evaluated to calculate the value(s) of the generator (as a side-effect). To return generated values, the generator must assign each value to the appropriate parameter in the parameters list.
In addition to its parameters, each generator is passed a value that indicates whether it is being called for the first time or not. This value is passed in a variable with the same name as the generator, but with a leading '?'. This variable has a value of 0 the first time the generator is called, and a value of 1 each time thereafter.
The first time a generator is called, it must initialize its context and save important information in its declared local-vars. Each time the generator successfully generates a new value or set of values, formula must evaluate to true. When the generator has generated all possible values and wishes to terminate, formula must evaluate to false.
While parameters and local variables are "local" to the defined generator, they are "global" to all formulas evaluated as a consequence of evaluating formula.
(def-defined-predicate (name parameters) (local-vars declarations) formula)
Type: Pseudo-predicate returning false on error.
Description: Include a new predicate, defined in terms of a first-order formula involving other predicates, in the domain language. name is a symbol naming the new predicate. parameters is a sequence of variables that are the arguments of the new predicate. declarations is a list of local variables and arrays. formula is a first-order formula that defines the new predicate. Note that formula may include a reference to the current predicate (thus recursive predicate definitions are allowed). To use this feature be sure you understand the evaluator's early termination rules. With early termination formula can be written so as to ensure any recursion terminates.
While parameters and local variables are "local" to the defined predicate, they are "global" to all formulas evaluated as a consequence of evaluating formula.
(define name list)
Type: Pseudo-predicate returning false on error.
Description: Define name as an abbreviation for list. This allows macro substitution in domain definition files.
(:= ?variable value)
Type: Pseudo-predicate returning false on error.
Description: := is a pseudo-predicate that assigns value to ?variable. Note that := is only used to assign values to variables. = is used to assign values to described functions (among other things).
Back to contents

Syntax of Formulas

Terms


constant
Type: Term.
Description: Any symbol, number, or string is a term.
?variable
Type: Term.
Description: Any symbol that starts with ? is a variable, and is also a term.
(?array index ...)
Type: Term.
Description: An array reference is a special type of variable, and is also a term. The declared dimension of the array must agree with the number of indices given.
(function term ...)
Type: Term.
Description: A list consisting of a function name followed by a sequence of terms is a term. function is a symbol that has been declared to be a domain function by one of the initial declarations. (See Initializations and Declarations.) The arity of function must agree with the number of terms given. Note that any of the built-in arithmetic functions can be used as functions (they do not need to be declared).
Back to contents

Atomic Formulas


(predicate term ...)
Type: Predicate.
Description: A list consisting of a predicate followed by a sequence of terms is an atomic formula. predicate is a symbol that has been defined to be a domain predicate one of the initial declarations. (See Initializations and Declarations.) The arity of predicate must agree with the number of terms given.
(= term1 term2)
Type: Predicate.
Description: Equality is a predefined binary predicate.
(TRUE)
Type: Predicate.
Description: The constant atomic formula that always evaluates to true.
(FALSE)
Type: Predicate.
Description: The constant atomic formula that always evaluates to false.
Back to contents

First-Order Formulas


atomic-formula
Type: Predicate.
Description: Any atomic formula is a first-order formula.
(and formula ...)
Type: Predicate.
Description: The logical and of a sequence of formulas.
(or formula ...)
Type: Predicate.
Description: The logical or of a sequence of formulas.
(xor formula ...)
Type: Predicate.
Description: The logical exclusive or of a sequence of formulas.
(not formula)
Type: Predicate.
Description: The logical negation of formula.
(implies formula1 formula2)
Type: Predicate.
Description: Logical implication, the result is true iff formula1 and formula2 are both true or formula1 is false.
(if-then-else formula1 formula2 formula3)
Type: Predicate.
Description: The result is true iff formula1 and formula2 are both true, or formula1 is false and formula3 is true.
(forall var-gen ... [formula])
Type: Predicate.
Description: Universal quantification, the formula is true iff formula is true for all bindings of the variables in var-gen that are generated by the generator in var-gen. This formula is trivially TRUE if the final formula is missing.
Multiple var-gens may appear in a quantified formula. This is shorthand for a nested invocation of the quantifier. For example, the formula:
(forall (?x) (at ROBOT ?x) (?y) (in ?x ?y) ...)
is equivalent to:
(forall (?x) (at ROBOT ?x) (forall (?y) (in ?x ?y) ...))
(exists var-gen ... [formula])
Type: Predicate.
Description: Existential quantification, the formula is true iff formula is true for some binding of the variables in var-gen that are generated by the generator in var-gen. The last item, formula, is optional. If it is absent then the formula is true iff the generator in var-gen generates some binding for the variables in var-gen.
Once again, multiple var-gens may appear in a quantified formula as shorthand for a nested invocation of the quantifier. For example, the formula:
(exists (?x) (at ROBOT ?x) (?y) (in ?x ?y) ...)
is equivalent to:
(exists (?x) (at ROBOT ?x) (exists (?y) (in ?x ?y) ...))
(exists! var-gen ... [formula])
Type: Predicate.
Description: Unique existential quantification, the formula is true iff formula is true for exactly one binding of the variables in var-gen that are generated by the generator in var-gen. If formula is absent then the formula is true iff generator generates only a single binding for the variables in var-gen.
When multiple var-gens appear in a quantified formula, it is shorthand for a nested invocation of the quantifier. For example, the formula:
(exists! (?x) (at ROBOT ?x) (?y) (in ?x ?y) ...)
is equivalent to:
(exists! (?x) (at ROBOT ?x) (exists! (?y) (in ?x ?y) ...))
Back to contents

Generators


(predicate-generator term ...)
Type: Generator.
Description: Any described predicate can serve as a generator. Every one of the immediately enclosing quantifier's variables must appear as a term of this formula. Additional variables appearing in term ... must have been bound by earlier quantifiers.
(= (function term ...) value)
Type: Generator.
Description: Any described function can be a generator. Every one of the immediately enclosing quantifier's variables must appear as a term of the function. Additional variables appearing in value and term ... must have been bound by earlier quantifiers.
Note that described functions generate at most one binding of the quantified variables.
(computed-generator term ...)
Type: Generator.
Description: An internal or user defined computed generator can be used as generator. Every one of the immediately enclosing quantifier's variables must appear as a term of the generator. Additional variables appearing in term ... must have been bound by earlier quantifiers. Look here for a list of the available internal generators, external or user defined generators are described here.
Back to contents

Syntax of Temporal Logic Formulas


first-order-formula
Type: Temporal formula.
Description: Any first-order formula is a temporal formula, as is any first-order formula that contains temporal formulas.
(next tf)
Type: Temporal formula.
Description: This formula is true of a sequence of states iff the temporal formula tf is true in the next state.
(eventually tf)
Type: Temporal formula.
Description: This formula is true of a sequence of states iff the temporal formula tf is true of some future state.
(t-eventually ispec tf)
Type: Temporal formula.
Description: This formula is true of a sequence of states iff the temporal formula tf is true of some future state in the interval ispec.
(always tf)
Type: Temporal formula.
Description: This formula is true of a sequence of states iff the temporal formula tf is true for all future states.
(t-always ispec tf)
Type: Temporal formula.
Description: This formula is true of a sequence of states iff the >Description: This formula is true of a sequence of states iff the temporal formula tf1 is true in all states until a state is reached where tf2 is true. Note that if tf2 is true in the current state, then so is the until formula.
(t-until ispec tf1 tf2)
Type: Temporal formula.
Description: This formula is true of a sequence of states iff the temporal formula tf1 is true in all states until a state is reached in the interval ispec where tf2 is true.
(delta tf)*
Type: Temporal formula.
Description: The user should not use this temporal formula constructor. It is used internally by the planner while progressing formulas. This formula is true iff tf.
(binding (variables) (values) tf)
Type: Temporal formula.
Description: The user should not use this temporal formula constructor. It is used internally by the planner while progressing formulas. This formula is true iff tf is true when the variables (that appear in tf) are bound (sequentially) to values.
Back to contents

Modalities


Modalities cause their arguments to be evaluated in the context of another world. Modalities can be applied to any first-order formula, temporal formula or generator, and the result, respectively, is a first-order formula, a temporal formula or a generator.

(goal formula|tf|generator)
Type: Modality.
Description: The specified first-order formula, temporal formula or generator is evaluated in the goal world. The goal modality can only be used when dealing with classical goals.
(previous formula|tf|generator)
Type: Modality.
Description: The specified first-order formula, temporal formula or generator is evaluated in the previous state. (previous tf) is always false in the initial world.
(current formula|tf|generator)
Type: Modality.
Description: The specified first-order formula, temporal formula or generator is evaluated in the current state. This modality is used with select-initial-world, select-final-world, select-previous-world and select-next-world to interrogate the results of a planning session.
Back to contents

Commands for Defining Operators

Defining STRIPS Operators

(def-strips-operator name pre del add cost duration priority)
Type: Pseudo-predicate returning false on error.
Description: This command defines a new STRIPS operator. It accepts seven sub-clauses, described below:
(name v ...)
The name clause declares the name of the operator and its parameters. The operator is given the name symbol, and the variables, v ..., are declared to be arguments of the operator.
When the variables are instantiated, the name and instantiated variables should provide a unique name for the action. This helps to make clear, just which operator generated each world. However, there is no requirement that the name clauses of distinct operators be distinct themselves. Sometimes this feature can be put to good use, allowing a single logical operation to be split up and then handled by two or perhaps more operators.
(pre formula ...)
The pre clause declares the precondition list. This is a list of conditions that must be satisfied before applying the operator. It is a list of atomic formulas, including negations of atomic formulas, i.e., expressions of the form (not atomic-formula). Arbitrary terms can appear in the atomic formulas. However, every variable in the list of preconditions must first appear as a term of a non-negated described predicate. Furthermore, every variable in the name clause must appear as a term in at least one formula of the pre clause.
(add p ...)
The add clause declares the additions list. The additions list specifies the described predicates that are added to the new world by the action. The additions list can also specify updates to described functions which have their values modified in the new world by the action.
The additions list is a list of atomic formulas formed from described predicates and described functions. Arbitrary terms are allowed in these predicates, but every variable that appears in these terms must have previously appeared in the pre clause.
(del p ...)
The del clause declares the delete list. The delete list specifies the described predicates (and described functions) which are removed from the world by the action. This clause has the same format as the add clause.
When modifying the value of a described function, it is not necessary to first delete the previous value of the function, before adding the new value. This action is implied by the add. The only time that the value of a described function might possibly need to be deleted would be to make the value of the function in question undefined.
(cost n)
The cost clause specifies the cost of the action, n. n may be a number or a term which evaluates to a number. The default cost is 1.
(duration n)
The duration clause specifies the duration of the action, n. n may be an number or a term which evaluates to a number. The default duration is 1.
(priority n)
The priority clause specifies the priority of the action, n, an integer. The priority is used during search to order the successors of a world (dependent on the search strategy). It defaults to 0. Operations with higher priorities are selected before those with lower priorities by priority-based search strategies.
Back to contents

Defining ADL Operators

(def-adl-operator name pre modifier-clauses cost duration priority)
Type: Pseudo-predicate returning false on error.
Description: This command defines a new ADL operator. It accepts six sub-clauses, described below.
(name v ...)
The name clause declares the name of the operator and its parameters. The operator is given the name symbol, and the variables, v ..., are declared as the arguments of the operator.
(pre var-gen ... [formula])
The pre clause declares the precondition list. It contains a sequence of one or more variable-generator pairs and a single, optional, first-order formula. It can be viewed like a quantifier, and has the same syntax as, for example, the forall quantifier. Each binding of the variables contained in var-gen that for make formula true generates a single instance of the ADL action that can be applied to the current world.
modifier-clauses
Each ADL operator must contain one or more modifier clauses. The modifier clauses describe what changes to make in the current world to create the new world generated by each of its instances. Each modifier clause is an arbitrary first-order formula with the addition of one or more add or del meta-predicate clauses.
The add and del clauses have the same syntax as the corresponding STRIPS clauses. However, within ADL operators, add and del act as meta-predicates that always evaluate to true. Thus in general, they may appear in modifier clauses anywhere an atomic formula may appear (except not as generator literals). add and del are meta-predicates since they take atomic formulas as arguments.
Modifier clauses are preprocessed internally by the planner so that all deletions act before all additions. When a modifier clause contains both add and del predicates, the planner acts as if it duplicates the clause, and removes all of the add meta-predicates from the first copy, and all of the del meta-predicates from the second.
(cost n)
The cost clause specifies the cost of the action, n. n may be a number or a term which evaluates to a number. The default cost is 1.
(duration n)
The duration clause specifies the duration of the action, n. n may be an number or a term which evaluates to a number. The default duration is 1.
(priority n)
The priority clause specifies the priority of the action, n, an integer. The priority is used during search to order the successors of a world (see search strategy). It defaults to 0.
Back to contents

Commands for Controlling the Planner

(set-tl-control temporal-formula)
Type: Pseudo-predicate returning false on error.
Description: Set the temporal control formula used by the planner. temporal-formula is specified using the temporal control logic. (See Syntax of Temporal Logic Formulas.)
(get-tl-control)
Type: Pseudo-function returning a formula.
Description: Display the current temporal control formula.
(reset-tl-control)
Type: Pseudo-predicate returning true.
Description: Reset the current temporal control formula to the default:
(always (true))
This control formula provides no search control.
(set-search-strategy strategy)
Type: Pseudo-predicate returning false on error.
Description: Set the planner's search strategy. strategy is the strategy's defined name. The predefined search strategies are:
Strategy
 Description
depth-first-priority This is the default strategy. The planner does depth-first search. However, when it expands the successors of a world it will explore those successors in order of their priority. By default the priority ranking of the successors is determined by the priority of the operator used to generate it. (In defining operators the user can set their priority.)
depth-first The planner does depth-first search. Successor priority is not considered.
depth-first-no-backtracking The planner does depth-first search. Successor priority is not considered. Only a single successor is generated for each world. This can greatly improve the speed of the planner. However, to successfully use this search strategy, the domain control mechanism must guarantee the viability of the first successor generated for each world.
depth-best-first The planner does depth-first heuristic search. This strategy requires a cost function, which defaults to optimal-cost. In the default case the planner will search for a plan using the action costs defined in the operator definitions. The successors of each world are explored in a best-first manner.
breadth-first-priority The planner does breadth-first search, examining all action sequences of length 1, then all sequences of length 2, etc. However, the successors of a world are eventually expanded in order of their priority. The default priority ranking is action priority.
breadth-first The planner does breadth-first search without considering successor priority.
best-first The planner does best-first heuristic search. This strategy requires a cost function, which defaults to optimal-cost. In the default case the planner will search for the optimal cost plan using the action costs defined in the operator definitions. Search is performed in a best-first manner exploring the least costly plan first.

(world-heuristic-rank ...)*
Type: Function returning a floating point value.
Description: Not fully implemented.
(get-search-strategy)
Type: Function returning a string value.
Description: Display the planner's current search strategy.
(reset-search-strategy)
Type: Pseudo-predicate returning true.
Description: Reset the planner's search strategy to its default.
(set-search-limit number)
Type: Pseudo-predicate returning false on error.
Description: Set a limit on the number of worlds the planner will expand when searching for a plan. number must be a positive integer.
(get-search-limit)
Type: Function returning an integer value.
Description: Return the planner's current search limit.
(reset-search-limit)
Type: Pseudo-predicate returning true.
Description: Reset the planner's search limit to its a positive number.
(reset-search-depth-limit)
Type: Pseudo-predicate returning true.
Description: Disable search depth limiting in the planner.
(get-search-depth-limit)
Type: Function returning an integer value.
Description: Return the current search depth limit. Returns 0 if search depth limiting is disabled.
(set-search-heuristic-limit limit)
Type: Pseudo-predicate returning false on error.
Description: Set the maximum heuristic limit for the planner. The specified limit must be a positive number.
(reset-search-heuristic-limit)
Type: Pseudo-predicate returning true.
Description: Disable heuristic limiting in the planner.
(get-search-heuristic-limit)
Type: Function returning a floating point value.
Description: Return the current heuristic limit. Returns 0 if heuristic limiting is disabled.
(set-goal-addendum formula)
Type: Pseudo-predicate returning false on error.
Description: Specify an addendum to the planner's goal predicate. Once a world satisfies the planner's internal goal predicate, control is passed to formula. formula may effect any number of side effects. It should return true to indicate that the current world is satisfactory (and planning should be terminated) or return false to continue planning.
(get-goal-addendum)
Type: Function returning a formula.
Description: get-goal-addendum returns the current goal addendum, or nil if no goal addendum is currently defined.
(reset-goal-addendum)
Type: Pseudo-predicate returning true.
Description: Disable the current goal-addendum, restoring the planner's normal goal predicate processing.
(disable feature)
(enable feature [option])
Type: Pseudo-predicate returning true.
Description: Enable or disable one of the following planner features:
Feature
 Description
backtracking When back tracking is disabled, all of the successor worlds of a world, except for the first (viable) one are discarded. Most domains require backtracking to function properly. (It is faster and more efficient to set the search strategy to depth-first-no backtracking, than it is to select depth-first-search and disable backtracking.) By default backtracking is enabled.
concurrent-planning Enabling concurrent-planning tells planner to initialize its event queue and it enables the domain to use the apropriate predicates and functions that access the event queue. Also, statistics and plans are output with information that is more useful for concurrent planning. By default, concurrent-planning is disabled.
cycle-checking Disabling cycle-checking causes the planner to avoid comparing each new world against previously generated worlds. (Each control strategy may have a different cycle checking method.) Cycle checking can use a significant proportion of the planner’s CPU resources. However, most domains require cycle checking to function properly. By default cycle-checking is enabled.
pddl-support Enabling pddl-support allows the planner to support some of the semantics of PDDL AIPS 2002. When pddl-support is being enabled, enable accepts one of two optional parameters, priority and cost, which affect how PDDL metric information is handled. If neither option is specified, PDDL metric information is ignored. If the cost option is asserted, then PDDL metric information is treated as a heuristic function. If the priority option is asserted, then PDDL metric information is treated as a priority function. By default, pddl-support is disabled.
pruning-all-successors Enabling pruning-all-successors causes the planner to prune all successor worlds using the temporal control formula, before selecting the next world to expand. In general, this process takes a great deal of CPU time, though it may save some memory space for some types of domains. By default, pruning-all-successors is disabled.
timing-statistics Enabling timing-statistics causes the planner to print timing statistics in the log file for each component of the planner’s CPU usage. By default timing-statitics is disabled.
Back to contents

Search Cost and Priority Routines

(set-priority-fn function)
Type: Pseudo-predicate returning false on error.
Description: Set the priority function to be function. function is a function that will be passed plan structures during search. It must return a numeric ranking of the plan. This ranking will be used to sort the successors of a world when depth-first-priority or breadth-first-priority search is being used. In particular, highest priority successors will be searched first. Alternately, function can be the symbol best-action. In this case action priority will be used to prioritize the world successors.
(get-priority-fn)
Type: Pseudo-function returning a formula.
Description: Return the current priority function.
(reset-priority-fn)
Type: Pseudo-predicate returning true.
Description: Reset the current cost function to its default, which ranks a world's successors by action priority, exploring the highest priority successors first.
(best-action)
Type: Function returning an integer value.
Description: Return the priority of the instantiated operation that created the current world.
(set-heuristic-fn function)
Type: Pseudo-predicate returning false on error.
Description: Set the current heuristic formula to function. function is typically the name of a defined function that accepts no arguments and returns an integer or floating point value.
(get-heuristic-fn)
Type: Pseudo-function returning a formula.
Description: Display the current heuristic formula, used by best-first search.
(reset-heuristic-fn)
Type: Pseudo-predicate returning true.
Description: Reset the current heuristic formula to optimal-cost.
(optimal-cost)
Type: Function returning a floating point value.
Description: optimal-cost returns the sum of all costs associated with the actions that generated the current world.
(a* cost-function)
Type: Function returning a floating point value.
Description: a* returns a value that is the sum of the plan's current cost and the value returned by the current heuristic function. a* is a cost function that will allow best-first search to perform A* search.
(heuristic-fn)
Type: Function returning a numeric value.
Description: Execute the current heuristic function on the current world.
Back to contents

Controlling information generated during planning

(verbose-on)
Type: Pseudo-predicate returning true.
Description: Select verbose output.
(verbose-off)
Type: Pseudo-predicate returning true.
Description: Select terse output.
(set-trace-level level)
Type: Pseudo-predicate returning false on error.
Description: Set the level of trace output. level must be a non-negative integer.
Level Information
0 No tracing.
1 Print the world being expanded and an indication as to whether or not it was successfully expanded.
2 Print the level 1 information and also print the progressed temporal formula.
3 Print the level 1 and 2 information and also print the successor worlds.

(get-trace-level)
Type: Function returning an integer value.
Description: Return the current trace level.
Back to contents

Commands for Running the Planner

(load-file "file-name")
Type: Pseudo-predicate returning false on error.
Description: Load a file containing TLPlan commands. The specified file-name should be in double quotes, and the file's extension should be included (typically TLPlan input files have a .tlp extension). The file name should also include a path if the file isn't available in the TLPlan working directory.
(load-domain name)
Type: Pseudo-predicate returning false on error.
Description: Load a domain. name is the domain's defined name. See def-domain.
(list-domains)
Type: Pseudo-predicate returning true.
Description: Display a list of names and descriptions of the known domains.
(set-goal-type goal-type)
Type: Pseudo-predicate returning false on error.
Description: Set the goal type for the current planning problem. goal-type is a quoted literal string, which may be either "classic" or "extended". The default goal type is "classic". The appropriate goal type must be selected before calling set-goal, since it determines how set-goal will interpret a specified goal.
Goal Type Description
classic This is the default goal type. The desired goal state is specified as a list of described predicates and functions which must be true in the goal world.
extended The desired goal state is specified as a temporal formula. Neither the goal modality nor a temporal control formula may be used with extended goals.

(plan)
Type: Pseudo-predicate returning false on failure or error.
Description: Run the planner on the current initial-world anin-left:.5in'>Description: Read a plan represented by action1 action2 ... into the planner. The domain, an initial world and a goal must have already been loaded into the planner. The planner cycles and for each action in sequence, it verifies that its preconditions are satisfied by the current world, before generating a new world satisfying the action. The planner will report an error if the plan is invalid or the final state does not satisfy the goal formula.
Back to contents

Commands for Specifying and Manipulating Worlds

Specifying Initial Worlds

Specifying Values for a Described Predicate


(predicate arg ...)
Description: Any atomic formula generated from a described predicate symbol in which all of the arguments are either symbols, numbers, or character objects (i.e. terms), serves as a described predicate specification. In particular, this expression specifies that predicate is true of arg ... in an initial world.
Back to contents

Specifying Values for a Described Function


(= (function arg ...) value)
Description: A described function specification consists of an item specifying that function takes on value given the arguments arg .... value and arg ... must be constants.
(+= (function arg ...) value)
Description: The value of the described function is modified by adding value to the function’s current value. The function must already have a numeric value assigned to it.
(-= (function arg ...) value)
Description: The value of the described function is modified by subtracting value from the function’s current value. The function must already have a numeric value assigned to it.
Back to contents

World Initializers


(set-initial-facts formula ...)
Type: Pseudo-predicate returning false on error.
Description: Modify the initial world by adding the specified described predicates and functions to the initial world. The intention of set-initial-facts is to allow various (constant) facts concerning the initial state of the domain to be specified in the domain definition file. This can help simplify the specification of problem sets for a domain. The formulas specified with set-initial-facts are applied to the initial world when set-initial-world is executed.
(set-initialization-sequence formula ...)
Type: Pseudo-predicate returning false on error.
Description: Modify the initial world by evaluating the specified sequence of formulas on the initial world. The intention of this command is to provide an algorithmic means of setting up the initial state of a domain. The formulas specified with set-initialization-sequence are applied when set-initial-world is executed after all other initial facts have been applied to the initial world.
Each formula is applied to the initial world in sequence. Each formula is evaluated on the previous temporary copy of the world, and it generates a new temporary world. After all formulas have been evaluated in this manner, the result is the final initial world, and all intermediate temporary worlds are discarded.
(update-world)
Type: Pseudo-predicate returning false on error.
Description: update-world may be included in an initialization or goal sequence to force the creation of a new temporary world in the middle of evaluating a formula. (Normally a new temporary world is only created after totally evaluating each formula in the sequence.) When an initialization or goal sequence is evaluated, the results of any changes to the world are not visible to a formula until a new temporary world is created. update-world can greatly simplify the generation of initial and goal worlds.
(set-initial-world [world-list])
Type: Pseudo-predicate returning false on error.
Description: Create a world out of world-list, a list of predicate and function specifications (assumed to be complete). Set the world to be the initial world for the current planning problem. It is possible to completely specify the initial world using set-initial-facts and/or set-initialization-sequence. In which case, set-initial-world should be called without any arguments to perform the initialization process.
Back to contents

Goal Initializers


(set-goal goal-list)
Type: Pseudo-predicate returning false on error
Description: Set the goal formula of the current planning problem. goal-list is a list of predicate and function specifications. If goal type is "extended" then goal-list can be an arbitrary temporal formula.
(set-goal-sequence formula ...)
Type: Pseudo-predicate returning false on error.
Description: Set up the goal world by evaluating the specified sequence of formulas in the goal world. The intention of this command is to provide an algorithmic means of setting up the goal state of a domain. The formulas specified with set-goal-sequence are applied when set-goal-formula is executed.
Each formula is applied to the goal world in sequence. Each formula is evaluated on the previous temporary copy of the world, and it generates a new temporary world. After all formulas have been evaluated in this manner, the result is the final goal world, and all intermediate temporary worlds are discarded.
(set-goal-formula)
Type: Pseudo-predicate returning false on error.
Description: Set the goal formula of the current planning problem. The goal formula is created from the goal world generated by set-goal-sequence. set-goal-sequence and set-goal-formula can be used together, instead of set-goal to set up a classic goal formula from a defined (random) problem generator.
Back to contents

Commands for Handling Files and I/O

File Operations

All file operations require a file stream identifier. File stream identifiers are small integer values. There are four standard streams. Additional streams can be created by calling open-file.
Stream Description
0 Standard output. Output goes to the terminal by default.
1 Standard input. Input comes from the terminal by default.
2 Standard error. Output goes to the terminal by default.
3 Standard log file. Output goes to the log file "tlplan.log". This file is created when TLPlan is called and is closed when TLPlan exits.

(open-file file-name access)
Type: Function returning an integer value.
Description: Open the file file-name with the specified access status. Return a file stream identifier.
Access Type Description
append The file is opened for write access. Output is appended to the end of the file.
read The file is opened for read access.
write A new file is created and opened for write access.

(close-file stream)
Type: Pseudo-predicate returning false on error.
Description: Close the specified file stream. The specified stream must have been created by a call to open-file. None of the standard streams may be closed.
(redirect stream1 stream2)
Type: Pseudo-predicate returning false on error.
Description: Redirect stream1 to access what stream2 currently accesses. Both streams must be open and they must have identical access statuses. Redirect is useful for redirecting the standard file streams to other files and devices.
Back to contents

Printing

(print stream format arg ...)
Type: Pseudo-predicate returning false on error.
Description: Format a string according to format and arg .... The resulting string is printed on stream. stream may be specified as the number 0 to direct output to the screen (when a valid stream is perhaps not available).
The following lisp-like format specifiers are available for formatting arguments:
Format Specifier Description
~A ~nA ~@nA Print a string or symbol name. Options @ and n are available.
  • n specifies the field width.
  • @ selects left justification. (The default is right justification.)
~D Print a decimal integer. (No options are available.)
~F ~wF ~,dF ~w,dF Print a floating point value. Options d and w are available.
  • d specifies the number of decimal places.
  • w specifies the field width.
~S ~nS ~@nS Print a string or symbol name. ~S is a synonym for ~A.
~T ~nT ~,rT ~n,rT Insert blanks up to the specified tab stop. Options n and r are available.
  • n specifies the column of the desired tab stop.
  • r specifies the tab stop repeat spacing.

If the number of characters already formatted, m, is greater than or equal to n, then n is increased by the minimum multiple of r to make it larger than m. If m is larger than n, and r is 0, the tab stop is ignored. n and r both default to 1.
~% Insert a newline character.
~~ Insert a tilde.

(print-plan-list stream)
Type: Pseudo-predicate returning false on error.
Description: Print a list of all the steps (instantiated operations) required to get to the current world from the initial world.
(print-world stream)
Type: Pseudo-predicate returning false on error.
Description: Print a description of the current world on the specified stream. This routine calls the print world function that has been declared with set-print-world-fn, or the default print world function.
(set-print-world-fn function)
(reset-print-world-fn)
Type: Pseudo-predicate returning true.
Description: Restore the print world function to the default generic print world function.
(print-world-list stream)
Type: Pseudo-predicate returning false on error.
Description: Print a description of the current world on the specified stream. This routine produces output which is suitable for input into an animator.
(print-delta-time [description])
Type: Pseudo-predictate returning true.
Description: print-delta-time prints the elapsed time since TLPLan was started (or since its counter was last zeroed), along with the description string. The information is printed on stream 2 (stderr). If print-delta-time is called without an argument, its counter is zeroed, and nothing is printed.
(set-statistics-file "file-name")
Type: Pseudo-predicate returning false on error.
Description: Enable statistics logging and specify the name of a file to use for logging statistics. If statistics logging are enabled, statistics are logged by plan, at the end of each planning session. Each planning session opens the log file, appends a single line to the end of the file, and then closes the file.
Each line in the statistics log is in the form of a comma separated list, which is suitable for loading into a spreadsheet or a database. The following data is recorded:
Datum Description
plan-name Plan name (quoted string).
plan-status Plan status (quoted string):
  • "OK" – planning succeeded.
  • "resources" – planning failed due to search limit reached.
  • "no-plan" – planning failed; no plan is possible.
worlds-generated Number of worlds generated by the planner (integer).
worlds-searched Number of worlds actually searched by the planner (integer). This value does not include worlds pruned by temporal control or discarded by cycle checking.
worlds-pruned Number of worlds pruned by temporal control (integer).
worlds-discarded Number of worlds discarded by cycle checking (integer).
worlds-unexamined Number of worlds generated but not actually searched by the planner (integer).
plan-length Number of steps in plan (integer).
plan-cost Total heuristic cost of the plan (floating point).
plan-cpu-time Total CPU time for the planning session (floating point). On some systems such as Windows 95/98, process accounting is not available, so the "elapsed" time is provided instead.
Back to contents

Commands for Installing a Domain

(reset-domains)
Type: Pseudo-predicate returning true.
Description: Reset the collection of domains that TLPlan knows about.
(def-domain name comment file ...)
Type: Pseudo-predicate returning false on error.
Description: Define a new domain in the system. name is a symbol that names the domain, i.e., it may be used in the load-domain command. Comment is a string argument that is a single sentence description of the domain. File-list is a list of path names of files that together comprise the files that define the domain. These file names should include type extensions (i.e., the final .tlp extension should appear as part of the name).
(list-domains)
Type: Pseudo-predicate returning true.
Description: List the set of domains known to the system. This is the set of domains that have been defined by various calls to def-domain.
(load-domain name)
Type: Pseudo-predicate returning false on error.
Description: Load the domain that has symbolic name, name. The symbolic name of a domain is determined by the name argument of def-domain. The set of files associated with the domain will be loaded into the system.
Back to contents

Utility Routines

Routines for Interrogating the Current World

(plan-length)
Type: Function returning an integer value.
Description: Return the depth of the current world in steps.
(plan-cost)
Type: Function returning a floating point value.
Description: Return the total cost of reaching the current world (i.e., the sum of the costs of all the ancestor actions leading to the current world).
(plan-duration)
Type: Function returning a floating point value.
Description: Return the total time taken in reaching the current world (i.e., the sum of the durations of all the ancestor actions leading to the current world).
(action-name)
Type: Pseudo-function returning a formula.
Description: Return the instantiated operation that generated the current world.
(action-cost)
Type: Function returning a floating point value.
Description: Return the cost of the action that generated the current world.
(action-priority)
Type: Function returning an integer value.
Description: Return the priority of the action that generated the current world.
(action-duration)
Type: Function returning a floating point value.
Description: Return the duration of the action that generated the current world.
(world-number)
Type: Function returning an integer value.
Description: Return the number of the current world. The planner increments a counter, each time a new world is generated. This world number serves as a unique identifier for each world.
Back to contents

Routines for Retrieving Planning Statistics

(plan-status)
Type: Function returning a string value.
Description: Return the status of the latest planning session.
Status Description
"OK" Planning succeeded.
"resources" Planning failed due to search limit reached.
"no-plan" Planning failed; there are no more worlds to search; no plan is possible.

(worlds-generated)
Type: Function returning an integer value.
Description: Return the number of worlds generated during planning.
(worlds-discarded)
Type: Function returning an integer value.
Description: Return the number of worlds discarded due to cycle checking.
(worlds-pruned)
Type: Function returning an integer value.
Description: Return the number of worlds pruned by the control formula.
(worlds-searched)
Type: Function returning an integer value.
Description: Return the number of worlds expanded by the planner, but not pruned
(worlds-unexamined)
Type: Function returning an integer value.
Description: Return the number of worlds generated by the planner, but never expanded.
(plan-cpu-time)
Type: Function returning a floating point value.
Description: Return the CPU time required for the latest planning session. On some operating systems, such as Windows 95 or 98, there is no process accounting, so that the elapsed time is returned instead.
(search-max-depth)
Type: Function returning an integer value.
Description: Return the maximum plan length explored by the planner.
(search-max-heuristic)
Type: Function returning an integer value.
Description: Return the maximum heuristic value encountered by the planner.
(set-plan-name "format" [arg...])
Type: Pseudo-predicate returning false on error.
Description: Specify a name for the current planning session. format and arg... are used to specify the name of the plan. The format string supports all of the same formatting features as the corresponding argument to print.
(reset-plan-name)
Type: Pseudo-predicate returning true.
Description: Clear the name of the current planning session.
(get-plan-name)
Type: Function returning a string value.
Description: Return the name of the current planning session, as specified by set-plan-name.
Back to contents

Arithmetic Functions and Predicates

Functions


(+ arg ...)
Type: Function returning a numeric value.
Description: Calculate the sum of all arguments. All arguments must be numeric. The result is floating point.
(- arg ...)
Type: Function returning a numeric value.
Description: Calculate the difference of all arguments. All arguments must be numeric. If only one argument is present, then the result is its additive inverse. If more than two arguments are present, the calculation is left associative. For example
(- a b c d) = (- (- (- a b) c) d).
(* arg ...)
Type: Function returning a numeric value.
Description: Calculate the product of all arguments. All arguments must be numeric.
(/ arg ...)
Type: Function returning a numeric value.
Description: Calculate the quotient of all arguments. All arguments must be numeric. If only one argument is present, then the result is its multiplicative inverse. If more than two arguments are present, the calculation is left associative. For example
(/ a b c d) = (/ (/ (/ a b) c) d).
Division by zero is an error.
(mod arg ...)
Type: Function returning a numeric value.
Description: Calculate the remainder after division of all arguments. All arguments must be numeric. If only one argument is present, then the result is that argument. If more than two arguments are present, the calculation is left associative. For example
(mod a b c d) = (mod (mod (mod a b) c) d).
Taking the remainder of two floating point arguments is perfectly legal. For example
(mod 6.2 3.05) = 0.1.
Division by zero is an error.
(max arg ...)
Type: Function returning a numeric value.
Description: Calculate the maximum of all arguments. All arguments must be numeric.
(expt arg ...)
Type: Function returning a floating point value.
Description: Calculate the power of all arguments. All arguments must be numeric. The calculation is left associative. For example
(expt a b c d) = (expt (expt (expt a b) c) d).
Exponentiating a negative number by a non-integer is an error. Try (expt a (round b)) instead of (expt a b).
(sqrt arg ...)
Type: Function returning a floating point value.
Description: Calculate the square root of a number. Taking the square root of a negative number is an error.
(abs arg ...)
Type: Function returning a numeric value.
Description: Calculate the absolute value. All arguments must be numeric. If more than one argument is present, then the result is the Euclidean vector length of the arguments.
(log arg ...)
Type: Function returning a floating point value.
Description: Calculate the logarithm of a number. If only one argument is present, the base is "e" (natural logarithm). Otherwise the second argument specifies the base. An error occurs if the base is less than or equal to 1 or the value is less than or equal to 0.
(exp arg ...)
Type: Function returning a floating point value.
Description: Calculate the exponential function of a number. All arguments must be numeric. The calculation is left associative. For example
(exp a b c d) = (exp (exp (exp a b) c) d).
Taking the exponential of a negative number by a non-integer is an error. Try (exp(round a)) instead of (exp a).
(round n)
Type: Function returning an integer value.
Description: Round a (floating point) number, n, to the nearest integer.
(int n)
Type: Function returning an integer value.
Description: Truncate a (floating point) number, n, to the nearest integer (toward zero).
(floor n)
Type: Function returning an integer value.
Description: Truncate a (floating point) number, n, to the nearest integer less than or equal to n.
(ceil n)
Type: Function returning an integer value.
Description: Raise a (floating point) number, n, to the nearest integer greater than or equal to n.
Back to contents

Predicates


(= arg1 arg2)
Type: Predicate.
Description: Returns true iff both arguments are the same type and evaluate to the same value. Arguments may be identifiers, numbers or strings.
(< arg1 arg2)
Type: Predicate.
Description: Returns true iff both arguments are numbers and the first argument is less than the second.
(<= arg1 arg2)
Type: Predicate.
Description: Returns true iff both arguments are numbers and the first argument is not greater than the second.
(> arg1 arg2)
Type: Predicate.
Description: Returns true iff both arguments are numbers and the first argument is greater than the second.
(>= arg1 arg2)
Type: Predicate.
Description: Returns true iff both arguments are numbers and the first argument is not less than the second.
Back to contents

Random Number Generators

(set-rng type)
Type: Pseudo-predicate returning false on error.
Description: Select a random number generator of the specified type.
Type Description
fibonacci This random number generator is based on code from the National Institute of Standards and Technology. This is the default random number generator. This generator is fast and is believed to generate good random numbers. The fibonacci random number generator has a range of 0 - 2147483647.
isaac This random number generator is based on code written by Bob Jenkins. This generator is believed to generate very good random numbers. The isaac random number generator has a range of 0 - 2147483647.
ms This random generator is compatible with the random number generator Microsoft uses to specify game numbers for many of its games. This generator is fast and is believed to generate poor random numbers. The ms random number generator has a range of 0 – 32767.
The Microsoft did not write the ms random number generator, so it is not specific to Windows or MS-DOS, and is available on all platforms supported by TLPlan.

(get-rng)
Type: Function returning a string value.
Description: Return the name of the current random number generator.
(reset-rng)
Type: Pseudo-predicate returning true.
Description: Reset the current random number generator to the default (fibonacci).
(rand)
Type: Function returning an integer value.
Description: Calculate a random number. The range of the result depends on the currently selected random number generator.
(seed n)
Type: Pseudo-predicate returning false on error.
Description: Reset the seed of the random number generator to n. The range of the argument depends on the currently selected random number generator.
(random low high)
Type: Function returning a floating point value.
Description: Calculate a random number between limits low and high. Low must be less than high.
Back to contents

Generators

(is-between ?var low high)
Type: Generator.
Description: is-between generates all of the integers between the specified low and high limits (inclusive). Numbers are generated in sequence, starting at low and ending at high.
(<-pos-int ?var high)
Type: Generator.
Description: <-pos-int generates all of the integers between 0 and the high limit (non-inclusive). The first number generated is 1 and the last is (- high 1).
(pos-int ?var)
Type: Generator.
Description: pos-int generates all of the integers greater than 0. (The first number generated is 1.)
(permute (predicate ?var ...))
Type: Generator.
Description: permute generates all of the tuples of terms for which predicate is true, in random order. predicate must be a described predicate.
(in-the-set (?var1 ?var2 ...) val1 val2 ...)
Type: Generator.
Description: in-the-set enumerates all of the tuples of terms val1 val2 .... The number of values must be an integer multiple of the number of variables.
(make-literal format arg1 ...)
Type: Generator.
Description: make-literal generates a single literal symbol with a name given by the format string. format may include format specifiers, requiring one or more arguments arg1 .... See print for a description of valid format specifiers. make-literal is typically used in problem generators to generate literal symbols for problems on the fly.
Back to contents

World Context Selectors

All formulas are executed within the context of the current world. At the command prompt, the current world is a special empty world, in which all described symbols are false. Within the actual planner, the current world is the world the planner is currently expanding.
The following world context selectors are particularly useful for interrogating a plan after a planning session has completed. Each selector behaves as though it sets a background world pointer. This background pointer is made accessible to formulas through the current modality.

(select-final-world)
Type: Pseudo-predicate returning false on error.
Description: Select the last world generated by a successful planning session.
(select-initial-world)
Type: Pseudo-predicate returning false on error.
Description: Select the initial world specified by set-initial-world.
(select-next-world)
Type: Pseudo-predicate returning false on error.
Description: Select the world following the current (background) world.
(select-previous-world)
Type: Pseudo-predicate returning false on error.
Description: Select the world preceding the current (background) world.
Back to contents

Miscellaneous Routines

(exit)
Type: Pseudo-predicate (does not return).
Description: Exits TLPlan.
(get-cpu-time)
Type: Function returning a floating point value.
Description: Return the CPU time used by TLPlan. This routine is most useful for measuring time intervals, since the epoch for this timer varies between operating systems. Some operating systems such as Windows 95 or Windows 98 do not have process accounting, so elapsed time is returned instead.
Back to contents

Reserved Formulas

(modify-world operator update-formula)
Type: Pseudo-predicate returning true.
Description: modify-world is a pseudo-predicate used internally by the planner. It is not available at the user level for use in the definitions of formulas or operators. operator is an operator formula, that associates the modify-world formula with the operator that generated it. update-formula is evaluated to perform the required actions to update the state of the new world.
Both ADL and STRIPS operators are converted into formulas that call modify-world. modify-world performs several functions required to implement the actions of operators on the current world:
First modify-world makes a copy of the current world. Then it labels the new world with the name of the operator which caused the world to be created. This label includes both the name of the operator and a list of the arguments satisfying the operator's preconditions.
Then modify-world associates the originating operator's priority with the new world. It also adds the current world's total cost and duration to the operator's corresponding incremental cost and duration, and associates these new totals with the new world.
Next modify-world evaluates the update-formula. The update-formula is evaluated in the context of the old world, but it acts only on the new world. The operator's actions on the new world are implemented through the pseudo-predicates add and del.
(add lit ...)
(del lit ...)
Type: Pseudo-predicate returning true.
Description: add adds the specified literals (i.e. described predicates and function values) to a new world (created by modify-world). del performs the complementary function, deleting the specified literals from the new world.
Both add and del rely on modify-world to provide a new world context for them to operate on. Furthermore, both add and del rely on the enclosing operator's preconditions, (and in the case of ADL operators, they rely on quantifiers in the operator's modifier clauses) to bind variables appearing as arguments to the specified literals. All such bindings are evaluated in the context of the current (old) world.
Whenever both add and del pseudo-predicates appear in the same operator definition, the planner constructs the update formula so that all deletes are performed before all additions. The purpose of reordering the actions in this manner is to simplify the writing of definitions of operators for the user.
add will complain (i.e. issue a warning message) if an operator adds a predicate to a world, when a previous instance of the predicate (with the same parameters) already exists. Similarly,
Back to contents

Support for Concurrent Planning

TLPlan provides support for concurrent planning through two pseudo-predicates called delayed-action and wait-for-next-event, which may be embedded in concurrent operators. To enable concurrent planning, an (enable concurrent-planning) command should appear near the top of the domain definition file.

In most cases concurrent operators use a simple initialization plus completion model. The initialization actions are placed outside of a delayed-action clause, and the completion actions are placed inside it.

The non-delayed actions of such a concurrent operator will typically initialize by allocating resources that will be needed for the operation (which will in turn block further invocations of the operator unless further resources are available). If the operator doesn’t need to allocate resources during initialization, it is important to set a semaphore, which will ensure that the planner doesn’t enter an infinite loop, invoking the same operator over and over again.

When a concurrent operator completes, typically it will release some of the resources it used, while it will have transmuted other resources. Between initialization and completion, the operator is treated like a black box – what it does with its resources are hidden from the planner until completion.

Concurrency occurs when the active operators do not utilize all of the resources of the domain and other operations can be initiated. In general, different operations will complete at different times, releasing resources or creating other resources that can be used to initiate further operations while other ongoing operations continue to run in the background.

TLPlan provides support for concurrent planning via a simple queuing model. When concurrent planning is enabled, operators may include one or more delayed-action clauses. Operator actions may be enclosed in a delayed-action clause or not. Actions that are not delayed, are evaluated immediately, and they directly affect the successor world, (which is given the current time as its timestamp). Actions that are delayed are queued to a time ordered queue for execution later. They are marked for dequeuing when the time has advanced to the operation start time plus the interval specified for the delayed action.

The delayed actions may have unbound variables in their formulas. Context for the evaluation of those variables is provided by generating the necessary bindings and queuing them together with the delayed action formulas. It is important to note that these bindings are evaluated in the context of the starting world of the operation, and they do not necessarily reflect the state of the world when the delayed actions are evaluated. If current information will be required when a delayed-action is evaluated, the world database or global variables should be queried directly.

To dequeue queued actions and advance the current time so that operations can be completed, TLPlan provides the pseudo-predicate wait-for-next-event. Typically a low priority operator is given the name “event” and is encoded in the domain. Typically this operator has no preconditions, and wait-for-next-event is its only action. When wait-for-next-event is evaluated, the next delayed action (visible to the current world) is dequeued, and its timestamp becomes the current time. If there are further delayed actions available for dequeuing at the same time, then all of them are dequeued together. Each delayed-action has all of its enclosed actions evaluated to generate the successor world of the “event” operator. The planner then restarts its cycle, and resumes searching for operators to apply to the new successor world.

(delayed-action delta tag formula)
Type: Pseudo-predictate returning false on error.
Description: delayed-action queues the specified formula and its current bindings list to the event queue for later execution. A delayed action is time stamped with a time equal to the current time when it was queued, plus its delta time (or duration). A delayed action is elegible for dequeuing and evaluation of its formula when there are no other delayed actions in the queue with smaller time stamps that are visible from the current world. (A delayed action is considered to be visible if it was generated by a direct ancestor of the current world.) delta is the time interval in arbitrary units, from the comencement of an operator action until the effects of the delayed action are evaluated. tag is a string that describes the delayed action. (Often tag is a restatement of the operator name, but in past tense.) formula specifies the actions to be applied to the current world when the delayed action is finally dequeued. A delayed action is supplied with a bindings list that is bound when the the action is first queued. However the delayed action is evaluated in the context of a world generated by wait-for-next-event and this world is guaranteed to be a descendant of the world that originally queued the delayed action.
(wait-for-next-event)
Type: Pseudo-predictate returning false on error.
Description: wait-for-next-event searches the event queue, looking for the first visible delayed action. If it finds such a delayed action, it generates a new world, and evaluates the formula of the delayed action and any other visible delayed actions with the same time stamp, in the context of the new world. It also formats an event description for each dequeued delayed action, using the action’s associated tag, and it appends each event description to its own action description. These event descriptions are technically not part of a plan, but are helpful for debugging and deciphering concurrent plans.
(global-delayed-action delta tag formula)
Type: Pseudo-predictate returning false on error.
Description: global-delayed-action queues the specified formula and its current bindings list to the event queue for later execution. Global delayed actions are visible from all worlds, and so may be dequeued whenever they appear at the front of the event queue. The parameters are treated the same as they are for delayed-action. delta is the time interval in arbitrary units, from the current time until the effects of the delayed action are evaluated. tag is a string that describes the delayed action. formula specifies the actions to be applied to the current world when the delayed action is finally dequeued
(inhibit-delayed-action delta tag)
Type: Pseudo-predictate returning false on error.
Description: inhibit-delayed-action stops a delayed action from being dequeued in any of the child states of the current world. This facility may be useful if it is necessary to change plans without backtracking. delta is the time interval, relative to the current time when the queued delayed action is due to be dequeued. tag is the tag originally associated with the delayed action to be inhibited. inhibit-delayed-action searches for a delayed action in the event queue, based on both the absolute time of the action and its tag. Both parameters must be specified correctly for the inhibit to be flagged correctly.
(reachable-event)
Type: Predicate.
Description: reachable-event returns true if there are any visible delayed actions in the event queue, that are reachable from the current world. To be reachable, a delayed action’s time stamp must be in future, with respect to the current world’s current time.
(clear-event-queue)
Type: Pseudo-predicate returning true.
Description: clear-event-queue deletes all delayed actions from the event queue.
(current-time)
Type: Function returning a floating point value.
Description: current-time returns the current time of the successor world. Clearly current-time is only meaningful in the context of an operator, and it is only really useful within an enclosing delayed-action, in which case it will provide the current time for a world actually generated by wait-for-next-event.
Back to contents

Graph Search Techniques

Some types of domains involve searching a finite graph. Typically a robot has to traverse a graph where the number of interesting locations where actual work can be done is sparse. To reduce the length or duration of the plan, the robot has to traverse the distance between interesting locations using direct, possibly optimal paths. Numerous efficient graph search algorithms are available, however encoding these algorithms in the language of the planner would be extremely tedious. Furthermore, the very general seach mechanism of the planner would run many times slower than a graph search algorithm specifically designed for the problem at hand.

TLPlan provides a number of graph search generators that have slightly different features, or which have different uses. Like the macro operators described in the next section, the graph search technique allows the planner to tunnel through the otherwise opaque regions of the search space, in this case, without resorting to blind breadth-first search. all-pairs-shortest-path is a generator typically used during initialization to generate described predicates, marking the nodes or edges of the graph, in a manner that will help to guide the planner through the graph traversal phases of its plan. In the case of a robot, it essentially keeps the robot moving along the best path, without any danger of making a misstep. Since all-pairs-shortest-path enumerates all possible pairs of vertices, it is perhaps best utilized on smaller graphs or on graphs where there is a high likelihood that the planner will have to traverse a moderate portion of the edges of the graph.

To efficiently traverse a graph from one interesting location to another, the planner must encode a graph traversal algorithm within its operators. Often the traversal algorithm is as simple as greedily following the next edge marked cheapest or fastest by the graph search generator. In other cases, extra state information, encoded as domain described predicates or functions may be required to properly traverse the graph.

While closest-first, closest-first-ex, nearest-first and nearest-first-ex can be called during initialization to mark all of the nodes of a graph, they are perhaps more typically used existentially to generate the first best path to take next. These generators were written in such a way as to avoid doing extra work in case they are terminated before enumerating the entire graph. In this sense, these generators may perhaps be better suited to larger or more sparsely traversed graphs than all-pairs-shortest-path.

(all-pairs-shortest-path vertex-predicate cost-function ?var-vertex1 ?var-vertex2 ?var-cost ?var-next)
Type: Generator.
Description: all-pairs-shortest-path enumerates all pairs of vertices (graph nodes) that have edges between them. It calculates the cost of the best path between the two vertices, and generates the first successor vertex along the best path. vertex-predicate is a described predicate of arity 1 that specifies the vertices of the graph. cost-function is a decribed function of arity 2, specifying the cost of traversing each adjacent pair of vertices in the graph. cost-function also implicitly specifies the structure of the graph, since an edge of the graph is assumed to exist iff it has an associated cost. ?var-vertex1 must be specified as a quantifier variable, and is used to enumerate the start vertex of each possible path. ?var-vertex2 must be specified as a quantifier variable, and is used to enumerate the end vertex of each possible path. ?var-cost must be specified as a quantifier variable, and is used to return the total cost of traversing the shortest/cheapest path from ?var-vertex1 to ?var-vertex2. ?var-next must be specified as a quantifier variable, and is used to return the successor vertex along the shortest/cheapest path from ?var-vertex1 to ?var-vertex2.
(closest-first edge-predicate cost-function start-vertex ?var-vertex ?var-cost [?var-edge-count])
Type: Generator.
Description: closest-first enumerates the paths from the start-vertex to every other reachable vertex in the graph, in best-first order. edge-predicate is a described predicate of arity 2 that specifies the edges of the graph. cost-function is a described function of arity 2, specifying the cost of traversing each adjacent pair of vertices in the graph. start-vertex is the starting vertex for the graph search. ?var-vertex must be specified as a quantifier variable, and is used to enumerate the end vertex of each possible path. ?var-cost must be specified as a quantifier variable, and is used to return the total (minimal) cost of traversing the shortest/cheapest path from start-vertex to ?var-vertex. ?var-edge-count must be specified as a quantifier variable, and is used to return the number of edges that must be traversed along the shortest/cheapest path from start-vertex to ?var-vertex.
(closest-first-ex (?var-from ?var-to)
(edge-predicate arg1 arg2 ...)
Type: Generator.
Description: closest-first-ex is a more flexible version of closest-first. closest-first should be used whenever possible since it is faster than closest-first-ex. closest-first-ex enumerates the paths from the start-vertex to every other reachable vertex in the graph, in best-first order. ?var-from and ?var-to must be specified as quantifier variables. These variables specify which arguments to edge-predicate and cost-function are their vertex arguments. Each must appear among the argument lists of both edge-predicate and cost-function. edge-predicate is a described predicate of at least arity 2 that specifies the edges of the graph. cost-function is a function (not necessarily only described) of at least arity 2, specifying or capable of calculating the cost of traversing each adjacent pair of vertices in the graph. The parameters to edge-predicate and cost-function, other than the ones matching ?var-from and ?var-to must be constant literals or must otherwise be bound. start-vertex is the starting vertex for the graph search. ?var-vertex must be specified as a quantifier variable, and is used to enumerate the end vertex of each possible path. ?var-cost must be specified as a quantifier variable, and is used to return the total cost of traversing the shortest/cheapest path from start-vertex to ?var-vertex. ?var-edge-count must be specified as a quantifier variable, and is used to return the number of edges that must be traversed along the shortest/cheapest path from start-vertex to ?var-vertex.
(nearest-first edge-predicate start-vertex ?next-vertex ?next-distance)
Type: Generator.
Description: nearest-first enumerates the paths from the start-vertex to every other reachable vertex in the graph, in shortest-path-first order, where the length of the path is defined by the minimal number of edges traversed. edge-predicate is a described predicate of arity 2 that specifies the edges of the graph. start-vertex is the starting vertex for the graph search. ?next-vertex must be specified as a quantifier variable, and is used to enumerate the next closest vertex along some minimal distance path. ?next-distance must be specified as a quantifier variable, and is used to return the total (minimal) number of edges required to traverse from start-vertex to ?next-vertex.
(nearest-first-ex (?loc-from ?loc-to)
(<edge-predicate> ?arg1 ?arg2 ...)
start-vertex ?next-vertex ?next-distance)
Type: Generator.
Description: nearest-first-ex is a more flexible version of nearest-first. nearest-first should be used whenever possible since it is faster than nearest-first-ex. nearest-first-ex enumerates the paths from the start-vertex to every other reachable vertex in the graph, in shortest-path-first order, where the length of the path is defined by the minimal number of edges traversed. ?loc-from and ?loc-to must be specified as quantifier variables. These variables specify which arguments to edge-predicate are its vertex arguments. Each must appear among the argument list of edge-predicate. edge-predicate is a described predicate of at least arity 2 that specifies the edges of the graph. start-vertex is the starting vertex for the graph search. ?next-vertex must be specified as a quantifier variable, and is used to enumerate the next closest vertex along some minimal distance path. ?next-distance must be specified as a quantifier variable, and is used to return the total (minimal) number of edges required to traverse from start-vertex to ?next-vertex.
(lowest-first function ?arg1 ?arg2 ...)
Type: Generator.
Description: lowest-first enumerates all of the tuples (arguments) of the specified described function in order of their corresponding function values. Arguments ?arg1 ?arg2 ... must be specified as quantifier variables, and must match the arity of function. function must be described, and must have an arity of at least 1.
Back to contents

PDDL Support

TLPlan offers limited support for PDDL AIPS 2002. TLPlan is capable of reading in a PDDL problem definition, and writing out PDDL plan specifications. However, TLPlan does not support PDDL domain specifications, since the PDDL planning paradigm is markedly different from TLPlan’s. However, it is generally not difficult to translate (manually) a PDDL domain specification into a form TLPlan can work with.

To enable PDDL support, it is necessary to invoke (enable pddl-support) near the start of the domain definition. See enable above.

TLPlan provides support for macro operators, and elided operators, primarily for use with PDDL.

Macro operators provide a powerful concept that allows TLPlan to efficiently solve certain types of (tedious) problems with very little effort. Basically a macro domain is encoded with ordinary operators, however, some of those operators will be encoded to perform the actions of several atomic operations in a single (macro) step. These macro operators allow the planner to tunnel through otherwise opaque regions of the search space (for which no good control strategy is available), by simply glossing over them. No special support is required to encode domains to work this way, however the plans generated will include macro actions, rather than the atomic actions that may have been part of original domain specification.

If the planner is constrained to generate plans containing only atomic actions, it must expand macro actions before writing out an actual plan. TLPlan provides support for expanding a macro plan with a very simple mechanism. To make use of this mechanism, the user must encode (at least) two domains that can be called the macro and expansion domains. The planner is invoked with the macro domain definition and uses it to solve the problem at the macro level. Inside the macro domain definition file, each macro operator is declared and associated with an expansion domain definition file, and a goal formula. (Typically a single common expansion domain definition is used for all macro operators.)

After the planner has generated a complete macro plan, it scans the plan, looking for macro actions. For each macro action, the planner’s internal seach mechanism is invoked with the macro operator’s associated expansion domain and goal formula. The initial world for this sub-invocation of the planner is the same world the macro action was originally applied to. The purpose of the expansion domain is to generate a sub-plan that transforms the provided initial world into the macro action’s successor world. If there is truly no control information avilable for the macro expansion, then blind, breadth first search may even be used. (Hopefully the macro expansion won’t be lengthy.) Once the appropriate sub-plan has been obtained, the planner merges the sub-plan back into the original macro plan, replacing the macro action that invoked its generation. The planner then resumes looking for further macro actions. Planning completes when all of the macro actions have been replaced by sub-plans. There is no allowance for recursively expanding macro actions in sub-plans, so the expansion domain should only contain atomic actions.

Elided operators are provided to allow a domain to be encoded with operators that were not present in the original domain definition and therefore should not appear as actions in plans. The only difference between an elided operator and any other operator is that it’s actions are skipped over when the plan is output. In a sense, elided operators are the opposite of macro operators. They allow the planner to use two or more actions to obtain a successor state that might otherwise be cumbersome to obtain with a single action.

TLPlan provides special support for concurrent planning for PDDL AIPS 2002. TLPlan’s native concurrent planning semantics make use of half-open time intervals. That is, concurrent actions commence exactly at their specified time, but they complete at some unspecified small (perhaps infinitesimal) interval of time less than their stated duration. (In this case, the temporal interval is closed at its start and open at its end, and is therefore half-open.) The import of this temporal model is that each action is completed before the end of its interval, and the results of its changes to the world are known (exactly) at the end of the interval, so another action, based on those changes can commence (exactly) at the end of the preceding action’s interval.

PDDL AIPS 2002 specifies closed time interval semantics. That is concurrent actions commence exactly at their specified time and they do not complete until the very end of their duration. (In this case, both ends of the interval are closed, so the interval is closed.) The import of this temporal model is that the results of an action’s changes on the world are not known at the end of its interval. The planner must wait an internally specified small (open) interval of time, before commencing any other action that depends on the preceding action’s changes to the world. The primary disadvantage to this temporal model is that it generates plan schedules that slide, and in general events do not occur at integral times, (which is distracting).

When PDDL support and concurrent planning are enabled, TLPlan will simulate closed temporal interval semantics, and generate plans meeting the concurrent planning specifications of PDDL AIPS 2002.

(load-pddl-problem name)
Type: Pseudo-predicate, returning true.
Description: Load a PDDL problem definition file. name is the name (and location) of the problem file.
(print-pddl-plan)
Type: Pseudo-predicate, returning true.
Description: Print a list of all of the steps (instantiated opeartions) required to get to the current world from the initial world. The plan is printed in PDDL AIPS 2002 format. The plan is written to a .soln file, in the same directory as the PDDL problem file.
(declare-elided-operators name ...)
Type: Pseudo-predicate, returning false on error.
Description: Declare the operators that should not appear in the plan output. Each name should be the name of a defined STRIPS or ADI operator.
(declare-macro-operators (name domain goal) ...)
Type: Pseudo-predicate, returning false on error.
Description: Declare the operators that must be macro expanded in the plan output. name specifies the name of a macro operator in the current domain definition. domain specfies the name (and location) of a an expansion domain file that will expand the corresponding macro action as a sub-plan of atomic actions. goal is a goal formula that will direct the expansion domain to obtain the successor state of the macro operation, given it’s starting state.
(clear-operators)
Type: Pseudo-predicate.
Description: Delete all operator definitions from the current domain. This command is normally placed near the top of each expansion domain definition file. It serves to delete all of the operators from the domain, before the expansion domain’s operators are loaded. Typically the macro operators must be deleted before commencing planning with the expansion domain, so that no macro operator subsumes the functionality of the atomic operators in the expansion domain.
Back to contents

User Libraries

TLPlan provides support for user written libraries. These libraries are dynamically linked to the planner at run time by calls to declare-external-symbols. Most of these libraries exist to provide features that aren't (yet) expressible in the interpreted language of TLPlan (typically random problem generators). Most of these libraries are specific to particular problem domains, and are documented in the domain files. CDF is a more generic user library and is documented here.

CDF – Cumulative Distribution Functions

The cumulative distribution functions are used for various statistical tests and calculations (such as confidence intervals).
(icdf-beta p a b)
Library Routine: ICDFBeta
Type: Function returning a floating point value.
Description: Calculate the inverse cumulative beta distribution function. The range of the result is [0, 1].
Where:
p is the CDF value (probability) [0, 1]
a is the first beta parameter [0, +infinity]
b is the second beta parameter [0, +infinity]
(icdf-binomial p Xn prob)
Library Routine: ICDFBinomial
Type: Function returning a floating point value.
Description: Calculate the inverse cumulative binomial distribution function. The range of the result is [0, Xn].
Where:
p is the CDF value (probability) [0, 1]
Xn is the number of trials (0, +infinity)
prob is the probability of success of a single trial [0, 1]
(icdf-chi-square p df)
Library Routine: ICDFChiSquare
Type: Function returning a floating point value.
Description: Calculate the inverse cumulative chi square distribution function. The range of the result is [0, +infinity].
Where:
p is the CDF value (probability) [0, 1]
df is the number of degrees of freedom (0, +infinity)
(icdf-non-central-chi-square p df pnon)
Library Routine: ICDFNonCentralChiSquare
Type: Function returning a floating point value.
Description: Calculate the inverse cumulative non-central chi square distribution function. The range of the result is [0, 1e300].
Where:
p is the CDF value (probability) [0, 1]
df is the number of degrees of freedom (0, +infinity)
pnon is the non-centrality [0, +infinity]
(icdf-f p dfn dfd)
Library Routine: ICDFF
Type: Function returning a floating point value.
Description: Calculate the inverse cumulative f distribution function. The range of the result is [0, 1e300].
Where:
p is the CDF value (probability) [0, 1]
dfn is the number of degrees of freedom of the numerator (0, +infinity)
dfd is the number of degrees of freedom of the denominator (0, +infinity)
(icdf-non-central-f p dfn dfd pnon)
Library Routine: ICDFNonCentralF
Type: Function returning a floating point value.
Description: Calculate the inverse cumulative non-central f distribution function. The range of the result is [0, 1e300].
Where:
p is the CDF value (probability) [0, 1]
dfn is the number of degrees of freedom of the numerator (0, +infinity)
dfd is the number of degrees of freedom of the denominator (0, +infinity)
pnon is the non-centrality [0, +infinity)
(icdf-gamma p a b)
Library Routine: ICDFGamma
Type: Function returning a floating point value.
Description: Calculate the inverse cumulative gamma distribution function. The range of the result is [0, 1e300].
Where:
p is the CDF value (probability) [0, 1]
a is the first gamma parameter (shape) [0, +infinity]
b is the second gamma parameter (scale) [0, +infinity]
(icdf-negative-binomial p n prob)
Library Routine: ICDFNegativeBinomial
Type: Function returning a floating point value.
Description: Calculate the inverse cumulative negative binomial distribution function, (the expected number of failures before the nth success). The range of the result is [0, 1e300].
Where:
p is the CDF value (probability) [0, 1]
n is the number of successes (0, +infinity)
prob is the probability of success of a single trial [0, 1]
(icdf-normal p mean sd)
Library Routine: ICDFNormal
Type: Function returning a floating point value.
Description: Calculate the inverse cumulative normal distribution function. The range of the result is (-infinity, +infinity).
Where:
p is the CDF value (probability) (0, 1)
mean is the center of the distribution (-infinity, +infinity)
sd is the standard deviation [0, +infinity)
(icdf-poison p mean)
Library Routine: ICDFPoison
Type: Function returning a floating point value.
Description: Calculate the inverse cumulative poison distribution function. The range of the result is [0, 1e300].
Where:
p is the CDF value (probability) [0, 1]
mean is the center of the distribution [0 +infinity]
(icdf-students-t p df)
Library Routine: ICDFStudentsT
Type: Function returning a floating point value.
Description: Calculate the inverse cumulative Student’s T distribution function. The range of the result is [1e-300, 1e10]. A normal distribution, with mean 0 and standard deviation 1 may be used in place of Student's T, for very large degrees of freedom.
Where:
p is the CDF value (probability) [0, 1]
Back to contents

Unofficial Stuff

(:<< symbol formula ...)
Type: Pseudo-predicate returning false on error.
Description: Appends one or more literal formulas to the value of symbol. This routine is not very useful right now since lists aren't fully supported by TLPlan.

(def-defined-macro ...)
Type: Pseudo-predicate returning false on error.
Description: Generates a list of one or more literals at compile time. This routine is not very useful right now since there is no practical way to pass useful non-constant parameters to macros.

(set-control control-type)
Type: Pseudo-predicate returning false on error.
Description: Set the control type for the current planning problem. control-type is a quoted literal string, which may be either "temporal" or "atemporal". The default control type is "temporal".
Type Description
temporal This is the default control type. Unwanted states are pruned by "progressing" the temporal control formula.
atemporal Unwanted states are pruned by "evaluating" the control formula in atemporal form.
Many types of temporal control formulas can be expressed in atemporal (first order logic) form, within the context of the planner. Atemporal formulas require less permanent memory than temporal formulas, so atemporal control may be useful for longer plans.
Back to contents

HPlan-P

Using HPlan-P

Run the hplanp script in the following way:

hplanp <domain-file> <problem-file> <heuristic>

To plan for the problem supplied in domain given as argument. The <heuristic> parameter should be a number between 1 and 44. These heuristics are prioritizations of the different heuristic functions described in this paper. They are currently defined in the preference-heuristics.tlp file.

Based on the value provided by the user, the planner configures the heuristic using the (select-strategy ?s) function, defined in preference-heuristics.tlp. Therefore, if the heuristic argument to hplanp is 14, the OD(0.9) strategy will be used (see preference-heuristics.tlp).
Back to contents

Configuring new heuristics

As described in this paper, the hplanp-p planner internally implements a set of 5 functions that can be combined as a prioritization to guide the search of the planner. To define a new heuristics one needs only to define the priorities of the 5 different functions. Priorities are defined using the keywords that follow (functions being prioritized should be obvious in the context of the paper)

(set-metric-priority <n1>)
(set-discounted-metric-priority <n2>)
(set-best-relaxed-metric-priority <n3>)
(set-preference-distance-priority <n4>)
(set-optimistic-metric-priority <n4>)
The <n?> parameter is a number between -1 and 4. -1 indicates that the function is not used in the final heuristic. Numbers between 0-4 define the priority if a function is going to be used, with 0 being the highest priority, and 4 the lowest. In addition, the keyword (set-metric-discount <r>) is used to set the discount factor of the D function to <r>.

Example: Suppose we want to extend hplanp-p with a new heuristic OBD(0.4). This heuristic uses G to compare two states and in case of a tie, it uses O, then B and finally D(0.4). We will add this heuristic as heuristic number 45 in the planner.

First we need to add a function that configures the hplan-p priority parameters. Let us assume that this function will be called foo-heuristic. We add the following function to file preference-heuristics.tlp:

(def-defined-predicate (foo-heuristic)
(and
(set-optimistic-metric-priority 0)
(set-best-relaxed-metric-priority 1)
(set-discounted-metric-priority 2)
(set-metric-discount 0.4)
(set-metric-priority -1)
(set-preference-distance-priority -1)))
Now, to define this heuristics as number 45, we add the following piece of code to the (select-strategy ?s) function:

(implies (= ?s 45) (foo-heuristic))
Back to contents
[an error occurred while processing this directive]