Publications by Year: 2001

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.Abstract
With 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.Abstract
Gaining 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).Abstract
Through adjustable autonomy (AA), an agent can dynamically vary the degree to which it acts autonomously, allowing it to exploit human abilities to improve its performance, but without becoming overly dependent and intrusive 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).Abstract
Conflict 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).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 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).Abstract
The operation of a human organization requires dozens of everyday tasks to ensure coherence in organizational activities, to monitor the status of such activities, to gather information relevant to the organization, to keep everyone in the organization informed, etc. Teams of software agents can aid humans in accomplishing these tasks, facilitating the organization’s coherent functioning and rapid response to crises, while reducing the burden on humans. Based on this vision, this paper reports on Electric Elves, a system that has been operational, 24/7, at our research institute since June 1, 2000. Tied to individual user workstations, fax machines, voice, mobile devices such as cell phones and palm pilots, Electric Elves has assisted us in routine tasks, such as rescheduling meetings, selecting presenters for research meetings, tracking people’s locations, organizing lunch meetings, etc. We discuss the underlying AI technologies that led to the success of Electric Elves, including technologies devoted to agenthuman interactions, agent coordination, accessing multiple heterogeneous information sources, dynamic assignment of organizational tasks, and deriving information about organization members. We also report the results of deploying Electric Elves in our own research organization.
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.Abstract
Research 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).Abstract
Recent 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).Abstract
The 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.Abstract
Conflict 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