Publications

Although algorithms for Distributed Constraint Optimization Problems (DCOPs) have emerged as a key technique for distributed reasoning, their application faces significant hurdles in many multiagent domains due to their inefficiency. Preprocessing techniques have been successfully used to speed up algorithms for centralized constraint satisfaction problems. This paper introduces a framework of very different preprocessing techniques that speed up ADOPT, an asynchronous optimal DCOP algorithm that significantly outperforms competing DCOP algorithms by more than one order of magnitude.

Distributed Constraint Optimization (DCOP) is an elegant formalism relevant to many areas in multiagent systems, yet complete algorithms have not been pursued for real world applications due to perceived complexity. To capably capture a rich class of complex problem domains, we introduce the Distributed Multi-Event Scheduling (DiMES) framework and design congruent DCOP formulations with binary constraints which are proven to yield the optimal solution. To approach real-world efficiency requirements, we obtain immense speedups by improving communication structure and precomputing best case bounds. Heuristics for generating better communication structures and calculating bound in a distributed manner are provided and tested on systematically developed domains for meeting scheduling and sensor networks, exemplifying the viability of complete algorithms.

Despite the recent advances in distributed MDP frameworks for reasoning about multiagent teams, these frameworks mostly do not reason about resource constraints, a crucial issue in teams. To address this shortcoming, we provide four key contributions. First, we introduce EMTDP, a distributed MDP framework where agents must not only maximize expected team reward, but must simultaneously bound expected resource consumption. While there exist single-agent constrained MDP (CMDP) frameworks that reason about resource constraints, EMTDP is not just a CMDP with multiple agents. Instead, EMTDP must resolve the miscoordination that arises due to policy randomization. Thus, our second contribution is an algorithm for EMTDP transformation, so that resulting policies, even if randomized, avoid such miscoordination. Third, we prove equivalence of different techniques of EMTDP transformation. Finally, we present solution algorithms for these EMTDPs and show through experiments their efficiency in solving application-sized problems.

Multi-agent teamwork is critical in a large number of agent applications, including training, education, virtual enterprises and collective robotics. The complex interactions of agents in a team as well as with other agents make it extremely difficult for human developers to understand and analyze agent-team behavior. It has thus become increasingly important to develop tools that can help humans analyze, evaluate, and understand team behaviors. However, the problem of automated team analysis is largely unaddressed in previous work. In this article, we identify several key constraints faced by team analysts. Most fundamentally, multiple types of models of team behavior are necessary to analyze different granularities of team events, including agent actions, interactions, and global performance. In addition, effective ways of presenting the analysis to humans is critical and the presentation techniques depend on the model being presented. Finally, analysis should be independent of underlying team architecture and implementation. We also demonstrate an approach to addressing these constraints by building an automated team analyst called ISAAC for post-hoc, off-line agent-team analysis. ISAAC acquires multiple, heterogeneous team models via machine learning over teams’ external behavior traces, where the specific learning techniques are tailored to the particular model learned. Additionally, ISAAC employs multiple presentation techniques that can aid human understanding of the analyses. ISAAC also provides feedback on team improvement in two novel ways: (i) It supports principled ”whatif” reasoning about possible agent improvements; (ii) It allows the user to compare different teams based on their patterns of interactions. This paper presents ISAAC’s general conceptual framework, motivating its design, as well as its concrete application in two domains: (i) RoboCup Soccer; (ii) software agent teams participating in a simulated evacuation scenario. In the RoboCup domain, ISAAC was used prior to and during the RoboCup’99 tournament, and was awarded the RoboCup Scientific Challenge Award. In the evacuation domain, ISAAC was used to analyze patterns of message exchanges among software agents, illustrating the generality of ISAAC’s techniques. We present detailed algorithms and experimental results from ISAAC’s application.

The successful integration and acceptance of many multi-agent systems into daily lives crucially depends on the ability to develop effective policies for adjustable autonomy. Adjustable autonomy encompasses the strategies by which an agent selects the appropriate entity (itself, a human user, or another agent) to make a decision at key moments when an action is required. We present two formulations that address this issue: user-based and agent-based autonomy. Furthermore, we discuss the current and future implications on systems composed of personal assistant agents, where autonomy issues are of vital interest.

