Publications

The problem of deriving joint policies for a group of agents that maximize some joint reward function can be modeled as a decentralized partially observable Markov decision process (POMDP). Yet, despite the growing importance and applications of decentralized POMDP models in the multiagents arena, few algorithms have been developed for efficiently deriving joint policies for these models. This paper presents a new class of locally optimal algorithms called “Joint Equilibriumbased search for policies (JESP)”. We first describe an exhaustive version of JESP and subsequently a novel dynamic programming approach to JESP. Our complexity analysis reveals the potential for exponential speedups due to the dynamic programming approach. These theoretical results are verified via empirical comparisons of the two JESP versions with each other and with a globally optimal brute-force search algorithm. Finally, we prove piece-wise linear and convexity (PWLC) properties, thus taking steps towards developing algorithms for continuous belief states

Coordination between large teams of highly heterogeneous entities will change the way complex goals are pursued in real world environments. One approach to achieving the required coordination in such teams is to give each team member a proxy that assumes routine coordination activities on behalf of its team member. Despite that approach’s success, as we attempt to apply this first generation of proxy architecture to larger teams in more challenging environments, some limitations become clear. In this paper, we present initial efforts on the next generation of proxy architecture and Team Oriented Programming (TOP), called Machinetta. Machinetta aims to overcome the limitations of the previous generation of proxies and allow effective coordination between very large teams of highly heterogeneous agents. We describe the principles underlying the design of the Machinetta proxies and present initial results from two domains.

The Distributed Constraint Optimization Problem (DCOP) is able to model many problems in multiagent systems but existing research has not considered the issue of unreliable communication which often arises in real world applications. Limited bandwidth, interference, loss of line-of-sight are some reasons why communication fails in the real world. In this paper we show that an existing asynchronous algorithm for DCOP can be made to operate effectively in the face of message loss through the introduction of a very simple timeout mechanism for selective communication. Despite its simplicity, this mechanism is shown to dramatically reduce communication overhead while preventing deadlocks that can occur when messages are lost. Results show that the optimal solution can be guaranteed even in the presence of message loss and that algorithm performance measured in terms of time to solution degrades gracefully as message loss probability increases.

Adjustable autonomy refers to agents’ dynamically varying their own autonomy, transferring decision making control to other entities (typically human users) in key situations. Determining whether and when such transfers of control must occur is arguably the fundamental research question in adjustable autonomy. Previous work, often focused on individual agent-human interactions, has provided several different techniques to address this question. Unfortunately, domains requiring collaboration between teams of agents and humans reveals two key shortcomings of these previous techniques. First, these techniques use rigid one-shot transfers of control that can result in unacceptable coordination failures in multiagent settings. Second, they ignore costs (e.g., in terms of time delays or effects of actions) to an agent’s team due to such transfers of control. To remedy these problems, this paper presents a novel approach to adjustable autonomy, based on the notion of transfer of control strategy. A transfer of control strategy consists of a sequence of two types of actions: (i) actions to transfer decision-making control (e.g., from the agent to the user or vice versa) (ii) actions to change an agent’s pre-specified coordination constraints with others, aimed at minimizing miscoordination costs. The goal is for high quality individual decisions to be made with minimal disruption to the coordination of the team. These strategies are operationalized using Markov Decision Processes to select the optimal strategy given an uncertain environment and costs to individuals and teams. We present a detailed evaluation of the approach in the context of a real-world, deployed multi-agent system that assists a research group in daily activities.

Distributed task allocation algorithms requires a set of agents to intelligently allocate their resources to a set of tasks. The problem is often complicated by the fact that resources may be limited, the set of tasks may not be exactly known, and the set of tasks may change over time. Previous resource allocation algorithms have not been able to handle over- constrained situations, the uncertainty in the environment and/or dynamics. In this paper, we present extensions to an algorithm for distributed constraint optimization, called Adopt-SC which allows it to be applied in such real-world domains. The approach relies on maintaining a probability distribution over tasks that are potentially present. The distribution is updated with both information from local sensors and information inferred from communication between agents. We present promising results with the approach on a distributed task allocation problem consisting of a set of stationary sensors that must track a moving target. The techniques proposed in this paper are evaluated on real hardware tracking real moving targets.

