ATTEND: Analytical Tools To Evaluate Negotiation Difficulty

Welcome to the USC-ISIATTEND project home page. This project is part of the ANTs (Autonomous Negotiating Teams) program sponsored by DARPA/ITO.

[This page was last modified on Friday, September 5, 2003 3:17 PM]

ATTEND seeks to develop a theoretical understanding of systems in which negotiation between multiple agents is needed to determine how a set of resources will be utilized. The goal is to be able to partition negotiation problems into sub-problems that make the negotiations simpler and, ultimately, to be able to provide warnings about the difficulty of each sub-problem. ATTEND seeks not just to do so on a theoretical basis, but to interface efficient implementations of its analytical tools to existing negotiation systems, and to demonstrate that the information supplied by ATTEND enables those systems to change their behavior in order to more effectively solve problems.

Project Goals

The main goal of our work is focused negotiation with advance negotiation-difficulty warnings that enable the system to predict and adapt in advance to hard problems. We propose a set of analytical tools suitable for identifying good-enough and soon-enough solution sets for constrained resource management systems. Given a set of tasks to perform in a common resource pool, which are potentially in contention, our analytical tools perform three valuable functions: 1) Partition the original problem into two sets: those that truly require negotiation and those that do not; 2) Identify groups of tasks that subset the negotiation-critical part of the problem into parts that can be resolved separately in parallel and 3) Generate negotiation-difficulty warnings for each of these groups. These warnings can be used by the negotiating system to adapt its constraints to meet the good-enough and soon-enough concerns imposed by the application.

The proposed work consists of three main tasks:
1. Develop the mathematical framework required by the approach and build efficient software components that support such analyses.
2. Implement a general API to make the analytical services available to agent systems and agents systems developers. The tools will primarily be used in designing systems of negotiating entities, but can also play a role in run-time systems, depending on the interactions between our analysis algorithms and the complexity of a given problem.
3. Evaluate the analytical tools in an ANT system application. We will perform these experiments in conjunction with USC ISI’s existing CAMERA project.

Approach

Our approach is based on mapping the resource management problem that the system is trying to solve by negotiations into a constraint-satisfaction problem (CSP). Within this formalism we use powerful analytical tools from computer science and physics to dynamically evaluate the problem-difficulty and use this information to produce negotiation-difficulty warnings that enable the system to adapt to computational time constraints. The body of analytical techniques included in our approach is based on Graph-Coloring and Partitioning and the Phase-Transition phenomena occurring combinatorial problems.

Graph-Coloring and Partitioning is used to incrementally resolve resource allocation conflicts, to identify the tasks that truly require negotiations, group tasks with different difficulty level and estimate the negotiation-difficulty of these groups of tasks. We plan to implement a physics-based approach to graph-coloring, with variable number of possible colors per node (Ki-coloring), by treating the graph as a system of interacting magnets or spins that can take different polarizations from a finite set. Within this formalism to solve the coloring problem is equivalent to finding the ground states of the system, which can be done using well-proven high-performance techniques from statistical mechanics and combinatorial optimization. Efficient graph-partitioning techniques like clique separation and minimum edge cutting are also contemplated as a mechanism to partition a given group of tasks into regions of decreasing level of negotiation difficulty.

In our approach the Phase-Transition phenomena that occurs in most combinatorial problems is used to identify the hard (exponential) and easy (polynomial) parts of the CSP associated to a set of tasks. Based on macroscopic properties of the problem we will determine in what part of the phase-transition curve the system is operating and use the proximity to the critical region to issue warnings of negotiation difficulty.

Current Plan

The main items that we expect to accomplish during the FY01 are:

