Publications

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
1997
Milind Tambe. 1997. “Agent architectures for flexible, practical teamwork .” In National Conference on Artificial Intelligence (AAAI-97) .Abstract
Teamwork in complex, dynamic, multi-agent domains mandates highly flexible coordination and communication. Simply fitting individual agents with precomputed coordination plans will not do, for their inflexibility can cause severe failures in teamwork, and their domain-specificity hinders reusability. Our central hypothesis is that the key to such flexibility and reusability is agent architectures with integrated teamwork capabilities. This fundamental shift in agent architectures is illustrated via an implemented candidate: STEAM. While STEAM is founded on the joint intentions theory, practical operationalization has required it to integrate several key novel concepts: (i) team synchronization to establish joint intentions; (ii) constructs for monitoring joint intentions and repair; and (iii) decision-theoretic communication selectivity (to pragmatically extend the joint intentions theory). Applications in three different complex domains, with empirical results, are presented.1
1997_3_teamcore_draft.pdf
Milind Tambe. 1997. “Towards Flexible Teamwork .” Journal of Artificial Intelligence Research, 7, Pp. 83-124.Abstract
Many AI researchers are today striving to build agent teams for complex, dynamic multi-agent domains, with intended applications in arenas such as education, training, entertainment, information integration, and collective robotics. Unfortunately, uncertainties in these complex, dynamic domains obstruct coherent teamwork. In particular, team members often encounter diering, incomplete, and possibly inconsistent views of their environment. Furthermore, team members can unexpectedly fail in fullling responsibilities or discover unexpected opportunities. Highly exible coordination and communication is key in addressing such uncertainties. Simply tting individual agents with precomputed coordination plans will not do, for their inexibility can cause severe failures in teamwork, and their domain-specicity hinders reusability. Our central hypothesis is that the key to such exibility and reusability is providing agents with general models of teamwork. Agents exploit such models to autonomously reason about coordination and communication, providing requisite exibility. Furthermore, the models enable reuse across domains, both saving implementation eort and enforcing consistency. This article presents one general, implemented model of teamwork, called STEAM. The basic building block of teamwork in STEAM is joint intentions (Cohen & Levesque, 1991b); teamwork in STEAM is based on agents' building up a (partial) hierarchy of joint intentions (this hierarchy is seen to parallel Grosz & Kraus's partial SharedPlans, 1996). Furthermore, in STEAM, team members monitor the team's and individual members' performance, reorganizing the team as necessary. Finally, decision-theoretic com- munication selectivity in STEAM ensures reduction in communication overheads of team- work, with appropriate sensitivity to the environmental conditions. This article describes STEAM's application in three dierent complex domains, and presents detailed empirical results.
1997_4_teamcore_jair.pdf
R. Hill, J. Chen, J. Gratch, P. S. Rosenbloom, and Milind Tambe. 1997. “Intelligent agents for the synthetic battlefield: A company of rotary wing aircraft.” Innovative Applications of Artificial Intelligence (IAAI-97).Abstract
We have constructed a team of intelligent agents that perform the tasks of an attack helicopter company 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.
1997_1_teamcore_iaai.pdf
H. Kitano, Milind Tambe, P. Stone, M. Veloso, S. Coradeschi, E. Osawa, H. Matsubara, I. Noda, and M. Asada. 1997. “The RoboCup Synthetic Agent Challenge 97.” International Joint Conference on Artificial Intelligence (IJCAI97).Abstract
RoboCup Challenge oers a set of challenges for intelligent agent researchers using a friendly competition in a dynamic, real-time, multi-agent domain: synthetic Soccer. While RoboCup in general envisions longer range challenges over the next few decades, RoboCup Challenge presents three specic challenges for the next two years: (i) learning of individual agents and teams; (ii) multi-agent team planning and plan-execution in service of teamwork; and (iii) opponent modeling. RoboCup Challenge provides a novel opportunity for researchers in planning and multi-agent arenas | it not only supplies them a concrete domain to evalute their techniques, but also challenges them to evolve these techniques to face key constraints fundamental to this domain: real-time and teamwork.
1997_2_teamcore_ijcai.pdf
1996
M. Tambe, W. L. Johnson, and W. Shen. 1996. “ Adaptive agent tracking in real-world multiagent domains: A preliminary report.” In AAAI Spring Symposium on Adaptation, Coevolution and Learning in Multiagent Systems.Abstract
In multi-agent environments, the task of agent track-ing (i.e., tracking other agents’ mental states) in-creases in difficulty when a tracker (tracking agent)only has an imperfect model of the trackee (trackedagent). Such model imperfections arise in many real-world situations, where a tracker faces resource con-straints and imperfect information, and the trackeesthemselves modify their behaviors dynamically. Whilesuch model imperfections are unavoidable, a trackermust nonetheless attempt to be adaptive in its agenttracking. In this paper, we analyze some key issuesin adaptive agent tracking, and describe an initial ap-proach based on discrimination-based learning. Themain idea is to identify the deficiency of a model basedon prediction failures, and revise the model by usingfeatures that are critical in discriminating successfuland failed episodes. Our preliminary experiments insimulated air-to-air combat environments have shownsome promising results but many problems remainopen for future research.
1996_8_teamcore_ss96_01_018.pdf
Milind Tambe and P. S. Rosenbloom. 1996. “Event tracking in a dynamic multi-agent environment.” Computational Intelligence 12.Abstract
This paper focuses on event tracking in one complex and dynamic multi-agent environment: the air-combat simulation environment. It analyzes the challenges that an automated pilot agent must face when tracking events in this environment. This analysis reveals three new issues that have not been addressed in previous work in this area: (i) tracking events generated by agents' flexible and reactive behaviors, (ii) tracking events in the context of continuous agent interactions, and (iii) tracking events in real-time. The paper proposes one solution to address these issues. One key idea in this solution is that the (architectural) mechanisms that an agent employs in generating its own flexible and reactive behaviors can be used to track other agents' flexible and reactive behaviors in real-time. A second key idea is the use of a world-centered representation for modeling agent interactions. The solution is demonstrated using an implementation of an automated pilot agent.
1996_4_teamcore_final3.pdf
Milind Tambe. 1996. “ Executing Team Plans in Dynamic Multi-agent environments.” In AAAI Fall Symposium on Plan Execution.Abstract
This paper focuses on flexible teamwork in dynamic and real-world multi-agent domains. Such teamwork is not simply a union of agents’ simultaneous execution of individual plans,even if such execution pre-coordinated. Indeed, uncertain-ties in complex, dynamic domains often obstruct pre-plannedcoordination, with a resultant breakdown in teamwork. Thecentral hypothesis in this paper is that for durable teamwork,agents should be provided explicit team plans, which directlyexpress a team’s joint activities. When agents execute such team plans, they abide by certain "commonsense" conventions of teamwork. Essentially, such conventions providea deeper model of teamwork, facilitating flexible reasoningabout coordination activities. Such a framework also frees the planner or the knowledge engineer from specifying very detailed low-level coordination plans. This framework has been implemented in the context of a real-world synthetic environment for helicopter-combat simulation.
1996_2_teamcore_team_plan2_final.pdf
1996. Intelligent Agents: Vol II, Workshop on Agents, theories, architectures and languages (ATAL-95). Publisher's VersionAbstract
This book is based on the second International Workshop on Agent Theories, Architectures, and Languages, held in conjunction with the International Joint Conference on Artificial Intelligence, IJCAI'95 in Montreal, Canada in August 1995.
The 26 papers are revised final versions of the workshop presentations selected from a total of 54 submissions; also included is a comprehensive introduction, a detailed bibliography listing 355 relevant publications, and a subject index. The book is structured into seven sections, reflecting the most current major directions in agent-related research. Together with its predecessor, Intelligent Agents, published as volume 890 in the LNAI series, this book provides a timely and comprehensive state-of-the-art report.

Pages