Despite the signicant progress in multiagent teamwork, existing research does not address the optimality of its prescriptions nor the complexity of the teamwork problem. Without a characterization of the optimality-complexity tradeos, it is impossible to determine whether the assumptions and approximations made by a particular theory gain enough eciency to justify the losses in overall performance. To provide a tool for use by multiagent researchers in evaluating this tradeo, we present a unied framework, the COMmunicative Multiagent Team Decision Problem (COM-MTDP). The COM-MTDP model combines and extends existing multiagent theories, such as decentralized partially observable Markov decision processes and economic team theory. In addition to their generality of representation, COM-MTDPs also support the analysis of both the optimality of team performance and the computational complexity of the agents' decision problem. In analyzing complexity, we present a breakdown of the computational complexity of constructing optimal teams under various classes of problem domains, along the dimensions of observability and communication cost. In analyzing optimality, we exploit the COM-MTDP's ability to encode existing teamwork theories and models to encode two instantiations of joint intentions theory taken from the literature. Furthermore, the COM-MTDP model provides a basis for the development of novel team coordination algorithms. We derive a domain-independent criterion for optimal communication and provide a comparative analysis of the two joint intentions instantiations with respect to this optimal policy. We have implemented a reusable, domain-independent software package based on COM-MTDPs to analyze teamwork coordination strategies, and we demonstrate its use by encoding and evaluating the two joint intentions strategies within an example domain.

Through adjustable autonomy (AA), an agent can dynamically vary the degree to which it acts autonomously, allowing it to exploit human abilities to improve its performance, but without becoming overly dependent and intrusive. AA research is critical for successful deployment of agents to support important human activities. While most previous work has focused on individual agent-human interactions, this paper focuses on teams of agents operating in real-world human organizations, as well as the novel AA coordination challenge that arises when one agent’s inaction while waiting for a human response can lead to potential miscoordination. Our multi-agent AA framework, based on Markov decision processes, provides an adaptive model of users that reasons about the uncertainty, costs, and constraints of decisions. Our approach to AA has proven essential to the success of our deployed Electric Elves system that assists our research group in rescheduling meetings, choosing presenters, tracking people’s locations, and ordering meals.

The operation of a human organization requires dozens of everyday tasks to ensure coherence in organizational activities, to monitor the status of such activities, to gather information relevant to the organization, to keep everyone in the organization informed, etc. Teams of software agents can aid humans in accomplishing these tasks, facilitating the organization’s coherent functioning and rapid response to crises, while reducing the burden on humans. Based on this vision, this paper reports on Electric Elves, a system that has been operational, 24/7, at our research institute since June 1, 2000. Tied to individual user workstations, fax machines, voice, mobile devices such as cell phones and palm pilots, Electric Elves has assisted us in routine tasks, such as rescheduling meetings, selecting presenters for research meetings, tracking people’s locations, organizing lunch meetings, etc. We discuss the underlying AI technologies that led to the success of Electric Elves, including technologies devoted to agenthuman interactions, agent coordination, accessing multiple heterogeneous information sources, dynamic assignment of organizational tasks, and deriving information about organization members. We also report the results of deploying Electric Elves in our own research organization.

While NASA is increasingly interested in multi-platform space missions, controlling such platforms via timed command sequences -- the current favored operations technique -- is unfortunately very difficult, and a key source of this complexity involves resolving conflicts to coordinate multiple spacecraft plans. We propose distributed constraint satisfaction (DCSP) techniques for automated coordination and conflict resolution of such multi-spacecraft plans. We introduce novel value ordering heuristics in DCSP to significantly improve the rate of conflict resolution convergence to meet the efficiency needs of multispacecraft missions. In addition, we introduce distributed POMDP (partially observable markov decision process) based techniques for DCSP convergence analysis, which facilitates automated selection of the most appropriate DCSP strategy for a given situation, and points the way to a new generation of analytical tools for analysis of DCSP and multi-agent systems in general.

