Flexible and Approximate Computation through State-Space ...

Flexible and Approximate Computation through State-Space ...

Flexible Methods for Multi-agent Distributed Resource Allocation by Exploiting Phase Transitions - Distributed Constraint Minimization Problems (DCMP) PM: Vijay Raghavan PI: Weixiong Zhang PI phone: (314)935-8788 PI email: [email protected] Institutions: Washington University in St. Louis Contract #: F30602-00-2-0531 AO #: K278 Award start date: 5/1/2000 Award end date: 4/31/2003 Agents: Daniel Daskiewich and Robert Paragi Agent Organization: US Airforce Lome Lab Washington University / DCMP 1 ANTs PI meeting, May 29-31, 2002 Subcontractors and Collaborators Subcontractor Washington University in St. Louis The project was transferred with the PI Collaborators

ISI/Camera, Vanderbilt (logistic scheduling) Achieved: Analyzed the complexity of Marbles scheduling problems. Developed modeling and encoding techniques, and studied various search algorithms for the problem Next step: Complexity of combined scheduling problems Goals: Understanding the complexity and features of the training scheduling problems. New search methods Kestrel (challenge problem) Achieved: Studied low-cost distributed algorithms for scheduling problems. Some phase transition results on distributed algorithms in sensor networks. Nest step: Complexity of distributed resource allocation Goal: Understanding the complexity of distributed resource allocation. New methods based on analysis. Washington University / DCMP 2 ANTs PI meeting, May 29-31, 2002 Problem Description, Objectives Understanding and characterizing distributed resource allocation problems in ANTs domains. Modeling methods (e.g., soft constraint satisfaction/optimization) Phase transitions and backbones (sources of complexity)

Scalability (impact of problem structures) Developing general and efficient algorithms for resource allocations Effective problem-solving methods for problems in ANTs domains Systematic search, approximation methods, distributed algorithms Phase-aware problem solving for good enough/sooner enough solutions What we try to do for the program Understanding computational challenges in ANTs Providing methods for avoiding computational thrashing Improving real-time performance Washington University / DCMP 3 ANTs PI meeting, May 29-31, 2002 Flexible Methods for Multi-Agent Distributed Resource Allocations by Exploiting Phase Transitions (DCMP) Environment PHASE-AWARE PROBLEM SOLVING

Less Global state estimator constrained Transformation Difficult Probably phase solvable Problem solver NEW IDEAS progress and constraint relaxation Unsolvable within bounds Progress monitor

Modeling distributed resource allocation problem (DRAP) as distributed soft constraint minimization problem (DCMP) Using soft/hard constraints with different penalties Finding solutions with minimal overall penalties Characterizing features of DCMP and DRAP Phase transitions and backbones, algorithmic complexity Efficient constraint solving approaches Modeling and encoding methods Systematic and approximate search algorithms Transformations methods exploiting phase transitions Estimating complexity through experimentation Adjust constraints at running time for anytime solutions SCHEDUL E IMPACT Understanding and theoretical characterization of the dynamics and computational complexity of distributed resource allocation problems Phase-aware methods Distributed constraint solvers Complexity and algorithms

Providing guidelines for designing and developing high performance multiagent systems and agent negotiation strategies Demonstration of innovative, phaseaware distributed problem-solving Washington University / DCMP methods for finding satisfactory Integrated solutions Modeling Demo on challenge problems Models, phase transitions and algorithms 4 Year 1 Year

Year 3 2002 ANTs2 PI meeting, May 29-31, Project Status Marbles pilot scheduling problems Worst-case complexity Various modeling and encoding schemes Many search algorithms Experiments on Marbles problems EW challenge problem Low-overhead distributed algorithms Some phase transition results Distributed scan scheduling Washington University / DCMP 5

ANTs PI meeting, May 29-31, 2002 Status on Marbles: Previous Results The problem is NP-hard Reduced from set packing (NP-complete) Two general approaches Model checking a set of satisfaction models Optimization attacking the problem directly Four types of models and ten resulting models Constraint optimization (COP), MAX-SAT Constraint satisfaction (CSP), SAT Encoding schemes (k-encoding) Experimental results (end of last quarter) Optimization models and algorithms are more efficient than satisfaction models and model-checking methods Encoding with using small variable domains does not help Washington University / DCMP 6 ANTs PI meeting, May 29-31, 2002 Status on Marbles: Results of this Period

