Information Technology Reference
In-Depth Information
Result
: a planning state
ps
, or failure
1
if
ps
is a final planning state
then
2
return
ps
;
3
steps ←{
(s
,σ,kas
)
|
s is the instance of a planning step,
σ
is a substitution such
that
is applicable or possibly-applicable w.r.t.
ps
D
and the knowledge acquisition scheme
kas}
;
4
if
choose
(s
,σ,kas
)
∈ steps
with the minimum overall cost
then
5
s
σ
is relevant for the next task,
s
if
kas
=
∅
then
ps
←
s
eff
(
ps
);
6
ps
←
plan(
ps
)
;
7
if
ps
=
failure
then
8
return
ps
;
9
else
10
return
(
ps
D
,ps
t
,ps
p
,kas
);
11
12
else
13
return
failure
;
Fig. 3.
Algorithm
plan
(
ps
)
Algorithm.
The simplified algorithm of the proposed HTN planning system is shown
by Fig. 3. The algorithm is an extension of the SHOP [10] algorithm that additionally
considers possibly-applicable decompositions.
A planning state is the input of the recursive planning algorithm. If the task list of
the given planning state is empty, then the planning process successfully generated a
complete plan and the given planning state is returned. Otherwise, the algorithm suc-
cessively chooses the applicable or possibly-applicable step with the lowest expected
cost. If the planner chooses an applicable planning step (i.e., no knowledge acquisition
is necessary and the knowledge acquisition scheme is the empty set), then it applies the
step and recursively calls the planning algorithm with the updated planning state (line
5-9).
In contrast, if the planner chooses an only possibly-applicable planning step, then it
stops the planning process and returns the current (intermediate) planning state includ-
ing the knowledge acquisition scheme of the chosen planning step (line 10-11). In this
way, the planner automatically decides whether it is more reasonable to continue the
planning or to first acquire additional information. In other words, it decides when to
switch between planning and acting. If it is neither possible to continue the planning
process nor to acquire relevant information, then the planner backtracks to the previous
choice point or returns
failure
if no such choice point exists.
3
Continual Planning and Acting
The overall idea of the proposed continual planning and acting system is to interleave
planning and acting so that missing information can be acquired by means of active in-
formation gathering. In Section 2 we described a new HTN planning system for open-
ended domains. Based on that, we describe the high-level control system ACogControl
in this section.
