Publications

2005
Nathan Schurr, Janusz Marecki, Milind Tambe, J. P. Lewis, and N. Kasinadhuni. 3/21/2005. “The Future of Disaster Response: Humans Working with Multiagent Teams using DEFACTO .” In AAAI Spring Symposium on Homeland Security. Stanford, CA.Abstract
When addressing terrorist threats we must give special attention to both prevention and disaster response. Enabling effective interactions between agent teams and humans for disaster response is a critical area of research, with encouraging progress in the past few years. However, previous work suffers from two key limitations: (i) limited human situational awareness, reducing human effectiveness in directing agent teams and (ii) the agent team’s rigid interaction strategies that limit team performance. This paper focuses on a novel disaster response software prototype, called DEFACTO (Demonstrating Effective Flexible Agent Coordination of Teams through Omnipresence). DEFACTO is based on a software proxy architecture and 3D visualization system, which addresses the two limitations described above. First, the 3D visualization interface enables human virtual omnipresence in the environment, improving human situational awareness and ability to assist agents. Second, generalizing past work on adjustable autonomy, the agent team chooses among a variety of “team-level” interaction strategies, even excluding humans from the loop in extreme circumstances.
2005_16_teamcore_ss105schurrn.pdf
3/21/2005. “Optimize My Schedule but Keep It Flexible: Distributed Multi-Criteria Coordination for Personal Assistants .” In AAAI Spring Symposium on Persistent Assistants: Living and Working with AI. Menlo Park, CA.Abstract
Research projects have begun focusing on deploying personal assistant agents to coordinate users in such diverse environments as offices, distributed manufacturing or design centers, and in support of first responders for emergencies. In such environments, distributed constraint optimization (DCOP) has emerged as a key technology for multiple collaborative assistants to coordinate with each other. Unfortunately, while previous work in DCOP only focuses on coordination in service of optimizing a single global team objective, personal assistants often require satisfying additional individual userspecified criteria. This paper provides a novel DCOP algorithm that enables personal assistants to engage in such multicriteria coordination while maintaining the privacy of their additional criteria. It uses n-ary NOGOODS implemented as private variables to achieve this. In addition, we’ve developed an algorithm that reveals only the individual criteria of a link and can speed up performance for certain problem structures. The key idea in this algorithm is that interleaving the criteria searches — rather than sequentially attempting to satisfy the criteria — improves efficiency by mutually constraining the distributed search for solutions. These ideas are realized in the form of private-g and public-g Multi-criteria ADOPT, built on top of ADOPT, one of the most efficient DCOP algorithms. We present our detailed algorithm, as well as some experimental results in personal assistant domains.
2005_7_teamcore_ss705bowringe.pdf
Rajiv T. Maheswaran, Jonathan P. Pearce, Pradeep Varakantham, Emma Bowring, and Milind Tambe. 3/21/2005. “Valuations of Possible States (VPS): A Quantitative Framework for Analysis of Privacy Loss Among Collaborative Personal Assistant Agents .” In AAAI Spring Symposium on Persistent Assistants: Living and Working with AI. Menlo Park, CA.Abstract
For agents deployed in real-world settings, such as businesses, universities and research laboratories, it is critical that agents protect their individual users’ privacy when interacting with others entities. Indeed, privacy is recognized as a key motivating factor in design of several multiagent algorithms, such as distributed constraint optimization (DCOP) algorithms. Unfortunately, rigorous and general quantitative metrics for analysis and comparison of such multiagent algorithms with respect to privacy loss are lacking. This paper takes a key step towards developing a general quantitative model from which one can analyze and generate metrics of privacy loss by introducing the VPS (Valuations of Possible States) framework. VPS is shown to capture various existing measures of privacy created for specific domains of distributed constraint satisfactions problems (DCSPs). The utility of VPS is further illustrated via analysis of DCOP algorithms, when such algorithms are used by personal assistant agents to schedule meetings among users. In addition, VPS allows us to quantitatively evaluate the properties of several privacy metrics generated through qualitative notions. We obtain the unexpected result that decentralization does not automatically guarantee superior protection of privacy
2005_4_teamcore_aaaiss05vps.pdf
H. Jung and Milind Tambe. 2005. “Communication in distributed constraint satisfaction problems .” In International Central and Eastern European Conference on Multi-Agent Systems (CEEMAS'05).Abstract
Distributed Constraint Satisfaction Problems (DCSP) is a general framework for multi-agent coordination and conflict resolution. In most DCSP algorithms, inter-agent communication is restricted to only exchanging values of variables, since any additional information-exchange is assumed to lead to significant communication overheads and to a breach of privacy. This paper provides a detailed experimental investigation of the impact of inter-agent exchange of additional legal values among agents, within a collaborative setting. We provide a new run-time model that takes into account the overhead of the additional communication in various computing and networking environments. Our investigation of more than 300 problem settings with the new run-time model (i) shows that DCSP strategies with additional information-exchange can lead to big speedups in a significant range of settings; and (ii) provides categorization of problem settings with big speedups by the DCSP strategies based on extra communication, enabling us to selectively apply the strategies to a given domain. This paper not only provides a useful method for performance measurement to the DCSP community, but also shows the utility of additional communication in DCSP.
2005_6_teamcore_ceemas05.pdf
Nathan Schurr, Janusz Marecki, Paul Scerri, J. P. Lewis, and Milind Tambe. 2005. “The DEFACTO System: Coordinating Human-Agent Teams for the Future of Disaster Response .” In Programming Multiagent Systems. Springer Press.Abstract
Enabling effective interactions between agent teams and humans for disaster response is a critical area of research, with encouraging progress in the past few years. However, previous work suffers from two key limitations: (i) limited human situational awareness, reducing human effectiveness in directing agent teams and (ii) the agent team’s rigid interaction strategies that limit team performance. This paper presents a software prototype called DEFACTO (Demonstrating Effective Flexible Agent Coordination of Teams through Omnipresence). DEFACTO is based on a software proxy architecture and 3D visualization system, which addresses the two limitations described above. First, the 3D visualization interface enables human virtual omnipresence in the environment, improving human situational awareness and ability to assist agents. Second, generalizing past work on adjustable autonomy, the agent team chooses among a variety of “team-level” interaction strategies, even excluding humans from the loop in extreme circumstances.
2005_11_teamcore_kluwerbookchapter.pdf
Nathan Schurr, Janusz Marecki, Paul Scerri, J. P. Lewis, and Milind Tambe. 2005. “The DEFACTO System: Training Tool for Incident Commanders .” In Innovative Applications of Artificial Intelligence (IAAI'05).Abstract
Techniques for augmenting the automation of routine coordination are rapidly reaching a level of effectiveness where they can simulate realistic coordination on the ground for large numbers of emergency response entities (e.g. fire engines, police cars) for the sake of training. Furthermore, it seems inevitable that future disaster response systems will utilize such technology. We have constructed a new system, DEFACTO (Demonstrating Effective Flexible Agent Coordination of Teams through Omnipresence), that integrates stateof-the-art agent reasoning capabilities and 3D visualization into a unique high fidelity system for training incident commanders. The DEFACTO system achieves this goal via three main components: (i) Omnipresent Viewer - intuitive interface, (ii) Proxy Framework - for team coordination, and (iii) Flexible Interaction - between the incident commander and the team. We have performed detailed preliminary experiments with DEFACTO in the fire-fighting domain. In addition, DEFACTO has been repeatedly demonstrated to key police and fire department personnel in Los Angeles area, with very positive feedback.
2005_18_teamcore_iaai052schurrn.pdf
Pradeep Varakantham, Rajiv T. Maheswaran, and Milind Tambe. 2005. “Exploiting Belief Bounds: Practical POMDPs for Personal Assistant Agents .” In International Conference on Autonomous Agents and Multiagent Systems, AAMAS.Abstract
Agents or agent teams deployed to assist humans often face the challenges of monitoring the state of key processes in their environment (including the state of their human users themselves) and making periodic decisions based on such monitoring. POMDPs appear well suited to enable agents to address these challenges, given the uncertain environment and cost of actions, but optimal policy generation for POMDPs is computationally expensive. This paper introduces three key techniques to speedup POMDP policy generation that exploit the notion of progress or dynamics in personal assistant domains. Policy computation is restricted to the belief space polytope that remains reachable given the progress structure of a domain. We introduce new algorithms; particularly one based on applying Lagrangian methods to compute a bounded belief space support in polynomial time. Our techniques are complementary to many existing exact and approximate POMDP policy generation algorithms. Indeed, we illustrate this by enhancing two of the fastest existing algorithms for exact POMDP policy generation. The order of magnitude speedups demonstrate the utility of our techniques in facilitating the deployment of POMDPs within agents assisting human users.
2005_13_teamcore_p774_varakantham.pdf
Ranjit Nair and Milind Tambe. 2005. “Hybrid BDI-POMDP Framework for Multiagent Teaming .” Journal of AI Research (JAIR), 23, Pp. 367-420.Abstract
Many current large-scale multiagent team implementations can be characterized as following the “belief-desire-intention” (BDI) paradigm, with explicit representation of team plans. Despite their promise, current BDI team approaches lack tools for quantitative performance analysis under uncertainty. Distributed partially observable Markov decision problems (POMDPs) are well suited for such analysis, but the complexity of finding optimal policies in such models is highly intractable. The key contribution of this article is a hybrid BDI-POMDP approach, where BDI team plans are exploited to improve POMDP tractability and POMDP analysis improves BDI team plan performance. Concretely, we focus on role allocation, a fundamental problem in BDI teams: which agents to allocate to the different roles in the team. The article provides three key contributions. First, we describe a role allocation technique that takes into account future uncertainties in the domain; prior work in multiagent role allocation has failed to address such uncertainties. To that end, we introduce RMTDP (Role-based Markov Team Decision Problem), a new distributed POMDP model for analysis of role allocations. Our technique gains in tractability by significantly curtailing RMTDP policy search; in particular, BDI team plans provide incomplete RMTDP policies, and the RMTDP policy search fills the gaps in such incomplete policies by searching for the best role allocation. Our second key contribution is a novel decomposition technique to further improve RMTDP policy search efficiency. Even though limited to searching role allocations, there are still combinatorially many role allocations, and evaluating each in RMTDP to identify the best is extremely difficult. Our decomposition technique exploits the structure in the BDI team plans to significantly prune the search space of role allocations. Our third key contribution is a significantly faster policy evaluation algorithm suited for our BDI-POMDP hybrid approach. Finally, we also present experimental results from two domains: mission rehearsal simulation and RoboCupRescue disaster rescue simulation.
2005_1_teamcore_nair_jair.pdf
Pradeep Varakantham, Rajiv T. Maheswaran, and Milind Tambe. 2005. “Practical POMDPs for Personal Assistant Domains .” In AAAI Spring Symposium.Abstract
Agents or agent teams deployed to assist humans often face the challenge of monitoring state of key processes in their environment, including the state of their human users, and making periodic decisions based on such monitoring. The challenge is particularly difficult given the significant observational uncertainty, and uncertainty in the outcome of agent’s actions. POMDPs (partially observable markov decision problems) appear well-suited to enable agents to address such uncertainties and costs; yet slow run-times in generating optimal POMDP policies presents a significant hurdle. This slowness can be attributed to cautious planning for all possible belief states, e.g., the uncertainty in the monitored process is assumed to range over all possible states at all times. This paper introduces three key techniques to speedup POMDP policy generation that exploit the notion of progress or dynamics in personal assistant domains. The key insight is that given an initial (possibly uncertain) starting set of states, the agent needs to be prepared to act only in a limited range of belief states; most other belief states are simply unreachable given the dynamics of the monitored process, and no policy needs to be generated for such belief states. The techniques we propose are complementary to most existing exact and approximate POMDP policy generation algorithms. Indeed, we illustrate our technique by enhancing generalized incremental pruning (GIP), one of the most efficient exact algorithms for POMDP policy generation and illustrate orders of magnitude speedup in policy generation. Such speedup would facilitate agents’ deploying POMDPs in assisting human users.
2005_12_teamcore_practical_pomdp.pdf
Syed M. Ali, Sven Koenig, and Milind Tambe. 2005. “Preprocessing Techniques for Accelerating the DCOP Algorithm ADOPT .” In Fourth International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS).Abstract
Methods for solving Distributed Constraint Optimization Problems (DCOP) have emerged as key techniques for distributed reasoning. Yet, their application faces significant hurdles in many multiagent domains due to their inefficiency. Preprocessing techniques have successfully been used to speed up algorithms for centralized constraint satisfaction problems. This paper introduces a framework of different preprocessing techniques that are based on dynamic programming and speed up ADOPT, an asynchronous complete and optimal DCOP algorithm. We investigate when preprocessing is useful and which factors influence the resulting speedups in two DCOP domains, namely graph coloring and distributed sensor networks. Our experimental results demonstrate that our preprocessing techniques are fast and can speed up ADOPT by an order of magnitude.
2005_8_teamcore_aamas_paper.pdf
M Huhns. 2005. “Research Directions for Service Oriented Multiagent Systems .” IEEE Internet Computing, 9, 6 2005, Pp. 65-70 .Abstract
Today’s service-oriented systems realize many ideas from the research conducted a decade or so ago in multiagent systems.Because these two fields are so deeply connected, further advances in multiagent systems could feed into tomorrow’s successful service-oriented computing approaches.This article describes a 15- year roadmap for service-oriented multiagent system research.
2005_14_teamcore_huhns.pdf
Nathan Schurr, Janusz Marecki, Milind Tambe, and Paul Scerri. 2005. “Towards Flexible Coordination of Human-Agent Teams .” Multiagent and Grid Systems - An International Journal, 1, Pp. 3-16.Abstract
Enabling interactions of agent-teams and humans is a critical area of research, with encouraging progress in the past few years. However, previous work suffers from three key limitations: (i) limited human situational awareness, reducing human effectiveness in directing agent teams, (ii) the agent team’s rigid interaction strategies that limit team performance, and (iii) lack of formal tools to analyze the impact of such interaction strategies. This article presents a software prototype called DEFACTO (Demonstrating Effective Flexible Agent Coordination of Teams through Omnipresence). DEFACTO is based on a software proxy architecture and 3D visualization system, which addresses the three limitations mentioned above. First, the 3D visualization interface enables human virtual omnipresence in the environment, improving human situational awareness and ability to assist agents. Second, generalizing past work on adjustable autonomy, the agent team chooses among a variety of team-level interaction strategies, even excluding humans from the loop in extreme circumstances. Third, analysis tools help predict the performance of (and choose among) different interaction strategies. DEFACTO is illustrated in a future disaster response simulation scenario, and extensive experimental results are presented.
2005_17_teamcore_schurr_mags.pdf
Pragnesh J. Modi, W. Shen, Milind Tambe, and Makoto Yokoo. 2005. “ADOPT: Asynchronous distributed constraint optimization with quality guarantees.” Artificial Intelligence Journal(AIJ), 161, Pp. 149-180.Abstract
The Distributed Constraint Optimization Problem (DCOP) is a promising approach for modeling distributed reasoning tasks that arise in multiagent systems. Unfortunately, existing methods for DCOP are not able to provide theoretical guarantees on global solution quality while allowing agents to operate asynchronously. We show how this failure can be remedied by allowing agents to make local decisions based on conservative cost estimates rather than relying on global certainty as previous approaches have done. This novel approach results in a polynomial-space algorithm for DCOP named Adopt that is guaranteed to find the globally optimal solution while allowing agents to execute asynchronously and in parallel. Detailed experimental results show that on benchmark problems Adopt obtains speedups of several orders of magnitude over other approaches. Adopt can also perform bounded-error approximation – it has the ability to quickly find approximate solutions and, unlike heuristic search methods, still maintain a theoretical guarantee on solution quality.
2005_3_teamcore_aij_modi.pdf
2004
Paul Scerri, K. Sycara, and Milind Tambe. 2004. “Adjustable autonomy in the context of coordination (invited paper) .” In First Intelligent Systems Technical Conference of the American Institute of Aeronautics and Astronautics.Abstract
Human-agent interaction in the context of coordination presents novel challenges as compared to isolated interactions between a single human and single agent. There are two broad reasons for the additional challenges: things continue to happen in the environment while a decision is pending and the inherent distributedness of the entities involved. Our approach to interaction in such a context has three key components which allow us to leverage human expertise by giving them responsibility for key coordination decisions, without risks to the coordination due to slow responses. First, to deal with the dynamic nature of the situation, we use pre-planned sequences of transfer of control actions called transfer-of-control strategies. Second, to allow identification of key coordination issues in a distributed way, individual coordination tasks are explicitly represented as coordination roles, rather than being implicitly represented within a monolithic protocol. Such a representation allows meta-reasoning about those roles to determine when human input may be useful. Third, the meta-reasoning and transfer-of-control strategies are encapsulated in a mobile agent that moves around the group to either get human input or autonomously make a decision. In this paper, we describe this approach and present initial results from interaction between a large number of UAVs and a small number of humans.
2004_9_teamcore_aiaa.pdf
Ranjit Nair, Makoto Yokoo, Maayan Roth, and Milind Tambe. 2004. “Communication for Improving Policy Computation in Distributed POMDPs .” In Third International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS-04).Abstract
Distributed Partially Observable Markov Decision Problems (POMDPs) are emerging as a popular approach for modeling multiagent teamwork where a group of agents work together to jointly maximize a reward function. Since the problem of finding the optimal joint policy for a distributed POMDP has been shown to be NEXP-Complete if no assumptions are made about the domain conditions, several locally optimal approaches have emerged as a viable solution. However, the use of communicative actions as part of these locally optimal algorithms has been largely ignored or has been applied only under restrictive assumptions about the domain. In this paper, we show how communicative acts can be explicitly introduced in order to find locally optimal joint policies that allow agents to coordinate better through synchronization achieved via communication. Furthermore, the introduction of communication allows us to develop a novel compact policy representation that results in savings of both space and time which are verified empirically. Finally, through the imposition of constraints on communication such as not going without communicating for more than K steps, even greater space and time savings can be obtained.
2004_5_teamcore_nair_aamas04.pdf
Ranjit Nair. 2004. “Coordinating multiagent teams in uncertain domains using distributed POMDPs ”.Abstract
Distributed Partially Observable Markov Decision Problems (POMDPs) have emerged as a popular decision-theoretic approach for planning for multiagent teams, where it is imperative for the agents to be able to reason about the rewards (and costs) for their actions in the presence of uncertainty. However, finding the optimal distributed POMDP policy is computationally intractable (NEXP-Complete). This dissertation presents two independent approaches which deal with this issue of intractability in distributed POMDPs. The primary focus is on the first approach, which represents a principled way to combine the two dominant paradigms for building multiagent team plans, namely the “beliefdesire-intention” (BDI) approach and distributed POMDPs. In this hybrid BDIPOMDP approach, BDI team plans are exploited to improve distributed POMDP tractability and distributed POMDP-based analysis improves BDI team plan performance. Concretely, we focus on role allocation, a fundamental problem in BDI teams – which agents to allocate to the different roles in the team. The hybrid BDI-POMDP approach provides three key contributions. First, unlike prior work in multiagent role allocation, we describe a role allocation technique that takes into account future uncertainties in the domain. The second contribution is a novel decomposition technique, which exploits the structure in the BDI team plans to significantly prune the search space of combinatorially many role allocations. Our third key contribution is a significantly faster policy evaluation algorithm suited for our BDI-POMDP hybrid approach. Finally, we also present experimental results from two domains: mission rehearsal simulation and RoboCupRescue disaster rescue simulation. In the RoboCupRescue domain, we show that the role allocation technique presented in this dissertation is capable of performing at human expert levels by comparing with the allocations chosen by humans in the actual RoboCupRescue simulation environment. The second approach for dealing with the intractability of distributed POMDPs is based on finding locally optimal joint policies using Nash equilibrium as a solution concept. Through the introduction of communication, we not only show improved coordination but also develop a novel compact policy representation that results in savings of both space and time which are verified empirically.
2014_11_teamcore_chao_2014_extend.pdf
Nathan Schurr, Paul Scerri, and Milind Tambe. 2004. “Coordination Advice: A Preliminary Investigation of Human Advice to Multiagent Teams .” In Spring Symposium.Abstract
This paper introduces a new area of advice that is specific to advising a multiagent team: Coordination Advice. Coordination Advice differs from traditional advice because it pertains to coordinated tasks and interactions between agents. Given a large multiagent team interacting in a dynamic domain, optimal coordination is a difficult challenge. Human advisors can improve such coordination via advice. This paper is a preliminary look at the evolution of Coordination Advice from a human through three different domains: (i) disaster rescue simulation, (ii) a self-maintaining robotics sensors, and (iii) personal assistants in a office environment. We study how the useful advice a person can give changes as the domains change and the number of agents and roles increase.
2004_8_teamcore_symposium.pdf
Jonathan P. Pearce, Rajiv T. Maheswaran, and Milind Tambe. 2004. “DCOP Games for Multi-Agent Coordination .” In CP 2004 Workshop on Distributed Constraint Reasoning (DCR-04).Abstract
Many challenges in multi-agent coordination can be modeled as distributed constraint optimization problems (DCOPs) but complete algorithms do not scale well nor respond effectively to dynamic or anytime environments. We introduce a transformation of DCOPs into graphical games that allows us to devise and analyze algorithms based on local utility and prove the monotonicity property of a class of such algorithms. The game-theoretic framework also enables us to characterize new equilibrium sets corresponding to a given degree of agent coordination. A key result in this paper is the discovery of a novel mapping between finite games and coding theory from which we can determine a priori bounds on the number of equilibria in these sets, which is useful in choosing the appropriate level of coordination given the communication cost of an algorithm
2004_7_teamcore_pearce_dcr04.pdf
Rajiv T. Maheswaran, Jonathan P. Pearce, and Milind Tambe. 2004. “Distributed Algorithms for DCOP: A Graphical Game-Based Approach .” In 17th International Conference on Parallel and Distributed Computing Systems (PDCS-2004).Abstract
This paper addresses the application of distributed constraint optimization problems (DCOPs) to large-scale dynamic environments. We introduce a decomposition of DCOP into a graphical game and investigate the evolution of various stochastic and deterministic algorithms. We also develop techniques that allow for coordinated negotiation while maintaining distributed control of variables. We prove monotonicity properties of certain approaches and detail arguments about equilibrium sets that offer insight into the tradeoffs involved in leveraging efficiency and solution quality. The algorithms and ideas were tested and illustrated on several graph coloring domains.
2004_2_teamcore_maheswaran_pearce04pdcs.pdf
Nathan Schurr, Steven Okamoto, Rajiv T. Maheswaran, Paul Scerri, and Milind Tambe. 2004. “Evolution of a Teamwork Model .” In Cognition and Multi-Agent Interaction: From Cognitive Modeling to Social Simulation. Cambridge University Press.Abstract
For heterogeneous agents working together to achieve complex goals, teamwork (Jennings, 1995; Yen, Yin, Ioerger, Miller, Xu, & Volz, 2001; Tambe, 1997a) has emerged as the dominant coordination paradigm. For domains as diverse as rescue response, military, space, sports and collaboration between human workmates, flexible, dynamic coordination between cooperative agents needs to be achieved despite complex, uncertain, and hostile environments. There is now emerging consensus in the multiagent arena that for flexible teamwork among agents, each team member is provided with an explicit model of teamwork, which entails their commitments and responsibilities as a team member. This explicit modelling allows the coordination to be robust, despite individual failures and unpredictably changing environments. Building on the well developed theory of joint intentions (Cohen & Levesque, 1991) and shared plans (Grosz & Kraus, 1996), the STEAM teamwork model (Tambe, 1997a) was operationalized as a set of domain independent rules that describe how teams should work together. This domain independent teamwork model has been successfully applied to a variety of domains. From combat air missions (Hill, Chen, Gratch, Rosenbloom, & Tambe, 1997) to robot soccer (Kitano, Asada, Kuniyoshi, Noda, Osawa, & Matsubara, 1997) to teams supporting human organizations (Pynadath & Tambe, 2003) to rescue response (Scerri, Pynadath, Johnson, P., Schurr, Si, & Tambe, 2003), applying the same set of STEAM rules has resulted in successful coordination between heterogeneous agents. The successful use of the same teamwork model in a wide variety of diverse domains provides compelling evidence that it is the principles of teamwork, rather than exploitation of specific domain phenomena, that underlies the success of teamwork based approaches. Since the same rules can be successfully used in a range of domains, it is desirable to build a reusable software package that encapsulates those rules in order to provide a lightweight and portable implementation. The emerging standard for deploying such a package is via proxies (Pynadath & Tambe, 2003). Each proxy works closely with a single domain agent, representing that agent in the team. The second generation of teamwork proxies, called Machinetta (Pynadath & Tambe, 2003; Scerri et al., 2003), is currently being developed. The Machinetta proxies use less computing resources and are more flexible than the proxies they have superseded. While approaches to teamwork have been shown to be effective for agent teams, new emerging domains of teamwork require agent-human interactions in teams. These emerging domains and the teams that are being developed for them introduce a new set of issues and obstacles. Two algorithms that need to be revised in particular for these complex domains are the algorithms for adjustable autonomy (for agent-human interaction) and algorithms for role allocation. This chapter focuses in particular on the challenge of role allocation. Upon instantiation of a new plan, the roles needed to perform that plan are created and must be allocated to members of the team. In order to allocate a dynamically changing set of roles to team members, previous mechanisms required too much computation and/or communication and did not handle rapidly changing situations well for teams with many members. A novel algorithm has been created for role allocation in these extreme teams. Generally in teamwork, role allocation is the problem of assigning roles to agents so as to maximize overall team utility (Nair, Ito, Tambe, & Marsella, 2002; Tidhar, Rao, & Sonenberg, 1996; Werger & Mataric, 2000). Extreme teams emphasize key additional properties in role allocation: (i) domain dynamics may cause tasks to disappear; (ii) agents may perform one or more roles, but within resource limits; (iii) many agents can fulfill the same role. This role allocation challenge in extreme teams will be referred to as extended GAP (E-GAP), as it subsumes the generalized assignment problem (GAP), which is NP-complete (Shmoys & Tardos, 1993).
2004_10_teamcore_bdibook_chapter.pdf

Pages