While NASA is increasingly interested in multi-platform space missions, controlling such platforms via timed command sequences -- the current favored operations technique -- is unfortunately very difficult, and a key source of this complexity involves resolving conflicts to coordinate multiple spacecraft plans. We propose distributed constraint satisfaction (DCSP) techniques for automated coordination and conflict resolution of such multi-spacecraft plans. We introduce novel value ordering heuristics in DCSP to significantly improve the rate of conflict resolution convergence to meet the efficiency needs of multispacecraft missions. In addition, we introduce distributed POMDP (partially observable markov decision process) based techniques for DCSP convergence analysis, which facilitates automated selection of the most appropriate DCSP strategy for a given situation, and points the way to a new generation of analytical tools for analysis of DCSP and multi-agent systems in general.

Recent years are seeing an increasing need for on-line monitoring of teams of cooperating agents, e.g., for visualization, or performance tracking. However, in monitoring deployed teams, we often cannot rely on the agents to always communicate their state to the monitoring system. This paper presents a non-intrusive approach to monitoring by overhearing, where the monitored team's state is inferred (via plan-recognition) from team-members' routine communications, ex- changed as part of their coordinated task execution, and observed (overheard) by the monitoring system. Key challenges in this approach include the demanding run-time requirements of monitoring, the scarceness of observations (increasing monitoring uncertainty), and the need to scale-up monitoring to address potentially large teams. To address these, we present a set of complementary novel techniques, exploiting knowledge of the social structures and procedures in the monitored team: (i) an ecient probabilistic plan-recognition algorithm, well-suited for processing communications as observations; (ii) an approach to exploiting knowledge of the team's social behavior to predict future observations during execution (reducing monitoring uncertainty); and (iii) monitoring algorithms that trade expressivity for scalability, representing only certain useful monitoring hypotheses, but allowing for any number of agents and their dierent activities to be represented in a single coherent entity. We present an empirical evaluation of these techniques, in combination and apart, in monitoring a deployed team of agents, running on machines physically distributed across the country, and engaged in complex, dynamic task execution. We also compare the performance of these techniques to human expert and novice monitors, and show that the techniques presented are capable of monitoring at human-expert levels, despite the diculty of the task.

Despite the significant progress in multiagent teamwork, existing research does not address the optimality of its prescriptions nor the complexity of the teamwork problem. Thus, we cannot determine whether the assumptions and approximations made by a particular theory gain enough efficiency to justify the losses in overall performance. To provide a tool for evaluating this tradeoff, we present a unified framework, the COMmunicative Multiagent Team Decision Problem (COM-MTDP) model, which is general enough to subsume many existing models of multiagent systems. We analyze use the COM-MTDP model to provide a breakdown of the computational complexity of constructing optimal teams under problem domains divided along the dimensions of observability and communication cost. We then exploit the COM-MTDP’s ability to encode existing teamwork theories and models to encode two instantiations of joint intentions theory, including STEAM. We then derive a domain-independent criterion for optimal communication and provide a comparative analysis of the two joint intentions instantiations. We have implemented a reusable, domain-independent software package based COM-MTDPs to analyze teamwork coordination strategies, and we demonstrate its use by encoding and evaluating the two joint intentions strategies within an example domain.

We consider the problem of disaster mitigation in the RoboCup Rescue Simulation Environment [3] to be a task allocation problem where the tasks arrive dynamically and can change in intensity. These tasks can be performed by ambulance teams, re brigades and police forces with the help of an ambulance center, a re station and a police oce. However the agents don't get automatically notied of the tasks as soon as they arrive and hence it is necessary for the agents to explore the simulated world to discover new tasks and to notify other agents of these. In this paper we focus on the problem of task allocation. We have developed two approaches, a centralized combinatorial auction mechanism demonstrated at Agents-2001 and a distributed method which helped our agents nish third in RoboCup-Rescue 2001. With regard to task discovery, we use a greedy search method to explore the world{ agents count the number of times they have visited each node, and attempt to visit nodes that have been visited the least number of times.

Multiagent research has made significant progress in constructing teams of distributed entities (e.g., robots, agents, embedded systems) that act autonomously in the pursuit of common goals. There now exist a variety of prescriptive theories, as well as implemented systems, that can specify good team behavior in different domains. However, each of these theories and systems addresses different aspects of the teamwork problem, and each does so in a different language. In this work, we seek to provide a unified framework that can capture all of the common aspects of the teamwork problem (e.g., heterogeneous, distributed entities, uncertain and dynamic environment), while still supporting analyses of both the optimality of team performance and the computational complexity of the agents’ decision problem. Our COMmunicative Multiagent Team Decision Problem (COM-MTDP) model provides such a framework for specifying and analyzing distributed teamwork. The COM-MTDP model is general enough to capture many existing models of multiagent systems, and we use this model to provide some comparative results of these theories. We also provide a breakdown of the computational complexity of constructing optimal teams under various classes of problem domains. We then use the COM-MTDP model to compare (both analytically and empirically) two specific coordination theories (joint intentions theory and STEAM) against optimal coordination, in terms of both performance and computational complexity.

