Bib database on Distributed AI by Mathijs de Weerdt

The CEC Project GOAL (Esprit 6283) aims to develop generic software tools to support a new project management paradigm, in which projects are collaborative, decentralised and inter-organizational. Our research and development activities have focussed on using multi-agent systems to address the inter-organizational aspects of interaction and communication between partners in such projects. The multi-agent framework we have been investigating and developing, called the Cooperation Services Framework (CSF), is designed to support distributed computer-supported cooperative work in inter-organizational project management. This position paper reviews our developments to date, describes our programme for realising a prototype demonstrator, and discusses some of the issues to be addressed in future investigation and experimentation. In particular, extending the CSF to include `agent brokering' between `rational agents' would enable other applications for inter-organizational interactions to be developed, such as trading systems and on-line information services.

Keywords: Practical Applications of Multi-Agent Systems, Intelligent Agents in Enterprise Integration Systems

Following earlier approaches we use game-theoretic techniques to model the conflict of interest and cooperation among agents. We apply this techniques to the domain of traffic signal control whose usual strategies are modelled in a decentralized fashion. In our architecture traffic elements are modelled as single agents which have diverse knowledge represented by means of information sets. Lack of knowledge is modelled by means of games with incomplete information. Interactions among agents are both cooperative and noncooperative and are based on the rationality of the agents, which pick one of the equilibrium points of the game. Therefore the problem of equilibrium selection for noncooperative games is explored. For cooperative games the bargaining solution is used. Some examples of the traffic signal control domain which map interactions in noncooperative as well as in cooperative situations are presented.

A multi-agent distributed architecture for autonomous planning and scheduling tasks of a space system formation is here proposed. Each physical element of the team is represented as an independent unit, with its own knowledge base, its own resources and its operational skills. High-level goals asking for single/ multiple units coordinated intervention can be dealt with. The pre/post-conditions consistent net definition to accomplish the distributed planning task is accomplished thanks to a Partial Ordered Planning algorithm. A temporal net formalism is chosen to cope with the distributed scheduling problem: the infra/inter agents' temporal consistency is gained by applying an All Shortest Paths algorithm. No instantiation is asked for solving the distributed net, to preserve robustness of the scheduling according to possible external uncertainties and system failures. As no leader exists, local and shared resource consistency is acquired thanks to iterative negotiation processes among agents for the best compromise selection devoted to lower the conflicts occurrence. Two negotiation strategies are presented, to emphasize either the team welfare or the single agent welfare respectively. The communication protocol is based on the innovation of the communication oriented graph concept The proposed architecture is here applied to a rovers scenario devoted to planetary exploration. Simulations show the validity of the proposed approach to assure multiple and robust final allocations. ©2005 IEEE.

This paper discusses specific features of planning in multiagent domains and presents concepts for a multiagent extension of PDDL, the Multiagent Planning Language MAPL. MAPL uses non-boolean state variables and thus allows to describe an agent's ignorance of facts as well as a simplified mutex concept. The time model of MAPL is based on Simple Temporal Networks and allows both quantitavive and qualitative use of time in plans, thereby subsuming the plan semantics of both partial order plans and PDDL 2.1.

In this paper we attempt to use reinforcement learning techniques to solve agent coordination problems in task-oriented environments. The Fuzzy Subjective Task Structure model (FSTS) is presented to model the general agent coordination. We show that an agent coordination problem modeled in FSTS is a Decision-Theoretic Planning (DTP) problem to which reinforcement learning can be applied. Two learning algorithms coarse-grained and fine-grained are proposed to address agents coordination behavior at two different levels. The coarse-grained algorithm operates at one level and tackle hard system constraints and the fine-grained at another level and for soft constraints. We argue that it is important to explicitly model and explore coordination-specific (particularly system constraints) information which underpins the two algorithms and attributes to the effectiveness of the algorithms. The algorithms are formally proved to converge and experimentally shown to be effective. © 2005 Springer Science+Business Media, Inc.

Keywords: Coordination, Multiagent system, Reinforcement learning, Task-oriented Environment

