Information Technology Reference
In-Depth Information
a new method has been developed to detect the conflicts not only at the primitive lev-
els, but also at abstract levels [2]. Recently, Hisashi [8] presented an HTN planning
agent system working in dynamic environments. The set of agents in his approach are
arranged in stratified form as parent and children agents which work together to achieve
the goal. As opposed to these approaches, integrating MAP with hierarchical prepro-
cessing techniques which prune the search space of a hierarchical planner has not been
considered so far. Recently, we have introduced the hierarchical landmark technique
for the purpose of domain model reduction [5]. In hierarchical planning,
landmarks
are
mandatory abstract or primitive tasks that have to be performed by any solution plan.
In this paper, we present a novel hybrid approach that combines the landmark pre-
processing technique in the context of hierarchical planning with multi-agent planning
in order to enhance planning efficiency. Our architecture consists of a set of agents.
The
pre-processing agent
analyzes a given planning problem by applying a landmark
algorithm in hierarchical planning. It does so by systematically inspecting the methods
that are eligible to decompose the relevant abstract tasks. Beginning with the (land-
mark) tasks of the initial plan, the procedure follows the way down the decomposition
hierarchy until no further abstract tasks qualify as landmarks. The
master agent
can be
divided into two parts: the first part handles a split process and the second handles a
merging process. Finally, the
slave agents
are a set of identical agent planners that are
executed concurrently, they do not cooperate among each others and each one of them
uses HTN-style planning to generate its own individual plan.
Before introducing our approach in section 3, we will review the underlying plan-
ning framework in section 2. Section 4 presents the merging technique that combines
individual plans to generate a solution plan. Section 5 describes the experimental setting
and the evaluation results. The paper ends with some concluding remarks in section 6.
2
Formal Framework
HTN planning relies on the concepts of tasks and methods [7]. Primitive tasks corre-
spond to classical planning operators, while abstract tasks represent complex activities.
For each abstract task, a number of methods are available each of which provides a task
network,
i.e., a plan that specifies a pre-defined (abstract) solution of the task
. Planning
problems are (initial) task networks. They are solved by incrementally decomposing the
abstract tasks until the network contains only primitive ones in executable order.
Our planning framework relies on a
hybrid
formalization [1] which combines HTN
planning with partial-order causal-link (POCL) planning. For the purpose of this pa-
per, only the HTN shares of the framework are considered, however. A task schema
t
(
τ
)=
prec
(
t
(
τ
))
,
add
(
t
(
τ
))
,
del
(
t
(
τ
))
specifies the preconditions and effects of a task
via conjunctions of literals over the task parameters
τ
=
τ
1
...τ
n
. States are sets of lit-
erals. Applicability of tasks and the state transformations caused by their execution are
defined as usual. A
plan
P
=
S, ≺,V,CL
consists of a set
S
of
plan steps
- (partially)
instantiated task schemata that carry a unique label to differentiate between multiple
occurrences of the same schema -, a set
≺
of
ordering constraints
that impose a partial
order on
S
,aset
V
of
variable constraints
,andaset
CL
of
causal links
.
V
consists of
(in)equations that associate variables with other variables or constants; it also reflects
