Publications

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.

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.

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.

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

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.

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.

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.

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.

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.

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.

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 standalone systems. This has led to an increasing interest in integration architectures that enable a heterogeneous variety of agents and humansto work together. These agents and humans differ in their capabilities, preferences, the level of autonomy they are willing to grant the integration architecture and their information requirements and performance. The challenge in coordinating such a diverse agentset isthat potentially a large number of domain-specific and agentspecific coordination plans may be required. We present a novel two-tiered approach to address this coordination problem. We first provide the integration architecture with general purpose teamwork coordination capabilities, but then enable adaptation of such capabilities for the needs or requirements of specific individuals. A key novel aspect of this adaptation is that it takes place in the context of other heterogeneous team members. We are realizing this approach in an implemented distributed agent integration architecture called Teamcore. Experimental results from two different domains are presented.

With the growing importance of multi-agent teamwork, tools that can help humans analyze, evaluate, and understand team behaviors are becoming increasingly important as well. To this end, we are creating ISAAC, a team analyst agent for post-hoc, off-line agentteam analysis. ISAAC's novelty stems from a key design constraint that arises in team analysis: multiple types of models of team behavior are necessary to analyze different granularities of team events, including agent actions, interactions, and global performance. These heterogeneous team models are automatically acquired 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. This paper presents ISAAC's general conceptual framework and its application in the RoboCup soccer domain, where ISAAC was awarded the RoboCup scientific challenge award.

Multi-agent teamwork is critical in a large number of agent applications, including training, education, virtual enterprises and collective robotics. Tools that can help humans analyze, evaluate, and understand team behaviors are becoming increasingly important as well. We have taken a step towards building such a tool by creating an automated analyst agent called ISAAC for post-hoc, off-line agent-team analysis. ISAAC’s novelty stems from a key design constraint that arises in team analysis: multiple types of models of team behavior are necessary to analyze different granularities of team events, including agent actions, interactions, and global performance. These heterogeneous team models are automatically acquired 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. This paper presents ISAAC’s general conceptual framework, motivating its design, as well as its concrete application in the domain of RoboCup soccer. In the RoboCup domain, ISAAC was used prior to and during the RoboCup’99 tournament, and was awarded the RoboCup scientific challenge award.

With the promise of agent-based systems, a variety of research/industrial groups are developing autonomous, heterogeneous agents, that are distributed over a variety of platforms and environments in cyberspace. Rapid integration of such distributed, heterogeneous agents would enable software to be rapidly developed to address large-scale problems of interest. Unfortunately, rapid and robust integration remains a difficult challenge. To address this challenge, we are developing a novel teamwork-based agent integration framework. In this framework, software developers specify an agent organization called a team-oriented program. To recruit agents for this organization, an agent resources manager (an analogue of a “human resources manager”) searches the cyberspace for agents of interest to this organization, and monitors their performance over time. Agents in this organization are wrapped with TEAMCORE wrappers, that make them team ready, and thus ensure robust, flexible teamwork among the members of the newly formed organization. This implemented framework promises to reduce the software development effort in agent integration while providing robustness due to its teamwork-based foundations. A concrete, running example, based on heterogeneous, distributed agents is presented.

Multi-agent teamwork is a critical capability in a large number of applications. Yet, despite the considerable progress in teamwork research, the challenge of intra-team conflict resolution has remained largely unaddressed. This chapter presents a system called CONSA, to resolve conflicts using argumentation-based negotiations. The key insight in CONSA(COllaborative Negotiation System based on Argumentation) is to fully exploit the benefits of argumentation in a team setting. Thus, CONSA casts conflict resolution as a team problem, so that the recent advances in teamwork can be fully brought to bear during conflict resolution to improve argumentation flexibility. Furthermore, since teamwork conflicts often involve past teamwork, recently developed teamwork models can be exploited to provide agents with reusable argumentation knowledge. Additionally, CONSA also includes argumentation strategies geared towards benefiting the team rather than the individual, and techniques to reduce argumentation overhead. We present detailed algorithms used in CONSA and shows a detailed trace from CONSA’s implementations.

