Information Technology Reference
In-Depth Information
Ta b l e 1 . Comparison of three methods for “Getting Money”
Approach
# resolution steps
Centralized ( Carc )
872 228
Root
ag0
ag1
ag2
ag3
ag4
ag5
Partition-based
30 344
25 664
16 346
26 126
188 143
20 286
Order
0-1-2-3-4-5 1-0-2-3-4-5 2-1-0-3-4-5 3-2-1-0-4-5 4-3-2-1-0-5 5-1-0-4-2-3
Cooperative
12 381
6 290
10 851
10 851
10 908
10 908
method restricts clauses sent to its parent to those constructed with the communica-
tion language between those partitions and (ii) the cooperative method performs conse-
quence finding in each agent only with top clauses sent from other agents.
6
Comparison with Other Distributed Consequence Finding
Consequence finding has been investigated in a distributed setting [14,3,1]. Inoue and
Iwanuma [14] consider a multi-agent framework which performs speculative computa-
tion under incomplete communication environments. This is a master-slave style multi-
agent system, in which a master agent asks queries to slave agents in problem solving
and proceeds computation with default answers when answers from slave agents are
delayed. Speculative computation is implemented with SOL resolution with the condi-
tional answer method to update agents' beliefs according to situation changes. On the
other hand, distributed consequence finding in this paper does not assume any master
agent to control the whole system. Amir and McIlraith [3] propose distributed theo-
rem proving to improve the efficiency of theorem proving for structured theories. Their
message-passing algorithm reasons over these theories using consequence-finding, and
our first (partition-based) approach in this paper also uses it. As already stated in Sec-
tion 3.3, the main difference between [3] and our partition-based approach is that the
goal of the former is theorem proving while our goal is consequence finding. Another
difference is that [3] considers how to partition a problem to minimize the intersection
of the languages, while we suppose the situation that such optimal partitioning cannot
be applied because of inherent distribution of knowledge and impossibility to collect all
information to one place. This last observation directed us to the second, cooperative
approach to distributed consequence finding, which is quite different from the first one.
The peer-to-peer (P2P) consequence finding system proposed by Adjiman et al. [1,2]
is perhaps closest to our work. Their method is related to our both first (partition-based)
and second (cooperative) approaches to consequence finding. [1] composes an acquain-
tance graph from the peers using information of shared symbols, which is similar to a
graph induced from the partitions in our first approach. The difference is that [1] does
not break cycles in a graph while we do. Also, [1] performs case splitting in goal-
oriented reasoning of a peer P 1 by sending to other peer P 2 only those subgoals con-
tained in the shared symbols between P 1 and P 2 , then the new consequences of P 2 are
returned to P 1 , which is then composed in P 1 by replacing the subgoal. Combining the
results derived from the subgoals often would result in a huge combination of clauses
 
Search WWH ::




Custom Search