Information Technology Reference
In-Depth Information
are present among the actions of the plan, which imply that the preconditions of the
later actions will appear as effects of other previous actions. An order constraint link
is then created between the two actions.
Algorithm 1 (Graph):
Computes the web services
composition graph
Inputs
: P = {a
0
,a
1
,…,a
n
}, the plan
Output
: G = (P,E), web services composition graph
E =
∅
for i = n down to 1
for each c
∈
prec(ai)
for j = i-1 down to 0
for each p
∈
add(aj)
if (c = p)
E = E U {(aj,ai)}
return G = (P,E)
The algorithm that discovers such kinds of links is called
Graph
and starts from the
last elements of the action list. Each one of its preconditions is then examined so as to
discover a previous action in the plan that produces this fact. This means to discover
an action that contains this fact in its effect list. So, another loop is needed to access
all the previous possible producers of this imminent link. When such a previous
action is found, a link is created among the two actions. This link illustrates an order
constrain and ensures that the action that produces the fact will be executed before the
one that consumes it in its preconditions list.
A simple example of the above procedure is depicted in
Fig. 2
. In this example there
are two actions in the plan, the actions
Drop Ball B
with which a robot puts down the
ball B and the action
Grab Ball A
that results in a state where the robot is holding the
ball
A
. The algorithm examines first the action
Grab Ball A
and loops on its precondi-
tions. In this case there is only one precondition, declaring that for executing this action,
the robot's gripper must be free. So, somewhere in the plan there should be an action
that realizes this fact. Exploring the previous actions of the plan, the algorithm confronts
the action
Drop Ball B
and matches the fact under consideration with the second result
of this action. Automatically, an order constraint link is created between the two actions
meaning that the robot should definitely perform first the action
Drop Ball B
so as to be
able then to perform the action
Grab Ball A
.
Fig. 2.
Example on discovering links
