Who Are We: Who Are We Negotiation Technology In Real Use


Users:MARINE AIR GROUP 13: Users: MARINE AIR GROUP 13


Slide3: Our Problem: Help Them Write the Schedules Who What When Where Using Hard to Write Evaluation Function to Characterize Good Schedules


Status of SNAP: Schedules Negotiated by Agent-Based Planners: Builds and repairs fully-detailed flight schedules for any planning horizon, without losing sight of command objectives, providing new opportunities to explore and manage alternative futures, in 1/10th-1/100th of current time Constraints Training code pre-requisites from T&R Manual Fly day Day & night missions Crew day rules Turn-around & briefing time Instructor requirements Range capabilities Availability & suitability Merging and splitting Range board Pilot SNIVELs Aircraft availability Simulator schedule Range Use Pilots’ View Scheduling Officer Feedback Status of SNAP: Schedules Negotiated by Agent-Based Planners Identifies needed ranges Tracks pilots Compares results to guidance Knows the situation Accepts guidance at any level of specificity Lets users adjust priorities Inputs Outputs Prioritized Guidance Squadron focus o Pilot focus o Sortie cycle Pilot builds o Pilot specific training code o Fly day Pilot snivels o Ranges o No. aircraft of each type Obeys the law SNAP Agents: Trade-off Exploration, Win-Win Scheduling Solutions Flow manager Pilots Aircraft Missions Ranges PMCF Simulators Sim. Monitors ODO Ordnance Academics Daily Schedule Produces schedules Weekly Sched. Monthly Sched. Electronic Feed to Maintenance


Methodology: Technology and Application Tracks: Methodology: Technology and Application Tracks Goals Build generic resource allocation technology … address requirements of the real world application Build application prototype for real use


Resource Allocation Problems: Resource Allocation Problems Basic resource allocation problem NP-Hard (Wayne Zhang) Desiderata: Distributed: tasks & resources are distributed agents Robustness: add/remove resources & tasks, dropped messages Good enough, soon-enough solutions


Resource Allocation Problems: Resource Allocation Problems Basic resource allocation problem NP-Hard (Wayne Zhang) Desiderata: Distributed: tasks & resources are distributed agents Robustness: add/remove resources & tasks, dropped messages Good enough, soon-enough solutions


Resource Allocation Problems: Resource Allocation Problems Basic resource allocation problem + bonus for resource usage NP-Hard (Wayne Zhang) Desiderata: Distributed: tasks & resources are distributed agents Robustness: add/remove resources & tasks, dropped messages Good enough, soon-enough solutions


Resource Allocation Problems: Resource Allocation Problems Basic resource allocation problem + bonus for resource usage + time: resources and tasks available only at certain times NP-Hard (Wayne Zhang) Desiderata: Distributed: tasks & resources are distributed agents Robustness: add/remove resources & tasks, dropped messages Good enough, soon-enough solutions


Resource Allocation Problems: Resource Allocation Problems Basic resource allocation problem + bonus for resource usage + time: resources and tasks available only at certain times + dependencies: - task pre-requisites - resource bundles NP-Hard (Wayne Zhang) Desiderata: Distributed: tasks & resources are distributed agents Robustness: add/remove resources & tasks, dropped messages Good enough, soon-enough solutions


Approach: Marbles: Approach: Marbles


Preliminary RA-Marbles Quality Evaluation(Randomly Generated Problems): Preliminary RA-Marbles Quality Evaluation (Randomly Generated Problems) Marbles Distributed Schemes Well-known Centralized Schemes Simulated Annealing SAT Encoding


ANTS Technology Transition Chronology(USC ISI CAMERA Project, Vanderbilt ISIS MAPLANT Project): Jan - Apr 2002: USMC Deputy Commandant for Aviation arranges briefings/demos for all Generals in USMC Aviation Dec 2001: DARPA Director reports work to Under Secretary of Defense for Acquisition, Technology and Logistics July 2001: Operational users lobby for full use -- “We want this for daily use throughout the entire Air Group.” ONR funds fielding to Marine Air Group 13 February 2000: first demonstration to users (VMA 513 selected) June 1999: contract initiated for DARPA research demonstration; plan is demos with input from a single USMC Harrier aircraft squadron ANTS Technology Transition Chronology (USC ISI CAMERA Project, Vanderbilt ISIS MAPLANT Project) October 2003: Follow-on to start on extension to all Navy and USMC tactical aircraft (Expected funding, $7.5 M over 3 yrs under ONR Future Naval Capabilities Knowledge Superiority Assurance Program) June 2002: Users deploy to Japan and the Pacific Region May 2002: Scheduled initial fielding


What Does It Take To Transition Your Technology: What Does It Take To Transition Your Technology Hotel clerks are your friends


Upcoming Technology Pull in CARTE(ONR Future Naval Capabilities): Upcoming Technology Pull in CARTE (ONR Future Naval Capabilities) Today: Coordinated Ops/Maint. pairs FY03-FY04 System of System Interactions: N-way Shared Resources FY04-FY05 Scale & control: Bigger probs. Much longer planning horizons Control of higher level architecture with support for parallel exploration


Objective: Distributed, Adaptive & Real-TimeWeapon-Target Pairing for UCAV Swarms: Objective: Distributed, Adaptive & Real-Time Weapon-Target Pairing for UCAV Swarms Enable UCAVs to autonomously and effectively adapt weapon-target pairings in the face of Changing Situations, Degraded Capabilities, Communication Disruptions by developing distributed algorithms that are with quantifiably measurable effectiveness. adaptive, real-time, and robust target gone new target detected UCAV lost laser designator non-operational intermittent link link out abandoning target 4 to attack higher-valued target 5 with UCAV D... not enough time... not initiating optimization of munitions for target 1... poor connectivity... let’s go with a less communication-intensive synchronization protocol...


ATTEND Complexity Results Applied to CAMERA:Example from SNAP : ATTEND Complexity Results Applied to CAMERA: Example from SNAP