Improving Coalition Performance by Exploiting Phase Transition Behavior
A project of the Computational
Intelligence Research Laboratory at the University of Oregon. Funded by DARPA as part of the Autonomous Negotiating
Teams (ANT) project.
Quad chart (single slide summarizing people, objectives, methods and time-line)
Autonomous Negotiating Teams (ANT) Project
See
Background
Phase Transitions, Computational Complexity and Computational Cliffs
"Phase transitions" are the name for the phenomenon where important
properties of a system vary discontinuously and dramatically as we
change some defining parameters. The most familiar example is from
real-world physical systems: consider the change in properties of
water as we change its temperature from above freezing to below
freezing. The predictability and suddenness, in terms of temperature,
of the transition from water to ice is statistical effect arising from
the large size of the system and arises despite the general
unpredictability of motions of individual molecules.
It has been known since the 1960's that similar phenomena also occur
in systems that are associated with computer science rather than
physics. In computer science, this is usually characterized by systems
changing from "almost always has property X" to "almost never has
property X" as we vary defining parameters and where property X is
some important property of the system. For example, for a scheduling
problem we might take X to be whether or not the tasks can be
scheduled to meet all the deadlines, and the defining parameter some
measure of overall tightness of the deadlines.
More recently, work in the artificial intelligence community discovered
such phase transitions can be associated with large peaks in the
computational cost of solving the system. The computer time to
discover whether or not the system does have property X is much larger
when the defining parameters are close to the phase transition region.
Answering the question as to whether a schedule exists becomes
exponentially harder as the tightness of deadlines approaches the
phase transition; a phenomenon we call a "computational cliff".
Further info can be found here
Project Overview
The large size and heterogeneity of many military problems, such as
logistics or resource allocation problems, makes them prone to
so-called "phase transitions", where small, seemingly
innocuous, changes to the problem characteristics can have drastic
effects on system performance.
Phase transitions will often generate "computational
cliffs" in which even slight improvement in solution
quality will probably require a disproportionately large, and
unpredictable, expenditure of computational effort.
Unless further improvement is critical to the problem, computational
resources will probably be better allocated elsewhere in such cases.
Conversely, judicious small relaxations in solution requirements might
lead to very large time savings.
Knowledge of phase transition structures gives opportunities to avoid
unexpected large adverse effects on scaling properties, and also to
obtain computational savings.
The objective of this effort is to understand the phase transition
structures occurring in real distributed problems, develop methods to
detect imminent computational cliffs, and mechanisms to use this
information to dynamically guide the system towards coalitions that
match well with the phase transition properties and provide
appropriate allocation of computational resources.
The resulting systems will have lower and more predictable search
times and will avoid unexpectedly encountering phase transitions that
could cause failure to meet the real-time bounds.
Project Technical Goals
- Develop deeper understanding of phase transitions in
distributed systems.
Most previous study of phase transitions has been for monolithic
rather than for distributed systems. Our goal is to understand the
nature of phase transitions, and associated computational cliffs in
distributed systems. In particular to find how the cliffs are affected
by different choices for the decomposition of the problem.
- Develop reasoning maintenance methods to detect computational
cliffs in a distributed system. The goal is to develop reasoning
maintenance techniques from the artificial intelligence community in
such a way as to
- detect when a sub-problem is approaching its computational cliff, and hence
allow re-allocation of computational resources in time.
- determine if the current decomposition of the problem is a bad
match to the problem structure and so allow an advisory agent to
recommend ways to adjust the decomposition.
Details of technical approach
Reports and Presentations
- Final Report, June 2004. (
PDF )
- Final Briefing at PI meeting, Nov 2003. (
PPT )
- Presentation at PI meeting, May 2003. (
PPT )
- Presentation at PI meeting, Dec 2002. (
PPT )
- Presentation at PI meeting, May 2002. (
PPT )
- Presentation at PI meeting, Arizona, Dec 2001. (
PDF,
ppt )
- CIRL's 2001 Technical project summary
- Presentation at PI meeting, Tahoe, May 2001. (
PDF,
ppt )
- Presentation at PI meeting, Charleston, Nov 2000. PDF
- CIRL's 2000 Technical project summary
- Presentation at PI meeting, Seattle, May 2000.Slide show
Related Publications
Funding
This project is funded by the
as part of the
Autonomous Negotiating Teams (ANT) Project .
Personnel
Contacts
Email: cirl-ants 'at' cirl.uoregon.edu
The URL for this
page is: http://www.cirl.uoregon.edu/ANTS/
Page last modified: 2001-09-26.
