2005
Paul Scerri, A. Farinelli, Steven Okamoto, and Milind Tambe. 7/2005. “
Allocating tasks in extreme teams .” In Fourth International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS).
AbstractExtreme teams, large-scale agent teams operating in dynamic environments, are on the horizon. Such environments are problematic
for current task allocation algorithms due to the lack of locality in
agent interactions. We propose a novel distributed task allocation
algorithm for extreme teams, called LA-DCOP, that incorporates
three key ideas. First, LA-DCOP’s task allocation is based on a
dynamically computed minimum capability threshold which uses
approximate knowledge of overall task load. Second, LA-DCOP
uses tokens to represent tasks and further minimize communication. Third, it creates potential tokens to deal with inter-task constraints of simultaneous execution. We show that LA-DCOP convincingly outperforms competing distributed task allocation algorithms while using orders of magnitude fewer messages, allowing a
dramatic scale-up in extreme teams, upto a fully distributed, proxybased team of 200 agents. Varying threshold are seen as a key to
outperforming competing distributed algorithms in the domain of
simulated disaster rescue.
2005_10_teamcore_final.pdf Milind Tambe, Emma Bowring, H. Jung, Gal Kaminka, Rajiv T. Maheswaran, Janusz Marecki, Pragnesh J. Modi, Ranjit Nair, Steven Okamoto, Jonathan P. Pearce, Praveen Paruchuri, D. V. Pynadath, Paul Scerri, Nathan Schurr, and Pradeep Varakantham. 7/2005. “
Conflicts in teamwork: Hybrids to the rescue .” In Fourth International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS).
AbstractToday within the AAMAS community, we see at least four
competing approaches to building multiagent systems: beliefdesire-intention (BDI), distributed constraint optimization
(DCOP), distributed POMDPs, and auctions or game-theoretic approaches. While there is exciting progress within
each approach, there is a lack of cross-cutting research. This
paper highlights hybrid approaches for multiagent teamwork. In particular, for the past decade, the TEAMCORE
research group has focused on building agent teams in complex, dynamic domains. While our early work was inspired
by BDI, we will present an overview of recent research that
uses DCOPs and distributed POMDPs in building agent
teams. While DCOP and distributed POMDP algorithms
provide promising results, hybrid approaches help us address
problems of scalability and expressiveness. For example, in
the BDI-POMDP hybrid approach, BDI team plans are exploited to improve POMDP tractability, and POMDPs improve BDI team plan performance. We present some recent
results from applying this approach in a Disaster Rescue
simulation domain being developed with help from the Los
Angeles Fire Department.
2005_15_teamcore_tambe.pdf Jonathan P. Pearce, Rajiv T. Maheswaran, and Milind Tambe. 7/2005. “
How Local Is That Optimum? k-optimality for DCOP .” In Fourth International Joint Conference Poster on Autonomous Agents and Multiagent Systems (AAMAS).
AbstractIn multi-agent systems where sets of joint actions (JAs) are generated, metrics are needed to evaluate these sets and efficiently allocate resources for the many JAs. For the case where a JA set can
be represented by multiple solutions to a DCOP, we introduce koptimality as a metric that captures desirable properties of diversity
and relative quality, and apply results from coding theory to obtain
upper bounds on cardinalities of k-optimal JA sets. These bounds
can help choose the appropriate level of k-optimality for settings
with fixed resources and help determine appropriate resource allocation for settings where a fixed level of k-optimality is desired.
2005_9_teamcore_pearce_aamas05.pdf R. Nair, P. Varakantam, M. Tambe, and M. Yokoo. 7/2005. “
Networked Distributed POMDPs: A Synergy of Distributed Constraint Optimization and POMDPs .” In International Joint Conference on Artificial Intelligence (IJCAI).
AbstractIn many real-world multiagent applications
such as distributed sensor nets, a network of
agents is formed based on each agent’s limited
interactions with a small number of neighbors.
While distributed POMDPs capture the realworld uncertainty in multiagent domains, they
fail to exploit such locality of interaction. Distributed constraint optimization (DCOP) captures the locality of interaction but fails to capture planning under uncertainty. This paper
present a new model synthesized from distributed POMDPs and DCOPs, called Networked
Distributed POMDPs (ND-POMDPs). Exploiting network structure enables us to present
a distributed policy generation algorithm that
performs local search.
2005_19_teamcore_post_0517.pdf Ranjit Nair, Pradeep Varakantham, Milind Tambe, and Makoto Yokoo. 7/2005. “
Networked Distributed POMDPs: A Synthesis of Distributed Constraint Optimization and POMDPs.” In Twentieth AAAI-05 National Conference on Artificial Intelligence.
AbstractIn many real-world multiagent applications such as distributed sensor nets, a network of agents is formed based
on each agent’s limited interactions with a small number
of neighbors. While distributed POMDPs capture the
real-world uncertainty in multiagent domains, they fail
to exploit such locality of interaction. Distributed constraint optimization (DCOP) captures the locality of interaction but fails to capture planning under uncertainty.
This paper present a new model synthesized from distributed POMDPs and DCOPs, called Networked Distributed POMDPs (ND-POMDPs). Exploiting network
structure enables us to present two novel algorithms
for ND-POMDPs: a distributed policy generation algorithm that performs local search and a systematic policy
search that is guaranteed to reach the global optimal.
2005_2_teamcore_297.pdf Rajiv T. Maheswaran, Jonathan P. Pearce, Pradeep Varakantham, Emma Bowring, and Milind Tambe. 7/2005. “
Valuations of Possible States (VPS): A Quantitative Framework for Analysis of Privacy Loss Among Collaborative Personal Assistant Agents.” In Fourth International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS).
AbstractFor 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_5_teamcore_p799_maheswaran.pdf 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.
AbstractWhen 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.
AbstractResearch 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.pdfRajiv 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.
AbstractFor 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).
AbstractDistributed 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.
AbstractEnabling 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).
AbstractTechniques 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.
AbstractAgents 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.
AbstractMany 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.
AbstractAgents 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).
AbstractMethods 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 .
AbstractToday’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.
AbstractEnabling 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.
AbstractThe 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