Internet auction not only is an integral part of Electronic Commerce but also becoming a promising field for applying autonomous agents and multi-agent system technologies. Auction, as an efficient resource allocation method, has been paid more and more attention among scholars. This paper gives a protocol (VAMA) and strategy for multi-attribute auction. Some useful properties like strategy-proof also have been proved. Then, we analyze the strategy of the buyer; give an optimal strategy for sellers. Finally, we compare this protocol with existing ones, improving the work of Esther David etc.

Keywords: Bidding and bargaining agents, Multi-agent systems, Multi-attribute auction, Bidding and bargaining agents, Multi-agent systems, Multi-attribute auction

The allocation of resources within a system of autonomous agents, that not only have preferences over alternative allocations of resources but also actively participate in computing an allocation, is an exciting area of research at the interface of Computer Science and Economics. This paper is a survey of some of the most salient issues in Multiagent Resource Allocation. In particular, we review various languages to represent the preferences of agents over alternative allocations of resources as well as different measures of social welfare to assess the overall quality of an allocation. We also discuss pertinent issues regarding allocation procedures and present important complexity results. Our presentation of theoretical issues is complemented by a discussion of software packages for the simulation of agent-based market places. We also introduce four major application areas for Multiagent Resource Allocation, namely industrial procurement, sharing of satellite resources, manufacturing control, and grid computing.

The Robotics Institute, Carnegie Mellon Univ. This paper focuses on operator overlap, which is a positive interaction (as opposed to the usual detection of only negative interactions) that occurs when two operators share work. The example is given using machinists making parts.

Negotiation in planning is demonstated using virtual circuits in a network as an example.

In this paper, we propose a generic planning model for the pulp and paper supply chain. We first review the different business units of the supply chain and the materiel flows. We then propose a supply chain decision matrix specifically designed for the pulp and paper industry. We further extend the discussion by addressing the difficult problem of distributed planning, even in a hierarchically organized system. To conclude, we propose a multi-agent framework to simulate different configurations of supply chain and anticipate the impact of the different decision models used by the different business units of the supply chain.

The need for coordinated material flow in supply chains is essential for the competitiveness of manufacturing firms. A hierarchical coordination is not applicable for each supply chain. A collaboration between entities is required to meet future challenges. Besides appropriate planning concepts an IT solution is a major challenge. Multi-Agent Systems (MAS) are an enabler for a decentralized coordination process. The evolvement of appropriate planning methods makes MAS interesting for collaborative Supply Chain Management (SCM). Nevertheless, the user should be seen as the supply chain engineer, holding the knowledge to create the collaborative supply chain processes. Therefore, the user has to be integrated in the IT solution. A configurable MAS, based on generic components, satisfies this requirement so that MAS can easily be adapted to the changing processes and environment by the user. This paper presents a concept of a configurable MAS and a prototype of a MAS-Editor for collaborative production planning © 2005 IEEE.

Randall Davis : Artificial Intelligence Laboratory, MIT Reid G. Smith : Schlumberger-Doll Research Ridgefield Ct. A framework, called the contract net that specifies communication and control in a distributed problem solver is presented. The announcement/bid/award sequence is explained. This paper gives a large example but is a little less detailed than the paper The Contract Net Protocol : High ... paper.

Dial-a-ride real-time scheduling algorithm including ride-sharing. This method uses insertion and both in-vehicle and between-vehicle exchanges to improve the quality.

The use of software agents for automatic contract negotiation in e-commerce and e-trading environments has been the subject of considerable recent interest. A widely studied abstract model considers the setting in which a set of agents have some collection of resources shared out between them and attempt to construct a mutually beneficial optimal reallocation of these by trading resources. The simplest such trades are those in which a single agent transfers exactly one resource to another-so-called 'one-resource-at-a-time' or 'O-contracts'. In this research note we consider the computational complexity of a number of natural decision problems in this setting.

Keywords: Negotiation, Multiagent systems, Computational complexity

We consider techniques suitable for combining individual agent plans into a global system plan, maintaining a commitment to considerations of global utility that may differ radically from individual agent utilities. We present a three-stage heuristic reduction process, consisting of a transformation from local to global utility measures, a global assessment of the local evaluations of agents, and approximation algorithms to maximize resource usage over time. We also consider how these techniques can be used with self-motivated agents, and show how the overall process can be distributed among a group of agents.

