Controlling Deliberation with the Success Probability
in a Dynamic Environment
Seiji YamadaInterdisciplinary Graduate School of Science and Engineering
Tokyo Institute of Technology
4259 Nagatsuda, Midori-ku, Yokohama, Kanagawa 226, JAPANE-mail: yamada@ymd.dis.titech.ac.jp

Abstractwith a Bayesian network, and we have developed aThis paper describes a novel method to interleave planning with execution in a dynamic environment. Though, in such planning, it is very
important to control deliberation: to determine
the timing for interleaving them, few research has
been done. To cope with this problem, we propose a method to determine the interleave timingwith the success probability, SP , that a plan will
be successfully executed in an environment. We
also developed a method to compute it eciently
with Bayesian networks and implemented SIP
system. The system stops planning when the locally optimal plan's SP falls below an execution
threshold, and executes the plan. Since SP depends on dynamics of an environment, a systemdoes reactive behavior in a very dynamic environment, and becomes deliberative in a static one.
We made experiments in Tileworld by changing
dynamics and observation costs. As a result, wefound the optimal threshold between reactivity
and deliberation in some problem classes. Furthermore we found out the optimal threshold isrobust against the change of dynamics and observation cost, and one of the classes in which SIP
works well is that the dynamics itself changes.

Introduction

tive behavior in a very dynamic environment, and becomes deliberative in a static one. Thus our approach
integrates reactivity with deliberation depending on
dynamics of an environment, and gives a solution to
the above issue.
We implemented the

SIP system for evaluating ourapproach, and made various experiments in the simplied Tileworld by changing dynamics and observation
costs. As a result, we found the optimal threshold exists between reactivity and deliberation in some problem classes.

Furthermore we found out the optimal

threshold is independent of the change of dynamics
and observation cost, and one of the classes in which

SIP works well is that the dynamics itself changes.

Elegant studies have been done on learning an optimal policy with time constraints in stochastic au-

tomata, and the envelop was proposed to speedup thelearning (Deanet al.

et al. 1993a).
deliberation scheduling