Perform basic studies and computer experiments of the problem of Ki-coloring of graphs where the number of available colors per node, Ki, can vary from node to node. Identify the order parameter that determines the complexity transition for the Ki-coloring problem associated with the resource management by agent-based systems
Perform theoretical and numerical studies of the relationship between the connectivity, the average number of colors and the total number of nodes in a graph to characterize the “degree-of-constraint” of the problem
Perform theoretical, numerical studies and develop algorithms for efficiently partitioning the task space to identify those that truly require negotiation and to sub-partition this set into groups with different negotiation-difficulty levels
Perform simulations and real-time flight sortie scheduling experiments with distributed CAMERA agents using the initial set of ATTEND tools to characterize the dependency of the problem difficulty in the relevant dimensions of the problem and to identify sets of agents requiring different solution and negotiation mechanisms

Technology Transition

All DARPA contractors in the agent-based community are considered to be potential users of our analytical package. We are using standard programming languages and software development tools to implement the analytical package. Therefore, we don't foresee any integration problems besides the ones that usually surface when integrating software developed using different programming languages via DLLs. This is really not a concern since the use of DLLs is standard industry procedure.

While we hope to demonstrate a methodology useful for multiple negotiation systems, we will test it in the context of a specific one: CAMERA. CAMERA is a currently-funded ANT negotiation system distinguished by having techniques for relaxing constraints to accept "least disrespectful counterproposals" as part of its approach to reasoning within time bounds. It also has a capability to apply different negotiation protocols to different parts of a problem, which makes it particularly easy to modify in order to demonstrate difficulty-sensitive adaptation, as we propose herein. The current application of CAMERA is to safety-oriented flight scheduling, and is being tested in a large-scale demonstration application being developed for Marine Air Group 13, Marine Corps Air Station Yuma, Arizona. We expect ATTEND results to transfer to the Marine Corps via CAMERA.

There are two types of experiments which we envision performing by adapting CAMERA to understand the results of the ATTEND analytical tools:

In the first type, the method can be used to warn CAMERA about the regions in the graph, i.e., the groups of sorties for which we can expect a solution using a soon-enough criteria or the group of those for which we can expect a good-enough solution. CAMERA is being developed to have the capability of setting time bounds for solutions and to loosen constraints so that approximate solutions can be reached within those bounds. Therefore, CAMERA can use its techniques to adapt its behavior accordingly and we can run tests which demonstrate differences in performance characteristics due to the presence or absence of difficulty warnings.
In the second type of experiments, we can use the problem solving capability of the analytical toolset to fine-tune and understand the behavior of CAMERA's negotiation protocols in well-characterized problems. By running CAMERA against benchmarked, fully-characterized problems where optimal performance can be determined in advance, its developers can gain insight into how to refine its procedures.

ATTEND Team

Staff Scientists	Graduate Students
Robert Neches (Principal Investigator)	Donghan Kim
Alejandro Bugacov
Geoff Pike

Results, Papers & Presentations

Description	Download
CAMERA-SNAP Scaling Properties: Empirical Results	[ PDF ]
The Marbles Manifesto: A Definition and Comparison of Cooperative Negotiation Schemes for Distributed Resource Allocation. Proceedings of the 2001 AAAI Fall Symposium on Negotiation Methods for Autonomous Cooperative Systems, 10 pages, (North Falmouth, Massachusetts, November 2-4) 2001.	[ PDF ]
SAT Encoding of the Marbles Problem: Endoding Definitions, Problems and formulas	[ PDF ]
SAT Encoding: Scaling of the number of clauses and variables	[ PDF ]
PB Encoding of the Zmarbles Problem	[ PDF ]

ANTs Meetings Presentations	Download
Slides Presented at the ANTS PI Meeting, Seattle, May 9, 2000	[ PDF ]
Slides Presented at Computational Complexity Fest I, Sept. 6, 2000	[ PDF , HTML]
Slides Presented at Computational Complexity Fest II, Nov. 6, 2000	[ PDF ]
Slides Presented at the ANTS PI Meeting, Charleston, Nov 29, 2000	[ PDF ]
Slides Presented at the ANTS PI Meeting, Lake Tahoe, May 1, 2001	[ PDF ]
Slides Presented at the ANTS PI Meeting, Scottsdale, December 17, 2001	[ PDF ]
Slides Presented at the ANTS PI Meeting, Captiva Island, May 29, 2002	[ PDF ]