Keywords: Distributed Problem Solving, Planning, Search

Automated negotiation is a key form of interaction in systems that are composed of multiple autonomous agents. The aim of such interactions is to reach agreements through an iterative process of making offers. The content of such proposals are, however, a function of the strategy of the agents. Here we present a strategy called the trade-off strategy where multiple negotiation decision variables are traded-off against one another (e.g., paying a higher price in order to obtain an earlier delivery date or waiting longer in order to obtain a higher quality service). Such a strategy is commonly known to increase the social welfare of agents. Yet, to date, most computational work in this area has ignored the issue of trade-offs, instead aiming to increase social welfare through mechanism design. The aim of this paper is to develop a heuristic computational model of the trade-off strategy and show that it can lead to an increased social welfare of the system. A novel linear algorithm is presented that enables software agents to make trade-offs for multi-dimensional goods for the problem of distributed resource allocation. Our algorithm is motivated by a number of real-world negotiation applications that we have developed and can operate in the presence of varying degrees of uncertainty. Moreover, we show that on average the total time used by the algorithm is linearly proportional to the number of negotiation issues under consideration. This formal analysis is complemented by an empirical evaluation that highlights the operational effectiveness of the algorithm in a range of negotiation scenarios. The algorithm itself operates by using the notion of fuzzy similarity to approximate the preference structure of the other negotiator and then uses a hill-climbing technique to explore the space of possible trade-offs for the one that is most likely to be acceptable. © 2002 Elsevier Science B.V. All rights reserved.

Keywords: Automated negotiation, Fuzzy similarity, Multi agent systems, Trade-off algorithm

The MARS system is described which models cooperative scheduling within a society of shipping companies as a multiagent system. Emphasis is placed on the functionality of the system as a whole - the solution of the global scheduling problem emerges from local decision-making and problem-solving strategies. An extension of the contract net protocol is presented; we show that it can be used to obtain good initial solutions for complex resource allocation problems. By introducing global information based upon auction protocols, this initial solution can be improved significantly. Experimental results are provided evaluating the performance of different cooperative scheduling strategies. Although the concepts for resource scheduling are presented solely for the transportation domain, their abstraction is useful for a broad variety of resource allocation problems. The MARS system solves the dynamic scheduling problem where no complete specification of the problem is available a priori; thus, it is designed as an on-line system based upon anytime algorithms.

A multi-agent system (MAS) for supporting the planning of transhipments of imported finished vehicles via a seaport is presented. The focus is on storage allocation, i.e. the allocation of parking areas for the temporary storage of vehicles, and on deployment scheduling, i.e. the allocation of drivers to the vehicles that have to be moved in the terminal area. These planning tasks, which in practice are usually carried out by different operators, are assigned to two different agent types. A further agent, the coordinator agent, is responsible for combining the local sub-plans into an overall plan in such a way that the demand for drivers in the planning period is minimised and balanced. The MAS is tested using randomly generated problem instances with different distributions of the manufacturer shares in the vehicle streams. The tests verify a certain robustness of the MAS with regard to changes in the problem data, in particular to the number of permanently employed drivers and the cost surcharge for hired drivers. In addition, the results highlight that the minimum overall (relative) costs of the drivers depends on the number of permanently employed drivers and on the level of the cost surcharge for hired drivers. © 2004 Elsevier B.V. All rights reserved.

Keywords: Genetic algorithms, Heuristics, Logistics, Multi-agent systems, Seaport automobile terminals, Supply chain management, Vehicle transhipment

A supply chain is a worldwide network of suppliers, manufactures, warehouses, distribution centers and retailers through which raw materials are acquired, transformed and delivered to customers. In recent years, a new system approach for managing the supply chain at the tactical and operational levels has emerged. It views a supply chain as composed of a set of intelligent (software) agents, who are responsible for one or more activities and interacting with other related agents in planning and executing their responsibilities. This paper presents a multiagent architecture of supply chain integration. Agents coordination using extended contract net protocol is discussed. Two types of bidding approaches, i.e., the customizing-type and webbing-type are introduced into the multiagent supply chain system. Finally, a heuristics and two programming models for the planning and coordination of demand-driven supply chains are suggested. © Springer-Verlag London Limited 2004.

