Publications by Year: 1998

1998
Z. Qiu and Milind Tambe. 1998. “Flexible Negotiations in Teamwork: Extended Abstract .” In AAAI Fall Symposium on Distributed Continual Planning.Abstract
In a complex, dynamic multi-agent setting, coherent team actions are often jeopardized by agents' conflicting beliefs about different aspects of their environment, about resource availability, and about their own or teammates' capabilities and performance. Team members thus need to communicate and negotiate to restore team coherence. This paper focuses on the problem of negotiations in teamwork to resolve such conflicts. The basis of such negotiations is inter-agent argumentation (based on Toulmin's argumentation structure), where agents assert their beliefs to others, with supporting arguments. One key novelty in our work is that agents' argumentation exploits previous research on general, explicit teamwork models. Based on such teamwork models, it is possible categorize the conflicts that arise into different classes, and more importantly provide a generalized and reusable argumentation facility based on teamwork constraints. Our approach is implemented in a system called CONSA (COllaborative Negotiation System based on Argumentation).
1998_6_teamcore_fss98.pdf
Milind Tambe. 1998. “Implementing agent teams in dynamic multi-agent environments .” Applied Artificial Intelligence 12, Pp. 189-210.Abstract
Teamwork is becoming increasingly critical in multi-agent environments ranging from virtual environments for training and education, to information integration on the internet, to potential multi-robotic space missions. Teamwork in such complex, dynamic environments is more than a simple union of simultaneous individual activity, even if supplemented with preplanned coordination. Indeed in these dynamic environments, unanticipated events can easily cause a breakdown in such preplanned coordination. The central hypothesis in this article is that for effective teamwork, agents should be provided explicit representation of team goals and plans, as well as an explicit representation of a model of teamwork to support the execution of team plans. In our work, this model of teamwork takes the form of a set of domain independent rules that clearly outline an agent’s commitments and responsibilities as a participant in team activities, and thus guide the agent’s social activities while executing team plans. This article describes two implementations of agent teams based on the above principles, one for a real-world helicopter combat simulation, and one for the RoboCup soccer simulation. The article also provides a preliminary comparison of the two agent-teams to illustrate some of the strengths and weaknesses of RoboCup as a common testbed for multi-agent systems.
1998_1_teamcore_aai.pdf
1998. “Social comparison for failure detection and recovery .” In Intelligent Agents IV: Agents, Theories, Architectures and Languages (ATAL). Springer Verlag.Abstract
Plan execution monitoring in dynamic and uncertain domains is an important and difficult problem. Multi-agent environments exacerbate this problem, given that interacting and coordinated activities of multiple agents are to be monitored. Previous approaches to this problem do not detect certain classes of failures, are inflexible, and are hard to scale up. We present a novel approach, SOCFAD, to failure detection and recovery in multi-agent settings. SOCFAD is inspired by Social Comparison Theory from social psychology and includes the following key novel concepts: (a) utilizing other agents in the environment as information sources for failure detection, (b) a detection and repair method for previously undetectable failures using abductive inference based on other agents’ beliefs, and (c) a decision-theoretic approach to selecting the information acquisition medium. An analysis of SOCFAD is presented, showing that the new method is complementary to previous approaches in terms of classes of failures detected.
1998_2_teamcore_atal97fin.pdf
Milind Tambe, W. L. Johnson, and W. Shen. 1998. “Adaptive agent tracking in real-world multi-agent domains: a preliminary report.” International Journal of Human-Computer Studies, 48, Pp. 105-124.Abstract
In multi-agent environments, the task of agent tracking (i.e., tracking other agents’ mental states) increases in difficulty when a tracker (tracking agent) only has an imperfect model of the trackee (tracked agent). Such model imperfections arise in many realworld situations, where a tracker faces resource constraints and imperfect information, and the trackees themselves modify their behaviors dynamically. While such model imperfections are unavoidable, a tracker must nonetheless attempt to be adaptive in its agent tracking. In this paper, we analyze some key issues in adaptive agent tracking, and describe an initial approach based on discrimination-based learning. The main idea is to identify the deficiency of a model based on prediction failures, and revise the model by using features that are critical in discriminating successful and failed episodes. Our preliminary experiments in simulated air-to-air combat environments have shown some promising results but many problems remain open for future research.
1998_9_teamcore_adaptive.pdf
G. Kaminka and M. Tambe. 1998. “Agent component synergy: Social comparison for failure detection.” In Second International Conference on Autonomous Agents (Agents).Abstract
Recently, encouraging progress has been made in integrating independent components in complete agents for real-world environments. While such systems demonstrate component integration, they often do not explicitly utilize synergistic interactions, which allow each component to function beyond its original capabilities because of the presence of other components. This abstract presents an implemented illustration of such explicit component synergy and its usefulness in dynamic multi-agent environments. In such environments, agents often have three important abilities: (a) collaboration with other agents (teamwork), (b) monitoring the agent’s own progress (execution monitoring), and (c) modeling other agents’ beliefs/goals (agent-modeling). Generally, these capabilities are independently developed, and are integrated in a single system such that each component operates independently of the others, e.g., monitoring techniques do not take into account the modeled plans of other agents, etc. In contrast, we highlight a synergy between these three agent components that results in significant improvement in capabilities of each component: (a) The collaboration component constrains the search space for the agentmodeling component via maintenance of mutual beliefs and facilitates better modeling, (b) the modeling and collaboration components enable SOCFAD (Social Comparison for Failure Detection), a novel execution monitoring technique which uses other agents to detect and diagnose failures (the focus of this abstract), and (c) the monitoring component, using SOCFAD, detects failures in individual performance that affect coordination, and allows the collaboration component to replan. SOCFAD addresses the well known problem of agent execution monitoring in complex dynamic environments, e.g., [4]. This problem is exacerbated in multi-agent environments due to the added requirements for coordination. The complexity and unpredictability of these environments causes an explosion of state space complexity, which inhibits the ability of any designer to enumerate the correct response in each possible state in advance. For instance, it is generally difficult to predict when communication message will get lost, sensors return unreliable answers, etc. The agents are therefore presented with countless opportunities for failure, and must autonomously detect them and recover. To detect failures, an agent must have information about the ideal behavior expected of it. This ideal is compared to the agent’s actual behavior to detect discrepancies indicating possible failure. Previous approaches to this problem (e.g., [4]) have focused on the designer or planner supplying the agent with redundant information, either in the form of explicitly specified execution-monitoring conditions, or a model of the agent itself which may be used for comparison. While powerful in themselves, these approaches have limitations which render them insufficient in dynamic multi-agent environments: (a) They fail to take into account information from sensors that monitor other agents, and are thus less robust. For example, a driver may not see an obstacle on the road, but if she sees another car swerve, she can infer the presence of the obstacle; (b) Monitoring conditions on agent behavior can be too rigid in highly dynamic environments, as agents must often adjust their behavior flexibly to respond to actual circumstances; and (c) Both approaches require the designer to supply redundant information, which entails further work for the designer, and encounters difficulties in scaling up to more complex domains. We propose a novel complementary approach to failure detection and recovery, which is unique to multi-agent settings. This approach, SOCFAD, is inspired by ideas from Social Comparison Theory [1], a theory from social psychology. The key idea in SOCFAD is that agents use other agents as information sources on the situation and the ideal behavior. The agents compare their own behavior, beliefs, goals, and plans to those of other agents, in order to detect failures and correct their behavior. The agents do not necessarily adapt the other agents’ beliefs, but can reason about the differences in belief and behavior, and draw useful conclusions regarding the correctness of their own actions. This approach alleviates the problems described above: (a) It allows relevant information to be inferred from other agents’ behavior and used to complement the agent’s own erroneous perceptions, (b) It allows for flexibility in monitoring, since the flexible behavior of other agents is used as an ideal, and (c) It doesn’t require the designer to provide the agent with redundant information, utilizing instead other agents as information sources. Teamwork or collaboration is ubiquitous in multi-agent domains. An important issue in SOCFAD is that the agents being compared should be socially similar to yield meaningful differences. By exploiting the synergy with the collaboration component, SOCFAD constrains the search for socially-similar agents to team-members only. Furthermore, the collaboration component is able to provide SOCFAD with guarantees on other agents’ behaviors (through mutual beliefs) which are exploited to generate confidence in any detected failures. By exploiting the agent-modeling component’s capacity to infer team members’ goals, SOCFAD enables efficient comparison without significant communication overhead. Knowledge of other agents can be communicated. However, such communication is often impractical given costs, risk in hostile territories, and unreliability in uncertain settings. Our implementation of SOCFAD relies instead on the agent modeling component that infers an agent’s beliefs, goals, and plans from its observable behavior and surroundings for comparison.
1998_12_teamcore_agents98poster.pdf
A. Drogoul, Milind Tambe, and T. Fukuda. 1998. Collective Robotics Workshop: Lecture notes in Artificial Intelligence 1456. Berlin: Springer Verlag. Publisher's Version
Milind Tambe, J. Adibi, Y. Alonaizan, A. Erdem, Gal Kaminka, S. Marsella, I. Muslea, and M. Tallis. 1998. “ISIS: Using an explicit model of teamwork in RoboCup 97.” In First robot world cup competition and conferences. Springer Verlag.Abstract
bstract Team ISIS ISI Synthetic successfully participated in the rst international RoboCup soccer tournament RoboCup held in Nagoya Japan in August ISIS won the thirdplace prize in over teams that participated in the simulation league of RoboCup the most popular among the three RoboCup leagues In terms of re search accomplishments ISIS illustrated the usefulness of an explicit model of teamwork both in terms of reduced development time and im proved teamwork exibility ISIS also took some initial steps towards learning of individual player skills This paper discusses the design of ISIS in detail with particular emphasis on its novel approach to tea
1998_8_teamcore_robocup_inai.pdf
Gal Kaminka, Milind Tambe, and C. Hopper. 1998. “The role of agent modeling in agent robustness.” In Conference on AI meets the real-world.Abstract
A key challenge in using intelligent systems in complex, dynamic, multi-agent environments is the attainment of robustness in face of uncertainty. In such environments the combinatorial nature of state-space complexity inhibits any designer’s ability to anticipate all possible states that the agent might find itself in. Therefore, agents will fail in such environments, as the designer cannot supply them with full information about the correct response to take at any state. To overcome these failures, agents must display post-failure robustness, enabling them to autonomously detect, diagnose and recover from failures as they happen. Our hypothesis is that through agent-modeling (the ability of an agent to model the intentions, knowledge, and actions of other agents in the environment) an agent may significantly increase its robustness in a multi-agent environment, by allowing it to use others in the environment to evaluate and improve its own performance. We examine this hypothesis in light of two real-world applications in which we improve robustness: domain-independent teamwork, and target-recognition and identification systems. We discuss the relation between the ability of an agent-modeling algorithm to represent uncertainty and the applications, and highlight key lessons learned for real-world applications.
1998_5_teamcore_aimtrwcr.pdf
R. Hill, J. Chen, J. Gratch, P. Rosenbloom, and M. Tambe. 1998. “Soar-RWA: Planning, teamwork, and intelligent behavior for synthetic rotary wing aircraft.” In Seventh Conference on Computer Generated Forces and Behavioral Representation.Abstract
We have constructed a team of intelligent agents that perform the tasks of an Army attack helicopter company and a Marine transport/escort combined team for a synthetic battlefield environment used for running largescale military exercises. We have used the Soar integrated architecture to develop: (1) pilot agents for a company of helicopters, (2) a command agent that makes decisions and plans for the helicopter company, and (3) an approach to teamwork that enables the pilot agents to coordinate their activities in accomplishing the goals of the company. This case study describes the task domain and architecture of our application, as well as the benefits and lessons learned from applying AI technology to this domain.
1998_11_teamcore_cgf_98.pdf
Milind Tambe and W. Zhang. 1998. “Towards flexible teamwork in persistent teams.” In International conference on multi-agent systems (ICMAS).Abstract
In a complex, dynamic multi-agent setting, coherent team actions are often jeopardized by agents' conflicting beliefs about different aspects of their environment, about resource availability, and about their own or teammates' capabilities and performance. Team members thus need to communicate and negotiate to restore team coherence. This paper focuses on the problem of negotiations in teamwork to resolve such conflicts. The basis of such negotiations is inter-agent argumentation (based on Toulmin's argumentation structure), where agents assert their beliefs to others, with supporting arguments. One key novelty in our work is that agents' argumentation exploits previous research on general, explicit teamwork models. Based on such teamwork models, it is possible categorize the conflicts that arise into different classes, and more importantly provide a generalized and reusable argumentation facility based on teamwork constraints. Our approach is implemented in a system called CONSA (COllaborative Negotiation System based on Argumentation).
1998_7_teamcore_icmas98.pdf
S. Marsella, J. Adibi, Y. Alonaizan, A. Erdem, R. Hill, Gal Kaminka, Milind Tambe, and Q Zhun. 1998. “Using an Explicit Teamwork Model and Learning in RoboCup: An Extended Abstract RoboCup 98.” In Second robot world cup competition and conferences. Springer Verlag.Abstract
duction The RoboCup research initiative has established synthetic and robotic soccer as testbeds for pursuing research challenges in Articial Intelligence and robotics This extended abstract focuses on teamwork and learning two of the multi agent research challenges highlighted in RoboCup To address the challenge of teamwork we discuss the use of a domainindependent explicit model of team work and an explicit representation of team plans and goals We also discuss the application of agent learning in RoboCup The vehicle for our research investigations in RoboCup is ISIS ISI Synthetic a team of synthetic soccerplayers that successfully participated in the simula tion league of RoboCup by winning the third place prize in that tournament In this position paper we brie y overview the ISIS agent architecture and our investigations of the issues of teamwork and learning The key novel issues for our team in RoboCup will be a further investigation of agent learning and further analysis of teamwork related issues
1998_10_teamcore_robocup_inai_2.pdf
Gal Kaminka and Milind Tambe. 1998. “What is wrong with us? Improving robustness through social diagnosis.” In National conference on Artificial Intelligence (AAAI).Abstract
Robust behavior in complex, dynamic environments mandates that intelligent agents autonomously monitor their own run-time behavior, detect and diagnose failures, and attempt recovery. This challenge is intensified in multiagent settings, where the coordinated and competitive behaviors of other agents affect an agent’s own performance. Previous approaches to this problem have often focused on single agent domains and have failed to address or exploit key facets of multi-agent domains, such as handling team failures. We present SAM, a complementary approach to monitoring and diagnosis for multi-agent domains that is particularly well-suited for collaborative settings. SAM includes the following key novel concepts: First, SAM’s failure detection technique, inspired by social psychology, utilizes other agents as information sources and detects failures both in an agent and in its teammates. Second, SAM performs social diagnosis, reasoning about the failures in its team using an explicit model of teamwork (previously, teamwork models have been employed only in prescribing agent behaviors in teamwork). Third, SAM employs model sharing to alleviate the inherent inefficiencies associated with representing multiple agent models. We have implemented SAM in a complex, realistic multi-agent domain, and provide detailed empirical results assessing its benefits.
1998_4_teamcore_aaai98.pdf