The project consists of three major tasks: (1) representation, (2) ANT organization, and (3) negotiation.
An ANT will be modeled as a rational agent, that is, one in which behavior is constrained by its mental state in the manner described by the SP theory. For example, intentions will serve to usefully constrain deliberation so that ANTs do not continually re-plan when faced with new goals or new information. Plans and actions - both individual and group - will be represented as rich, structured entities based on the SP theory of collaboration. The ANT architecture will be a resourse-bounded one and will be implemented in SRI?s Procedural Reasoning System (PRS). PRS will be extended to support the SP framework. Additions will include data structures standing for intentions-that, intentions-to, as well as predicates for individual and group notions of ability. PRS will also be extended to include data structures for the various plan definitions from SP built from these primitives (both individual and shared partial plans). These will supply the basic structures for a rich plan representation. PRS procedures will then be developed that operate on these data structures and update them as new information is processed.
2. ANT Organization
Relevance reasoning techniques developed at SRI will be used to analyze the information-sharing needs of individual ANTs and to identify groups that are working on closely related problems (informationally). Other ways of grouping ANTs will be investigated including geographically, by shared resources, or by using existing organizational (e.g., military command) structure.
A belief justification system will be developed and justifications will be tailored to focus on the relevant issues in the negotiation. These may only address certain aspects of the plan, in order to focus effort on a particular part of the problem space. Each ANT may only have a local utility model, though it may also have some understanding of shared goals, and of other agents? goals. Therefore, in general, a given ANT?s contribution to the justification for a particular proposal will focus on its local needs. Another ANT may make a counter-proposal by proposing a modification to the plan, eliminating a weakness in the original plan from its local perspective. Alternatively, it may agree with the proposed plan, and broadcast an updated justification that shows increased support for the plan, by adding its local evaluation.
In our vision of the ANT community, some ANTs will emerge as evaluation specialists that can be thought of as mediators. These ANTs will take a global perspective, combining their beliefs about the local utility functions of other ANTs, performing a global optimization process, and producing counter-proposals that may better satisfy the overall needs of the ANT community.
We will build on previous work on strategic negotiation that applies game-theoretic tools to modeling cooperative negotiations in which negotiation strategies range over time. That work is based on a model of alternating offers: in that model strategies are rules for choosing actions that can depend on earlier choices. During strategic negotiations, agents communicate their respective desires and compromise to reach mutually beneficial agreements. Strategic negotiation is a process that may include several iterations of offers and counteroffers. A major consideration in the development of the strategic negotiation model has been to reduce overhead costs resulting from the time spent on planning and negotiation. This is necessary since one of the presumed difficulties in using negotiation as a way of reaching mutual benefit is that negotiation may become a costly and time-consuming process and, consequently, it may increase the overhead of coordination. Thus, in the presence of time constraints, planning time and negotiation time should both be taken into consideration. The strategic negotiation model provides a unified solution to a wide range of problems. It is appropriate for agents acting in dynamic real-world domains and provides them with a way of reaching mutually beneficial agreements without delay.
We will extend that approach so that negotiations are structured around the planning stages described above; hence, negotiations need not be postponed until all information is available. We will focus on developing anytime algorithms for such structured negotiations. Part of this task involves identifying the elements of the chosen domain of application that correspond to the game-theoretic notions of equilibria, and so forth. Since SharedPlans supports contracting in cases in which a master-slave negotiation relationship is appropriate; our approach will make use of contract nets in such instances.