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.
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.
The system
is distributed as a tar file named tlplan.tar Follow the following
sequence of steps.
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.
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
Commands for Defining a Domain
Initializations
and Declarations
Commands for Defining 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
Commands
for Handling Files and I/O
Commands for Installing a Domain
Routines
for Interrogating the Current World
Routines
for Retrieving Planning Statistics
Arithmetic
Functions and Predicates
CDF – Cumulative
Distribution Functions
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.
Type: Pseudo-predicate returning false on
error.
Description: Define name as an abbreviation for list. This allows macro substitution in
domain definition files.
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).
Type: Term.
Description: Any symbol, number, or string is a
term.
Type: Term.
Description: Any symbol that starts with ? is a variable, and is also a term.
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.
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).
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.
Type: Predicate.
Description: Equality is a predefined binary
predicate.
Type: Predicate.
Description: The constant atomic formula that
always evaluates to true.
Type: Predicate.
Description: The constant atomic formula that
always evaluates to false.
Type: Predicate.
Description: Any atomic formula is a first-order formula.
Type: Predicate.
Description: The logical and of a sequence of
formulas.
Type: Predicate.
Description: The logical or of a sequence of
formulas.
Type: Predicate.
Description: The logical exclusive or of a
sequence of formulas.
Type: Predicate.
Description: The logical negation of formula.
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) ...))
(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.
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.
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.
Type: Temporal formula.
Description: Any first-order formula is a temporal formula,
as is any first-order formula that contains temporal formulas.
Type: Temporal formula.
Description: This formula is true of a sequence
of states iff the temporal formula tf is true in the next state.
Type: Temporal formula.
Description: This formula is true of a sequence
of states iff the temporal formula tf is true of some future state.
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.
Type: Temporal formula.
Description: This formula is true of a sequence
of states iff the temporal formula tf is true for all future states.
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.
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.
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.
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.
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.
(def-strips-operator
name pre
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.
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.
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.
The
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.
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.
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.
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.
(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
The add and del clauses have the same syntax as the
corresponding STRIPS clauses. However, within ADL operators, add and
Modifier
clauses are preprocessed internally by the planner so that all deletions act
before all additions. When a modifier clause contains both add and
(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.
(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.)
Type: Pseudo-function returning a
formula.
Description: Display the current temporal
control formula.
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 |
|
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. |
|
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. |
|
|
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. |
|
|
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. |
|
|
The planner does breadth-first search without considering
successor priority. |
|
|
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.
Type: Function returning a string value.
Description: Display the planner's current
search strategy.
Type: Pseudo-predicate returning true.
Description: Reset the planner's search strategy
to its default.
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.
Type: Function returning an integer
value.
Description: Return the planner's current search
limit.
Type: Pseudo-predicate returning true.
Description: Reset the planner's search limit to
its a positive number.
Type: Pseudo-predicate returning true.
Description: Disable search depth limiting in
the planner.
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.
Type: Function returning a floating point
value.
Description: Return the current heuristic limit.
Returns 0 if heuristic limiting is disabled.
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. |
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.
Type: Pseudo-function returning a
formula.
Description: Return the current priority
function.
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.
Type: Function returning an integer
value.
Description: Return the priority of the
instantiated operation that created the current world.
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.
Type: Pseudo-function returning a
formula.
Description: Display the current heuristic
formula, used by best-first search.
Type: Pseudo-predicate returning true.
Description: Reset the current heuristic formula
to 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.
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.
Type: Function returning a numeric value.
Description: Execute the current heuristic
function on the current world.
Type: Pseudo-predicate returning true.
Description: Select verbose output.
Type: Pseudo-predicate returning true.
Description: Select terse output.
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.
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.
Type: Pseudo-predicate returning false on
error.
Description: Load a domain. name
is the domain's defined name. See def-domain.
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.
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.
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.
(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.
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.
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.
|
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.
|
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.
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.
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.
|
|
~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.
|
|
~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.
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.
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.
Type: Pseudo-predicate returning true.
Description: Restore the print world function to
the default generic print world function.
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):
|
|
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. |
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.
Type: Function returning an integer
value.
Description: Return the depth of the current
world in steps.
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).
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).
Type: Pseudo-function returning a
formula.
Description: Return the instantiated operation
that generated the current world.
Type: Function returning a floating point
value.
Description: Return the cost of the action that
generated the current world.
Type: Function returning an integer
value.
Description: Return the priority of the action
that generated the current world.
Type: Function returning a floating point
value.
Description: Return the duration of the action
that generated the current world.
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.
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.
Type: Function returning an integer
value.
Description: Return the number of worlds
discarded due to cycle checking.
Type: Function returning an integer
value.
Description: Return the number of worlds pruned
by the control formula.
Type: Function returning an integer
value.
Description: Return the number of worlds
expanded by the planner, but not pruned
Type: Function returning an integer
value.
Description: Return the number of worlds
generated by the planner, but never expanded.
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.
Type: Function returning an integer value.
Description: Return the maximum plan length
explored by the planner.
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.
Type: Pseudo-predicate returning true.
Description: Clear the name of the current
planning session.
Type: Function returning a string value.
Description: Return the name of the current
planning session, as specified by set-plan-name.
Type: Function returning a numeric value.
Description: Calculate the sum of all arguments.
All arguments must be numeric. The result is floating point.
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).
Type: Function returning a numeric value.
Description: Calculate the product of all
arguments. All arguments must be numeric.
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.
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.
Type: Function returning a numeric value.
Description: Calculate the maximum of all
arguments. All arguments must be numeric.
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).
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.
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.
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.
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).
Type: Function returning an integer
value.
Description: Round a (floating point) number, n, to the nearest integer.
Type: Function returning an integer
value.
Description: Truncate a (floating point) number,
n, to the
nearest integer (toward zero).
Type: Function returning an integer
value.
Description: Truncate a (floating point) number,
n, to the
nearest integer less than or equal to n.
Type: Function returning an integer
value.
Description: Raise a (floating point) number, n, to the nearest integer greater
than or equal to n.
(= 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.
Type: Predicate.
Description: Returns true iff both arguments are
numbers and the first argument is less than the second.
Type: Predicate.
Description: Returns true iff both arguments are
numbers and the first argument is not greater than the second.
Type: Predicate.
Description: Returns true iff both arguments are
numbers and the first argument is greater than the second.
Type: Predicate.
Description: Returns true iff both arguments are
numbers and the first argument is not less than the second.
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.
Type: Pseudo-predicate returning true.
Description: Reset the current random number
generator to the default (fibonacci).
Type: Function returning an integer
value.
Description: Calculate a random number. The
range of the result depends on the currently selected random number generator.
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.
Type: Function returning a floating point
value.
Description: Calculate a random number between
limits low and high. Low must be less than 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.
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).
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.
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.
Type: Pseudo-predicate returning false on
error.
Description: Select the last world generated by
a successful planning session.
Type: Pseudo-predicate returning false on
error.
Description: Select the initial world specified
by set-initial-world.
Type: Pseudo-predicate returning false on
error.
Description: Select the world following the
current (background) world.
Type: Pseudo-predicate returning false on
error.
Description: Select the world preceding the
current (background) world.
Type: Pseudo-predicate (does not return).
Description: Exits TLPlan.
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.
(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
(add 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).
Both add and
Whenever
both add and
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,
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.
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.
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.
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.
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]
(:<< 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. |