Performance of Planning Systems

A. Meystel

Drexel University, National Institute of Standards and Technology

Planning is learning from experience in the

domain of imagination.

From the Section 10 of this paper

The goal of this paper is to help in the organization of

further research in the area of Planning.

1. Emergence and Development of the Theoretical

Domain on Planning

The area of planning is a victim of linguistics:

professionals of different domains give different

interpretation to the phenomenon of "planning."

Traditionally, it was associated with human activities

and the help of science was expected

a) in a better organization of information for

planning supporting the way the humans plan

b) in proposing of techniques that help to

come up with "interesting" alternatives of planning

decisions

c) in structuring the process of planning so

that to make it more efficient

d) in modeling human activities during the

process of planning.

Simon and Newell were the first that

visualized planning as an element of each problem

solving process. However, AI treated planning in the

way it treated other problems - with the help of toyproblems (like Hanoi-Tower and block-world

situations.

Specialists in control did not realize and did

not appreciate the fact that feedforward control is

actually the result of planning. The elegant discoveries

of Nilsson and Fikes in their heuristic search methods

remained unnoticed by control community until

recently.

Specialists in automation of therapeutic

solutions did not realize that they plan the process of

disease development and plan the process of healing.

Specialists in education did not realize that

proposing a curriculum and/or a particular syllabus has

no difference from the processes of feedforward

control and process of disease development and

healing.

Specialists in optimization (re: operation

research) did not realize that their problems were just

elements of the planning theory.

Specialists in cognitive psychology seldom

saw anything in common between "planning" and

"imagination."

Thinkers of finding the goal did not have

anything in common with thinkers computing

schedules of goal achievement.

A common wisdom about planning was (and

is) that there are many ways of planning and each of

them has its place.

The following linkages were totally

neglected:

a) the linkage between off-line planning and

on-line control,

b) the linkage between specifying the goal

and finding a schedule of achieving the goal.

c) the linkage between the linguistics of

finding the image of "goal" and searching of the best

schedule.

d) the linkage between the methodology and

the performance of planning.

2. Planning for Behavior Generation

Robotics became the integrated domain that

provided for blending the goals and testing the means

of achieving them, i.e. a domain with a direct need for

planning. In 1983, T. Lozano-Perez has introduced the

idea of search in "configurations space". From the

experience of using this search, it became clear that the

exhaustive search would be computationally

prohibitive if the configuration space is tessellated with

the accuracy required for motion control. But his

theory made two important thing obvious: 1) planning

is an apogee of creating admissible alternatives and

searching for the trajectories entailed by these

alternatives. 2) planning is performed upon milestones

in the state space, and if they do not exist in the reality,

they should be created artificially (re: centers of the

tessellata in the configuration space).

This development helped to realize that

planning should combine the exhaustive (or

meaningfully thorough) search off-line, and an

efficient algorithm of an off-line control. It was about

of this time that we stopped talking about control of

actions and introduced a more balanced term of

Behavior Generation. The latter became a codeword

for the joint process of arranging and testing the

alternatives within the mechanism of "planning" (open
loop, feedforward control) blended with the on-line

finding the alternatives of feedback for error

compensation (closed-loop control, or "execution").

Behavior Generation alludes to many

mechanisms of planning and execution. At the present

time, these mechanisms cannot be considered as

known thoroughly, and the general theory of planning

can hardly be immediately attempted. There is a merit

in discussing a subset of problems in which the goal is

determined as attainment of a particular state.

The following are scattered notes on the

progress in the domain of planning.

• Most of the realistic problems can be

translated into this paradigm. Other types of

realizations can also be imagined: in chess the

goal is clear (to win) but this goal cannot be

achieved by achieving a particular position in

a space (even in a descriptive space.) Most of

the problems related to the theory of games

and linked with pursuit and evasion are

characterized by a similar predicament.

• Let us notice the following: no matter what is

the domain of decision making, the process of

planning can be performed only by searching

the state space and thus, determining both the

final goal, and the trajectory of motion

leading to this goal.

• In 1981 J. Albus has introduced the

methodology of task decomposition for

hierarchical systems which has grown into a

NIST-RCS methodology.

• In 1981 G. Giralt outlines the concept of

planning for mobile robots via tessellated

