Nondeterministic Action Planner - NonPlan

A Brief Manual

By Patrik Haslum.

NonPlan is a simple regressive, propositional planner designed mainly to demonstrate what planning scenarios, and their solutions, may look like in a formalism allowing nondeterministic context-dependent operators and arbitrarily incomplete initial state. It can not be expected to solve any problems of realistic size (or even larger toy-problems).

Some teoretical work underlying the planner can be found in my "exjobb".

Running the planner

The planner comes in the shape of an applet, and runs in an appletviewer or Java-capable web browser. It is currently located at

http://www.ida.liu.se/~pahas/nonplan/[scenario]

where [scenario] is the name of the scenario file. Scenario files currently include

Blocksworld (blocksworld.html): A small example from the well-known blocksworld.
The turkey scenario (turkey.html): Variations on the Yale shooting scenario, demonstrates planning with disjunctive initial state and/or non-deterministic actions.
RISC (risc.html): Assembler program synthesis for a very simple processor. A scenario with disjunctive initial state and context-dependent operators.

NOTE: The applet appears not to work in Netscape 4, or variations thereof. It works in Netscape 3, some version of Internet Explorer, and in the appletviewer.

The above scenarios and more, without the embedded applet, may be found in the examples section.

Overview and some terminology

The operators of the formalism are called actions (for want of a better word). The planner actually recognises only a subset of the formalism, actions without nested conditional reassignments. The planner preforms a regressive, and more or less exhaustive, search of the space of action sequences. All action sequences are termed plans, even if they are not actually plans in the sense that they solve the problem. The extensions of a plan are the plans formed be prepending the plan with some action. The remaining goal of a plan is a formula which has to be satisfied before execution of the plan for the true goal to be satisfied after execution. When the remaining goal is implied by the initial state the plan is complete, and a solution to the planning scenario.

The state of the world is described by a set of boolean variables, which called fluents.

Scenario descriptions

To run the planner, one has to specify a scenario, a problem for it to solve. In the three examples above there are scenario specifications allready, which can be run as is, or modified to try different variations.

The description language is mostly propositional logic. A literal is written f or !f. Fluents do not have to be declared in any way, and are allways boolean. A formula is a boolean combination of literals, using the connectives & (for and) and | (for or). Conjunctions and disjunctions must be enclosed in brackets, though it is possible to have more than one connective of the same kind within the same pair of brackets. A reassignment is written f := v, where f is a state variable and v is a constant from the variables value domain. Since all variables are boolean, the only constants used are T and F. A reassignment formula is a boolean combination of reassignments, using the same connectives and bracketing as for formulas.

A scenario description contains five different types of information, each distinguished by a keyword at the beginning of the line. They are:

Action specifications

The format of an action specification is

act A => (p₁ -> e₁, p₂ -> e₂, ..., p_n -> p_n)

where A is the action identifier, p_i is a formula and e_i is a reassignment formula. Each expression p_i -> e_i constitutes a branch of the action. The conditions of all branches of an action must be mutually exclusive.

Initial state

It is possible to state observations at arbitrary timepoints, but only those at timepoint 0 will be considered by the planner. The conjunction of all observations at timepoint 0 constitutes the initial state. The format of an observation is

sch [t]a

where t is an integer (usualy 0) and a is a formula.

Goal

The goal is specified as an observation, using the keyword goal instead of sch. The timepoint specified for the goal is used by the planner as cost bound when searching depth-first.

Domain constraints

Domain constraints are facts that hold in every possible world situation, but which are not logical tautologies. They can be used stop the planner from considering intermediary goals that are impossible to achieve, but which are nontheless satisfiable formulas. The format of a domain constraint is

con c

where c is a formula describing the constraint.

Schedule statements

Schedule statements specify which actions will be executed and when. Any schedule statements in the scenario description are ignored by the planner. Pressing the Fill in scenario button causes the planner to replace any schedule statements with the last found plan, if any plan has been found. The format of a schedule statement is

sch [s,t]A

where s and t are timepoints and A is the action identifier.

The control window

The control window consists of a large text display showing the scenario, as described above, and a number of option switches and buttons. The scenario display can be edited to run variations on the basic scenario, or to write in an alltogether new scenario.

The functions of the buttons are:

Read scenario: Parses the text in the scenario display. If successfull it reprints the scenario in the display, which will result in comments disappearing, charater conversion to lower case, etc, and shows that the parsing was without problems.
Start planner: Resets trace and starts a new search with the currently selected options. If the scenario has not been read, this is done first. Available actions are those of the last read scenario, initial state is the conjunction of all observations at timepoint 0 and goal is the goal specified in the scenario. The timepoint for the goal is used as cost bound in depth-first searches.
Fill in scenario: Fills in the scenario with the last found plan, in the form of schedule statements for actions in the plan. If no plan has been found, it does nothing.
Step: Single steps the search. This is only available after the search has been started. After each single step, the search is frozen.
Continue: Resumes a frozen search. The search freezes when a plan is found, or after executing a single step.

The options are:

Breadth-first/Depth-first search: Selects the order of search tree traversal.
Extensions using fwlp: Selects the type of goal direction. fwlp implements a stronger direction condition, but is incomplete for scenarios containing non- deterministic actions or incomplete information about the initial state. If this option is not selected, the weaker goal direction condition relevance is used.
Preferential enumeration: Selecting this option causes the planner to search the tree of possible plans in a heuristic order of fitness, i.e. in best-first order. When searching breadth-first, this ordering is applied to the entire front of the search tree, and when searching depth-first it is applied to the possible extensions to each considered plan. The heuristic used is degree of entailment, defined as the ratio of the number of models that satisfy both the initial state and the remaining goal over the number of models that satify the initial state.

The trace window

The trace window shows information about the ongoing search. It has five information fields:

Information on the currently examined plan: Shows plan number, length, cost and fitness. Cost is the same as length. The fitness value is an estimate of how close the plan is to solving the problem, and is only used if the preferential enumeration option is selected.
Currently examined plan: If the Show examined plan option is selected, the plan currently being examined is shown in this text field.
Information on extensions: Shows the number of extensions generated by the currently examined plan, the average number of extensions generated by plans examined so far, the total number number of extensions generated by all plans examined so far and the number of extensions generated but not yet examined.
Extensions list/Resulting plan: If the Show extensions option is selected, the extending action of all extensions generated by the currently examined plan is listed in this field. The number in brackets following the action name is the fitness value of the resulting plan, a dash indicates that action was either not relevant or not possible. Double-clicking an action in the extensions list displays the resulting plan in the text field next to it.

The trace window also has three option checkboxes, and a button:

Show examined plan, Show extensions

Selects the level of detail in the trace output, as explained above.

Summary

Pressing the summary button opens a dialog window in which a brief summary of the current search is printed. The window has to be closed and then opened again to get a new summary.

The summary shows the number of SAT tests performed, and the average number of fluents in each test. Complete SAT tests refer to tests where all possible combinations of fluent values have been tested (this is used when computing the degree of entailment). Fixed fluents, as opposed to variable, are those that occur in a formula either only in possitive or only in negative, and which therefore do not have to be tested in both forms. The number of SAT tests multiplied by the average number of varying fluents provides a good implementation semi-independent measure of how much work the planner has to do to solve a problem.

The summary also lists the number of plans examined and the number of extensions generated. The average branching factor is the average number of extensions generated for each plan examined. The number of bound-outs is the number of plans that have been discarded because their length exceeds the given limit (this can only happen when performing a depth- first search).

Force window updates

Obsolete.