The utility of the multi-agent team approach for coordination of distributed agents has been demonstrated in a number of large-scale systems for sensing and acting like sensor networks for real-time tracking of moving targets (Modi et al. 2001) and disaster rescue simulation domains, such as RoboCup Rescue Simulation Domain (Kitano et al. 1999; Tadokoro et al. 2000) These domains contain tasks that can be performed only by collaborative actions of the agents. Incomplete or incorrect knowledge owing to constrained sensing and uncertainty of the environment further motivate the need for these agents to explicitly work in teams. A key precursor to teamwork is team formation, the problem of how best to organize the agents into collaborating teams that perform the tasks that arise. For instance, in the disaster rescue simulation domain, injured civilians in a burning building may require teaming of two ambulances and three nearby fire-brigades to extinguish the fire and quickly rescue the civilians. If there are several such fires and injured civilians, the teams must be carefully formed to optimize performance. Our work in team formation focuses on dynamic, realtime environments, such as sensor networks (Modi et al. 2001) and RoboCup Rescue Simulation Domain (Kitano et al. 1999; Tadokoro et al. 2000). In such domains teams must be formed rapidly so tasks are performed within given deadlines, and teams must be reformed in response to the dynamic appearance or disappearance of tasks. The problems with the current team formation work for such dynamic real-time domains are two-fold: i) most team formation algorithms (Tidhar, Rao, & Sonenberg 1996; Hunsberger & Grosz 2000; Fatima & Wooldridge 2001; Horling, Benyo, & Lesser 2001; Modi et al. 2001) are static. In order to adapt to the changing environment the static algorithm would have to be run repeatedly, ii) Team formation has largely relied on experimental work, without any theoretical analysis of key properties of team formation algorithms, such as their worst-case complexity. This is especially important because of the real-time nature of the domains. In this paper we take initial steps to attack both these problems. As the tasks change and members of the team fail, the current team needs to evolve to handle the changes. In both the sensor network domain (Modi et al. 2001) and RoboCup. Rescue (Kitano et al. 1999; Tadokoro et al. 2000), each re-organization of the team requires time (e.g., fire-brigades may need to drive to a new location) and is hence expensive because of the need for quick response. Clearly, the current configuration of agents is relevant to how quickly and well they can be re-organized in the future. Each reorganization of the teams should be such that the resulting team is effective at performing the existing tasks but also flexible enough to adapt to new scenarios quickly. We refer to this reorganization of the team as ”Team Formation for Reformation”. In order to solve the “Team Formation for Reformation” problem, we present R-COM-MTDPs (Roles and Communication in a Markov Team Decision Process), a formal model based on communicating decentralized POMDPs, to address the above shortcomings. RCOM-MTDP significantly extends an earlier model called COM-MTDP (Pynadath & Tambe 2002), by making important additions of roles and agents’ local states, to more closely model current complex multiagent teams. Thus, RCOM-MTDP provides decentralized optimal policies to take up and change roles in a team (planning ahead to minimize reorganization costs), and to execute such roles. R-COM-MTDPs provide a general tool to analyze roletaking and role-executing policies in multiagent teams. We show that while generation of optimal policies in R-COMMTDPs is NEXP-complete, different communication and observability conditions significantly reduce such complexity. In this paper, we use the disaster rescue domain to motivate the “Team Formation for Reformation” problem. We present real world scenarios where such an approach would be useful and use the RoboCup Rescue Simulation Environment (Kitano et al. 1999; Tadokoro et al. 2000) to explain the working of our model.