Keywords: Coordination, Multiagent, Planning, Supply chain

We view meeting scheduling as a distributed task where each agent knows its user's preferences and calendar availability in order to act on behalf of its user. Although we may have some intuitions about how some parameters could affect the scheduling efficiency and meeting quality, we run several experiments in order to explore the tradeoffs between different parameters. Our experiments show how the calendar and preference privacy affect the schedulling efficiency and the meeting joint quality under different experimental scenarios. The results show how the scheduling performance is more stable and constant when agents try to keep both calendar and preference privacy. We believe that these parameters play a key role in the distributed meeting scheduling task, specially if we are interested in building distributed systems with truly autonomous and independent agents where there is not a fixed centralized host agent.

Despite more than a decade of experimental work in multi-robot systems, important theoretical aspects of multi-robot coordination mechanisms have, to date, been largely untreated. To address this issue, we focus on the problem of multi-robot task allocation (MRTA). Most work on MRTA has been ad hoc and empirical, with many coordination architectures having been proposed and validated in a proof-of-concept fashion, but infrequently analyzed. With the goal of bringing objective grounding to this important area of research, we present a formal study of MRTA problems. A domain-independent taxonomy of MRTA problems is given, and it is shown how many such problems can be viewed as instances of other, well-studied, optimization problems. We demonstrate how relevant theory from operations research and combinatorial optimization can be used for analysis and greater understanding of existing approaches to task allocation, and show how the same theory can be used in the synthesis of new approaches.

Hendler : Univ. of Maryland, Tate : Univ. of Edinburgh, Drummond : NASA Ames Research Center. Summary of different planning techniques : blocks world, distributed planning, STRIPS.

Dial-a-ride algorithm using mini-clustering and column generation

Plan synchronization is a method of analyzing multiagent plans, in order to introduce ordering constraints between them so that their concurrent execution achieve a desired goal. We describe a plan synchronization method for goals expressed using temporal logic specifications. Our goals can involve both qualitative and quantitative time requirements. The key to our method is a technique for checking goal formulas, incrementally, over models of concurrent executions of plans. Our approach covers more general problems than comparable methods and promises an easy integration with standard AI planning search control and heuristic strategies.

Keywords: multiagent planning, coordination

Keywords: graph coloring complexity

This paper outlines the basic principles underlying reasoning about resources in IPP, which is a classical planner based on planning graphs originally introduced with the Graphplan system. The main idea is to deal with resources in a strictly action-centered way, i.e. one specifies how each action consumes or produces resources, but no explicit temporal model is used. This avoids the computational problems of solving general constraint satisfaction problems by using instead interval arithmetics and propagation of resource requirements over time steps in the planning graph.

Coalition formation methods allow agents to join together and are thus necessary in cases where tasks can only be performed cooperatively by groups. This is the case in the Request For Proposal (RFP) domain, where some requester business agent issues an RFP - a complex task comprised of sub-tasks - and several service provider agents need to join together to address this RFP. In such environments the value of the RFP may be common knowledge, however the costs that an agent incurs for performing a specific sub-task are unknown to other agents. Additionally, time for addressing RFPs is limited. These constraints make it hard to apply traditional coalition formation mechanisms, since those assume complete information, and time constraints are of lesser significance there. To address this problem, we have developed a protocol that enables agents to negotiate and form coalitions, and provide them with simple heuristics for choosing coalition partners. The protocol and the heuristics allow the agents to form coalitions in the face of time constraints and incomplete information. The overall payoff of agents using our heuristics is very close to an experimentally measured optimal value, as our extensive experimental evaluation shows.

This paper provides an introduction to Finite-domain Constraint Logic Programming (CLP) and its application to problems in scheduling and planning. We cover the fundamentals of CLP and indicate recent developments and trends in the field. Some current limitations are identified, and areas of research that may contribute to addressing these limitations are suggested.

