Speculative computation with multi-agent belief revision

ABSTRACT

In multi-agent system, we often face incompleteness of information due to communication failure or other agent's suspension of decisions. To solve the incompleteness, we previously proposed speculative computation using abduction in the context of matter-slave multi-agent systems and gave a procedure in abductive logic programming [14]. In the work, a master agent prepares a default value for a question in advance and it performs speculative computation using the default without waiting for a reply for the question. This computation is effective unless the contradictory reply with the default is returned. However, we find that this mechanism is not sufficient for speculative computation in more general multi-agent systems such that replies can be revised according to other agents' speculative computation. In this paper, we formalize speculative computation with multi-agent belief revision and propose a correct procedure for such computation.

REFERENCES

• 1: Burton, F. W., "Speculative Computation, Parallelism, and Functional Programming", IEEE Transactions on Computers, vol c-34 pp. 1190--1193 (1985)
• 2: Steve Gregory, Experiments with speculative parallelism in Parlog, Proceedings of the 1993 international symposium on Logic programming, p.370-387, December 1993, Vancouver, British Columbia, Canada
• 3: Hayashi, H., "Replanning in Robotics by Dynamic SLDNF", Proc. of IJCAI-99 WS on Scheduling and Planning Meet -- Real-Time Monitoring in a Dynamic and Uncertain World (1999)
• 4: Katsumi Inoue, Linear resolution for consequence finding, Artificial Intelligence, v.56 n.2-3, p.301-353, Aug. 1992 [doi>10.1016/0004-3702(92)90030-2]
• 5: Inoue, K., Kawaguchi, S., and Haneda, H., "Controlling Speculative Computation in Multi-Agent Environments", Proc. of ICLP2001 Workshop on Computational Logic in Multi-Agent Systems (CLIMA-01), pp. 9--18 (2001)
• 6: Nick R. Jennings, Coordination techniques for distributed artificial intelligence, Foundations of distributed artificial intelligence, John Wiley & Sons, Inc., New York, NY, 1996
• 7: Kakas, A. C., Kowalski, R., Toni, F., "The Role of Abduction in Logic Programming", Handbook of Logic in Artificial Intelligence and Logic Programming 5, pp. 235--324 (1998)
• 8: Robert A. Kowalski , Francesca Toni , Gerhard Wetzel, Executing suspended logic programs, Fundamenta Informaticae, v.34 n.3, p.203-224, June 1, 1998
• 9: Robert Kowalski , Fariba Sadri, From logic programming towards multi-agent systems, Annals of Mathematics and Artificial Intelligence, v.25 n.3-4, p.391-419, 1999 [doi>10.1023/A:1018934223383]
• 10: João Alexandre Leite , José Júlio Alferes , Luís Moniz Pereira, MINERVA - A Dynamic Logic Programming Agent Architecture, Revised Papers from the 8th International Workshop on Intelligent Agents VIII, p.141-157, August 01-03, 2001
• 11: T. C. Przymusinski, On the declarative semantics of deductive databases and logic programs, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 12: Fariba Sadri , Francesca Toni , Paolo Torroni, Dialogues for Negotiation: Agent Varieties and Dialogue Sequences, Revised Papers from the 8th International Workshop on Intelligent Agents VIII, p.405-421, August 01-03, 2001
• 13: Sakama, C., Inoue, K., Iwanuma, K., and Satoh, K., "A Defeasible Reasoning System in Multi-Agent Environments", Proc. of CL2000 Workshop on Computational Logic in Multi-Agent Systems (CLIMA-00), pp.1--6 (2000)
• 14: Speculative Computation by Abduction under Incomplete Communication Environments, Proceedings of the Fourth International Conference on MultiAgent Systems (ICMAS-2000), p.263, July 10-12, 2000

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Multiagent systems

General Terms:
Theory