Multi-Agent Systems (MAS) promise to offer solutions to problems where established, older paradigms fall short. In order to validate such claims that are repeatedly made in software agent publications, empirical in-depth studies of advantages and weaknesses of multi-agent solutions versus conventional ones in practical applications are needed. Climate control in large buildings is one application area where multi-agent systems, and market-oriented programming in particular, have been reported to be very successful, although central control solutions are still the standard practice. We have therefore constructed and implemented a variety of market designs for this problem, as well as different standard control engineering solutions. This article gives a detailed analysis and comparison, so as to learn about differences between standard versus agent approaches, and yielding new insights about benefits and limitations of computational markets. An important outcome is that "local information plus market communication produces global control".

There are p heterogeneous objects to be assigned to n competing agents (n > p) each with unit demand. It is required to design a Groves mechanism for this assignment problem satisfying weak budget balance, individual rationality, and minimizing the budget imbalance. This calls for designing an appropriate rebate function. When the objects are identical, this problem has been solved which we refer as WCO mechanism. We measure the performance of such mechanisms by the redistribution index. We first prove an impossibility theorem which rules out linear rebate functions with non-zero redistribution index in heterogeneous object assignment. Motivated by this theorem, we explore two approaches to get around this impossibility. In the first approach, we show that linear rebate functions with non-zero redistribution index are possible when the valuations for the objects have a certain type of relationship and we design a mechanism with linear rebate function that is worst case optimal. In the second approach, we show that rebate functions with non-zero efficiency are possible if linearity is relaxed. We extend the rebate functions of the WCO mechanism to heterogeneous objects assignment and conjecture them to be worst case optimal.

This paper introduces AntNet, a novel approach to the adaptive learning of routing tables in communications networks. AntNet is a distributed, mobile agents based Monte Carlo system that was inspired by recent work on the ant colony metaphor for solving optimization problems. AntNet's agents concurrently explore the network and exchange collected information. The communication among the agents is indirect and asynchronous, mediated by the network itself. This form of communication is typical of social insects and is called stigmergy. We compare our algorithm with six state-of-the-art routing algorithms coming from the telecommunications and machine learning fields. The algorithms' performance is evaluated over a set of realistic testbeds. We run many experiments over real and artificial IP datagram networks with increasing number of nodes and under several paradigmatic spatial and temporal traffic distributions. Results are very encouraging. AntNet showed superior performance under all the experimental conditions with respect to its competitors. We analyze the main characteristics of the algorithm and try to explain the reasons for its superiority.

We investigate a hybrid between temporal partial-order and forward-chaining planning where each action in a partially ordered plan is associated with a partially defined state. The focus is on centralized planning for multi-agent domains and on loose commitment to the precedence between actions belonging to distinct agents, leading to execution schedules that are flexible where it matters the most. Each agent, on the other hand, has a sequential thread of execution reminiscent of forward-chaining. This results in strong and informative agent-specific partial states that can be used for partial evaluation of preconditions as well as precondition control formulas used as guidance. Empirical evaluation shows the resulting planner to be competitive with TLplan and TALplanner, two other planners based on control formulas, while using a considerably more expressive and flexible plan structure.

Multiagent planning is computationally hard in the general case due to the exponential blowup in the action space induced by concurrent action of different agents. At the same time, many scenarios require the computation of plans that are strategically meaningful for self-interested agents, in order to ensure that there would be sufficient incentives for those agents to participate in a joint plan. In this paper, we present a multiagent planning and plan improvement method that is based on conducting iterative best-response planning using standard single-agent planning algorithms. In constrained types of planning scenarios that correspond to congestion games, this is guaranteed to converge to a plan that is a Nash equilibrium with regard to agents' preference profiles over the entire plan space. Our empirical evaluation beyond these restricted scenarios shows, however, that the algorithm has much broader applicability as a method for plan improvement in general multiagent planning problems. Extensive empirical experiments in various domains illustrate the scalability of our method in both cases.

Multiply Sectioned Bayesian Networks (MSBNs) extend single-agent Bayesian networks to the setting of multi-agent probabilistic reasoning. The MSBN global propagation is conducted through inter-agent message passing, coupled with intra-agent (local) message passing at local domains. Existing LJF-based MSBN inference algorithms require repeated full-scale local propagation, which may cause bottlenecks in a non-sparse network. We propose a novel method that conducts 1) delayed inter-agent message manipulation, and 2) partial local message propagation. Analysis shows that our approach significantly reduces the amount of local computation while maintaining the correctness of MSBN global propagation.

Multi-robot task allocation is an important problem for heterogeneous mobile robots. Simultaneous allocations with which multiple tasks are being allocated concurrently tend to lead to more efficient allocations than online or single task allocations. However, the simultaneous allocation also increases the complexity in the winner determination process, especially when robots are required to collaborate in order to accomplish certain tasks. This paper presents a winner determination algorithm for the simultaneous allocation of multi-robot tasks. The complete approach layers alow-level coalition formation algorithm for solving one multi-robot task with a high-level simultaneous task allocation approach. We implement a tree-based winner determination algorithm with an iterative deepening A* (IDA*) search and show that the algorithm is able to generate the optimal task-coalition mapping in the initial round and the IDA* performs efficiently based on time and space complexities.

Although freewriting strategies are commonly taught in composition courses, there have been few empirical studies on freewriting. We address this gap by examining effects of prior writing skills (as measured by a pre-write essay), freewriting training, text-box size (1, 10, 20 lines), and repetitive writing on freewriting quality. Participants watched an agent-based vicarious learning freewriting instruction video or a control video including brief instructions on freewriting. After training, participants wrote six freewrites, two in each box size. Lesson delivery and text box size did not affect expert human ratings of the freewrites. Furthermore, participants did not benefit from writing successive freewrites regardless of their initial skill level. We describe how these results have been used to inform the design of Writing-Pal, an essay-writing intelligent tutoring system.

We revisit a framework for designing peer-based intelligent tutoring systems motivated by McCalla's ecological approach, where learning is facilitated by the previous experiences of peers with a corpus of learning objects. Prior research demonstrated the value of a proposed algorithm for modeling student learning and for selecting the most beneficial learning objects to present to new students. In this paper, we first adjust the validation of this approach to demonstrate its ability to cope with errors in assessing the learning of student peers. We then deepen the representation of learning objects to reflect the expected time to completion and demonstrate how this may lead to more effective selection of learning objects for students, and thus more effective learning. As part of our exploration of these new adjustments, we offer insights into how the size of learning object repositories may affect student learning, suggesting future extensions for the model and its validation.

Behavior-based and reactive control methods are popular choices for building fast and lightweight intelligent controllers for resource-constrained systems. Reactive methods are extremely useful in highly resource-constrained applications, but at a cost: they tend to be even more susceptible to certain types of failures than deliberative techniques. Without a planner to adapt to changes, even a small failure can result in incorrect behavior from the entire controller. In this paper, we propose extensions to behavior-based subsumption that can detect four types of failures.