Information Technology Reference
In-Depth Information
introduced by some method which decomposes t ( τ ) ; hence, they are local landmarks
of t ( τ ) . The optional task set O ( t ( τ )) contains for each method decomposing t ( τ ) the
set of ground tasks which are not in the mandatory set.
Once the landmark table has been constructed, the pre-processing agent terminates
itself after sending the landmark table to the master agent. Please note that the informa-
tion about landmarks can be exploited in two ways. The first way is to reduce the domain
model by ignoring infeasible method decompositions or, more precisely, to transform
a universal domain model into one that includes problem-specific pruning information
[5]. The second application of the landmark table is to serve as a reference for the plan-
ning strategy to deduce heuristic guidance from the knowledge about which tasks have
to be decomposed on refinement paths that lead towards a solution [6]. Each slave agent
will use the former way in order to construct its individual solution plan.
3.2
Planning Agents
Our planning scenario includes a set of planning agents. They integrate to generate a
final solution for the given planning problem. The set of planning agents is divided into
two different types: a master agent and a set of identical agents so-called slave agents .
Master Agent: It takes a hierarchical planning problem Π and the computed landmark
table LT as input and generates the final solution plan. To this end, the master agent
performs two processes: a split process and a merging process.
In the split process, the master agent decomposes a planning problem Π into a set
of clusters according to two different techniques: Dependent ( Dep ) and Independent
( Ind ) .The Dep technique relies on the idea of constructing a set of dependent clusters,
while the Ind technique creates a set of independent clusters. A comparison of the
respective results will be done in the experimental section (cf. Sec. 5).
In each iteration of the Dep algorithm (Alg. 2), in the current plan, the tasks that are
not preceded by other tasks are separated in one cluster. While the set of constraints
between tasks in different clusters is inserted in the shared constraints set SC .
The Dep algorithm takes the planning problem Π , a landmark table LT (i.e., the
LT is computed by the pre-processing agent) ,andaset Γ = Π γ ,SC as input and
computes the final set Γ .Theset Γ consists of the shared constraints set SC and the
set of clusters Π γ = i =0 γ i } ,where n is the number of clusters. Each cluster Π γ i
will be considered as a sub-problem. In order to identify different clusters, the Dep
algorithm runs recursively through all tasks in the initial plan P init until all tasks have
been traversed. Each cluster Π γ = D, s init ,P γ init ,LT γ includes a domain model D ,
an initial state s init , a partial plan P γ init which represents an initial plan for the cluster
Π γ ,andan LT γ that represents relative landmark information of the tasks in the partial
plan P γ init .
Now, we will have a look at how the set Γ is constructed by our Dep algorithm. First,
the set Γ is initialized (line 2). Afterwards, in the current plan P init ,thetasks te i that are
pre-request-free are collected (line 2). In lines 2 to 2, a new cluster Π γ i is created, and
the tasks in te i are added to the task network of the plan P γ init . Then, the tasks te i are
removed from the task network TE of the plan P init . For the current tasks te i at hand,
lines 2 to 2 illustrate iterative loops to extend the created cluster Π γ i
by adding different
Search WWH ::




Custom Search