space.

• In 1983, T. Lozano-Perez has introduced

search in Configuration Space.

• In 1986, A. Meystel has demonstrated (CDC,

Athens) that the most efficient functioning of

a multilevel learning/control systems can be

provided by a proper choice of a ratio of

lower level/higher level of resolution. This

concept of planning/control becomes a strong

theoretical support for the hierarchical

architecture of intelligent system control

developed by J. Albus during the period of

1980-1998.

• In 1985-87 M. Arbib's school of control via

"schemata" came up with a numerous

schemes of "reactive" behavior. This gave

birth to a multiplicity of robot control

concepts which explore and exercise reactive

behavior generation.

• In the meantime, the primary focus of

robotics shifts to the area of systems which do

not require any planning (robotics with

"situated behavior"). Thus, the interest in

planning diminishes (R. Brooks, MIT, R.

Arkin, Georgia Tech) and the curiosity of

researchers shifts toward emerging

phenomena in non-intelligent robots.

3. Planning in a Representation Space with a Goal

This is an outline of the common

methodology of planning pertaining to most of the

disciplines and areas of application. The world is

assumed to be judged upon by using its State Space (or

the Space of Representation) which is interpreted as a

time tagged vector space with a number of important

properties. Any activity (motion) in the World (Space

of Representation) can be characterized by a trajectory

of motion along which the "working point" or "present

state" (PS) is traversing this space from one point

(initial, or state, IS) to one or many other states (goal

states, GS.) The goal states are given initially from the

external source as a "goal region", or a "goal subspace"

in which the goal state is not completely defined in a

general case. 

From the point of view of planning, state

space does not differ from the configuration space.

Indeed, the upcoming behavior is represented as a

trajectory in the state-space (and/or configuration

space). One of the stages of planning (often the initial

one) is defining where exactly is the GS within the

"goal region." In this paper, we will focus upon

planning problems in which one or many GS remain

unchanged through all period of their achievement.

Traversing from IS to GS is associated with consuming

time, or another commodity (cost). So, the straightforward exhaustive search is feasible which allows for

exploring all possible alternatives.

Researchers in the area of reactive behavior

introduced a method of potential fields for producing

comparatively sophisticated obstacle avoiding schemes

of motion. Reactive behavior is considered to be an

anti-thesis for planning. It is not so. Planning based

motion can be called reactive, too. The difference is

that in the papers on reactive behavior, we react to the

present situation. In the system with planning, we react

too: but we react to the anticipated future.

Thus, planning can be considered an

anticipatory reactive behavior. The difference is in the

fact that anticipation requires representation richer than

the simple reactive behavior requires. The philosophy

of the approach affects the performance of planning.

4. Types of Representation Available

All Representation Spaces are acquired from

the external reality by the processes of Learning. Many

types of learning are mentioned in the literature

(supervised, unsupervised, reinforcement, dynamic,

PAC, etc.) Before classifying a need in a particular
method of learning and deciding how to learn, we

would like to figure out what exactly we should learn.

Can the process of learning be separated into two

different learning processes:

• that of representation, and

• that of the rules of action,

or are these two kinds of learning just two sides of the

same core learning process?

The following knowledge should be contained

in the Representation Space. If no GS is given, any

pair of state representations should contain implicitly

the rule of moving from one state to another. In this

case, while learning we inadvertently consider any

second state as a provisional GS.

 We will call "proper" representation a

representation similar to the mathematical function

and/or field description: at any point the derivative is

available together with the value of the function; the

derivative can be considered an action required to

produce the change in the value of the function.

We will call "goal oriented" representation a

representation in which at each point a value of the

action is given required for describing not the best way

of achieving an adjacent point but the best way of

achieving the final goal.

Both "proper" and "goal oriented"

representations can be transformed into each other.

However, they differ in the productivity of planning.

5. Components of Representation Space

Representation (that of the World) can be

characterized by the following artifacts:

• existence of states with its boundaries

determined by the resolution of (each

state is presented as a tessellatum, or an

elementary unit of representation, the

lowest possible bounds of attention)

• characteristics of the tessellatum which is

defined as an indistinguishability zone

