Information Technology Reference
In-Depth Information
consists of a causal link and the threatening plan step, for example. If no flaws can be
found, the plan is a solution and returned (line 1). In line 1, the modification generating
function
f
ModGen
calculates all plan modifications that address the flaws of the current
plan. Afterwards, the modification ordering function
f
ModOrd
orders these modifications
according to a given strategy. The fringe is finally updated in two steps. First, the plans
resulting from applying the modifications are computed (line 1) and put at the beginning
of the fringe (line 1). Second, the plan ordering function
f
PlanOrd
orders the updated
fringe. This step can also be used to discard plans, i.e., to delete plans permanently
from the fringe. This is useful for plans that contain unresolvable flaws such as an
inconsistent ordering of tasks. If the fringe becomes empty, no solution exists and
fail
is returned.
Algorithm 1.
Refinement Planning Algorithm
input
: The sequence
Fringe
=
P
init
.
output
: A solution or
fail
.
while
Fringe
=
P
1
...P
n
=
ε
do
1
F ← f
FlawDet
(
P
1
)
2
if
F
=
∅
then return
P
1
3
(
f
∈F
m
1
...
m
n
←f
ModOrd
f
ModGen
(
f
))
4
succ
←apply
(
m
1
,P
1
)
... apply
(
m
n
,P
1
)
5
Fringe
← f
PlanOrd
(
succ
◦P
2
...P
n
)
6
return
fail
7
3
Hybrid Multi-agent Planning
Figure 1 depicts the components of our architecture. It consists of the pre-processing
agent and the planning agents. The planning agents encapsulate the master agent and
slave agents as well as a shared constraints set in their context. The shared constraints
set
(
SC
)
is a shared memory that includes a set of constraints. Note, that all agents have
complete knowledge about the initial state of the planning problem. In the following
subsections, we will illustrate the key features of our agents.
Fig. 1.
Hybrid Multi-agent Planning Architecture
