Information Technology Reference
In-Depth Information
3.1
Pre-processing Agent
The pre-processing agent uses a preprocessing technique in order to perform some prun-
ing of the search space before the actual search is performed in order to reduce the plan-
ning effort. Recently, we introduced a landmark technique which restricts the domain
and problem description of an HTN to a smaller subset, since some parts of the domain
description might be irrelevant for the given problem at hand [5,6]. Therefore, the pre-
processing agent relies on hierarchical landmarks - ground tasks that occur in the plan
sequences leading from an initial plan to its solution. They are defined as follows.
Definition 2 (Solution Sequences).
Let
V
Π
, E
Π
be the induced search space of plan-
ning problem
Π
. Then,
SolSeq
Π
(
P
):=
{P
1
...P
n
|P
1
=
P,
(
P
i
,P
i
+1
)
∈E
Π
for all
1
≤ i<n
, and
P
n
∈Sol
Π
,n≥
1
}
.
Definition 3 (Landmark).
A ground task
t
(
τ
)
is called a
landmark
of planning prob-
lem
Π
, if and only if for each
P
1
...P
n
∈SolSeq
Π
(
P
init
)
there is an
1
≤ i ≤ n
,such
that
t
(
τ
)
∈ Ground
(
S
i
,V
n
)
for
P
i
=
S
i
, ≺
i
,V
i
,CL
i
and
P
n
=
S
n
, ≺
n
,V
n
,CL
n
.
While a landmark occurs in every plan sequence that is rooted in the initial plan and
leads towards a solution, a
local
landmark occurs merely in each such sequence rooted
in a plan containing a specific abstract ground task
t
(
τ
)
.
Definition 4 (Local Landmark of an Abstract Task).
For an abstract ground task
t
(
τ
)
let
P
Π
(
t
(
τ
)) :=
{P ∈P
Π
|P
=
S,≺,V,CL
and
t
(
τ
)
∈ Ground
(
S, V
)
}
.
A ground task
t
(
τ
)
is a
local landmark
of
t
(
τ
)
, if and only if for all
P ∈P
Π
(
t
(
τ
))
and
each
P
1
...P
n
∈SolSeq
Π
(
P
)
there is an
1
≤ i ≤ n
, such that
t
(
τ
)
∈ Ground
(
S
i
,V
n
)
for
P
i
=
S
i
, ≺
i
,V
i
,CL
i
and
P
n
=
S
n
, ≺
n
,V
n
,CL
n
.
Since there are only finitely many task schemata and we assume only finitely many con-
stants, there is only a finite number of (local) landmarks. Given a planning problem
Π
,
the relevant landmark information can be extracted in a pre-processing step. The out-
comes of the extraction procedure that is introduced by Elkawkagy et al. [5] is stored in
a so-called
landmark table
. Its definition relies on a
Task Decomposition Graph
(
TDG
).
A
TDG
is a representation of all possible ways to decompose the initial plan
P
init
of
Π
using methods in
M
. More formally, a
TDG
of a planning problem
Π
is a bipartite
graph
V
T
,V
M
,E
,where
V
T
is a set of ground tasks (called
task vertices
),
V
M
is a set of
methods (called
method vertices
), and
E
is the set of edges connecting task vertices with
method vertices according to
M
. Note, that a
TDG
is finite as there are only finitely many
ground tasks and a finite number of methods. The
landmark table
is a data structure that
represents the
TDG
plus some additional information about local landmarks.
Definition 5 (Landmark Table).
Let
V
T
,V
M
,E
be a
TDG
of the planning problem
Π
.The
landmark table
of
Π
is the set
LT
=
{t
(
τ
)
,M
(
t
(
τ
))
,O
(
t
(
τ
))
|t
(
τ
)
∈ V
T
}
,
where
M
(
t
(
τ
))
and
O
(
t
(
τ
))
are defined as follows:
M
(
t
(
τ
))
=
{t
(
τ
)
∈ V
T
| t
(
τ
)
∈ Ground
(
S, V
)
t
(
τ
)
, S,≺,V,CL ∈ V
M
}
O
(
t
(
τ
))
=
{Ground
(
S, V
)
\ M
(
t
(
τ
))
|t
(
τ
)
, S,≺,V,CL ∈ V
M
}
for all
Each landmark table entry partitions the tasks introduced by decompositions into two
sets. Mandatory tasks
M
(
t
(
τ
))
are those ground tasks that are contained in all plans