1993b)(Dean

Furthermore the agent does

for assigning the computational resource to making envelopes and optimizing a policy (Deanet al.

in an environment, and the time constraints are ex-ment, reactive planning recently has become a significant topic in arti cial intelligence and robotics (Agre& Chapman 1987)(Brooks 1986) (George

SP eciently. Since SP depends

1993b)(Dean et al. 1993a). However no goal changes

To select an action for an agent in a dynamic environ-1987).

method to computeon dynamics of an environment, our system does reac-& LanskySome researchers argue no planning is neces-sary to intelligent behavior. However, we obviously require planning for more intelligent behavior including

plicitly given to an agent. In a Tileworld whereSIP

is evaluated, goals constantly change and no explicit
time constraint is given.

Since the time constraints

exist implicitly in an environment, an agent has to estimate them with observation.
Though McDermott

rst proposed the interleaveplanning (McDermott 1978), he did not describe any

prediction, and need to integrate reactivity with de-method to determine the timing of interleaving. Pol-liberation. In this context, there is a signi cant issue:lack made experiments in a Tileworld for investigat-

how to control deliberation in a dynamic environment.

ing an IRMA model (Pollack & Ringuette 1990), andUnfortunately we have few promising solutions.

Kinny studied the relation between commitment andIn this paper, we propose a novel method to interleave planning with execution in a dynamic environment.

dynamics (Kinny & George1991)(Kinny, George , &Hendler 1992). Unfortunately they did not deal withFor controlling deliberation: determining thecontrolling deliberation. Boddy proposed the anytime

timing to switch planning to execution, a system uses

algorithm which returns better answer as time passes

the success probability,

SP that it successfully exe-

cutes a plan in an environment. A plan is represented(Boddy & Dean 1989).

However they focused on atime restriction, and did not directly deal with envi-ronment dynamics. Subsumption architecture (Brooks1986) tried to integrates reactivity with deliberation.

De nition 1 (a dynamic environment)
A dynamic environment where a

SIP agent acts is

Unfortunately it did not provide a general procedure toa problem space where goals appear and disappear as

determine when a high-level process subsumed the low-time passes.

level ones. Drummond's goal satisfaction probability

agent repeatedly tries to achieve a goal before it dis-Each goal

Gi has value Vi and a SIP(Drummond & Bresina 1990) is similar to ours. How-appears and obtains the value. The agent's purpose isever the operators are too simple to represent complex

to get as high total value as possible.

causality.
Kirman investigated the prediction of real-time planner performance by domain characterization (Kirman1994). Our work of characterizing the class in which

SIP works well is concerned with his study. However,since his framework is de ned on the Markov decision
process and our domain including a Tileworld may notsatisfy the Markov property, we consider that his approach is not straightforwardly applied to our domain.

Our study is also concerned with real-time search.
RTA* (Korf 1990) is real time search which interleaves
planning with execution.

Though RTA* is constant-time planning, dynamics was ignored and no method
to determine the interleave timing. DTA* (Russell &Wefald 1991) is a decision-theoretic search algorithm
interleaving planning with actions.

It control delib-

eration by estimating the possibility that the further
search may overrule the current decision. In contrast
with DTA*,

SIP estimates the possibility that the cur-rent plan execution will be success. Furthermore DTA*
dose not do modeling an environment.

Ishida ap-

plied deliberation to improve the Moving Target Search(Ishida 1992). When an agent gets caught in the local
minima in the utility function, it begins deliberationfor escaping. The criterion for switching reactivity todeliberation is far di erent fromwith dynamics.

SIP , and no dealing

2

Next we de ne operators and plans used in

SIP .

Note that SIP uses a single operator, called a goal
operator, for planning. In the followings, +P and 0P

mean a true and a negation value of a propositionalvariableP . :P means negation of P .

De nition 2 (a goal-operator and plans) The

goal-operator O achieves a goal and gets the value. It

C, a
D and an add-list A. Ai of Oi includes a success literal si which means obtaining the value of Oi 's
is a STRIPS-like operator consisting of a cond-list

delete-list

goal. The operator also has an execution-time function

et(O) which returns the time taken for executing it. A
plan is a sequence of instantiated goal-operators, [O1 ,. . ., On ] describing order of goals to be achieved. A literal L in Ci , Di , Ai of Oi are characterized with LCi ,LDi , LAi . They are called a cond-literal, a delete-literal2and an add-literal .

Concrete methods for executing a goal-operator likepath-planning are described depending on a domain

SIP , deliberation means plan-and given as input. Inning with goal-operators: scheduling an optimal goal

order to be achieve. Reactivity means re ective actionof an agent without such scheduling.

SIP : Interleave planning with SPA

SIP agent consists of an observer, an environment
SIP planner and a plan executor as shown

modeler, aInterleaving planningwith execution using SP

in Fig.1. An observer constantly obtains data from anenvironment parallel to other modules, and gives thestate descriptions (literals) to an environment modeler

What is a criterion for determining the timing to switch
planning to execution in a dynamic environment? In
a very dynamic environment, we should switch themin short intervals. In contrast, the intervals should be
longer in a more static environment. Thus we argue

and a

SIP planner. Using them, an environment mod-eler estimates the persistence probabilities, and gives
them toSIP planner. The SIP planner obtains state

descriptions from an observer as an initial state, andgenerates a plan.

that \When the success possibility of a plan execution

keeps high, planning should be continued. The planningis stopped and the plan is executed when the possibility
falls below a certain value ". We call the success probability SP , and a certain value an execution threshold.

We developed a planning procedure based on the above
claim, and call it

SIP (Success probability-based In-

Environment
SIP agent
Sensing

Environment
modeler

ObserverStatesterleave Planning).

ActionPersistence Pr
SIP planner

Plan executorPlans

A domainFirst we de ne a dynamic environment.

The probFigure 1

lem de nition is generalized from real-time knowledgebased systems (La y et al.

1988) and the simpli ed

Tileworld (Kinny & George1991).

The detailedA

SIP agent

SIP procedure is shown in Fig.2. The

basic strategy of planning is forward beam search withan evaluation function:

expected value.

First aSIP

system obtains initial states from an observer (Obser-

vation in Fig.2), and gets the persistence probabilities
from an environment modeler (Getting environment
structure in Fig.2). Next the planner applies goal-

Fig.3 shows the behavior of the optimal plan's

SP as

the plan grows. When an execution threshold is 0.8,

the plan is executed at 2 steps, and if it is 0.3, theexecution is done at 6 steps.

operators to the current state, and expands all new

1states. At every depth of planning, the planner com-

SP and the expected values of all the expanded
w plans with the highest expectedvalues, where w is width of beam search.

0.8
Success probability

putes

plans, and selects

A procedure SIP(G, w, )(G: a goal state,w : a beam width, : an execution threshold)while true do
begin
Observation;
Getting environment structure;
CS {(the observed state, [ ])};
P [ ];% CS is a set of sp-pair: (State, Plan).
MSP 2;
while MSP >P is not a complete plan in CS do
begin
NS all sp-pairs expanded from CSwith operator applications;
Computing SP and expected values for NS;
CS w sp-pairs with high expected values in NS;
MSP the success probability of the plan Pwith the maximum expected value in CS
end[O1, ..., On ] P ;i 1;
while i ≠ n +1 the literal s of Oi –1 is achieved do
begin
executing Oi ;i i +1end
end

Figure 2
If

A

SP of an (locally) optimal plan which has theselected

SIP will stop

If not, thew states will be expanded, and planning will

start again.

The plan executor executes operators in order of aplan until any execution fails or all of them are successfully executed. The above cycle is repeated. The

complete plan includes all of the observed goals, andthe partial plan is not complete one. Forward chaining
guarantees that any partial plan is executable in an
initial state, and beam search reduces a search space.

w and an execution threshold are given to a system as

input. This procedure realizes our claim.

Planning depth is controlled by changing an execution threshold

0.2
0Figure 3

0 1 2 3 4 5 6 7Plan length

SP and an execution threshold

The success probability of a plan

We de ne the success of an operator execution, a plan
execution and an expected value.

P r(A; B ) means P r(A ^ B ).

In the followings,

De nition 3 (success of operator execution)

Oi is success i the
Oi 's success literal si becomes true in an environment
after the execution. A proposition Si means success of
Oi 's execution.
2

An execution of a goal-operator

De nition 4 (success probability) A plan execution is success iall executions of operators in a planS1 ^ 1 1 1 ^ Sn becomes true after a plan[O1 ,. . .,On ] is executed. P r (+S1 , . . ., +Sn ) is a successprobability SP of a plan.
2

are success:and a partial plan.

highest expected value falls below an execution threshplanning and execute the optimal plan.

0.4

Note that Def. 4 is available for both a complete plan

SIP procedure

old or any complete plan is generated,

0.6

 2 [0, 1]. When  is high, planning

depth becomes short and the behavior becomes reactive, whereas when it is low, the planning depth is longand the behavior becomes deliberative. For example,

With an execution procedure in

Fig. 2, we de ne an expected value of a plan.

De nition 5 (expected value of a plan) An expected value E [V ] of a plan [O1 , . . ., On ] is P r(+S1 )1V1+

P r(+S1 ; +S2 ) 1 V2 + 1 1 1 + P r(+S1 , . . ., +Sn ) 1 Vn ,Vi is the value of Oi 's goal.
2

where

The plan Bayesian networks

For representing probabilistic causality between eventsand computing the success probability, we introduce

the plan Bayesian network.

De nition 6 (temporal proposition) L; tisatemporal proposition that means a literal L is true ata timet in an environment.

De nition 7 (causal relation and time points)

2

LCj is LAi added by Oi in a plan, there will be
LAi  LCj . For plan [O1 , . . ., On ], t0
Pi
is an execution start time of O1 , ti = t0 +et(Ok )
k=1
is an execution nish time of Oi , and t(L) is a functionIfa causal relation

returning the time when the observer observed that aliteral

L became true in an environment.

2

SIP needs the following input probabilities.

BEL( Ob(L), t(L) ) = (O-P r(L),(observation-pr):
1

0 O-P r(L)).

 E ect probability, E -P r(Oi ; L): A probability thatan Oi 's add-literal L becomes true in an environment
after executing Oi . This means the certainty of the(eect-pr): If x = Observation probability, O-P r(L): A probability
that an observed literal L was really true in an en-(persistence-pr): If

De nition 8 (input probabilities)

Ex(Oi ); ti 1 and y is the childx, thenE -P r(Oi ; L) 1 0 E -P r(Oi ; L) .
=0node ofMy xjoperator's e ect.

01

x = LAi ; T1 or Ob(L); T1 , andy = LCj ; T2 , thenMy x= P -P r(L;0T2 0 T1 ) 1 0 P -P r(1L; T2 0 T1 ) .

vironment. This means the certainty of information
obtained by the observer.

j Persistence probability, P -P r(L; T ): A probability
that a literal L is yet true when the time T has(cond-pr):passed from when it became true in an environment.
This means the degree of the change in an environ-

2

ment.

If

an

execution-node

ci ,. . .,cm , thenn
P r(+Exjc1 ; . . . ; cm ) = 01
P r(0Exjc1 ; . . . ; cm ) =nUsing a plan, time points and above input probabilities, we completely construct the plan Bayesian network,

P BN . P BN is described with a Bayesian net-

work (Pearl 1988) widely used for representing probabilistic causality.
Next

we

explainhowtoconstruct

the

P BN .

V , E are sets of nodes andedges, and e(v1 ; v2 ) 2 E stands for a directededge v1 ! v2 .
BEL(x) is a vector (P r(+xje),
P r(0xje)) (e is conjunction of evidences), and
In

a

the

followings,

conditional

probability

assignedto

e(x; y)isr(+yj + x) P r(0yj + x)
My x = P
P r(+yj 0 x) P r(0yj 0 x) . A proposition Ob(L; t) means an observation that a literal L
became true at a time point t, and Ex(O ) means thatan goal-operator O is executable in an environment.
The time point ti and t(L) were described in Def. 7.
j

De nition 9 (plan Bayesian network)

The plan
Bayesian network, P BN , of a plan [O1 , . . ., On ] isa directed acyclic graph consisting ofin the followings, where 1

 V and E : i  n.

A2: Execution-node is true i

all of its cond-nodes

are true.

Though the assumptions may slightly restrict representation power ofputationofnext section.

SP

P BN , they make the com-very

ecientasmentioned

P = [O1 , O2 , O3 ]aC1 , bC1 ], [cD1 ], [dA1 ]), ([dC2 , : eC2 ], [ ], [fA2 ]),([dC3 , fC3 , : cC3 ], [ ], [gA3 ])]. The causal relation is f
dA1  dC3 , cD1  :cC3 , fA2  fC3 g.
[([〈Ob(aC ),t(aC )〉1〈Ob(bC ),t(bC )〉1〈aC , t0 〉1

〈d A ,t1 〉1〈Ob(¬ eC ),t(¬ eC )〉12〈¬ c D , t1 〉2〈dC , t1 〉1〈bC , t0 〉〈 Ex(O1 ), t 0 〉1〈¬ eC , t 1〉

2

2

〈 Ex(O2 ), t1 〉00

〈 fA , t1 〉2

〈d C , t2 〉3

〈 fC , t 2 〉3〈¬ cC , t2 〉3

〈 Ex(O3 ), t2 〉00

〈gA , t3 〉300 Conditional probabilities :in

Fig.4 shows a plan Bayesian net-

work constructed from a plan

=

0

0

,

c ^ 1 1 1 ^ cm . 2

are mutually probabilistic independent.

10c ^ 1 1 1 ^ cm

if + 1otherwise
if + 1otherwise

A1: Cond-nodes and add-nodes of the same operator

j0

cond-nodes

We use two assumptions for the above de nitions.

V , E and My x

Ex(Oi ); ti 1 2 V .
(cond-node):
LCi ; ti 1 2 V , e( LCi ; ti 1 ,Ex(Oi ); ti 1 ) 2 E .
(add-node):
LAi ; ti 2 V , e( Ex(Oi ); ti 1 ,LAi ; ti ) 2 E .
(delete-node)::LDi ; ti 2 V , e( Ex(Oi ); ti 1 ,:LDi ; ti ) 2 E .
(observation-node): If L; ti 1 was observed, then
Ob(L); t(L) 2 V and e( Ob(L); t(L) , L; ti 1 ).
(relation-edge): If LAi  LCj exists, then e( LAi ; ti ,LCj ; tj 1 ) 2 E . If LDi  :LCj exists, thene( :LDi ; ti , :LCj ; tj 1 ) 2 E .
(execution-node):

0
1

has

Figure 4

The plan Bayesian network

Computing the success probability

simpli ed Tileworld is a chess-board-like grid in which

Using a temporal proposition, the success of operator

Si in Def. 4, is described as si ; ti . Thus,
SP of executing aplan P = [O1 , . . ., On ] at time point t0 as SP (P , t0 ) =P r(+ s1 ; t1 , . . ., + sn ; tn ). The t0 is the start time
execution,with Def. 3 and Def. 4, we describe

point to execute a plan.

there are agents, obstacles and holes (see Fig.5). An
agent can move up, down, left or right, one cell at atime. An obstacle is a immovable cell. A hole (a goal)
is a cell with a score (a value). By moving to the hole,an agent obtains the score, and then the hole disappears. Holes appears or disappear as time passes.

SP (P; t0 ) is expanded in the followings. Equationei = + s1 ; t1
^ 1 1 1 ^ + si ; ti . Equation (2) and (3) are obtained(1) is obtained with a chain rule, where

A : An agent
A

20

from a method developed in (Pearl 1988) under A1

20 : A holeand A2. Describing the essence of the derivation, as

P r(+ si ; ti j + s1 ; t1 , . . ., + si 1 ; ti 1 ),the condition events + s1 ; t1 , . . ., + si 1 ; ti 1 block
all of the relevant loops and make the P BN singlycomputing00: An obstacle

0

0

65

connected. Consequently we can straightforward apply
an ecient and exact method (Pearl 1988) to compute

SP .

Figure 5

SP (P; t0 )P r(+ s1 ; t1 ; . . . ; + sn ; tn )

=

n
Y

=

P r(+ si ; ti jei 1 )One of the purposes of the experiments is to
(1)

0

i=1

Pr(+ si ; ti jei 1 )Y=E -P r (Oi ; + si ; ti ) P r (+ LCi ; ti 1 jei 1 ) (2)
0

0

0

L2Ci

P r(+ LCi ; ti 1 jei 1 )(P -P r(L; ti 1 0 th )(a)
E -P r(Oh ; L) 1 P -P r(L; ti 1 0 th ) (b) (3)=O-P r(L) 1 P -P r(L; ti 1 0 th )(c)(a)  (c) in equation (3) are in the followings, where
N is a parent node of LCi ; ti 1 and th is the time0

A simpli ed Tileworld

0

0

0

0

0

point.

the class of problems in whichnd outSIP outperforms both areactive system and a deliberative one. In other words,
it is tond out the problems in which the optimal

execution threshold exists neither near to 0 nor 1.
The another purpose is to characterize the classes inwhich

SIP works well. Since SIP estimates the degreeof the dynamics on-line, it is adaptive to the change ofdynamics. Thus we attempt to characterize the class inwhich

SIP outperforms the interleave planning which

is not adaptive.

There is few experiments for examining the tradeo

between deliberation and reactivity, and the adap-

tation of planning to the change of dynamics.

Thus

the experimental results are signi cant for designingan agent in a dynamic domain.

(a): N is a node of a literal s of Ex(O1); t0 
Ex(Oi 1 ); ti 2 or any cond-node of Ex(O1 ); t0 
Ex(Oi 1 ); ti 2 is a brother node of LCi ; ti 1 .
(b): Not (a), and N is an add-node or a delete-nodeof Ex(Oh , th ) .
(c): Not (a), and N is an observation-node.
With equation (1), (2), and (3), SP is computed

Parameters and procedure

ity for one step of a plan is constant. Thus, the time Dynamics, d = 1, 2, . . ., 8: The rate at which the

0

0

0

0

0

incrementally as growing plans, and the time complexcomplexity to compute

SP of a n step plan is O(n).

In contrast that the complexity for updating probabili-ties in Bayesian networks is generally NP-hard (Cooper1990), computing

SP on P BN is very ecient. Fur-thermore, since input probabilities depend on dynamics and an observation cost,them.

SIP is able to deal with

Experiments in the Tileworld
We made experiments in the simpli ed Tileworld(Kinny & George1991), a standard test-bed for a dy-

namic environment (Pollack & Ringuette 1990). The

We characterize the simpli ed Tileworld using the following properties: (1) Dynamics of an environment,(2) Uncertainty of actions including observations, (3)Costs for planning and observations. We selected necessary parameters for the properties and gave the default setting.

Parameters to be examined:

world changes for an agent.

 observation cost, c: The time taken for an observation.

 Execution threshold :  = 0, 0.1, . . ., 1

Agent parameters: Execution time for a single moving : 2 ( xed)
 A goal-operators : This describes a move from a holeto other holes. For path planning, an agent uses hill-

climbing with Manhattan distance as an evaluation
function.

 Width of beam search, w = 4. We

xed it since nosigni cant change was observed by changing it.

 Input probabilities : Observation probability is 1 0 u,
and e ect probability that an agent moves successfully for

p Manhattan distance is (1 0 u)p .

We use a simple
8 persistence probability function,

P -P r(L; t) =<:1

rt 0 rb + 1
0t < b)
1(b  t < b + r )1(b + r  t)

Fist we changed an observation costc for 5, 50, 100

and 200. Due to space constraints, the typical experi-

(

de-

1
rived from hole life-expectancy .

 Uncertainty, u = 0.01: The probability u that one-step moving and an observation fails. Failure of mov-

c = 100) is shown in Fig.6. The resultsc = 5, 50, 200 were almost similar to Fig.6. The
x-axis and y-axis stand for an execution threshold and a scoring rate " respectively. Through four obser-

mental result (forvation costs, it is natural that a scoring rate decreases
as dynamic increases. In Fig.6, when an environment

d = 1), the scoring rates are high independ = 2,

is static (dent of an execution threshold. However, for

3 and 4, the scoring rates near to 0 and 1 decrease.

Consequently we found out that the optimal execution
threshold existed between reactivity and deliberation

ing means no moving. If an observation fails, the ob-

in some problems. Note that there is a single peak ofject is observed randomly in one of the four neighbora scoring rate in most of the problems. This is impor-(up, down, left and right) cells on the true position.

tant for a hill-climbing method to search the optimal

Environment parameters:

execution threshold. We observed these properties also

 Grid size : 20 2 20. No obstacle.
 Hole scores : Chosen from a uniform distribution forin other results.

[60, 100].

d=1
d=2
d=3

 Hole life-expectancy : The interval between an ap-

pearance and a natural disappearance of a hole.

d=7
d=8

1

Chosen from a uniform distribution for [1200, 5200].

 Hole gestation time : The interval between the appearances of successive holes.

d=4
d=5
d=6

0.8

Chosen from a uni-

A scoring rate

form distribution [100, 300].

 Initial holes' positions : The initial holes positions
are randomly set.

Since the complexity for computing

SP for one step

is constant, we de ned a unit of agent-time as the time

0.6
0.4

The c time-units
d environment-time

0.2

sumed an agent knows true distance to a target hole,0for expanding a node in planning.
are taken by one observation, andpasses as one agent-time passes. For simplicity, we asthus no obstacle was necessary.
moves using hill-climbing.

An agent actually0

0.2 0.4 0.6 0.8
An execution threshold

We used the scoring rate

obtained score" = the maximum possible
score it could have achieved as

Figure 6

Changing dynamics (performance measurement. Through all experiments,

a terminal condition was that the standard deviationof" converges to 0.01, and1

ve results of the identicalparameters were averaged. In the following, problems
are described with the di erence from default setting.

Exp-A: Changing dynamics and an
observation cost

We investigated in uence of dynamics and an observation cost on an agent's performance, and attempted tond out the optimal execution threshold was between
0 and 1: the most deliberative and the most reactive.
For simplicity, we gave persistence probabilities to a

SIP agent through these experiment. The environment modeler of SIP will be implemented in the next
section.

1[b; b + r1 ] is equal to the range of hole life-expectancy,[1200, 5200], mentioned later.

Forc = 100)

c = 50, 100 and 200, there are the peaks between

0 and 1, and the rank correlation coecients of any
di erent dynamics pair in the same observation costare positive, 0.2

0.5. Hence we consider the optimal

execution thresholds are robust against the change ofdynamics. Furthermore, since the peaks are around 0.7
in Fig.7 showing scoring rates averaged over dynamics,
it is robust also against the change of an observation
cost. These properties derives from

SP is computed

depending on dynamics and an observation cost.

The environment modeler
We implemented the environment modeler for advanced experiments. In

SIP , the environment mod-eling means the estimation of persistence probabilities
with data from the observer. The data include the observed life-expectancies. The persistence probabilitiesc=5
c = 50c = 100c = 200

d=1
d=2
d=3

1

d=4
d=5
d=6

d=7
d=8

1
0.8

0.6

A scoring rate

A scoring rate

0.8

0.4

0.2
0

Figure 70

0.2 0.4 0.6 0.8
An execution threshold

1

0.6
0.4

0.2
0

Averaged scoring rates to dynamics

1 2 3 4 5 6 7 8 9 10
Fixed depth

signi cantly depend on dynamics of an environment.
A following equations (Dean & Kanazawa 1989) wereused for estimating

Figure 8d and r of P -P r(L; t) described ear-

Fixed-depth planninglier, and the modeling can be constantly done parallel
to planning, execution and observation. The input isU : a set of last n samples of observed life-expectancies.

The modeler is able to update the estimated value because the sample is constantly updated.

We assume

the agent knows the model of persistence probabilities
and can use a parametric method. If the assumption
is not hold, the error of estimation will increase.

d(U )

=

r(U )

=

We expected that the optimal threshold ofwould be more robust than the optimal depth ofdepth planning.

U
0 0 :5the average of U 0 d(U )does not deal with dynamics, and it may change theoptimal depth widely depending on the change of dy-" at  =depth = 6 (which are the optimal conditions at d= 3) and the maximum ", at d = 3, 4, 5 and 6. Smaller

namics. Fig.9 shows the di erences between

the di erence is, more robust the system is. Thus wesee

SIP is more robust than

Exp-B: Adaptation to the change ofdynamics

Difference from the maximum

SIP-diff

SIP is adaptive to the change of dynamics because of
the environment modeler.

Hence we were interested

in comparing

xed-depth planning which

stops the planning at the given depth.

Though thexed-depth planning can control deliberation, it is not
adaptive to the change of dynamics because ofxed

depth. The same parameters of Exp-A were used, except changing theThising with Fig.6, the maximum scoring rates are almost
equal to ones in Fig.6. This is showed also in otherxed depth planning,c.

SIP can change thexed execution thresh-2old. Unfortunately, the advantage is not shown .

We consider since the causality between goals is too
simple, SP is smoothly decreased and the interleave timingof two planning are not much di erent.
2

0.1
0.05
0
– 0.05
4
5
Dynamics

6

xed-depth planner is

SIP , except that the planning depth is xed.
The results for c = 100 is shown in Fig.8. Compar-

plan length on-line even with aFixed-diff

0.15

3

same toUnlike thexed-depth planning.

0.2

xed-depth from 1 to 10 instead ofan execution threshold.

xed-

xed-depth planning

0.6 orthe minimum of

SIP with

It is because

SIP

Figure 9

Robustness of

SIP

SIP to the
SIP with the environment

Next, we investigated the adaptation ofchange of dynamics. Using
modeler andxed-depth planner, we made the experi-

ment in which dynamics itself changed. The dynamics
was initially three, changed to four at 10000 agenttime, and to
numberve at 20000 agent-time.

The sample

n of a modeler was set 20 and c = 100. The

results are shown in Fig.10. Though thexed-depthplanner outperformed

SIP until 10000 time, after dySIP is better than the xed-

namics changed twice,

Cooper, G. F. 1990. The computational complexity ofprobabilistic inference using bayesian belief networks.

depth because of its adaptation to the change of dy-

Arti cial Intelligence 42:393{405.

namics. Thus we consider one of the classes in which

Dean, T., and Kanazawa, K. 1989. Persistence and

SIP works well is the environment where dynamics

itself changes.

IEEE Transaction on Systems, Man, and Cybernetics 19(3):374{385.

probabilistic projection.

Dean, T.; Kaelbling, J. K.; Kirman, J.; and Nicholson, A.

1

A scoring rate

0.8

Fixed depth

0.6

the Ninth Conference on Uncertainty in Arti cial Intelligence, 309{316.
Dean, T.; Kaelbling, J. K.; Kirman, J.; and Nicholtic domains. In Proceedings of the Eleventh National

Conference on Arti cial Intelligence, 574{579.

Drummond, M., and Bresina, J. 1990. Anytime syn-00

Figure 10

10000
20000
Agent time

30000

Adaptation to the change of dynamics

Conclusion

SIP method for controlling deliberation in a dynamic environment. SIP computes the
success probability SP that a plan will be executed
successfully, and stops planning when the SP falls be-

low an execution threshold. A plan is transformed intoa plan Bayesian network, and theputed on it.

SP is eciently com-

We made experiments in the simpli ed

SIP . As a result, we found
SIP worked better than a reactive and a deliber-

Tileworld for evaluating

ative system in some problems. Furthermore we foundout the optimal threshold is robust, and one of good

SIP is where dynamics itself changes. HowSIP needs to deal with replanning, and we needclasses for

systematic characterization, like (Kirman 1994), of theclasses where

SIP works well.

reasoning and planning. In Proceedings of the Sixth
National Conference on Arti cial Intelligence, 677{
Ishida, T.

1992.

Moving target search with intelli-gence. In Proceedings of the Tenth National Confer-ence on Arti cial Intelligence, 525{532.

Kinny, D., and George , M. 1991. Commitment ande ectiveness of situated agents. In Proceedings of the
Twelfth International Joint Conference on Arti cialIntelligence, 82{88.

Kinny, D.; George , M.; and Hendler, J. 1992. Experiments in optimal sensing for situated agent. In

Proceedings of the Second Paci c Rim International
Conference on Arti cial Intelligence, 1176{1182.
Kirman, J. 1994. Predicting Real-Time Planner Performance by Domain Characterization. Ph.D. Dissertation, Brown University.

References
Agre, P. E., and Chapman, D. 1987. Pengi: A im-

plementation of a theory of activity. In Proceedingsof the Sixth National Conference on Arti cial Intelligence, 268{272.
1989.

cial

La y, T. J.; Cox, P. A.; Schmidt, J. L.; Kao, S. M.;

terface Laboratories for useful discussion.

Solving time-dependent planning problems. In Proceedings of theEleventh International Joint Conference on Arti cialIntelligence, 979{984.
Brooks, R. A. 1986. A robust layered control system

IEEE Transaction on Robotics

and Automation 2(1):14{23.

George , M. P., and Lansky, A. L. 1987. Reactive

Korf, R. E. 1990. Real-time heuristic search. Arti

Acknowledgments

for a mobile robot.

satisfaction. In Proceedings of the Eighth National
Conference on Arti cial Intelligence, 138{144.

Intelligence 42:189{211.

Many thanks to Yoshinori Isoda at NTT Human In-

Boddy, M., and Dean, T.

thetic projection: Maximizing the probability of goal682.

We proposed aeverDeliberation scheduling for time-son, A. 1993b. Planning with deadlines in stochas-

0.4
0.2

out

1993a.

critical sequential decision making. In Proceedings of

SIP

and Read, J. Y.

1988.

Real-time knowledge-based

systems. In AI magazine, volume 9. 27{45.

McDermott, D. 1978. Planning and action. Cognitive
Science 2:77{110.
Pearl, J. 1988. Probabilistic Reasoning in Intelligent
Systems: Networks of Plausible Inference. Morgan
Kaufmann.
Pollack, M. E., and Ringuette, M. 1990. Introducing
the tileworld: Experimentally evaluating agent architectures. In Proceedings of the Eighth National Con-

ference on Arti cial Intelligence, 183{189.
Russell, S., and Wefald, E. 1991. Do the Right Thing.
MIT Press.