More local search algorithms considered Developed a COP solver for COP models Analyzed NB-Wsat for CSP models, WalkSat for SAT models and Wsat(OIP) for MAX-SAT models A large number of experiments Instances from ISI and randomly generated (e.g., 100 tasks and 200 resources) Conclusions Optimization models and algorithms are more efficient than satisfaction models and algorithms Problem features interplay with search algorithms E.g., number of resource requirements has significant impact on the efficiency of a search algorithm. Washington University / DCMP 7 ANTs PI meeting, May 29-31, 2002 Status on CP Technical issues considered Scalability how do problem structures affect complexity? Anytime (real-time) performance

Scan scheduling for detecting new targets quickly with small amount of energy Tracking (just started) Washington University / DCMP 8 ANTs PI meeting, May 29-31, 2002 Status on CP: Distributed Algorithms Distributed constraint optimization as a way of resource allocation Low-overhead distributed algorithms Scalability (information from local neighborhood) Simply strategies High performance (solution quality) Fast convergence (real-time feature) Distributed algorithms considered Distributed breakout algorithm (DBA)

Previously developed for distributed CSP Distributed stochastic algorithm (DSA) a set of algorithms (conservative fixed probability algorithm (CFP) considered by Kestrel is one variation) Washington University / DCMP 9 ANTs PI meeting, May 29-31, 2002 Status on CP: Summary of Results (1) Distributed breakout algorithm (DBA) Completeness on acyclic constraint graphs (selfstabilization) Finding a solution or determining there exists no solution in O(n^2) steps, where n is the number of nodes The results can be extended to optimization Incompleteness on cyclic constraint graphs Constructed a ring structure on which DBA wont terminate Developed stochastic strategies to increase DBAs performance on graphs Experimental results on graph coloring and scan scheduling in ANTs domain

Washington University / DCMP 10 ANTs PI meeting, May 29-31, 2002 Status on CP: Summary of Results (2) Distributed stochastic algorithm (DSA or CFP) It is an efficient algorithm in general It has a phase transition behavior (solution quality and communication cost) if not controlled properly Extensive experimental study Distributed graph coloring Distributed scan scheduling in ANTs CP. Washington University / DCMP 11 ANTs PI meeting, May 29-31, 2002 Status on CP: Summary of Results (3) DSAs phase-transition behavior on scan scheduling

Shortest schedule T to cover all the sectors of each sensor Minimal energy use minimizing overlapping of multiple sensors scanning shared area optimization Solution quality Washington University / DCMP Communication cost 12 ANTs PI meeting, May 29-31, 2002 Status on CP: Summary of Results (4) Anytime performance of DSA and DBA on scan scheduling Solution quality Communication cost DBA DBA Washington University / DCMP 13

ANTs PI meeting, May 29-31, 2002 Status on CP: Summary of Results (5) Distributed scan scheduling using DSA and DBA Results from DSA Results from DBA Scalability next sets of experiments to be done Washington University / DCMP 14 ANTs PI meeting, May 29-31, 2002 Status on CP: Publications Publications on distributed algorithms for problems in ANTs W. Zhang and L. Wittenburg, Distributed breakout revisited, AAAI2002, to appear. W. Zhang, et al., Distributed problem solving in sensor networks, 1st Intern. Joint Conf. on Autonomous Agents and Multi-agent systems (AAMAS-2002), to appear. W. Zhang, G. Wang and L. Wittenberg, distributed stochastic search for constraint satisfaction and optimization: Parallel, phase transitions and performance, AAAI-2002 Workshop on Probabilistic Strategies in Search, to appear. W. Zhang and Z. Xing, Distributed breakout vs. distributed stochastic:

A comparative evaluation on scan scheduling, AAMAS-2002 Workshop on Distributed Constraint Reasoning, to appear. Publications on complexity and phase transitions S. Climer and W. Zhang, Searching for backbones and fat: A limitcrossing approach with applications, AAAI-2002, to appear. A. K. Sen, A. Bagchi and W. Zhang, An average-case analysis of graph search, AAAI-2002, to appear. Washington University / DCMP 15 ANTs PI meeting, May 29-31, 2002 Project Plans Scheduling in Logistics domain Analyzing the complexity and features of Marbles 2 and the integrated problems combining pilot and maintenance scheduling Challenge problem Extending the current work to distributed tracking Complexity of distributed resource allocation Possible phase transition in terms of the speed of moving targets;