(we consider that resolution of the space

shows how far the "adjacent" tessellata

(states) are located from the "present

state" (PS)

• lists of coordinate values at a particular

tessellatum in space and time

• lists of actions to be applied at a

particular tessellatum in space and time

in order to achieve a selected adjacent

tessellatum in space and time

• existence of strings of states intermingled

with the strings of actions required to

receive next consecutive tessellata of

these strings of states

• boundaries (the largest possible bounds

of the space) and obstacles

• costs of traversing from a state to a state

and through strings of states.

In many cases, the states contain information

which pertains to the part of the world which is beyond

our ability to control it, and this part is called

"environment." Another part of the world is to be

controlled: this is the system for which the planning is

to be performed. We will refer to it frequently as

"self." Thus, a part of the representation is related to

"self" including knowledge about actions which this

"self" should undertake in order to traverse the

environment.

It is seen from the list of artifacts that all

knowledge is represented at a particular resolution.

Thus, the same reality can be represented at many

resolutions and the "multiresolutional representation"

is presumed.

The system of representation is expected to be

organized in a multiresolutional fashion. This will

invoke the need in applying a number of special

constraints and rules. The rules of inclusion

(aggregation/decomposition) are especially important.

6. Planning in Redundant Systems

Non-redundant systems have a unique

trajectory of motion from a state to a state. Redundant

system is defined as a system in which there is more

than one trajectory of motion from one state to another.

It can be demonstrated for many realistic couples

"system-environment" that

• they have a multiplicity of traversing

trajectories from a IS to a GS

• these trajectories can have different costs.

These systems contain a multiplicity of

alternatives of space traversal. Redundancy grows

when the system is considered to be a stochastic one.

The number of available alternatives grows even

higher when we consider also a multiplicity of goal

tessellata of a particular level of resolution under the

condition of assigning the goal at a lower resolution

level which is the fact in multiresolutional systems

(such as NIST-RCS.)

In on-redundant systems there is no problem

of planning. Since the trajectory of motion to be

executed is a unique one, the problem is to find this

trajectory and to provide tracking of it by an

appropriate classical control system.

7. Learning as a Source of Representation

Learning is defined as knowledge acquisition

via experience of functioning. Thus, learning is

development and enhancement of the representation

space under various goals. The representation can be

characterized in the following ways:

• by a set of paths (to one or more goals)

previously traversed
• by a set of paths (to one or more goals)

previously found and traversed

• by a set of paths (to one or more goals)

previously found and not traversed

• by a totality of (set of all possible) paths

• by a set of paths executed in the space in a

random way.

One can see that this knowledge contains

implicitly both the description of the environment and

the description of the actions required to traverse a

trajectory in this environment. Moreover, if some

particular system is the source of knowledge, then the

collected knowledge contains information about

properties of the system which moved in the

environment.

All this information arrives in the form of

experiences which record states, actions between each

couple of states, and evaluation of the outcome. The

collection of information obtained in one or several of

these ways forms knowledge of space, KS.

If the information base contains all tessellata

of the space with all costs among the adjacent

tessellata - we usually call it the “a complete

representation.” The tessellation can be a randomized

one: a factor strongly affecting the performance.

Thus, the representation is equivalent to the

multiplicity of explanations how to traverse, or how to

move. In other words: all kinds of learning mentioned

in p. 3 are equivalent.

Comments: a) Knowledge of the space (KS)

is realized via knowing states, and/or knowing the

"derivatives" (or actions) from a state to a state.

 b) Apparently, each state can be

characterized by some cumulative cost (value), while

each traversal from a state to a state can be

characterized by some incremental cost (goodness of a

move or a set of moves.)

8. Standardizing the Problems of Planning

Any problem of planning is associated with

• actual existence of the present state

• actual, or potential existence of the goal state

• knowledge of the values for all or part of the

states as far as some particular goal is

concerned.

From this knowledge the cumulative costs of

trajectories to a particular goal (or goals) can be

deduced. On the other hand, the knowledge of costs for

the many trajectories traversed in the past can be

obtained which is equivalent to knowing cumulative

costs from the initial state (PS) to the goal state (GS)

(from which the values of the states can be deduced.)

In other words, any problem of planning

contains two components: the first one is to determine

and/or to refine the goal (bring it to the higher

resolution.) The second one is to determine the motion

trajectory to this refined goal. These two parts can be