Due to the widespread availability of the Internet, large scale distributed projects in manufacturing are becoming popular. In order to address the dynamic requirements of multi-project production, this paper develops a collaborative multi-project planning and scheduling system based on the multi-agent technology. The hybrid framework of system is presented and discussed with detail. Six types of intelligent agents are proposed in this system. These agents are dynamically deployed at each location where a project is executed. Further more, a negotiation mechanism for multi-project planning and scheduling is developed to coordinate these distributed agents. Task allocation strategy and critical resource leveling strategy are also presented. Through which a predictable and nearly optimal scheduling with agility and adaptability can be realized in distributed multiple projects manufacturing environment. Finally, a prototype system was implemented upon this framework, and was validated in an aerospace company. © 2005 IEEE.

Keywords: Distributed manufacturing, Intelligent agent, Multiple projects, Negotiation mechanism, Planning and scheduling

There is an increasing interest in the relation between logic and the changes involved in reasoning and, specifically, in plan generation. Up to now, several attempts in this direction have been made, either by embedding actions into a classical framework or by using nonstandard formalisms. We think that these attempts, though promising, miss their objectives, for a lack of a suitable logic, and that the effort must be pursued. In this paper, we show how to obtain a strong and clean correspondence between proofs and sequences of actions by using only Girard's linear logic, eliminating from the classical logic the structural rules which are not adapted to our purpose. A theorem is presented which expresses the new adequacy between proofs and actions.

A multicriteria approach for distributed planning and conflict resolution in multiagent systems is presented in the paper. A graph representation is used to model the plans of each agent and a multicriteria ``best'' path procedure can be used in order to obtain the ``best'' path for each agent considering her/his private goals. In our approach private and local goals do not necessarily coincide. A conflict and/or positive cooperation may occur and a detection procedure is triggered as soon as the agents broadcast their ``best plans''. A negotiation process is the established if necessary. Such a process iterates the use of the graph representation and of the ``best'' path algorithm to a level including the agents that have to negotiate. The parameters of the multicriteria model used to evaluate the paths are then negotiated or even the model itself. Some open problems conclude the paper.

The recent approaches of extending the GRAPHPLAN algorithm to handle more expressive planning formalisms raise the question of what the formal meaning of ``expressive power'' is. We formalize the intuition that expressive power is a measure of how concisely planning domains and plans can be expressed in a particular formalism by introducing the notion of ``compilation schemes'' between planning formalisms. Such compilation schemes restrict the growth of planning domains and the corresponding plans. Using this notion, we analyze the expressiveness of a large family of propositional planning formalisms, ranging from basic STRIPS to a formalism with conditional effects, partial state specifications, and propositional formulae in the preconditions. One of the results is that conditional effects cannot be compiled away if plan size should grow only linearly but can be compiled away if we allow for polynomial growth of the resulting plans. This result confirms that the recently proposed extensions to the GRAPHPLAN algorithm concerning conditional effects are optimal with respect to the ``compilability'' framework. Another result is that general propositional formulae cannot be compiled into conditional effects if the plan size should be preserved. This implies that allowing general propositional formulae in preconditions and effect conditions adds another level of difficulty in generating a plan.

In this paper, we propose an autonomous decentralized optimization system for multi-stage production processes. The proposed system consists of a Material Requirement Planning subsystem, a Distribution Planning subsystem and Decentralized Scheduling subsystems belonging to each production stage that constitute the entire plant. In the proposed system, each subsystem repeats both optimization of the schedule at each subsystem and data exchange among the subsystems. Computational results demonstrate that the results of the proposed planning system are superior to those of the hierarchical planning system, despite the fact that the proposed system has wide flexibility for adding the constraints and modifying the criterion of performance evaluation. © 2005 Springer Science+Business Media, Inc.

Keywords: Autonomous decentralized system, Distributed scheduling, Flowshop problem, Planning and scheduling, Simulated annealing, Supply chain

In this paper, we propose a metalevel coordination strategy to implement an adaptive organization for reactive cooperative planning. The adaptive organization changes its organizational scheme adaptively as a means of coping with the dynamic problem spaces. Preliminary experiments shows that an adaptive organization can be made to the increase efficiency in dynamic problem spaces. The reason for this works is that reducing the degree of freedom in the problem space, while increasing the degree of interaction, demands greater coordination. However, if the number of effective local plans decrease, it would seem likely that if the agents were to have a better metalevel strategy, they would be better able to search this reduced space efficiently. The metalevel coordination incorporates an agent-wide metalevel heuristic function. In designing the metalevel coordination strategy, we take three aspects of reactive cooperative planning into account. These aspects include: the difference in the degree of achievement in successive turns; the certainty of shared information; and the degree of freedom of choice for agent's behavior. The adaptive organization works efficiently in cases where the communication cost is relatively expensive.

