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.
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.
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.
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.
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.
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
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
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.
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).
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.