Information Technology Reference
In-Depth Information
In this section, we thus consider an alternative approach to distributed consequence
finding that is suitable for such
autonomous
agent systems. The new method is more
cooperative
than the previous one in the sense that agents are always seeking other
agents who can accept new consequences for further inference. In this method, we
do not presuppose network structures of agents, but any agent can have a chance to
communicate with other agents. As the language and knowledge of each agent evolves
through interactions, this framework is more
dynamic
than the first method. Since the
method is not partition-based, we do not call each distributed component as a partition,
butcallitan
agent
in this section.
Algorithm 4 (Cooperative Consequence Finding)
1. Suppose a set
I
of
input clauses
is given. This consists of a query or a goal clause
in the case of query answering or abduction as well as any clause input to the whole
system
Lit
A
be the (stable) production field, where
Lit
A
is the set of all literals in the language
of
A
.Let
A
i
be a newly created agent whose axiom set is
I
.Let
P
A
=
A
. Perform consequence finding in
A
i
,andlet
N
:=
Carc
(
A
i
,
P
A
)
.
2. For each clause
C
∈
N
, decide an agent
A
j
to which
C
is sent from
A
i
.Put
i
:=
j
.
3. In
A
i
, consequence finding is performed by SOL resolution with the top clause
C
.
Let
N
:=
Newcarc
(
N
)
.
4. Repeat Steps 2 to 3 until no more new characteristic clause is derived.
A
i
,C,
P
A
)
.Put
A
i
:=
μ
(
A
i
∪
Algorithm 4 repeats the process of (a) and (b): (a) new consequences obtained in
an agent are sent to others, and (b) then they trigger consequence finding in those
agents. An advantage of this method is that we only need to compute
new characteris-
tic clauses
Newcarc
(
P
A
)
in Step 3. In fact, computation of new characteristic
clauses is easier than computation of the whole characteristic clauses by SOL resolu-
tion. The whole characteristic clauses are still obtained by accumulating the new ones
with subsumption checking by simulating (1) and (2) in Step 3. Note that computation
of
Carc
(
A
i
,C,
P
A
)
in Step 1 is not necessary when
I
is a single clause or contains no
complimentary literals.
In Step 2 of Algorithm 4, we assume that any agent can decide to which agent each
clause
C ∈ N
should be sent. One such implementation is to associate with each agent
A
i
the set of predicates with their polarities appearing in the axiom set. This set must
be updated each time a new characteristic clause is computed in the agent. Then, it
becomes easier to find a literal that is complementary to a literal in
C
in other agents.
One can also use the current communication language
l
(
i,j
)
between two agents: if
C
A
i
,
A
j
. Note here that we do not
need to break cycles, but
l
(
i,j
)
needs to be updated whenever the axioms are updated.
In another way, a blackboard architecture like [5] can be considered as a place to store
new characteristic clauses deduced by agents. An agent should check whether (s)he has
a clause which can be resolved with a new characteristic clause.
Note that implementation of Steps 2 to 4 can be parallelized provided that synchro-
nization is properly done. The first message passing for unit clauses is illustrated in
Fig. 4 for the example of Section 3.2.
Termination of Algorithm 4 is similar to the case of Algorithm 3. For the correctness
of Algorithm 4, the following theorem holds.
∩
l
(
i,j
)
=
∅
holds, then
C
can be sent from
A
i
to