Coordination is one of those words: it appears in most science and social fields, in politics, warfare, and it is even the subject of sports talks. While the usage of the word may convey different ideas to different people, the definition of coordination in all fields is quite similar - it relates to the control, planning, and execution of activities that are performed by distributed (perhaps independent) actors. Computer scientists involved in the field of distributed systems and agents focus on the distribution aspect of this concept. They see coordination as a separate field from all the others - a field that rather complements standard fields such as the ones mentioned above. This paper focuses on explaining the term coordination in relation to distributed and multi-agent systems. Several approaches to coordination are described and put in perspective. The paper finishes with a look at what we are calling emergent coordination and its potential for efficiently handling coordination in open environments. Copyright © 2005 John Wiley & Sons, Ltd.

Keywords: Coordination technologies, Distributed computing, Multi-agent systems

Keywords: Algorithms, Alternation, Complexity theory, Game theory, Incomplete information, Blindfold

One of the landmark papers of Plotkin about SOS.

Queuing and accepting reservations are common social methods for allocating scarce resources in our daily lives. However, neither method is flexible when they are components of large, complex plans. In this paper we investigate the use of mobile devices that provide timely information, facilitate planning, and enable the trading of reservations. We investigate the behavior of a closed society of simple agents competing for scarce resources. The results of the experiments demonstrate that a simple reservation mechanism can actually reduce the social welfare under certain conditions, but tradable reservations and clairvoyance each improve it. While in many situations queues are unavoidable, better information and more flexibility in reservation handling can facilitate planning.

Computer Science Dept Stanford Univ. A set of communication primitives are defined which are used to synchronize multiple agents when they create plans

Distributed planning is fundamental to the generation of co-operative activities in Multi-Agent Systems. It requires both an adequate plan representation and efficient interacting methods allowing agents to coordinate their plans. This paper proposes a recursive model for the representation and the handling of plans by means of Recursive Petri Nets (RPN) which support the specification of concurrent activities, reasoning about simultaneous actions and continuous processes, a theory of verification and mechanisms of transformation (e.g. abstraction, refinement, merging). The main features of the RPN formalism are domain independence, broad coverage of interacting situations and operational coordination. This paper also provides an approach to the interleaving of execution and planning which is based on the RPN semantics and gives some significant methods allowing plan management in distributed planning. It goes on to show how this approach can be used to coordinate agents' plans in a shared and dynamic environment.

Computational infrastructures for cooperative work should contain embedded agents for handling many routine tasks, but as the number of agents increases and the agents become geographically and/or conceptually dispersed, supervision of the agents will become increasingly problematic. We argue that agents should be provided with deep domain knowledge that allos them to make justifiable decisions, rather than shallow models of users to mimic. In this paper, we use the application domain of distributed meeting scheduling to investigate how agents embodying deeper domain knowledge can choose among alternative strategies for searching their calendars in order to create flexible schedules within reasonable cost.

Keywords: Distributed search, intelligent negotiating agents

The Contract Net protocol is presented, a high-level protocol for communication among the nodes in a distributed problem solver. It facilitates distributed control of cooperative task distribution (task-sharing) with efficient internode communication. This paper presents in more detail the complications and extensions to the protocol than the Negotiation as a Metaphor ... paper.

Epistemic utility theory, originally developed to model single-agent cognitive decision-making, is extended to the multi-agent case and applied to practical coordinated decision-making. For an M-agent society, individual and multiple agent coordination information is contained in a 2M-dimensional coordination space. The coordination function is a joint probability mass (or density) function defined over the coordination space that characterizes: (a) each individual agent's goals and standards; (b) each individual agent's abductive considerations, such as cost, hazard, or resource consumption; and (c) information pertaining to the interactions within the society, such as cooperation, competition, exploitation, compromise, tolerance, and indifference. The coordination function is used to derive two joint utilities, termed accuracy and rejectability, and a joint version of Levi's rule of epistemic utility is applied to identify the satisficing set of decision vectors that represent jointly rational behavior for the society.