Researchers building multi-agent algorithms typically work with problems abstracted away from real applications. The abstracted problem instances allow systematic and detailed investigations of new algorithms. However, a key question is how to apply algorithm, developed on an abstract problem, in a real application. In this paper, we report on what was required to apply a particular distributed resource allocation algorithm developed for an abstract coordination problem in a real hardware application. A probabilistic representation of resources and tasks was used to deal with uncertainty and dynamics and local reasoning was used to deal with delays in the distributed resource allocation algorithm. The probabilistic representation and local reasoning enabled the use of the multi-agent algorithm which, in turn, improved the overall performance of the system.

We present a new polynomial-space algorithm, called Adopt, for distributed constraint optimization (DCOP). DCOP is able to model a large class of collaboration problems in multi-agent systems where a solution within given quality parameters must be found. Existing methods for DCOP are not able to provide theoretical guarantees on global solution quality while operating both efficiently and asynchronously. Adopt is guaranteed to find an optimal solution, or a solution within a user-specified distance from the optimal, while allowing agents to execute asynchronously and in parallel. Adopt obtains these properties via a distributed search algorithm with several novel characteristics including the ability for each agent to make local decisions based on currently available information and without necessarily having global certainty. Theoretical analysis shows that Adopt provides provable quality guarantees, while experimental results show that Adopt is significantly more efficient than synchronous methods. The speedups are shown to be partly due to the novel search strategy employed and partly due to the asynchrony of the algorithm.

Agent integration architectures enable a heterogeneous, distributed set of agents to work together to address problems of greater complexity than those addressed by the individual agents themselves. Unfortunately, integrating software agents and humans to perform real-world tasks in a large-scale system remains difficult, especially due to three main challenges: ensuring robust execution in the face of a dynamic environment, providing abstract task specifications without all the low-level coordination details, and finding appropriate agents for inclusion in the overall system. To address these challenges, our Teamcore project provides the integration architecture with general-purpose teamwork coordination capabilities. We make each agent team-ready by providing it with a proxy capable of general teamwork reasoning. Thus, a key novelty and strength of our framework is that powerful teamwork capabilities are built into its foundations by providing the proxies themselves with a teamwork model. Given this teamwork model, the Teamcore proxies addresses the first agent integration challenge, robust execution, by automatically generating the required coordination actions for the agents they represent. We can also exploit the proxies’ reusable general teamwork knowledge to address the second agent integration challenge. Through team-oriented programming, a developer specifies a hierarchical organization and its goals and plans, abstracting away from coordination details. Finally, KARMA, our Knowledgeable Agent Resources Manager Assistant, can aid the developer in conquering the third agent integration challenge by locating agents that match the specified organization’s requirements. Our integration architecture enables teamwork among agents with no coordination capabilities, and it establishes and automates consistent teamwork among agents with some coordination capabilities. Thus, team-oriented programming provides a level of abstraction that can be used on top of previous approaches to agent-oriented programming. We illustrate how the Teamcore architecture successfully addressed the challenges of agent integration in two application domains: simulated rehearsal of a military evacuation mission and facilitation of human collaboration.

This paper presents an initial formalization of teamwork in multi-agent domains. Although analyses of teamwork already exist in the literature of multi-agent systems, almost no work has dealt with the problem of teams that comprise self-interested agents. The main contribution of this work is that it concentrates specifically on such teams of self interested agents. Teams of this kind are common in multi-agent systems as they model the implicit competition between team members that often arises within a team.