performed together, or separately. Frequently we are

dealing with them separately. In the latter case they are

formulated as follows:

a) given PS, GS and KS (all paths) find the

subset of KS with a minimum cost, or with a preassigned cost, or with a cost in a particular interval.

b) given PS and GS from the lower resolution

level and KS (all paths) find the GS with a particular

value (which is satisfactory for the system).

9. Performance of Planning Algorithms

Finding solutions for these problems is done

by a process that is called planning. In other words,

planning is construction of the goal states, and/or

strings of states connecting the present state with the

goal states. Performance of planning algorithms is

determined by the way these procedures are arranged.

The first component of the planning algorithm

is translation of the goal state description from the

language of low resolution to the level of high

resolution. Frequently, it is associated with increasing

of the total number of the state variables. In all cases it

is associated with reduction of the indistinguishability

zone, or the size of the tessellatum associated with a

particular variable.

The second component is the simulation of all

available alternatives of the motion from the initial

state, IS to one or several goal states, GS and selection

of the "best" trajectory. Procedurally, this simulation is

performed as a search, i.e. via combinatorial

construction of all possible strings (groups). To make

this combinatorial search for a desirable group more

efficient we reduce the space of searching by focusing

attention.

Thus, all planning algorithms consist of two

components: a) a module for exploration of spatial

distribution of the trajectory, and b) a module for

exploration of the temporal distribution. No algorithm

of planning is conceivable without these two

components.

The need in planning is determined by the

multialternative character of the reality The process of

planning can be made more efficient by using

appropriate heuristics which is not considered in this

paper.

10. The Relations Between Planning and Learning

Planning is learning from experience in the

domain of imagination. Planning is performed by

searching within a limited subspace

• for a state with a particular value

(designing the goal)

• for a string (a group) of states

connecting SP and GP satisfying
some conditions on the cumulative

cost (planning of the course of

actions)

The process of searching is associated ether

with collecting the additional information about

experiences, or with extracting from KS the implicit

information about the state and moving from state to

state, or learning. In other words, planning is

inseparable from and complementary to learning.

This unified planning/learning process is

always oriented toward improvement of functioning in

engineering systems (improvement of accuracy in an

adaptive controller) and/or toward increasing of

probability of survival (emergence of the advanced

viruses for the known diseases that can resist various

medications, e.g. antibiotics.)

Thus, this joint process can be related to a

system as well as to populations of systems and

determines their evolution.

11. Other Components of Planning

Planning algorithms consist of the procedures

of Job Assignment and Scheduling. Job Assignment

distributes the motion among the spatial coordinates.

Scheduling distributes the motion along the time axis.

Together, they contribute to the search process. Search

is performed by constructing feasible combinations of

the states within a subspace. (“Feasible” means:

satisfying a particular set of conditions.) Search is

interpreted as exploring (physically, or in simulation)

as many as possible alternatives of possible motion and

comparing them afterwards.

Each alternative is created by using a

particular law of producing the group of interest

(cluster, string, etc.) Usually, grouping presumes

exploratory construction of possible combinations of

the elements of space (combinatorial search) and as

one or many of these combinations satisfy conditions

of "being an entity" - substitution of this group by a

new symbol with subsequent treating it as an object

(grouping.)

The larger the space of search is the higher is

the complexity of search. This is why a special effort is

allocated with reducing the space of search. This effort

is called focusing attention and it results in

determining two conditions of searching, namely, its

upper and lower boundaries:

a) the upper boundaries of the space in which

the search should be performed, and

b) the resolution of representation (the lower

boundaries)

12. Planning Embodies the Intelligence of a System

Formation of multiple combinations of

elements (during the search procedure, S) satisfying

required conditions of transforming them into entities

(grouping, G) within a bounded subspace (focusing

attention, F) is a fundamental procedure in both

learning and planning. Since these three procedures

work together we will talk about them as about a triplet

of computational procedures which include grouping,

focusing attention and search (GFS.) Notice, that in

learning it creates lower resolution levels out of higher

resolution levels (bottom-up) while in planning it

progresses from the lower resolution levels out of

higher resolution levels (top-down.)

This triplet of computational procedures is

characteristic for intelligence and probably is the

elementary computational unit of intelligence. Its

