Information Technology Reference
In-Depth Information
the (partial) instantiation of the plan steps in
P
. We denote by
Ground
(
S, V
)
the set of
ground tasks obtained by equating all parameters of all tasks in
P
with constants, in a
way compatible with
V
. The causal links are adopted from POCL planning: a causal
link
s
i
→
ϕ
s
j
indicates that
ϕ
is implied by the precondition of plan step
s
j
and at the
same time is a consequence of the effects of plan step
s
i
. Hence, the precondition
ϕ
is said to be
supported
this way. Methods
m
=
t
(
τ
)
,P
relate an abstract task
t
(
τ
)
to
aplan
P
, which is called an
implementation
of
t
. In general, multiple methods are
provided for each abstract task. Please also note that no application conditions are as-
sociated with the methods, as opposed to other representatives of HTN-style planning.
An HTN planning problem
Π
=
D, s
init
,P
init
is composed of a domain model
D
=
T,M
,where
T
and
M
denote sets of task schemata and decomposition methods, an
initial state
s
init
, and an initial plan
P
init
. Note, that in our
hybrid
planning framework,
one can specify a goal state. However, since we restrict ourselves in this paper to pure
HTN planning, the goal state is omitted. A plan
P
=
S, ≺,V,CL
is a solution to
Π
if and only if: (1)
P
is a refinement of
P
init
i.e., a successor of the initial plan in the
induced search space (see Def. 1 below), (2) each precondition of a plan step in
P
is
supported by a causal link in
CL
and no such link is threatened, i.e., for each causal link
s
i
→
ϕ
s
j
the ordering constraints in
≺
ensure that no plan step
s
k
with an effect that
implies
¬ϕ
can be placed between plan steps
s
i
and
s
j
, (3) the ordering and variable
constraints are consistent, i.e.,
≺
does not induce cycles on
S
and the (in-) equations in
V
are not contradictory, and (4) all plan steps in
S
are primitive ground tasks. Please
note that we encode the initial state via the effects of an artificial primitive task, as it
is usually done in POCL planning. In doing so, the second criterion guarantees that the
solution is executable in the initial state.
In order to refine the initial plan into a solution, there are various
refinement steps
(or
plan modifications
) available; in HTN planning, these are: (1) the decomposition of
abstract tasks using methods, (2) the insertion of causal links to support open precondi-
tions of plan steps, (3) the insertion of ordering constraints, and (4) the insertion of vari-
able constraints. Given an HTN planning problem
Π
, its initial plan and the available
plan modifications we can define the induced search space as follows.
(¯
τ
)
Definition 1 (Induced Search Space).
The directed graph
P
Π
=
V
Π
, E
Π
with ver-
tices
V
Π
and edges
E
Π
is called the induced search space of the planning problem
Π
iff
(1)
P
init
∈V
Π
, (2) if there is a plan modification refining
P ∈V
Π
into a plan
P
,then
P
∈V
Π
and
(
P, P
)
∈E
Π
, and (3)
P
Π
is minimal such that (1) and (2) hold. For
P
Π
,
we write
P ∈P
Π
instead of
P ∈V
Π
. In general,
P
Π
is neither acyclic nor finite.
In order to search for solutions, the induced search space is explored in a heuristically
guided manner by our refinement planning algorithm (Alg. 1).
The fringe
P
1
...P
n
is a sequence containing all unexplored plans that are direct
successors of visited non-solution plans in
P
Π
. It is ordered in a way such that a plan
P
i
is estimated to lead more quickly to a solution than plan
P
j
for
j>i
. The current
plan is always the first plan of the fringe. The planning algorithm iterates on the fringe
as long as no solution is found and there are still plans to refine (line 1). Hence, the
flaw detection function
f
FlawDet
in line 1 calculates all flaws of the current plan. A flaw
is a set of plan components that are involved in the violation of a solution criterion.
The presence of an abstract task raises a flaw that consists of that task, a causal threat