Possible phase transition due to limited resources and the number of moving targets. Phase-aware (or phase-inspired) problem solving General optimization problems ANTs problems Washington University / DCMP 16 ANTs PI meeting, May 29-31, 2002 Project Schedule and Milestones Finished tasks Ongoing tasks

Marbles: modeling methods, encoding schemes, complexity, and search algorithms CP: distributed algorithms and phase-transition behavior, distributed scan scheduling General phase-aware methods (for TSP and number partitioning) Scheduling in logistic domain: integrated scheduling Distributed scan scheduling and tracking Phase-aware methods for ANTs problems Integrated solutions Tasks to start Phase-aware methods Integrated solutions for all ANTs problems Demo on challenge problems

Phase transitions, constraint solver Complexity and algorithms Models and modeling techniques Washington University / DCMP Year 1 Milestone1: Models, phase transitions and algorithms 17 Year 2 Year 3 ANTs PI meeting, May 29-31, 2002 Technology Transition/Transfer To be worked on Washington University / DCMP

18 ANTs PI meeting, May 29-31, 2002 Program Issues Complexity and phase-transition analysis How can the complexity and phase-transition results be directly shown in the systems? How close is a simulation to a real problem setup? How do we handle sensor interference? What to do when no reading? The complexity workshops for Marbles scheduling problems that we had before were very useful. Should we continue to have them in the future? Looking forward to the Vanderbilt workshop Washington University / DCMP 19 ANTs PI meeting, May 29-31, 2002

Recently Viewed Presentations

  • The Prompt

    The Prompt

    Write an essay An essay that compares AND contrasts C&C the short story and the novel And linking them through their thematic idea Using setting, character development and conflict S. of an H H.B Thematic Idea Individuality through freedom Individuality...
  • Budget Update Elva Martinez, Assistant Director Budget Planning

    Budget Update Elva Martinez, Assistant Director Budget Planning

    FY 14 Budget Planning Calendar Jan 30 Census Date Spring 2013 Semester Mar 20 Revenue Projections and Debt Service Budgets to Fee Funded areas Mar 7-22 Budget coordination to validate permanent positions, review funding available in salary accounts and request...
  • Sensory Interaction

    Sensory Interaction

    Frank Searle, photo Adams/ Corbis-Sygma. Dick Ruhl. Children's schemas represent reality as well as their abilities to represent what they see. Schemas. Schemas are concepts that organize and interpret unfamiliar information. Courtesy of Anna Elizabeth Voskuil.
  • Group of Subsystems: Nitrogen oxides metabolism Dmitry Rodionov,

    Group of Subsystems: Nitrogen oxides metabolism Dmitry Rodionov,

    Next, during denitrification nitrite is reduced to NO by one of the two different types of nitrite reductases (Cu-NiR or cytochrome cd1-NiR), then to N2O by one of the two types of nitric oxide reductase (quinol-dependent qNOR or cytochrome bc-type...
  • Smart Coating for In-Situ Monitoring of Engine Components

    Smart Coating for In-Situ Monitoring of Engine Components

    Small Business Innovation Research Innovative Dynamics, Inc. Ithaca, NY INNOVATION Depositing a crackwire incipient crack sensor on turbine engine disks and blades for detection based on signals generated from its interaction with microwaves
  • General Division of Environment PowerPoint Template 3.19

    General Division of Environment PowerPoint Template 3.19

    For more information on PowerPoint formatting, please see the KDHE PowerPoint Style Guide, available on the intranet. PowerPoints must be reviewed by Communications before use. Please send completed PowerPoints to Graphic Designer Lindsay Gray at [email protected] at least three days...
  • Chapter 5 Time Value of Money Copyright  2012

    Chapter 5 Time Value of Money Copyright 2012

    The cash flow of a firm can be described by its pattern—single amount, annuity, or mixed stream. Future value (FV) relies on compound interest to measure future amounts: The initial principal or deposit in one period, along with the interest...
  • John's Letters - Baptist Start

    John's Letters - Baptist Start

    The Letters of John Life Light First John 1:5-2:2 Page 1034 in Pew Bibles Love Confidence Born of God That you may know First John 1:5-10 Chapter 2 The Letters of John First John 2:1-2 Page 1034 in Pew Bibles...