Given a large group of cooperative agents, selecting the right coordination or conflict resolution strategy can have a significant impact on their performance (e.g., speed of convergence). While performance models of such coordination or conflict resolution strategies could aid in selecting the right strategy for a given domain, such models remain largely uninvestigated in the multiagent literature. This paper takes a step towards applying the recently emerging distributed POMDP (partially observable markov decision process) frameworks, such as the MTDP (markov team decision process) in service of creating such performance models. To address issues of scale-up, we use small-scale models, called building blocks that represent the local interaction among a small group of agents. We discuss several ways to combine building blocks for performance prediction of a larger-scale multiagent system. Our approach is presented in the context of DCSP (distributed constraint satisfaction problem), where we are able to predict the performance of five different DCSP strategies in different domain settings by modeling and combining building blocks. Our approach points the way to new tools based on building blocks for performance analysis in multiagent systems.

Distributed, collaborative agents are promising to play an important role in large-scale multiagent applications, such as distributed sensors and distributed spacecraft. Since no single agent can have complete global knowledge in such large scale applications, conflicts are inevitable even among collaborative agents over shared resources, plans, or tasks. Fast conflict resolution techniques are required in many multiagent systems under soft or hard time constraints. In resolving conflicts, we focus on the approaches based on DCSP (distributed constraint satisfaction problems), a major paradigm in multiagent conflict resolution. We aim to speed up conflict resolution convergence via developing efficient DCSP strategies. We focus on multiagent systems characterized by agents that are collaborative, homogeneous, arranged in regular networks, and relying on local communication (found in many multiagent applications). This thesis provides the followings major contributions. First, we develop novel DCSP strategies that significantly speed up conflict resolution convergence. The novel strategies are based on the extra communication of local information between neighboring agents. We formalize a set of DCSP strategies which exploit the extra communication: in selecting a new choice of actions, plans, or resources to resolve conflicts, each agent takes into account how much flexibility is given to neighboring agents. Second, we provide a new run-time model for performance measurement of DCSP strategies since a popular existing DCSP performance metric does not consider the extra communication overhead. The run-time model enables us to evaluate the strategy performance in various computing and networking environments. Third, the analysis of message processing and communication overhead of the novel strategies shows that such overhead caused by the novel strategy is not overwhelming. Thus, despite extra communication, the novel strategies indeed show big speedups in a significant range of problems (particularly for harder problems). Fourth, we provide categorization of problem settings with big speedups by the novel strategies Finally, to select the right strategy in a given domain, we develop performance modeling techniques based on distributed POMDP (Partially Observable Markov Decision Process) based model where scalability issue is addressed with a new decomposition technique.

To coordinate effectively, multiple agents must reason and communicate about the interactions between their individual local decisions. Distributed planning, distributed scheduling, distributed resource allocation and distributed task allocation are some examples of multiagent problems where such reasoning is required. In order to represent these types of automated reasoning problems, researchers in Multiagent Systems have proposed distributed constraints as a key paradigm. Previous research in Artificial Intelligence and Constraint Programming has shown that constraints are a convenient yet powerful way to represent automated reasoning problems. This dissertation advances the state-of-the-art in Multiagent Systems and Constraint Programming through three key innovations. First, this dissertation introduces a novel algorithm for Distributed Constraint Optimization Problems (DCOP). DCOP significantly generalizes existing satisfaction-based constraint representations to allow optimization. We present Adopt, the first algorithm for DCOP that allows asynchronous concurrent execution and is guaranteed to terminate with the globally optimal solution. The key idea is to perform systematic distributed optimization based on conservative solution quality estimates rather than exact knowledge of global solution quality. This method is empirically shown to yield orders of magnitude speedups over existing synchronous methods and is shown to be robust to lost messages. Second, this dissertation introduces bounded-error approximation as a flexible method whereby agents can find global solutions that may not be optimal but are guaranteed to be within a given distance from optimal. This method is useful for time-limited domains because it decreases solution time and communication overhead. Bounded-error approximation is a significant departure from existing incomplete local methods, which rely exclusively on local information to obtain a decrease in solution time but at the cost of abandoning all theoretical guarantees on solution quality. Third, this dissertation presents generalized mapping strategies that allow a significant class of distributed resource allocation problem to be automatically represented via distributed constraints. These mapping strategies are signficant because they illustrate the utility of the distributed constraint representation. These mapping strategies are useful because they provide multiagent researchers with a general, reusable methodology for understanding, representing and solving their own distributed resource allocation problems. Our theoretical results show the correctness of the mappings.

