2002
D. V. Pynadath and Milind Tambe. 2002. “
Multiagent teamwork: Analyzing key teamwork theories and models.” In First Autonomous Agents and Multiagent Systems Conference (AAMAS).
AbstractDespite the significant progress in multiagent teamwork, existing research
does not address the optimality of its prescriptions nor the complexity of the
teamwork problem. Thus, we cannot determine whether the assumptions
and approximations made by a particular theory gain enough efficiency
to justify the losses in overall performance. To provide a tool for evaluating this tradeoff, we present a unified framework, the COMmunicative
Multiagent Team Decision Problem (COM-MTDP) model, which is general enough to subsume many existing models of multiagent systems. We
analyze use the COM-MTDP model to provide a breakdown of the computational complexity of constructing optimal teams under problem domains
divided along the dimensions of observability and communication cost. We
then exploit the COM-MTDP’s ability to encode existing teamwork theories
and models to encode two instantiations of joint intentions theory, including STEAM. We then derive a domain-independent criterion for optimal
communication and provide a comparative analysis of the two joint intentions instantiations. We have implemented a reusable, domain-independent
software package based COM-MTDPs to analyze teamwork coordination
strategies, and we demonstrate its use by encoding and evaluating the two
joint intentions strategies within an example domain.
2002_13_teamcore_aamas02.pdf Ranjit Nair, T. Ito, Milind Tambe, and S. Marsella. 2002. “
Task allocation in the RoboCup Rescue simulation domain: A short note .” In International Symposium on RoboCup (RoboCup'01).
AbstractWe consider the problem of disaster mitigation in the RoboCup Rescue Simulation Environment [3] to be a task allocation problem where the tasks arrive
dynamically and can change in intensity. These tasks can be performed by ambulance teams, re brigades and police forces with the help of an ambulance
center, a re station and a police oce. However the agents don't get automatically notied of the tasks as soon as they arrive and hence it is necessary for the
agents to explore the simulated world to discover new tasks and to notify other
agents of these.
In this paper we focus on the problem of task allocation. We have developed
two approaches, a centralized combinatorial auction mechanism demonstrated
at Agents-2001 and a distributed method which helped our agents nish third
in RoboCup-Rescue 2001. With regard to task discovery, we use a greedy search
method to explore the world{ agents count the number of times they have visited
each node, and attempt to visit nodes that have been visited the least number
of times.
2002_1_teamcore_rescue.pdf D. V. Pynadath and Milind Tambe. 2002. “
Team coordination among distributed agents: Analyzing key teamwork theories and models .” In AAAI Spring Symposium on Intelligent Distributed and Embedded Systems.
AbstractMultiagent research has made significant progress in constructing teams
of distributed entities (e.g., robots, agents, embedded systems) that act
autonomously in the pursuit of common goals. There now exist a variety of prescriptive theories, as well as implemented systems, that can
specify good team behavior in different domains. However, each of
these theories and systems addresses different aspects of the teamwork
problem, and each does so in a different language. In this work, we
seek to provide a unified framework that can capture all of the common
aspects of the teamwork problem (e.g., heterogeneous, distributed entities, uncertain and dynamic environment), while still supporting analyses of both the optimality of team performance and the computational
complexity of the agents’ decision problem. Our COMmunicative Multiagent Team Decision Problem (COM-MTDP) model provides such
a framework for specifying and analyzing distributed teamwork. The
COM-MTDP model is general enough to capture many existing models
of multiagent systems, and we use this model to provide some comparative results of these theories. We also provide a breakdown of the
computational complexity of constructing optimal teams under various
classes of problem domains. We then use the COM-MTDP model to
compare (both analytically and empirically) two specific coordination
theories (joint intentions theory and STEAM) against optimal coordination, in terms of both performance and computational complexity.
2002_8_teamcore_springsymp_commtdp.pdf Ranjit Nair, Milind Tambe, and S. Marsella. 2002. “
Team formation for reformation .” In AAAI Spring Symposium on Intelligent Distributed and Embedded Systems.
AbstractThe utility of the multi-agent team approach for coordination of distributed agents has been demonstrated in a number of large-scale systems for sensing and acting like sensor
networks for real-time tracking of moving targets (Modi et
al. 2001) and disaster rescue simulation domains, such as
RoboCup Rescue Simulation Domain (Kitano et al. 1999;
Tadokoro et al. 2000) These domains contain tasks that can
be performed only by collaborative actions of the agents. Incomplete or incorrect knowledge owing to constrained sensing and uncertainty of the environment further motivate the
need for these agents to explicitly work in teams. A key precursor to teamwork is team formation, the problem of how
best to organize the agents into collaborating teams that perform the tasks that arise. For instance, in the disaster rescue
simulation domain, injured civilians in a burning building
may require teaming of two ambulances and three nearby
fire-brigades to extinguish the fire and quickly rescue the
civilians. If there are several such fires and injured civilians, the teams must be carefully formed to optimize performance.
Our work in team formation focuses on dynamic, realtime environments, such as sensor networks (Modi et al.
2001) and RoboCup Rescue Simulation Domain (Kitano
et al. 1999; Tadokoro et al. 2000). In such domains
teams must be formed rapidly so tasks are performed within
given deadlines, and teams must be reformed in response
to the dynamic appearance or disappearance of tasks. The
problems with the current team formation work for such
dynamic real-time domains are two-fold: i) most team
formation algorithms (Tidhar, Rao, & Sonenberg 1996;
Hunsberger & Grosz 2000; Fatima & Wooldridge 2001;
Horling, Benyo, & Lesser 2001; Modi et al. 2001) are static.
In order to adapt to the changing environment the static algorithm would have to be run repeatedly, ii) Team formation has largely relied on experimental work, without any
theoretical analysis of key properties of team formation algorithms, such as their worst-case complexity. This is especially important because of the real-time nature of the domains.
In this paper we take initial steps to attack both these problems. As the tasks change and members of the team fail, the
current team needs to evolve to handle the changes. In both
the sensor network domain (Modi et al. 2001) and RoboCup.
Rescue (Kitano et al. 1999; Tadokoro et al. 2000), each
re-organization of the team requires time (e.g., fire-brigades
may need to drive to a new location) and is hence expensive because of the need for quick response. Clearly, the
current configuration of agents is relevant to how quickly
and well they can be re-organized in the future. Each reorganization of the teams should be such that the resulting team is effective at performing the existing tasks but
also flexible enough to adapt to new scenarios quickly. We
refer to this reorganization of the team as ”Team Formation for Reformation”. In order to solve the “Team Formation for Reformation” problem, we present R-COM-MTDPs
(Roles and Communication in a Markov Team Decision
Process), a formal model based on communicating decentralized POMDPs, to address the above shortcomings. RCOM-MTDP significantly extends an earlier model called
COM-MTDP (Pynadath & Tambe 2002), by making important additions of roles and agents’ local states, to more
closely model current complex multiagent teams. Thus, RCOM-MTDP provides decentralized optimal policies to take
up and change roles in a team (planning ahead to minimize
reorganization costs), and to execute such roles.
R-COM-MTDPs provide a general tool to analyze roletaking and role-executing policies in multiagent teams. We
show that while generation of optimal policies in R-COMMTDPs is NEXP-complete, different communication and
observability conditions significantly reduce such complexity. In this paper, we use the disaster rescue domain to motivate the “Team Formation for Reformation” problem. We
present real world scenarios where such an approach would
be useful and use the RoboCup Rescue Simulation Environment (Kitano et al. 1999; Tadokoro et al. 2000) to explain
the working of our model.
2002_2_teamcore_r_com_mtdp_ss02.pdf Ranjit Nair, Milind Tambe, and S. Marsella. 2002. “
Team formation for reformation in multiagent domains like RoboCupRescue .” In International Symposium on RoboCup (RoboCup'02).
AbstractTeam formation, i.e., allocating agents to roles within a team
or subteams of a team, and the reorganization of a team upon team member failure or arrival of new tasks are critical aspects of teamwork. They
are very important issues in RoboCupRescue where many tasks need
to be done jointly. While empirical comparisons (e.g., in a competition
setting as in RoboCup) are useful, we need a quantitative analysis beyond the competition | to understand the strengths and limitations of
dierent approaches, and their tradeos as we scale up the domain or change domain properties. To this end, we need to provide complexityoptimality tradeos, which have been lacking not only in RoboCup but
in the multiagent eld in general.
To alleviate these diculties, this paper presents R-COM-MTDP, a formal model based on decentralized communicating POMDPs, where agents
explicitly take on and change roles to (re)form teams. R-COM-MTDP
signicantly extends an earlier COM-MTDP model, by introducing roles
and local states to better model domains like RoboCupRescue where
agents can take on dierent roles and each agent has a local state consisting of the ob jects in its vicinity. R-COM-MTDP tells us where the problem is highly intractable (NEXP-complete) and where it can be tractable
(P-complete), and thus understand where algorithms may need to tradeo optimality and where they could strive for near optimal behaviors.
R-COM-MTDP model could enable comparison of various team formation and reformation strategies | including the strategies used by our own teams that came in the top three in 2001 | in the RoboCup Rescue
domain and beyond.
2002_7_teamcore_robo_cup_rescue2002.pdf Paul Scerri, D. V. Pynadath, and Milind Tambe. 2002. “
Towards adjustable autonomy for the real-world .” Journal of AI Research (JAIR), 17, Pp. 171-228.
AbstractAdjustable autonomy refers to entities dynamically varying their own autonomy, transferring decision-making control to other entities (typically agents transferring control to
human users) in key situations. Determining whether and when such transfers-of-control
should occur is arguably the fundamental research problem in adjustable autonomy. Previous work has investigated various approaches to addressing this problem but has often
focused on individual agent-human interactions. Unfortunately, domains requiring collaboration between teams of agents and humans reveal two key shortcomings of these previous
approaches. First, these approaches use rigid one-shot transfers of control that can result in
unacceptable coordination failures in multiagent settings. Second, they ignore costs (e.g.,
in terms of time delays or eects on actions) to an agent's team due to such transfers-ofcontrol.
To remedy these problems, this article presents a novel approach to adjustable autonomy, based on the notion of a transfer-of-control strategy. A transfer-of-control strategy
consists of a conditional sequence of two types of actions: (i) actions to transfer decisionmaking control (e.g., from an agent to a user or vice versa) and (ii) actions to change an
agent's pre-specied coordination constraints with team members, aimed at minimizing
miscoordination costs. The goal is for high-quality individual decisions to be made with
minimal disruption to the coordination of the team. We present a mathematical model
of transfer-of-control strategies. The model guides and informs the operationalization of
the strategies using Markov Decision Processes, which select an optimal strategy, given an
uncertain environment and costs to the individuals and teams. The approach has been
carefully evaluated, including via its use in a real-world, deployed multi-agent system that
assists a research group in its daily activities.
2002_11_teamcore_jair_aa.pdf Paul Scerri, D. V. Pynadath, and Milind Tambe. 2002. “
Why the elf acted autonomously: Towards a theory of adjustable autonomy .” In First Autonomous Agents and Multiagent Systems Conference (AAMAS).
AbstractAdjustable autonomy refers to agents' dynamically varying their own autonomy, transferring decision making control to other entities (typically human users) in key situations. Determining whether and when such transfer of control must occur is arguably the fundamental research question in adjustable autonomy. Practical systems have made significant in-roads in answering this question and in providing high-level guidelines for transfer of control decisions. For instance, [11] report that Markov decision processes were successfully used in transfer of control decisions in a real-world multiagent system, but that use of C4.5 led to failures. Yet, an underlying theory of transfer of control, that would explain such successes or failures is missing. To take a step in building this theory, we introduce the notion of a transfer-of-control strategy, which potentially involves several transfer of control actions. A mathematical model based on this notion allows both analysis of previously reported implementations and guidance for the design of new implementations. The practical benefits of this model are illustrated in a dramatic simplification of an existing adjustable autonomy system.
2002_10_teamcore_aamas02_aa.pdf 2001
David V. Pynadath, Milind Tambe, and Gal A. Kaminka. 2001. “
Adaptive infrastructures for agent integration .” In First International Workshop on Infrastructures for Scalable multi-agent systems, Springer Lecture Notes in Computer Science.
AbstractWith the proliferation of software agents and smart hardware devices
there is a growing realization that large-scale problems can be addressed by integration of such stand-alone systems. This has led to an increasing interest in
integration infrastructures that enable a heterogeneous variety of agents and humans to work together. In our work, this infrastructure has taken the form of an
integration architecture called Teamcore. We have deployed Teamcore to facilitate/enable collaboration between different agents and humans that differ in their
capabilities, preferences, the level of autonomy they are willing to grant the integration architecture, their information requirements and performance. This paper
first provides a brief overview of the Teamcore architecture and its current applications. The paper then discusses some of the research challenges we have
focused on. In particular, the Teamcore architecture is based on general purpose
teamwork coordination capabilities. However, it is important for this architecture
to adapt to meet the needs and requirements of specific individuals. We describe
the different techniques of architectural adaptation, and present initial experimental results.
2001_11_teamcore_incs01.pdf Milind Tambe, D. V. Pynadath, and Paul Scerri. 2001. “
Adjustable Autonomy: A Response .” In Intelligent Agents VII Proceedings of the International workshop on Agents, theories, architectures and languages.
AbstractGaining a fundamental understanding of adjustable autonomy (AA) is critical if
we are to deploy multi-agent systems in support of critical human activities. Indeed,
our recent work with intelligent agents in the “Electric Elves” (E-Elves) system has
convinced us that AA is a critical part of any human collaboration software. In the
following, we first briefly describe E-Elves, then discuss AA issues in E-Elves.
2001_8_teamcore_atal_panel.pdf Paul Scerri, D. V. Pynadath, and Milind Tambe. 2001. “
Adjustable autonomy in real-world multi-agent environments .” In International Conference on Autonomous Agents (Agents'01).
AbstractThrough adjustable autonomy (AA), an agent can dynamically vary
the degree to which it acts autonomously, allowing it to exploit human abilities to improve its performance, but without becoming
overly dependent and intrusive in its human interaction. AA research is critical for successful deployment of multi-agent systems
in support of important human activities. While most previous AA
work has focused on individual agent-human interactions, this paper focuses on teams of agents operating in real-world human organizations. The need for agent teamwork and coordination in such
environments introduces novel AA challenges. First, agents must
be more judicious in asking for human intervention, because, although human input can prevent erroneous actions that have high
team costs, one agent’s inaction while waiting for a human response
can lead to potential miscoordination with the other agents in the
team. Second, despite appropriate local decisions by individual
agents, the overall team of agents can potentially make global decisions that are unacceptable to the human team. Third, the diversity in real-world human organizations requires that agents gradually learn individualized models of the human members, while
still making reasonable decisions even before sufficient data are
available. We address these challenges using a multi-agent AA
framework based on an adaptive model of users (and teams) that
reasons about the uncertainty, costs, and constraints of decisions
at all levels of the team hierarchy, from the individual users to the
overall human organization. We have implemented this framework
through Markov decision processes, which are well suited to reason
about the costs and uncertainty of individual and team actions. Our
approach to AA has proven essential to the success of our deployed
multi-agent Electric Elves system that assists our research group in
rescheduling meetings, choosing presenters, tracking people’s locations, and ordering meals.
2001_10_teamcore_agents01_aa.pdf H. Jung and Milind Tambe. 2001. “
Argumentation as Distributed Constraint Satisfaction: Applications and Results .” In International Conference on Autonomous Agents (Agents'01).
AbstractConflict resolution is a critical problem in distributed and collaborative multi-agent systems. Negotiation via argumentation (NVA),
where agents provide explicit arguments or justifications for their
proposals for resolving conflicts, is an effective approach to resolve
conflicts. Indeed, we are applying argumentation in some realworld multi-agent applications. However, a key problem in such
applications is that a well-understood computational model of argumentation is currently missing, making it difficult to investigate
convergence and scalability of argumentation techniques, and to
understand and characterize different collaborative NVA strategies
in a principled manner. To alleviate these difficulties, we present
distributed constraint satisfaction problem (DCSP) as a computational model for investigating NVA. We model argumentation as
constraint propagation in DCSP. This model enables us to study
convergence properties of argumentation, and formulate and experimentally compare 16 different NVA strategies with different
levels of agent cooperativeness towards others. One surprising result from our experiments is that maximizing cooperativeness is not
necessarily the best strategy even in a completely cooperative environment. The paper illustrates the usefulness of these results in
applying NVA to multi-agent systems, as well as to DCSP systems
in general.
2001_2_teamcore_agents01_argue.pdf Pragnesh J. Modi, H. Jung, Milind Tambe, W. Shen, and S. Kulkarni. 2001. “
A Dynamic Distributed Constraint Satisfaction Approach to Resource Allocation .” In International Conference on Principles and Practices of Constraint programming.
Abstract In distributed resource allocation a set of agents must assign their resources to a set of tasks. This problem arises in many real-world domains such
as disaster rescue, hospital scheduling and the domain described in this paper:
distributed sensor networks. Despite the variety of approaches proposed for distributed resource allocation, a systematic formalization of the problem and a general solution strategy are missing. This paper takes a step towards this goal by
proposing a formalization of distributed resource allocation that represents both
dynamic and distributed aspects of the problem and a general solution strategy
that uses distributed constraint satisfaction techniques. This paper defines the notion of Dynamic Distributed Constraint Satisfaction Problem (DyDCSP) and proposes two generalized mappings from distributed resource allocation to DyDCSP,
each proven to correctly perform resource allocation problems of specific difficulty and this theoretical result is verified in practice by an implementation on a
real-world distributed sensor network
2001_5_teamcore_cp01.pdf Pragnesh J. Modi, H. Jung, Milind Tambe, W. Shen, and S. Kulkarni. 2001. “
Dynamic distributed resource allocation: A distributed constraint satisfaction approach .” In Intelligent Agents VIII Proceedings of the International workshop on Agents, theories, architectures and languages (ATAL'01).
AbstractIn distributed resource allocation a set of agents must assign their resources to a set of tasks. This problem arises in many real-world domains such
as distributed sensor networks, disaster rescue, hospital scheduling and others.
Despite the variety of approaches proposed for distributed resource allocation,
a systematic formalization of the problem, explaining the different sources of
difficulties, and a formal explanation of the strengths and limitations of key approaches is missing. We take a step towards this goal by proposing a formalization
of distributed resource allocation that represents both dynamic and distributed aspects of the problem. We define four categories of difficulties of the problem. To
address this formalized problem, the paper defines the notion of Dynamic Distributed Constraint Satisfaction Problem (DDCSP). The central contribution of
the paper is a generalized mapping from distributed resource allocation to DDCSP. This mapping is proven to correctly perform resource allocation problems
of specific difficulty. This theoretical result is verified in practice by an implementation on a real-world distributed sensor network.
2001_6_teamcore_atal01.pdf H. Chalupsky, Y. Gil, Craig Knoblock, K. Lerman, J. Oh, D. V. Pynadath, T. Russ, and Milind Tambe. 2001. “
Electric Elves: Applying Agent Technology to Support Human Organizations .” In International Conference on Innovative Applications of AI (IAAI'01).
AbstractThe operation of a human organization requires dozens of everyday tasks to ensure coherence in organizational activities,
to monitor the status of such activities, to gather information
relevant to the organization, to keep everyone in the organization informed, etc. Teams of software agents can aid humans
in accomplishing these tasks, facilitating the organization’s
coherent functioning and rapid response to crises, while reducing the burden on humans. Based on this vision, this paper
reports on Electric Elves, a system that has been operational,
24/7, at our research institute since June 1, 2000.
Tied to individual user workstations, fax machines, voice,
mobile devices such as cell phones and palm pilots, Electric
Elves has assisted us in routine tasks, such as rescheduling
meetings, selecting presenters for research meetings, tracking people’s locations, organizing lunch meetings, etc. We
discuss the underlying AI technologies that led to the success
of Electric Elves, including technologies devoted to agenthuman interactions, agent coordination, accessing multiple
heterogeneous information sources, dynamic assignment of
organizational tasks, and deriving information about organization members. We also report the results of deploying Electric Elves in our own research organization.
2001_1_teamcore_iaai01.pdf D. V. Pynadath, Paul Scerri, and Milind Tambe. 2001. “
MDPs for Adjustable autonomy in a real-world multi-agent environment.” In AAAI Spring Symposium on Decision theoretic and Game Theoretic Agents.
AbstractResearch on adjustable autonomy (AA) is critical if we are to
deploy multiagent systems in support of important human activities. Through AA, an agent can dynamically vary its level
of autonomy — harnessing human abilities when needed, but
also limiting such interaction. While most previous AA work
has focused on individual agent-human interactions, this paper focuses on agent teams embedded in human organizations
in the context of real-world applications. The need for agent
teamwork and coordination in such environments introduces
novel AA challenges. In particular, transferring control to
human users becomes more difficult, as a lack of human response can cause agent team miscoordination, yet not transferring control causes agents to take enormous risks. Furthermore, despite appropriate individual agent decisions, the
agent teams may reach decisions that are completely unacceptable to the human team.
We address these challenges by pursuing a two-part decisiontheoretic approach. First, to avoid team miscoordination due
to transfer of control decisions, an agent: (i) considers the
cost of potential miscoordination with teammates; (ii) does
not rigidly commit to a transfer of control decision; (iii)
if forced into a risky autonomous action to avoid miscoordination, considers changes in the team’s coordination that
mitigate the risk. Second, to ensure effective team decisions, not only individual agents, but also subteams and teams
can dynamically adjust their own autonomy. We implement
these ideas using Markov Decision Processes, providing a
decision-theoretic basis for reasoning about costs and uncertainty of individual and team actions. This approach is central
to our deployed multi-agent system, called Electric Elves, that
assists our research group in rescheduling meetings, choosing
presenters, tracking people’s locations and ordering meals.
2001_7_teamcore_spring_symp01.pdf Gal Kaminka, D. V. Pynadath, and Milind Tambe. 2001. “
Monitoring Deployed Agent Teams .” In International Conference on Autonomous Agents (Agents'01).
AbstractRecent years have seen an increasing need for on-line monitoring
of deployed distributed teams of cooperating agents, for visualization, for performance tracking, etc. However, in deployed applications, we often cannot rely on the agents communicating their state
to the monitoring system: (a) we rarely have the ability to change
the behavior of already-deployed agents such that they communicate the required information (e.g., in legacy or proprietary systems); (b) different monitoring goals require different information
to be communicated (e.g., agents’ beliefs vs. plans); and (c) communications may be expensive, unreliable, or insecure. This paper presents a non-intrusive approach based on plan-recognition, in
which the monitored agents’ state is inferred from observations of
their normal course of actions. In particular, we focus on inference
of the team state based on its observed routine communications, exchanged as part of coordinated task execution. The paper includes
the following key novel contributions: (i) a linear time probabilistic plan-recognition algorithm, particularly well-suited for processing communications as observations; (ii) an approach to exploiting
general knowledge of teamwork to predict agent responses during
normal and failing execution, to reduce monitoring uncertainty; and
(iii) a technique for trading expressivity for scalability, representing only certain useful monitoring hypotheses, but allowing for any
number of agents and their different activities, to be represented in
a single coherent entity. Our empirical evaluation illustrates that
monitoring based on observed routine communications enables significant monitoring accuracy, while not being intrusive. The results
also demonstrate a key lesson: A combination of complementary
low-quality techniques is cheaper, and better, than a single, highly optimized monitoring approach.
2001_4_teamcore_agents01_deploy.pdf D. V. Pynadath and Milind Tambe. 2001. “
Revisiting Asimov's First Law: A Response to the Call to Arms .” In Intelligent Agents VIII Proceedings of the International workshop on Agents, theories, architectures and languages (ATAL'01).
AbstractThe deployment of autonomous agents in real applications promises
great benefits, but it also risks potentially great harm to humans who interact with
these agents. Indeed, in many applications, agent designers pursue adjustable
autonomy (AA) to enable agents to harness human skills when faced with the
inevitable difficulties in making autonomous decisions. There are two key shortcomings in current AA research. First, current AA techniques focus on individual
agent-human interactions, making assumptions that break down in settings with
teams of agents. Second, humans who interact with agents want guarantees of
safety, possibly beyond the scope of the agent’s initial conception of optimal AA.
Our approach to AA integrates Markov Decision Processes (MDPs) that are applicable in team settings, with support for explicit safety constraints on agents’
behaviors. We introduce four types of safety constraints that forbid or require
certain agent behaviors. The paper then presents a novel algorithm that enforces
obedience of such constraints by modifying standard MDP algorithms for generating optimal policies. We prove that the resulting algorithm is correct and present
results from a real-world deployment.
2001_9_teamcore_atal01_asimov.pdf H. Jung and Milind Tambe. 2001. “
Towards Argumentation as Distributed Constraint Satisfaction .” In AAAI Fall Symposium 2001 on Agent Negotiation.
AbstractConflict resolution is a critical problem in distributed and collaborative multi-agent systems. Negotiation via argumentation (NVA), where agents provide explicit arguments (justifications) for their proposals to resolve conflicts, is an effective approach to resolve conflicts. Indeed, we are applying argumentation in some real-world multi-agent applications. However, a key problem in such applications is that
a well-understood computational model of argumentation is
currently missing, making it difficult to investigate convergence and scalability of argumentation techniques, and to understand and characterize different collaborative NVA strategies in a principled manner. To alleviate these difficulties,
we present distributed constraint satisfaction problem (DCSP)
as a computational model for NVA. We model argumentation
as constraint propagation in DCSP. This model enables us to
study convergence properties of argumentation, and formulate and experimentally compare two sets of 16 different NVA
strategies (over 30 strategies in all) with different levels of
agent cooperativeness towards others. One surprising result
from our experiments is that maximizing cooperativeness is
not necessarily the best strategy even in a completely cooperative environment. In addition to their usefulness in understanding computational properties of argumentation, these results could also provide new heuristics for speeding up DCSPs.
2001_3_teamcore_aaai_fallsymp01.pdf