Teamwork is a critical capability in multiagent environments Many such en vironments mandate that the agents and agentteams must be persistent ie exist over long periods of time Agents in such persistent teams are bound together by their longterm common interests and goals This paper focuses on exible teamwork in such persistent teams Unfortunately while previous work has investigated exible teamwork persistent teams remain unexplored For exible teamwork one promising approach that has emerged is modelbased ie providing agents with general models of teamwork that explicitly specify their commitments in teamwork Such models enable agents to autonomously reason about coordination Unfortunately for persistent teams such models may lead to coordination and communication actions that while locally optimal are highly problematic for the teams longterm goals We present a decisiontheoretic technique based on Markov decision processes to enable persistent teams to over come such limitations of the modelbased approach In particular agents reason about expected team utilities of future team states that are pro jected to result from actions recommended by the teamwork model as well as lowercost or highercost variations on these actions To accomodate realtime constraints this reasoning is done in an anytime fashion Implemented examples from an analytic search tree and some realworld domains are presented.

Future large-scale human organizations will be highly agentized, with software agents supporting the traditional tasks of information gathering, planning, and execution monitoring, as well as having increased control of resources and devices (communication and otherwise). As these heterogeneous software agents take on more of these activities, they will face the additional tasks of interfacing with people and sometimes acting as their proxies. Dynamic teaming of such heterogeneous agents will enable organizations to act coherently, to robustly attain their mission goals, to react swiftly to crises, and to dynamically adapt to events. Advances in this agentization could potentially assist all organizations, including the military, civilian disaster response organizations, corporations, and universities and research institutions. Within an organization, we envision that agent-based technology will facilitate (and sometimes supervise) all collaborative activities. For a research institution, agentization may facilitate such activities as meeting organization, paper composition, software development, and deployment of people and equipment for out-of-town demonstrations. For a military organization, agentization may enable the teaming of military units and equipment for rapid deployment, the monitoring of the progress of such deployments, and the rapid response to any crises that may arise. To accomplish such goals, we envision the presence of agent proxies for each person within an organization. Thus, for instance, if an organizational crisis requires an urgent deployment of a team of people and equipment, then agent proxies could dynamically volunteer for team membership on behalf of the people or resources they represent, while also ensuring that the selected team collectively possesses sufficient resources and capabilities. The proxies must also manage efficient transportation of such resources, the monitoring of the progress of individual participants and of the mission as a whole, and the execution of corrective actions when goals appear to be endangered. The complexity inherent in human organizations complicates all of these tasks and provides a challenging research testbed for agent technology. First, there is the key research question of adjustable autonomy. In particular, agents acting as proxies for people must automatically adjust their own autonomy, e.g., avoiding critical errors, possibly by letting people make important decisions while autonomously making the more routine decisions. Second, human organizations operate continually over time, and the agents must operate continually as well. In fact, the agent systems must be up and running 24 hours a day 7 days a week (24/7). Third, people, as well as their associated tasks are very heterogeneous, having a wide and rich variety of capabilities, interests, preferences, etc. To enable teaming among such people for crisis response or other organizational tasks, agents acting as proxies must represent and reason with such capabilities and interests. We thus require powerful matchmaking capabilities to match two people with similar interests. Fourth, human organizations are often large, so providing proxies often means a big scale-up in the number of agents, as compared against typical multiagent systems in current operation. Our Electric Elves project is currently investigating the above research issues and the impact of agentization on human organizations in general, using our own Intelligent Systems Division of USC/ISI as a testbed. Within our research institution, we intend that our Electric Elves agent proxies automatically manage tasks such as: Select teams of researchers for giving a demonstration out of town, plan all of their travel arrangements and ship relevant equipment; also, resolve problems that come up during such a demonstration (e.g., a selected researcher becomes ill at the last minute) Determine the researchers interested in meeting with a visitor to our institute, and schedule meetings with the visitor Reschedule meetings if one or more users are absent or unable to arrive on time at a meeting Monitor the location of users and keep others informed (within privacy limits) about their whereabouts This short paper presents an overview of our project, as space limitations preclude a detailed discussion of the research issues and operation of the current system. We do have a working prototype of about 10 agent proxies running almost continuously, managing the schedules of one research group. In the following section, we first present an overview of the agent organization, which immerses several heterogeneous agents and sets of agents within the existing human organization of our division. Following that, we describe the current state of the system, and then conclude.