Team formation, i.e., allocating agents to roles within a team or subteams of a team, and the reorganization of a team upon team member failure or arrival of new tasks are critical aspects of teamwork. They are very important issues in RoboCupRescue where many tasks need to be done jointly. While empirical comparisons (e.g., in a competition setting as in RoboCup) are useful, we need a quantitative analysis beyond the competition | to understand the strengths and limitations of dierent approaches, and their tradeos as we scale up the domain or change domain properties. To this end, we need to provide complexityoptimality tradeos, which have been lacking not only in RoboCup but in the multiagent eld in general. To alleviate these diculties, this paper presents R-COM-MTDP, a formal model based on decentralized communicating POMDPs, where agents explicitly take on and change roles to (re)form teams. R-COM-MTDP signicantly extends an earlier COM-MTDP model, by introducing roles and local states to better model domains like RoboCupRescue where agents can take on dierent roles and each agent has a local state consisting of the ob jects in its vicinity. R-COM-MTDP tells us where the problem is highly intractable (NEXP-complete) and where it can be tractable (P-complete), and thus understand where algorithms may need to tradeo optimality and where they could strive for near optimal behaviors. R-COM-MTDP model could enable comparison of various team formation and reformation strategies | including the strategies used by our own teams that came in the top three in 2001 | in the RoboCup Rescue domain and beyond.

Adjustable autonomy refers to entities dynamically varying their own autonomy, transferring decision-making control to other entities (typically agents transferring control to human users) in key situations. Determining whether and when such transfers-of-control should occur is arguably the fundamental research problem in adjustable autonomy. Previous work has investigated various approaches to addressing this problem but has often focused on individual agent-human interactions. Unfortunately, domains requiring collaboration between teams of agents and humans reveal two key shortcomings of these previous approaches. First, these approaches use rigid one-shot transfers of control that can result in unacceptable coordination failures in multiagent settings. Second, they ignore costs (e.g., in terms of time delays or eects on actions) to an agent's team due to such transfers-ofcontrol. To remedy these problems, this article presents a novel approach to adjustable autonomy, based on the notion of a transfer-of-control strategy. A transfer-of-control strategy consists of a conditional sequence of two types of actions: (i) actions to transfer decisionmaking control (e.g., from an agent to a user or vice versa) and (ii) actions to change an agent's pre-specied coordination constraints with team members, aimed at minimizing miscoordination costs. The goal is for high-quality individual decisions to be made with minimal disruption to the coordination of the team. We present a mathematical model of transfer-of-control strategies. The model guides and informs the operationalization of the strategies using Markov Decision Processes, which select an optimal strategy, given an uncertain environment and costs to the individuals and teams. The approach has been carefully evaluated, including via its use in a real-world, deployed multi-agent system that assists a research group in its daily activities.

Adjustable autonomy refers to agents' dynamically varying their own autonomy, transferring decision making control to other entities (typically human users) in key situations. Determining whether and when such transfer of control must occur is arguably the fundamental research question in adjustable autonomy. Practical systems have made significant in-roads in answering this question and in providing high-level guidelines for transfer of control decisions. For instance, [11] report that Markov decision processes were successfully used in transfer of control decisions in a real-world multiagent system, but that use of C4.5 led to failures. Yet, an underlying theory of transfer of control, that would explain such successes or failures is missing. To take a step in building this theory, we introduce the notion of a transfer-of-control strategy, which potentially involves several transfer of control actions. A mathematical model based on this notion allows both analysis of previously reported implementations and guidance for the design of new implementations. The practical benefits of this model are illustrated in a dramatic simplification of an existing adjustable autonomy system.

With the proliferation of software agents and smart hardware devices there is a growing realization that large-scale problems can be addressed by integration of such stand-alone systems. This has led to an increasing interest in integration infrastructures that enable a heterogeneous variety of agents and humans to work together. In our work, this infrastructure has taken the form of an integration architecture called Teamcore. We have deployed Teamcore to facilitate/enable collaboration between different agents and humans that differ in their capabilities, preferences, the level of autonomy they are willing to grant the integration architecture, their information requirements and performance. This paper first provides a brief overview of the Teamcore architecture and its current applications. The paper then discusses some of the research challenges we have focused on. In particular, the Teamcore architecture is based on general purpose teamwork coordination capabilities. However, it is important for this architecture to adapt to meet the needs and requirements of specific individuals. We describe the different techniques of architectural adaptation, and present initial experimental results.