This paper describes plan reuse in multiagent domains. In distributed planning, a plan is created by distributed centers of planner agents that have their own viewpoints. Plan reuse where a past plan result is reused for the new problem was proposed for single-agent planning and can achieve efficient planning. A special issue for applying it to distributed planning is that, even if the local agent thinks that the new problem is identical to a past problem, other agents may have quite different goals. Another issue is to realize efficient distributed planning, like in a single-agent case. This paper shows that the past plan can be reused regardless of other agents' goals under the assumption that the initial state has only ``in-facts.'' A generated plan and related information are stored as a plan template so that an agent can reuse it in future planning. This information includes generated plans, subgoals, non-local effects that may affect or be affected by other agents' plans, and their conflict resolution methods that were actually used. An agent can create a plan efficiently using a template, because it can skip a part of planning actions, detect conflicts in an early stage, and reduce communication costs. First, this paper presents the planning-with-reuse framework. Then how plan templates are created and reused is also illustrated using some block world examples. Finally, we experimentally show that efficient distributed planning can be achieved.

Coordination is an essential technique in cooperative, distributed multi-agent systems. However, sophisticated coordination strategies are not always cost-effective in all problem-solving situations. This paper presents a learning method to acquire coordination plans for specific problem-solving situations so that the appropriate type of coordination strategy is used. This learning is accomplished by recording and analyzing traces of inferences after problem solving. The analysis results in identification of situations where inappropriate coordination strategies have caused redundant activities or the lack of timely execution of important activities, thus degrading system performance. Based on this identification, situation-specific coordination plans are created which use additional non-local information about activities in the networks to remedy the problem. An example from a real distributed problem-solving application involving diagnosis of a local area network is described.

Keywords: Combinatorial auction, False-name-proof, Multi-attribute

The Robotics Institute Carnegie Mellon Univ. When cooperation can not be assumed between agents, a mechanism whereby the goals and behaviour of other agents can be modified to increase the cooperativeness of the agents is developed.

Although previous studies have achieved a great deal on the local decision areas including inventory policies, vendor selection, production scheduling, etc., and the strategic problems, e.g. networks design, simulation and prediction of the supply chain as a whole, few attempts have been focused on the integrated solution for supply chain operational management. As the structure of Multi-agent systems (MAS) inherently meets the requirements of autonomy and decentralization for supply chains, we propose a multi-agent-based model of planning, scheduling and execution that is capable of supporting the resource coordination between the self-interested agents through a combinatorial auction mechanism. And a general framework of ASCMS (Agile Supply Chain Management System) is presented as the background. To facilitate the functions of this system, the components of various agents and the negotiation process are also discussed in this paper. © 2005 IEEE.

This paper presents a system for designing and updating a personalized study plan in a collaborative environment. Unlike existing systems, which are mainly interested in storing the study plan, this system based on learning agents is able to suggest a study plan and if needed, identify potentially problematic choices in the future, thus bringing dynamics in to the system. By collaborating with other agents in a multi-agent environment, the chances of finding a mutually beneficial result is improved A prototype of the system for creating study plans is available. Initial empirical results show that after a short learning period, the system is able to form a study plan which requires minimal attention from the students.

Keywords: Autonomous agents, Collaborative planning, Personalized study plans

The basic theme of this writing is that knowledge of resource contention can be used to detect parallelism in plans. The language SIPE briefly discussed allows declaration of objects (e.g., blocks) to be declared as resources for a particular planning activity.