Distributed Sensor Networks is the first book of its kind to examine solutions to this problem using ideas taken from the field of multiagent systems. The field of multiagent systems has itself seen an exponential growth in the past decade, and has developed a variety of techniques for distributed resource allocation.
Distributed Sensor Networks contains contributions from leading, international researchers describing a variety of approaches to this problem based on examples of implemented systems taken from a common distributed sensor network application; each approach is motivated, demonstrated and tested by way of a common challenge problem. The book focuses on both practical systems and their theoretical analysis, and is divided into three parts: the first part describes the common sensor network challenge problem; the second part explains the different technical approaches to the common challenge problem; and the third part provides results on the formal analysis of a number of approaches taken to address the challenge problem.

Combining the unique capabilities of robots, agents and people (RAPs) promises to improve the safety, efficiency, reliability and cost at which some goals can be achieved, while allowing the achievement of other goals not previously achievable. Despite their heterogeneity, and indeed, because of their heterogeneity, our key hypothesis is that in order for RAPs to work together effectively, they must work as a team: they should be aware of the overall goals of the team, and coordinate their activities with their fellow team members in order to further the team’s goals. This poses a challenge, since different RAP entities may have differing social abilities and hence differing abilities to coordinate with their teammates. To construct such RAP teams, we make the RAPs “team ready” by providing each of them with teamwork-enabled proxies. While proxy-based architectures have been explored earlier for flexible multiagent teamwork, their application to RAP teams exposes two weaknesses. To address the problems with existing role allocation algorithms for RAP teams operating in dynamic environments, we provide a new approach for highly flexible role allocation and reallocation. Second, we enrich the communication between RAPs and between a RAP and its proxy, to improve teamwork flexibility while limiting the number of messages exchanged. This paper discusses the proxy based architecture and our initial attempts at developing algorithms that address the problems that emerge when the RAP teams are used in complex domains.

Integrating approaches based on belief-desire-intentions (BDI) logics with the more recent developments of distributed POMDPs is today a fundamental challenge in the multiagent systems arena. One common suggestion for such an integration is to use stochastic models (POMDPs) for generating agent behaviors, while using the BDI components for monitoring and creating explanations. We propose a completely inverse approach, where the BDI components are used to generate agent behaviors, and distributed POMDPs are used in an analysis mode. In particular, we focus on teamoriented programs for tasking multiagent teams, where the team-oriented programs specify hierarchies of team plans that the team and its subteams must adopt as their joint intentions. However, given a limited number of agents, finding a good way to allocate them to different teams and subteams to execute such a team-oriented program is a difficult challenge We use distributed POMDPs to analyze different allocations of agents within a team-oriented program, and to suggest improvements to the program. The key innovation is to use the distributed POMDP analysis not as a black box, but as a glass box, offering insights into why particular allocations lead to good or bad outcomes. These insights help to prune the search space of different allocations, offering significant speedups in the search. We present preliminary experimental results to illustrate our methodology.

Integrating approaches based on belief-desire-intentions (BDI) logics with the more recent developments of distributed POMDPs is today a fundamental challenge in the multiagent systems arena. One common suggestion for such an integration is to use stochastic models (POMDPs) for generating agent behaviors, while using the BDI components for monitoring and creating explanations. We propose a completely inverse approach, where the BDI components are used to generate agent behaviors, and distributed POMDPs are used in an analysis mode. In particular, we focus on teamoriented programs for tasking multiagent teams, where the team-oriented programs specify hierarchies of team plans that the team and its subteams must adopt as their joint intentions. However, given a limited number of agents, finding a good way to allocate them to different teams and subteams to execute such a team-oriented program is a difficult challenge We use distributed POMDPs to analyze different allocations of agents within a team-oriented program, and to suggest improvements to the program. The key innovation is to use the distributed POMDP analysis not as a black box, but as a glass box, offering insights into why particular allocations lead to good or bad outcomes. These insights help to prune the search space of different allocations, offering significant speedups in the search. We present preliminary experimental results to illustrate our methodology.

