Information Technology Reference
In-Depth Information
constraints and updating SC by inserting new constraints. For each task t in the set of
tasks te i , the preprocessing information in the LT which is relevant to the current task
t is added to the field LT γ i in the cluster Π γ i . This information in LT γ i will help the
planner (slave) agent to reduce the planning effort necessary to find the individual plan
for the cluster Π γ i (line 2). In lines 2 and 2, the plan P γ init in the cluster Π γ i is extended
by adding all variable V ,ordering and CL constraints that point to a relation between
the current task t and the other tasks in the set te i . After that, these constraints are
removed from the current plan P init in Π . Afterwards, the shared constraints set SC
and the current partial plan P init are updated by inserting and removing respectively all
constraints that relate task t to other tasks outside the set of tasks te i (lines 2 and 2).
Finally, the current set Γ is updated by adding the current new cluster Π γ i to the set of
cluster Π γ as well as updating the shared constraints set SC (line 2). Note that SC will
play a great role in the merging process. The Dep algorithm is called recursively with
the modified plan and the updated Γ to inspect a new cluster (line 2).
On the other hand, in each iteration of the Ind algorithm, in the current plan, the
tasks that are dependent are collected in one cluster and consequently SC get empty.
Therefore, in order to split the planning problem into a set of clusters according to the
Ind algorithm, we will replace line 2 in Algorithm 2 by the following line ”Select tasks
te i that are dependent” . Due to this replacement, the set of clusters which are produced
are explicitly independent, and the shared constraints set SC will be empty.
Once the set of clusters has been generated either by the Dep or Ind algorithm, the
master agent initiates a number of slave agents based on the number of clusters and
distributes these clusters among slave agents in order to construct individual solution
plans for them. Afterwards, the master agent suspends its activity until all slave agents
respond by returning individual solution plans for all clusters, and then wakes up again
to perform the merging process in order to generate a general solution plan (cf. sec. 4).
Algorithm 2. Dependent (Dep) Algorithm
Input
: Π = D, s init ,P init : Planning problem,
LT : LandmarkTable, Γ
= Π γ ,SC
Output : Γ
Γ
= Π γ ,SC←− null
1
if ( TE == ) then return Γ
2
Select tasks te i that are pre-request-free from P init .
3
Create a new cluster Π γ i = D, s init ,P γ init ,LT γ i .
4
Add these tasks te i to the partial plan P γ init
in cluster Π γ i .
5
Let TE ←− ( TE− te i )
6
foreach (task t ∈ te i ) do
7
Attach the relevant information of the task t in the LT to the LT γ i
in the cluster Π γ i
8
Add all constraints ( t ,V t ,CL t ) that relate task t with the other tasks in te i to P γ init
9
Let V ←− ( V − V t )
≺←− ( ≺−≺ t )
; CL ←− ( CL − CL t )
;
10
Insert all constraints ( t ,V t ,CL t ) that relate task t with another task t∈ te i into SC .
11
≺←− ( ≺−≺ t )
; V ←− ( V − V t )
; CL ←− ( CL − CL t )
Let
12
Γ
= Π γ ,SC←− ( Π γ ∪ Π γ i ) ,SC
13
return Dependent( Π,LT, Γ )
14
Search WWH ::




Custom Search