Publications

2003
V. Lesser, C. Ortiz, and Milind Tambe. 2003. Distributed sensor nets: A multiagent perspective . Kluwer academic.Abstract
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.
2003_18_teamcore_tambe_book.jpg
Paul Scerri, Johnson L., D. V. Pynadath, P. S. Rosenbloom, M. Si, Nathan Schurr, and Milind Tambe. 2003. “Getting robots, agents and people to cooperate: An initial study .” In AAAI Spring Symposium.Abstract
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.
2003_9_teamcore_rap.pdf
Ranjit Nair, Milind Tambe, and S. Marsella. 2003. “Integrating BDI approaches with POMDPs: The case of team-oriented programs .” In AAAI Spring Symposium.Abstract
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.
2003_5_teamcore_nair_spring_symp.pdf
Ranjit Nair, Milind Tambe, and Stacy Marsella. 2003. “Integrating Belief-Desire-Intention Approaches with POMDPs: The Case of Team-Oriented Programs .” In AAAI Spring Symposium on Logical Formalisms for Commonsense Reasoning.Abstract
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.
2003_19_teamcore_nair_tambe_marsella.pdf
H. Jung and Milind Tambe. 2003. “Performance models for large-scale multiagent systems: Using Distributed POMDP building blocks .” In Second International Joint conference on agents and multiagent systems (AAMAS).Abstract
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.
2003_14_teamcore_jungh_aamas03.pdf
Paul Scerri, Johnson L., D. V. Pynadath, P. S. Rosenbloom, M. Si, Nathan Schurr, and Milind Tambe. 2003. “A prototype infrastructure for distributed robot, agent, person teams .” In Second International Joint conference on agents and multiagent systems (AAMAS).Abstract
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.
2003_7_teamcore_rap_aamas03.pdf
Ranjit Nair, Milind Tambe, and S. Marsella. 2003. “Role allocation and reallocation in multiagent teams: Towards a practical analysis .” In Second International Joint conference on agents and multiagent systems (AAMAS).Abstract
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.
2003_3_teamcore_nair_aamas03.pdf
Ranjit Nair, Milind Tambe, and S. Marsella. 2003. “The role of emotions in multiagent teamwork .” In Who needs emotions: The brain meets the machine, edited by J. Fellous and M. Arbib. MIT Press.Abstract
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.
2003_4_teamcore_nair_emotions.pdf
Ranjit Nair, Milind Tambe, Makoto Yokoo, D. V. Pynadath, and S. Marsella. 2003. “Taming Decentralized POMDPs: Towards efficient policy computation for multiagent settings .” In International Joint conference on Artificial Intelligence (IJCAI).Abstract
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
2003_2_teamcore_nair_ijcai03.pdf
Paul Scerri, David V. Pynadath, Nathan Schurr, Alessandro Farinelli, Sudeep Gandhe, and Milind Tambe. 2003. “Team Oriented Programming and Proxy Agents: The Next Generation .” In Lecture notes in computer science, Proceedings of the workshop on Programming multiagent systems, Springer.Abstract
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.
2003_17_teamcore_10_1_1_69.9607.pdf
Pragnesh J. Modi, Syed M. Ali, Rishi Goel, and Milind Tambe. 2003. “Distributed Constraint Reasoning under Unreliable Communication.” In International workshop on distributed constraint reasoning DCR-03.Abstract
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.
2003_1_teamcore_modi_dcr03.pdf
2002
Milind Tambe, Paul Scerri, and D. V. Pynadath. 2002. “Adjustable autonomy for the real world .” In AAAI Spring Symposium on Safe learning agents.Abstract
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.
2002_9_teamcore_ss02.pdf
Karen Myers and Milind Tambe. 2002. “Agents, theories, architectures and languages (ATAL-01).” In Springer lecture notes in Artificial Intelligence LNAI 2333.
Paul Scerri, Pragnesh Jay Modi, Wei-Min Shen, and Milind Tambe. 2002. “Applying Constraint Reasoning to Real-world Distributed Task Allocation .” In Autonomous Agents and Multi-Agent Systems Workshop on Distributed Constraint Reasoning.Abstract
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.
2002_15_teamcore_scerri_workshop2002.pdf
D. V. Pynadath and Milind Tambe. 2002. “The communicative multiagent team decision problem: Analyzing teamwork theories and models .” Journal of AI Research (JAIR), 16, Pp. 389-423.Abstract
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.
2002_14_teamcore_jair_compd.pdf
D. V. Pynadath and Milind Tambe. 2002. “Electric Elves: Adjustable autonomy in real-world multiagent environments .” In Socially Intelligent Agents creating relationships with computers and Robots. Kluwer Academic Publishers.Abstract
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.
2002_12_teamcore_pynadath_elves_aa.pdf
H. Chalupsky, Y. Gil, Craig Knoblock, K. Lerman, J. Oh, D. V. Pynadath, T. Russ, and Milind Tambe. 2002. “Electric Elves: Agent Technology for Supporting Human Organizations (longer version of IAAI'01 paper).” AI Magazine.Abstract
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.
2002_6_teamcore_aimag_elves.pdf
Hyuckchul Jung, Milind Tambe, Anthony Barrett, and Bradley Clement. 2002. “Enabling Efficient Conflict Resolution in Multiple Spacecraft Missions via DCSP .” In International NASA Workshop on Planning and Scheduling for Space.Abstract
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.
2002_16_teamcore_nasa_ws02.pdf
H. Jung, Milind Tambe, A. Barrett, and B. Clement. 2002. “Enabling efficient conflict resolution in multiple spacecraft missions via DCSP .” In NASA workshop on planning and scheduling.Abstract
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.
2002_5_teamcore_jung_nasa.pdf
Gal Kaminka, D. V. Pynadath, and Milind Tambe. 2002. “Monitoring teams by overhearing: A multiagent plan-recognition approach .” Journal of AI Research (JAIR, 17, Pp. 83-135.Abstract
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.
2002_4_teamcore_jair_overhearing.pdf

Pages