This paper presents the development of an agent-based negotiation approach to integrate process planning and scheduling (IPPS) in a job shop kind of flexible manufacturing environment. The agent-based system comprises two types of agents, part agents and machine agents, to represent parts and machines respectively. For each part, all feasible manufacturing processes and routings are recorded as alternative process plans. Similarly, alternative machines for an operation are also considered. With regard to the scheduling requirements and the alternative process plans of a part, the proposed agent-based IPPS system aims to specify the process routing and to assign the manufacturing resources effectively. To establish task allocations, the part and machine agents have to engage in bidding. Bids are evaluated in accordance with a currency function which considers an agent's multi-objectives and IPPS parameters. A negotiation protocol is developed for negotiations between the part agents and the machine agents. The protocol is modified from the contract net protocol to cater for the multiple-task and many-to-many negotiations in this paper. An agent-based framework is established to simulate the proposed IPPS approach. Experiments are conducted to evaluate the performance of the proposed system. The performance measures, including makespan and flowtime, are compared with those of a search technique based on a co-evolutionary algorithm.

Keywords: Agents, Currency function, Integrated process planning and scheduling, Negotiation

We consider a homogeneous cooperative multiagent system organized as a multiply sectioned Bayesian network (MSBN). Earlier work has shown that (1) multiagent MSBNs can be applied to distributed interpretation tasks; and (2) a distributed communication operation can be used to ensure the global consistency among agents. In this paper, we address the following problem: During a communication operation, each agent is unavailable to process new evidence for a time interval (called off-line time). We consider the minimization of total length of off-line time of the entire system. To concentrate on the factors affecting the off-line time, we abstract communication in MSBNs into a graphical model for off-line time study. Using the model, we present the optimal schedules when communication is initiated from an arbitrarily selected agent. We show now the optimal schedules can be constructed in a distributed fashion.

To achieve fully autonomy of deep space spacecraft, onboard planning is a crucial technology. Though, lots of successful applications about it in spacecraft operations have recently been used in real or experimental flight, the inherent distribution and concurrency of the spacecraft subsystem was not taken into consideration. To improve the efficiency of planning system, a multi-agent planning system (MAPS) of autonomous spacecraft is proposed in this paper. MAPS subdivides the search space into some small ones and every PA manages and operates in its own space. With the help of planning manager agent (PMA), all of the planning agents communicate and cooperate with each other to produce partial plan which satisfied all the constraints of the system. To be capable of describing simultaneous activity, continue time, resource and temporal constraints in MAPS, a new planning formal model is given firstly. As the application of this architecture, an MAPS prototype system for deep spacecraft, which is realized with Java language, is designed. © 2005 Elsevier Ltd. All rights reserved.

Keywords: Deep space exploration, Multi-agent, Planning system, Simulation

What is the influence of taxi regulations (price and entry controls) on the passenger waiting time, the taxi utilization, and the number of taxis used.

The dynamics of resource contention in multiagent systems with imperfect information can be extremely complex. It was shown by Hogg and Huberman that when agents can follow different strategies in a system with resource contention, it is possible to render otherwise unstable and chaotic behavior into equilibrium. In a number of computer experiments we explore this mechanism and find the existence of bursty behavior which sporadically punctuates the existing equilibrium. This phenomenon is shown to arise out of the underlying fluctuations of the multiagent system. This mechanism of equilibria punctuated by bursts of erratic activity appears to be quite general in systems where agents explore strategies in search of local improvements.

Due to similarities in terms of network structure and interactions among them, most infrastructure systems can be viewed as coupled layers of a generalized transportation network in which the passenger, freight, data, water, and energy flows are the commodities in the different layers. The coupling is due to the varying degrees of interactions among these layers in terms of shared physical networks, budgetary constraints, socio-economic environments, environmental concerns, information/other resources, and in particular, functional interdependencies. However, these interactions are normally ignored in the engineering planning, design and analysis of infrastructure systems. Identifying and understanding these interactions using a holistic perspective can lead to more efficient infrastructure systems. This paper presents a preliminary network flow equilibrium model of dynamic multi-layer infrastructure networks in the form of a differential game involving two essential time scales. In particular, three coupled network layers - automobiles, urban freight and data - are modeled as being comprised of Cournot-Nash dynamic agents. An agent-based simulation solution structure is introduced to solve the flow equilibrium and optimal budget allocation problem for these three layers under the assumption of a super authority that oversees investments in the infrastructure of all three technologies and thereby creates a dynamic Stackelberg leader-follower game. © Springer Science+Business Media, Inc. 2005.

Keywords: Agent-based simulation, Dynamic flows, Game theory, Infrastructure networks, User behavior