Report 85 25 Decision Procedures . S Stanford Matthew L. Ginsberg May 1985

LOGIC CROUP KNOWLEDGE SYSTEMS LABORATORY Department of Computer Science Stanford tIniversity Stanford, California 91305 Decision Precedures Abstract Distributed artificial intelligence is the study of how a group of individual intelligent agents can combine to solve a difficult global problem. This paper discusses in very general terms the problems of achieving this global goal by considering simpler, local subproblems; we drop the usual requirement that the agents working on the subproblems do not interact. We are led to a single assumption. An example of a distributed computation using these ideas is presented. Introduction The thrust of research in distributed artificial intelligence (DAI) is the investigation of the possibility of solving a difficult problem by presenting each of a variety of machines with simpler parts of it. The approach that has been taken has been to consider the problem of dividing tho original problem: what:,libtasks should be pursued at any given time? To which available machine should a..iven subtask be assigned? The question of how the individual machines should g9 about solving their subproblems has been left to the non-distributed Al community (or perhaps to a recursive application of DAI techniques). The assumption underlying this approach--that each of the agents involved in the solution of the subproblems can proceed independently of the others--has recently been called into question 12,3,6,7,101. It has been realized that, in a world of limited resources, it is inappropriate to dedicate a substantial fraction of those resources to each processor. The increasing attract:witless of parallel architectures in which processors share memory is an example of this: memory is a scarce resource. Automated factories must inevitably encounter similar difficulties. Are the robots working in such factories to be given distinct bins of component parts, and non-overlapping regions in which to work or to travel from one area of the factory to another?