purpose is transformation of large volumes of

information into a manageable form which ensures

success of functioning. The way it functions in a joint

learning-planning process explains the pervasive

character of hierarchical architectures in all domains of

activities.

The need in GFS is stimulated by the property

of knowledge representations to contain a multiplicity

of alternatives of space traversal (which is a property

of representations to be redundant.) Redundancy of

representations determines the need in GFS: otherwise

the known systems would not be able to function

efficiently (it is possible that redundancy of

representations is a precondition for the possibility of

Life and the need in Intelligence)

13. Planning is Inseparable From Control

Development of a plan is equivalent to

computing the "feedforward control." To compute

FFC, we have to have a model of a system

(representation) and apply an operation if inverse

(computing the required FFC control commands for

the motion preassigned). Even if a system

representation is in a not-invertible form, the inverse

can be found by a forward searching.

 Representations reduce the redundancy of

reality. Elimination of redundancy allows for having

problems that can be solved in a closed form (no

combinatorics is possible and/or necessary).

Sometimes, this ultimate reduction of redundancy is

impossible and the combinatorial search is the only

way of solving the problem). If the problem cannot be

solved in a closed form, we introduce redundancy

intentionally to enable functioning of GFS (grouping,

focusing attention, and searching).

At each level of resolution, planning is done

as a reaction for the slow changes in situation which

invokes the need in anticipation and active interference

a) to take advantage of the growing

opportunities, or

b) to take necessary measures before the

negative consequences occur.
The deviations from a plan are compensated

for by the compensatory mechanism also in a reactive

manner. Thus, both feedforward control (planning) and

feedback compensation are reactive activities as far as

interaction system-environment is concerned. Both can

be made active in their implementation. This explains

different approaches in control theory.

Examples:

a) Classical control systems are systems with

no redundancy, they can be solved in a closed form.

Thus, they do not require any searching.

b) Any stochastics introduced to a control

system creates redundancy and requires either for

elimination of redundancy and bringing the solution to

a closed form, or performing search.

c) Optimum control allows for the degree of

redundancy which determines the need in searching.

Recently, an area of "supervisory control" has

emerged as a partial introduction of the control theory

to the domain of planning.

14. Research for Planning: Topics For Exploration

and Discussion

The following research topics can be outlined:

a) development of the system of

representation for planning purposes; it should provide

for a multiresolutional organization of information

b) analysis of existing and potentially

beneficial techniques of synthesizing the goal

assignments (spatial plan distribution)

--by using combinatorial techniques

(computer and human-based)

--by analytical methods (e.g.

variational)

c) analysis of existing and potentially

beneficial techniques of determining preferable

clusters, or groups: determining the preferred

schedules for strings of the way points, or milestones

(temporal plan distribution)

--by using search in the state space

--by using game-theoretical methods

--by using self-organization of

multiple agents

d) quantitative evaluation of the tools for

narrowing attention: determining envelopes around the

trajectory of motion (string of the milestone events) for

the consecutive refinement (repetition of the planning

procedure at the higher resolution level)

e) construction of the state spaces for the

consecutive searching

f) analysis of the methodologies of state-space

tessellation for applying different 

methodologies of consecutive refinement

g) exploring the methods of search applicable

for determining the preferential strings

--by searching techniques induced by

dynamic programming

--by standard techniques of

exhaustive search

--by methods of heuristic guiding

during the search

--by searching via evolutionary

programming

--by searching in nonlinear problems

h) testing the results of planning via various

simulation methodologies

i) exploring the phenomenon of nestedness of

plans obtained at various resolutions (at various

levels of resolution)

j) dealing with uncertainties of information

--by decision-making procedures

when the values of alternatives are

uncertain and do not allow for an

unequivocal choice

--by development and maintenance

of contingency plans

k) analyze the role of prediction in planning,

develop a system of creating and using predictions

l) analyze the phenomenon of goal

m) determine methods of forming different

functionals of "cost", or "goodness"

n) explore planning under condition of

multiple criteria (costs)

o) test benefits and deficiencies of various

schemes of decision-making in planning

p) the computer aspects of planning are

virtually unexplored: do we need a language for

planning?

All positions of this list affect the

performance both of the system in the World and of

planning algorithms as a part of the Design process.