Information Technology Reference
In-Depth Information
Slave Agents:
It is a set of identical agents working concurrently in order to solve the
set of clusters which are passed by the master agent. To this end, each slave agent uses
our refinement planning algorithm (cf. Alg. 1) to generate its own individual plan. Our
refinement algorithm takes the initial plan
P
γ
init
of the assigned cluster as an input and
refines it stepwise until the individual solution plan is found.
Since our approach is based on a
declarative
model of task abstraction, the exploita-
tion of knowledge about hierarchical landmarks can be done
transparently
during the
generation of the task expansion modifications: First, the respective modification gen-
eration function
f
ModGen
AbsT ask
is deployed with a reference to the landmark table
LT
γ
i
of
the cluster problem
Π
γ
i
. During planning, each time an abstract task flaw indicates an
abstract plan step
t
(
τ
)
the function
f
ModGen
AbsT ask
does not need to consider all methods pro-
vided in the domain model for the abstract task
t
(
τ
)
. Instead, it operates on a reduced
set of applicable methods according to the respective options
O
(
t
(
τ
))
in the
LT
γ
.
It is important to see that the overall plan refinement procedure is not affected by
this domain model reduction, neither in terms of functionality
(flaw and modification
modules do not interfere)
nor in terms of search control
(strategies are defined indepen-
dently, and completeness of search is preserved)
.
Note that if the refinement planning algorithm returns
fail
, the slave agent works as
a master agent and performs all functions of the master agent. Finally, each slave agent
terminates itself after sending the generated individual solution
p
γ
to the master agent.
4
Merging Methodology
Our merging methodology depends on the notion of
Fragments
. The merging technique
proceeds in two processes. Firstly, the set of individual plans
P
Γ
=
{p
γ
1
,p
γ
2
, ··· ,p
γ
n
}
(i.e., which are produced by slave agents)
is divided into a set of
Fragments
.These
Fragments
are constructed according to the ordering constraints in the
SC
. Each frag-
ment
F
,andaset
of ordering constraints
O
γ
that impose a partial order on
P
γ
. For example, suppose
the ordering constraints in
SC
are
{s
1
≺ s
2
,s
2
≺ s
3
,s
4
≺ s
5
}
. Let a set of indi-
vidual plans
P
Γ
=
{p
γ
1
, ··· ,p
γ
7
}
be respectively a solution plan for abstract plan
steps
s
1
, ··· ,s
7
. Then according to the ordering information in
SC
, these plans in
P
Γ
constitute three different fragments
F
1
=
{p
γ
1
,p
γ
2
,p
γ
3
}, {p
γ
1
≺ p
γ
2
,p
γ
2
≺ p
γ
3
}
,
F
2
=
{p
γ
4
,p
γ
5
}, {p
γ
4
≺ p
γ
5
}
,and
F
0
=
{p
γ
6
,p
γ
7
}, {∅}
. Note that there are two
types of fragments.
Related-Fragment
includes those individual plans that are depen-
dent such as
F
1
and
F
2
,and
Zero-Fragment
which includes those individual plans that
do not have explicit dependency such as
F
0
.
Secondly, the plans in each fragment are merged to produce a plan so-called
Merge-
Fragment-Plan (MFPlan)
, and then all
MFPlans
are combined in order to generate
a general final solution plan. To this end, we need to identify the implicit dependency
between individual plans especially in
Zero-Fragment
. This dependency is identified by
matching preconditions and effects of the tasks in individual plans. This means, certain
postcondition of plan
p
γ
i
tasks required as preconditions for plan
p
γ
j
tasks.
There are two reasons for determining the plan dependency: canceling the negative
interactions
( one task deletes the effect or precondition of another task)
, and benefit
=
P
γ
,O
γ
consists of a set of individual plans
P
γ
(
P
γ
⊆ P
Γ
)