2001
David V. Pynadath, Milind Tambe, and Gal A. Kaminka. 2001. “
Adaptive infrastructures for agent integration .” In First International Workshop on Infrastructures for Scalable multi-agent systems, Springer Lecture Notes in Computer Science.
AbstractWith the proliferation of software agents and smart hardware devices
there is a growing realization that large-scale problems can be addressed by integration of such stand-alone systems. This has led to an increasing interest in
integration infrastructures that enable a heterogeneous variety of agents and humans to work together. In our work, this infrastructure has taken the form of an
integration architecture called Teamcore. We have deployed Teamcore to facilitate/enable collaboration between different agents and humans that differ in their
capabilities, preferences, the level of autonomy they are willing to grant the integration architecture, their information requirements and performance. This paper
first provides a brief overview of the Teamcore architecture and its current applications. The paper then discusses some of the research challenges we have
focused on. In particular, the Teamcore architecture is based on general purpose
teamwork coordination capabilities. However, it is important for this architecture
to adapt to meet the needs and requirements of specific individuals. We describe
the different techniques of architectural adaptation, and present initial experimental results.
2001_11_teamcore_incs01.pdf Milind Tambe, D. V. Pynadath, and Paul Scerri. 2001. “
Adjustable Autonomy: A Response .” In Intelligent Agents VII Proceedings of the International workshop on Agents, theories, architectures and languages.
AbstractGaining a fundamental understanding of adjustable autonomy (AA) is critical if
we are to deploy multi-agent systems in support of critical human activities. Indeed,
our recent work with intelligent agents in the “Electric Elves” (E-Elves) system has
convinced us that AA is a critical part of any human collaboration software. In the
following, we first briefly describe E-Elves, then discuss AA issues in E-Elves.
2001_8_teamcore_atal_panel.pdf Paul Scerri, D. V. Pynadath, and Milind Tambe. 2001. “
Adjustable autonomy in real-world multi-agent environments .” In International Conference on Autonomous Agents (Agents'01).
AbstractThrough 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 in its human interaction. AA research is critical for successful deployment of multi-agent systems
in support of important human activities. While most previous AA
work has focused on individual agent-human interactions, this paper focuses on teams of agents operating in real-world human organizations. The need for agent teamwork and coordination in such
environments introduces novel AA challenges. First, agents must
be more judicious in asking for human intervention, because, although human input can prevent erroneous actions that have high
team costs, one agent’s inaction while waiting for a human response
can lead to potential miscoordination with the other agents in the
team. Second, despite appropriate local decisions by individual
agents, the overall team of agents can potentially make global decisions that are unacceptable to the human team. Third, the diversity in real-world human organizations requires that agents gradually learn individualized models of the human members, while
still making reasonable decisions even before sufficient data are
available. We address these challenges using a multi-agent AA
framework based on an adaptive model of users (and teams) that
reasons about the uncertainty, costs, and constraints of decisions
at all levels of the team hierarchy, from the individual users to the
overall human organization. We have implemented this framework
through Markov decision processes, which are well suited to reason
about the costs and uncertainty of individual and team actions. Our
approach to AA has proven essential to the success of our deployed
multi-agent Electric Elves system that assists our research group in
rescheduling meetings, choosing presenters, tracking people’s locations, and ordering meals.
2001_10_teamcore_agents01_aa.pdf H. Jung and Milind Tambe. 2001. “
Argumentation as Distributed Constraint Satisfaction: Applications and Results .” In International Conference on Autonomous Agents (Agents'01).
AbstractConflict resolution is a critical problem in distributed and collaborative multi-agent systems. Negotiation via argumentation (NVA),
where agents provide explicit arguments or justifications for their
proposals for resolving conflicts, is an effective approach to resolve
conflicts. Indeed, we are applying argumentation in some realworld multi-agent applications. However, a key problem in such
applications is that a well-understood computational model of argumentation is currently missing, making it difficult to investigate
convergence and scalability of argumentation techniques, and to
understand and characterize different collaborative NVA strategies
in a principled manner. To alleviate these difficulties, we present
distributed constraint satisfaction problem (DCSP) as a computational model for investigating NVA. We model argumentation as
constraint propagation in DCSP. This model enables us to study
convergence properties of argumentation, and formulate and experimentally compare 16 different NVA strategies with different
levels of agent cooperativeness towards others. One surprising result from our experiments is that maximizing cooperativeness is not
necessarily the best strategy even in a completely cooperative environment. The paper illustrates the usefulness of these results in
applying NVA to multi-agent systems, as well as to DCSP systems
in general.
2001_2_teamcore_agents01_argue.pdf Pragnesh J. Modi, H. Jung, Milind Tambe, W. Shen, and S. Kulkarni. 2001. “
A Dynamic Distributed Constraint Satisfaction Approach to Resource Allocation .” In International Conference on Principles and Practices of Constraint programming.
Abstract In distributed resource allocation a set of agents must assign their resources to a set of tasks. This problem arises in many real-world domains such
as disaster rescue, hospital scheduling and the domain described in this paper:
distributed sensor networks. Despite the variety of approaches proposed for distributed resource allocation, a systematic formalization of the problem and a general solution strategy are missing. This paper takes a step towards this goal by
proposing a formalization of distributed resource allocation that represents both
dynamic and distributed aspects of the problem and a general solution strategy
that uses distributed constraint satisfaction techniques. This paper defines the notion of Dynamic Distributed Constraint Satisfaction Problem (DyDCSP) and proposes two generalized mappings from distributed resource allocation to DyDCSP,
each proven to correctly perform resource allocation problems of specific difficulty and this theoretical result is verified in practice by an implementation on a
real-world distributed sensor network
2001_5_teamcore_cp01.pdf Pragnesh J. Modi, H. Jung, Milind Tambe, W. Shen, and S. Kulkarni. 2001. “
Dynamic distributed resource allocation: A distributed constraint satisfaction approach .” In Intelligent Agents VIII Proceedings of the International workshop on Agents, theories, architectures and languages (ATAL'01).
AbstractIn distributed resource allocation a set of agents must assign their resources to a set of tasks. This problem arises in many real-world domains such
as distributed sensor networks, disaster rescue, hospital scheduling and others.
Despite the variety of approaches proposed for distributed resource allocation,
a systematic formalization of the problem, explaining the different sources of
difficulties, and a formal explanation of the strengths and limitations of key approaches is missing. We take a step towards this goal by proposing a formalization
of distributed resource allocation that represents both dynamic and distributed aspects of the problem. We define four categories of difficulties of the problem. To
address this formalized problem, the paper defines the notion of Dynamic Distributed Constraint Satisfaction Problem (DDCSP). The central contribution of
the paper is a generalized mapping from distributed resource allocation to DDCSP. This mapping is proven to correctly perform resource allocation problems
of specific difficulty. This theoretical result is verified in practice by an implementation on a real-world distributed sensor network.
2001_6_teamcore_atal01.pdf H. Chalupsky, Y. Gil, Craig Knoblock, K. Lerman, J. Oh, D. V. Pynadath, T. Russ, and Milind Tambe. 2001. “
Electric Elves: Applying Agent Technology to Support Human Organizations .” In International Conference on Innovative Applications of AI (IAAI'01).
AbstractThe 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.
2001_1_teamcore_iaai01.pdf D. V. Pynadath, Paul Scerri, and Milind Tambe. 2001. “
MDPs for Adjustable autonomy in a real-world multi-agent environment.” In AAAI Spring Symposium on Decision theoretic and Game Theoretic Agents.
AbstractResearch on adjustable autonomy (AA) is critical if we are to
deploy multiagent systems in support of important human activities. Through AA, an agent can dynamically vary its level
of autonomy — harnessing human abilities when needed, but
also limiting such interaction. While most previous AA work
has focused on individual agent-human interactions, this paper focuses on agent teams embedded in human organizations
in the context of real-world applications. The need for agent
teamwork and coordination in such environments introduces
novel AA challenges. In particular, transferring control to
human users becomes more difficult, as a lack of human response can cause agent team miscoordination, yet not transferring control causes agents to take enormous risks. Furthermore, despite appropriate individual agent decisions, the
agent teams may reach decisions that are completely unacceptable to the human team.
We address these challenges by pursuing a two-part decisiontheoretic approach. First, to avoid team miscoordination due
to transfer of control decisions, an agent: (i) considers the
cost of potential miscoordination with teammates; (ii) does
not rigidly commit to a transfer of control decision; (iii)
if forced into a risky autonomous action to avoid miscoordination, considers changes in the team’s coordination that
mitigate the risk. Second, to ensure effective team decisions, not only individual agents, but also subteams and teams
can dynamically adjust their own autonomy. We implement
these ideas using Markov Decision Processes, providing a
decision-theoretic basis for reasoning about costs and uncertainty of individual and team actions. This approach is central
to our deployed multi-agent system, called Electric Elves, that
assists our research group in rescheduling meetings, choosing
presenters, tracking people’s locations and ordering meals.
2001_7_teamcore_spring_symp01.pdf Gal Kaminka, D. V. Pynadath, and Milind Tambe. 2001. “
Monitoring Deployed Agent Teams .” In International Conference on Autonomous Agents (Agents'01).
AbstractRecent years have seen an increasing need for on-line monitoring
of deployed distributed teams of cooperating agents, for visualization, for performance tracking, etc. However, in deployed applications, we often cannot rely on the agents communicating their state
to the monitoring system: (a) we rarely have the ability to change
the behavior of already-deployed agents such that they communicate the required information (e.g., in legacy or proprietary systems); (b) different monitoring goals require different information
to be communicated (e.g., agents’ beliefs vs. plans); and (c) communications may be expensive, unreliable, or insecure. This paper presents a non-intrusive approach based on plan-recognition, in
which the monitored agents’ state is inferred from observations of
their normal course of actions. In particular, we focus on inference
of the team state based on its observed routine communications, exchanged as part of coordinated task execution. The paper includes
the following key novel contributions: (i) a linear time probabilistic plan-recognition algorithm, particularly well-suited for processing communications as observations; (ii) an approach to exploiting
general knowledge of teamwork to predict agent responses during
normal and failing execution, to reduce monitoring uncertainty; and
(iii) a technique for trading expressivity for scalability, representing only certain useful monitoring hypotheses, but allowing for any
number of agents and their different activities, to be represented in
a single coherent entity. Our empirical evaluation illustrates that
monitoring based on observed routine communications enables significant monitoring accuracy, while not being intrusive. The results
also demonstrate a key lesson: A combination of complementary
low-quality techniques is cheaper, and better, than a single, highly optimized monitoring approach.
2001_4_teamcore_agents01_deploy.pdf D. V. Pynadath and Milind Tambe. 2001. “
Revisiting Asimov's First Law: A Response to the Call to Arms .” In Intelligent Agents VIII Proceedings of the International workshop on Agents, theories, architectures and languages (ATAL'01).
AbstractThe deployment of autonomous agents in real applications promises
great benefits, but it also risks potentially great harm to humans who interact with
these agents. Indeed, in many applications, agent designers pursue adjustable
autonomy (AA) to enable agents to harness human skills when faced with the
inevitable difficulties in making autonomous decisions. There are two key shortcomings in current AA research. First, current AA techniques focus on individual
agent-human interactions, making assumptions that break down in settings with
teams of agents. Second, humans who interact with agents want guarantees of
safety, possibly beyond the scope of the agent’s initial conception of optimal AA.
Our approach to AA integrates Markov Decision Processes (MDPs) that are applicable in team settings, with support for explicit safety constraints on agents’
behaviors. We introduce four types of safety constraints that forbid or require
certain agent behaviors. The paper then presents a novel algorithm that enforces
obedience of such constraints by modifying standard MDP algorithms for generating optimal policies. We prove that the resulting algorithm is correct and present
results from a real-world deployment.
2001_9_teamcore_atal01_asimov.pdf H. Jung and Milind Tambe. 2001. “
Towards Argumentation as Distributed Constraint Satisfaction .” In AAAI Fall Symposium 2001 on Agent Negotiation.
AbstractConflict resolution is a critical problem in distributed and collaborative multi-agent systems. Negotiation via argumentation (NVA), where agents provide explicit arguments (justifications) for their proposals to resolve conflicts, is an effective approach to resolve conflicts. Indeed, we are applying argumentation in some real-world multi-agent applications. However, a key problem in such applications is that
a well-understood computational model of argumentation is
currently missing, making it difficult to investigate convergence and scalability of argumentation techniques, and to understand and characterize different collaborative NVA strategies in a principled manner. To alleviate these difficulties,
we present distributed constraint satisfaction problem (DCSP)
as a computational model for NVA. We model argumentation
as constraint propagation in DCSP. This model enables us to
study convergence properties of argumentation, and formulate and experimentally compare two sets of 16 different NVA
strategies (over 30 strategies in all) with different levels of
agent cooperativeness towards others. One surprising result
from our experiments is that maximizing cooperativeness is
not necessarily the best strategy even in a completely cooperative environment. In addition to their usefulness in understanding computational properties of argumentation, these results could also provide new heuristics for speeding up DCSPs.
2001_3_teamcore_aaai_fallsymp01.pdf