Given a large group of cooperative agents, selecting the right coordination or conflict resolution strategy can have a significant impact on their performance (e.g., speed of convergence). While performance models of such coordination or conflict resolution strategies could aid in selecting the right strategy for a given domain, such models remain largely uninvestigated in the multiagent literature. This paper takes a step towards applying the recently emerging distributed POMDP (partially observable Markov decision process) frameworks, such as MTDP (Markov team decision process), in service of creating such performance models. To address issues of scale-up, we use small-scale models, called building blocks that represent the local interaction among a small group of agents. We discuss several ways to combine building blocks for performance prediction of a larger-scale multiagent system. We present our approach in the context of DCSPs (distributed constraint satisfaction problems), where we first show that there is a large bank of conflict resolution strategies and no strategy dominates all others across different domains. By modeling and combining building blocks, we are able to predict the performance of five different DCSP strategies for four different domain settings, for a large-scale multiagent system. Our approach thus points the way to new tools for strategy analysis and performance modeling in multiagent systems in general.

Effective coordination of robots, agents and people promises to improve the safety, robustness and quality with which shared goals are achieved by harnessing the highly heterogeneous entities’ diverse capabilities. Proxy-based integration architectures are emerging as a standard method for coordinating teams of heterogeneous entities. Such architectures are designed to meet imposing challenges such as ensuring that the diverse capabilities of the group members are effectively utilized, avoiding miscoordination in a noisy, uncertain environment and reacting flexibly to changes in the environment. However, we contend that previous architectures have gone too far in taking coordination responsibility away from entities and giving it to proxies. Our goal is to create a proxy-based integration infrastructure where there is a beneficial symbiotic relationship between the proxies and the team members. By leveraging the coordination abilities of both proxies and socially capable team members the quality of the coordination can be improved. We present two key new ideas to achieve this goal. First, coordination tasks are represented as explicit roles, hence the responsibilities not the actions are specified, thus allowing the team to leverage the coordination skills of the most capable team members. Second, building on the first idea, we have developed a novel role allocation and reallocation algorithm. These ideas have been realized in a prototype software proxy architecture and used to create heterogeneous teams for an urban disaster recovery domain. Using the rescue domain as a testbed, we have experimented with the role allocation algorithm and observed results to support the hypothesis that leveraging the coordination capabilities of people can help the performance of the team.

Despite the success of the BDI approach to agent teamwork, initial role allocation (i.e. deciding which agents to allocate to key roles in the team) and role reallocation upon failure remain open challenges. What remain missing are analysis techniques to aid human developers in quantitatively comparing different initial role allocations and competing role reallocation algorithms. To remedy this problem, this paper makes three key contributions. First, the paper introduces RMTDP (Role-based Multiagent Team Decision Problem), an extension to MTDP [9], for quantitative evaluations of role allocation and reallocation approaches. Second, the paper illustrates an RMTDP-based methodology for not only comparing two competing algorithms for role reallocation, but also for identifying the types of domains where each algorithm is suboptimal, how much each algorithm can be improved and at what computational cost (complexity). Such algorithmic improvements are identified via a new automated procedure that generates a family of locally optimal policies for comparative evaluations. Third, since there are combinatorially many initial role allocations, evaluating each in RMTDP to identify the best is extremely difficult. Therefore, we introduce methods to exploit task decompositions among subteams to significantly prune the search space of initial role allocations. We present experimental results from two distinct domains.

Emotions play a significant role in human teamwork. However, despite the significant progress in multiagent teamwork, as well as progress in computational models of emotions, there have been very few investigations of the role of emotions in multiagent teamwork. This chapter attempts a first step towards addressing this shortcoming. It provides a short survey of the state of the art in multiagent teamwork and in computational models of emotions. It considers three cases of teamwork, in particular, teams of simulated humans, agent-human teams and pure agent teams, and examine the effects of introducing emotions in each. Finally, it also provides preliminary experimental results illustrating the impact of emotions on multiagent teamwork.