Agents in complex, dynamic, multi-agent environments face uncertainty in the execution of their tasks, as their sensors, plans, and actions may fail unexpectedly, e.g., the weather may render a robots camera useless, its grip too slippery, etc. The explosive number of states in such environments prohibits any resource-bounded designer from predicting all failures at design time. This situation is exacerbated in multi-agent settings, where interactions between agents increase the complexity. For instance, it is difficult to predict an opponent's behavior. Agents in such environments must therefore rely on runtime execution monitoring and diagnosis to detect a failure, diagnose it, and recover. Previous approaches have focused on supplying the agent with goal-attentive knowledge of the ideal behavior expected of the agent with respect to its goals. These approaches encounter key pitfalls and fail to exploit key opportunities in multi-agent settings: (a) only a subset of the sensors (those that measure achievement of goals) are used, despite other agents' sensed behavior that can be used to indirectly sense the environment or complete the agent's knowledge; (b) there is no monitoring of social relationships that must be maintained between the agents regardless of achievement of the goal (e.g., teamwork); and (c) there is no recognition of failures in others, though these change the ideal behavior expected of an agent (for instance, assisting a failing teammate). To address these problems, we investigate a novel complementary paradigm for multi-agent monitoring and diagnosis. Socially-Attentive Monitoring (SAM) focuses on monitoring the social relationships between the agents as they are executing their tasks, and uses models of multiple agents and their relationships in monitoring and diagnosis. We hypothesize that failures to maintain relationships would be indicative of failures in behavior, and diagnosis of relationships can be used to complement goal-attentive methods. In particular, SAM addresses the weaknesses listed above: (a) it allows inference of missing knowledge and sensor readings through other agents' sensed behavior; (b) it directly monitors social relationships, with no attention to the goals; and (c) it allows recognition of failures in others (even if they are not using SAM!). SAM currently uses the STEAM teamwork model, and a role-similarity relationship model to monitor agents. It relies on plan-recognition to infer agents' reactive-plan hierarchies from their observed actions. These hierarchies are compared in a top-down fashion to find relationship violations, e.g., cases where two agents selected different plans despite their being on the same team. Such detections trigger diagnosis which uses the relationship models to facilitate recovery. For example, in teamwork, a commitment to joint selection of plans further mandates mutual belief in preconditions. Thus a difference in selected plans may be explained by a difference in preconditions, and can lead to recovery using negotiations. We empirically and analytically investigate SAM in two dynamic, complex, multi-agent domains: the ModSAF battlefield simulation, where SAM is employed by helicopter pilot agents; and the RoboCup soccer simulation where SAM is used by a coach agent to monitor teams' behavior. We show that SAM can capture failures that are otherwise undetectable, and that distributed monitoring is better (correct and complete) detection) and simpler (no representation of ambiguity) than a centralized scheme (complete and incorrect, requiring representation of ambiguity). Key contributions and novelties include: (a) a general framework for socially-attentive monitoring, and a deployed implementation for monitoring teamwork; (b) rigorously proven guarantees on the applicability and results of practical socially-attentive monitoring of teamwork under conditions of uncertainty; (c) procedures for diagnosis based on a teamwork relationship model. Future work includes the use of additional relationship models in monitoring and diagnosis, formalization of the social diagnosis capabilities, and further demonstration of SAM's usefulness in current domains and others.

tract Increasingly multiagent systems are being designed for a variety of complex dynamic domains Eective agent interactions in such domains raise some of the most fundamental research challenges for agentbased systems in teamwork multiagent learning and agent modelling The RoboCup research initiative particularly the simulation league has been proposed to pursue such multiagent research challenges using the common testbed of simulation soccer Despite the significant popularity of RoboCup within the research community general lessons have not often been extracted from participation in RoboCup This is what we attempt to do here We have elded two teams ISIS and ISIS in RoboCup competitions These teams have been in the top four teams in these competitions We compare the teams and attempt to analyze and generalize the lessons learned This analysis reveals several surprises pointing out lessons for teamwork and for multi-agent learning.

The Robot World Cup Soccer Games and Conferences (RoboCup) are a series of competitions and events designed to promote the full integration of AI and robotics research. Following the first RoboCup, held in Nagoya, Japan, in 1997, RoboCup-98 was held in Paris from 2–9 July, overlapping with the real World Cup soccer competition. RoboCup-98 included competitions in three leagues: (1) the simulation league, (2) the real robot small-size league, and (3) the real robot middle- size league. Champion teams were CMUNITED-98 in both the simulation and the real robot smallsize leagues and CS-FREIBURG (Freiburg, Germany) in the real robot middle-size league. RoboCup-98 also included a Scientific Challenge Award, which was given to three research groups for their simultaneous development of fully automatic commentator systems for the RoboCup simulator league. Over 15,000 spectators watched the games, and 120 international media provided worldwide coverage of the competition.