ANTS Spring 2000 Demonstration Meeting Report Jon Doyle and Chris van Buskirk April 14, 2000 Chris van Buskirk and Jon Doyle met at MIT on April 13-14, 2000 to work out the structure of the upcoming May demonstration based on the discussions last week in Arlington, Virginia, on the refined scenario developed by Rick Wong and Joan Crunk on April 13, and on some mid-meeting advice from Bob Laddaga. We both felt the meeting was very successful. We were able to identify a large set of behaviors and strategies implicit in the refined scenario, to whittle these down to a small focus area appropriate for the active part of the May demo, and to make some preliminary estimates of the feasibility of adapting the current demo to the new script. The script we sketched out can be shrunk further as time pressures require. This report builds on both the "MICANTS Scenario: Maintenance Scheduling" draft of April 5, 2000 distributed by Chris, and on the refined MAG scenario distributed by Rick and Joan, appended at the end of this document. ---------------------------------------------------------------------- DEMONSTRATION AIMS We kept in mind the following aims for the demonstration. Bob was especially insistent on making sure we have some demo of something, regardless of whether the May demo corresponds significantly to the October 1999 demo or to the planned September 2000 demo, and regardless of whether it addresses all or any of the most interesting negotiation issues implicit in the MAG domain. 1. The script should lead to a functioning demonstration system within the next two weeks, allowing a review by Gabor and subsequent tweaking as needed. 2. The active portion of the demonstration should attempt to demonstrate negotiation ideas in as simple a form as possible, and indicate how these ideas scale to larger portions of the demonstration scenario. We should not try to implement larger or further negotiations that only server to illustrate the same ideas. 3. Ideally, the demonstration script should illustrate several key ideas: A. Dynamic change of negotiation methods or procedures triggered by changes in the negotiating situation or goals. i. Change of negotiation protocol or method. ii. Change of negotiation preferences or goals. B. Dynamically change of negotiation participants appropriate to changes in situation or goals. ---------------------------------------------------------------------- SUMMARY OF DEMONSTRATION SCRIPT The MAG domain involves numerous negotiations, including jockeying of the commander for assignments and resources that will increase the prestige of the unit and his own promotability, competitions among missions assigned to the MAG for MAG resources, and negotiations within and without the MAG for maintenance resources. The demonstration scenario concerns only the last of these, negotiations for maintenance resources. Negotiations among missions may be more important, but we leave that for future demonstrations. Maintenance negotiations prove entirely adequate to demonstrate key negotiation concepts. Within the realm of maintenance negotiations, one can identify negotiations concerning replacement part procurement, whether by purchase, barter, repair, or cannibalization; negotiations concerning personnel procurement; and negotiations concerning maintenance facility reservation. Each of these activities in turn provides room in which to conduct many subsidiary negotiations among different classes of agents. To make a manageable demonstration, we restricted the demonstration focus to one element of the part procurement process, namely procurement of replacement parts from sources outside the squadron needing the part. Within the realm of extra-squadron replacement part procurement, we propose a demonstration involving only a single maintenance task. Competitions among maintenance tasks are surely important, but these do not illustrate negotiation ideas beyond the ones involved in handling a single negotiation task. This demonstration might seem pretty microscopic compared to the full MAG context, but it is plenty rich for even a demonstration with more preparation time. We intend to illustrate the rich context and larger scope of negotiations in the MAG domain in one or more posters. The large-scale maps of processes may be pretty busy, but suffice to show there are many negotiations involved. The finest-scale map focusing on the processes actually treated by the active demo will make the rich structure of even these detailed processes clear. We recommend using the larger-scale posters as the static or "grayed-out" portions of the demo, that is, portions of a more realistic demo for possible future implementation and refinement. The specific active demonstration will consist of one to three repetitions of the same maintenance task with different initial conditions. Each of these runs illustrates a different key concept of negotiation. The notional order of these runs is as follows: 1. The first run consists of a single maintenance task for which the time available suffices for a significant amount of negotiation activity. This run illustrates the following concepts: A. Standard contract-net or market-auction optimization of resources. B. Discrimination among different classes of potential negotiation participants based on situational and organizational information, that is, on richer structures than fixed organizational trees and universal contracting broadcasts. 2. The second run consists of a variation on the first, in which the negotiation process itself changes the structure of the participant classes. This run illustrates illustrates the concepts involved in Run 1 plus: C. Dynamic change of negotiation relationships and classes of negotiation participants. If demonstration time is short, Run 1 can be skipped in favor of Run 2. If development time is short, Run 2 can be skipped and merely pointed out as a corollary of the operation of Run 1. 3. The third run consists of a single maintenance task for which the time available does not suffice for the standard optimizing activity. In this run, the maintenance task agent starts out attempting the standard optimizing activity, but then switches (perhaps immediately, depending on the initial conditions) to a "panic mode" in which it seeks to minimize negotiation time without regard to other costs. This run illustrates the following concepts: D. Dynamic change of negotiation method based on changes in the negotiation situation. E. Dynamic change of negotiation preferences based on changes in the negotiation situation. If demonstration time is short, this third run can be used to subsume Run 1, illustrating points A, B, D, and E. We could even subsume Run 2, illustrating point C, if necessary, though some of these illustrations probably come across clearer by separating the runs as laid out in the preceding. To reduce the computational load of the demonstration, we adjust reality by assuming the MAG contains only three squadrons, and that the external environment contains only two or three suppliers of parts. These suffice to convey the essential ideas. ---------------------------------------------------------------------- BASE NEGOTIATION METHODS The above script sketch involves two base negotiation methods, namely cost-optimization negotiations unbounded by time, and time-pressured negotiation. Each of these in turn comes in different varieties appropriate to different classes of negotiating partners. The actual negotiation methods used in the demonstration combine some of these varieties into more complicated methods. We summarize some of the ideas in turn. UNPRESSURED COST OPTIMIZATION Unpressured cost optimization corresponds to standard contract-net or market-auction mechanisms. Requests for proposals to sell, or bids to buy, are communicated to a set of possible proposers or bidders, and then evaluated, either to find the minimum-cost bid among these or to refine the proposal or buy-bid in order to stimulate the next round of bids in an attempt to further lower the cost. This structure, in itself, contains nothing novel. We combine this mechanism with a dynamic "proximity" relation among the agent and potential negotiating partners, to obtain a series of cascading auctions through less and less proximate sets of partners. The idea here is that negotiation communications themselves cost resources and time, and the proximity relations should reflect a variety of concerns including communications cost, transportation or transaction costs, familiarity, reliability, trust, etc. For example, in the MAG script, we envision the unpressured proximity groups consisting of a minimum of two sets. The first proximity group PG1 consists of the maintenance chiefs or agents of the sister squadrons together with the outside suppliers with which the squadron has completed transactions. The second proximity group consists of all other outside suppliers. The cascade optimization method thus starts by having the Resource Management Agent (RMA) broadcasting the squadron's request to agents in PG1 and finding the best offer, and then, if time permits and further cost reduction seems warranted, broadcasting the request to PG2. Several comments are in order here. First, these two groups simplify the scenario outlined by Rick and Joan, in that we ignore the existence of group inventories on base but not held by the squadrons. They also ignore the manifold gradations we might place on the vast numbers of agents in PG2. Second, these groups are dynamic by definition. While the sister squadrons do not change (or at least do not for the purposes of this demonstration), agents move from PG2 to PG1 whenever negotiations with agents in PG1 fails to find a suitable deal and the squadron procures a part from some agent in PG2. In fact, this same prior-partner mechanism might be though to also apply to the sister squadrons; the requesting squadron might broadcast the request to everyone in the sister squadrons, who sensibly all pass on the requests to their maintenance chief or maintenance supply agent (MSA), who then responds on behalf of the sister squadron. Indeed, if that chief is replaced, then the sister squadron's new chief will eventually have to enter PG1 by means of some future transaction. (This isn't to imply that we have to keep the group-definition rule so ignorant; we might allow the sister squadron to simply let us know of the replacement.) In this way, the participants in each stage of the unpressured negotiation are determined by dynamic or historical knowledge, not by fixed organizational charts. PANIC MODE In panic mode, the prime objective of the RMA is to obtain the part in the miminum amount of time. The RMA thus makes much larger offers than in unpressured optimization in order to cut off unnecessary negotiation time. That said, the panic mode negotiation employs different proximity groups from the unpressured optimization method. This illustrates dynamic change of negotiating organization with the negotiating strategy. In panic mode, the squadron's RMA first proximity group consists of the sister squadrons alone, and to these it makes its very best offer first, along with an indication it is in panic mode. The idea here is that the sister squadrons, sharing the same underlying missions, and reporting to the same commander, will use this desperation bid to see if they can swing the deal, and take only what they need of the bid if they can. The second proximity group for panic mode consists of outside suppliers with whom the squadron has had past transactions. It conducts a routine negotiation with these, but in contrast to unpressured optimization, uses an exponential bidding strategy to quickly determine if a deal is possible. This does not tell the supplier about the squadrons' desperation explicitly, though it does allow the supplier to infer this desperation from the character of the offers being made. The third proximity group for panic mode consists of outside suppliers without transaction history. The squadron uses the exponential bidding strategy with them too. OTHER NEGOTIATION POSTURES There are numerous other negotiation methods which we do not anticipate using in the current demo but which may play a role in future demonstrations. For example, one different kind of negotiation method is based on group welfare considerations. In this strategy, the squadron seeks to bolster the strength of a weaker element of the MAG while accomplishing its own goal, whether this be in minimizing its own costs or minimizing its own negotiating time. If it finds it can buy the replacement part from either sister squadron, but that one squadron is swimming in spares while the other has but one to spare, the squadron would buy from the squadron with the surfeit rather than the one that would be left at minimum reserves by the transaction. More generally, negotiations might be conducted with many types of goals. Here is a brief list of some of the possibilities: 1. Maximizing individual unit strength 2. Maximizing group strength A. Total group strength B. Weakest-member strength C. Strength of the strongest member (peak-member strength) D. Concentration of group strength E. Group integrity (weakest-member strength or loyalty) 3. Mission performance levels (variants as in group strength, here across group of missions) F. Minimizing mission damage (in contexts of degredation) G. Scores in evaluations by superiors or external auditors 4. Overt costs A. Time B. Money C. Stores D. Personnel These examples reflect some general dimensions of variation or competition: 1. Units vs. Missions 2. Individuals vs. Groups 3. Cost factors vs. other cost factors These other possibilities support many new combination types, such as a sort of "gracious negotiation" in which the squadron tries to buck up the weaker MAG components until degredation threatens the ability to carry out central missions, at which point it seeks to minimize the damage to overall mission goals, even if this means sacrificing accomplishment of its own task. ---------------------------------------------------------------------- NEGOTIATION PLANS We assume most of the activities of the MAG regarding negotiation can be captured as formal plans or process models. We intend to exploit such formal models in Zeus, though perhaps not in the current demo. Zeus has a very rudimentary capability for this, in which only the graph structure is explicit, and all the meanings and properties of the plan nodes remain implicit (through connections between node names and the Java code contained in files sharing the same name!). Zeus also builds into its plan-execution mechanism a very simple fixed procedure corresponding to a universal contract-net call, and forces all variation of negotiation into situation-independent choices keyed to the goal type and respondent type. Zeus also has no store of plans for use in different circumstances. We expect to have to augment Zeus by adding explicit representations for plans, by formalizing the existing Zeus mechanisms as plans in this representation, by changing the Zeus executive to interpret these plans of its own activities, by adding a library of plans to each agent, and by augmenting the existing Zeus procedures with additional plans corresponding to the more complicated negotiation methods outlined above. We postponed consideration of what sort of language to use for describing these plans. One possibility is to use the ACT language developed at SRI by Myers and Wilkins for plan synthesis (Wilkins' SIPE) and reactive execution. Other languages might fit our needs as well. ---------------------------------------------------------------------- SCHEDULE 1. Chris will work on the demo with the grad students over the next two weeks, aiming to complete the review version by April 24. 2. Jon will write up more details of negotiation strategies and structures during this time, advise Chris as needed, and make some attempt at constructing posters of the demonstration context as needed. 3. Gabor will review the demonstration on April 24. 4. Jon will brief Bob on the presentation of the negotiation strategies on or before May 2, but will be away at another meeting afterwards. 5. The demonstration will be presented at the ANTS PI meeting May 9-11. ---------------------------------------------------------------------- APPENDIX ANTS SCENARIO - INSUFFICIENT MATERIAL RESOURCES Rick Wong and Joan Crunk April 13, 2000 Problem: A pilot from Squadron 211 detects a discrepancy with the right hand fuel indicator during takeoff for a routine flight test. The tanks were filled with fuel before takeoff but the indicator showed the right tank close to empty. Upon returning to the base, Maintenance was able to isolate the problem to a faulty switch. In order to determine the priority for repairing or replacing the faulty switch, the following questions and decisions need to be made: * Is this aircraft needed for continuous sorties? If so, what is the schedule date/time for the next sortie? * Is the switch critical to the flight test or mission? Scenario 1: If the next scheduled sortie for this aircraft is for a training exercise and little fuel is required (e.g. touch and go, short flight duration, etc.) the switch may not be critical. If that's the case, Maintenance will order or repair the switch as a routine action when the aircraft can be scheduled for downtime. Until the switch can be replaced, each upcoming sortie will be evaluated to determine if the switch is critical to the flight or mission. Scenario 2: If it is determined that the switch is critical to the next flight (e.g. next sortie is cross-country or in-flight refueling is required), Maintenance will proceed to follow the processes required to remove the defective switch and expedite the following actions: * Check schedule for next flight/mission. Check TEPs (Training Exercise Plans) and Mission Planning Data for upcoming aircraft flight schedules to determine how much time is available to replace or repair the switch. * Check existing inventory within Squadron 211 for a replacement switch. If inventory is not available: * Check other on-base inventory locations, central warehouse, other Squadrons, etc. via NALCOMIS or contact Squadron Leaders by phone. If inventory is still not available: * Check with supplier to determine if a new switch can be purchased and shipped in time to meet the next flight/mission. If the suppliers lead time does not support the schedule: * Check to determine if the switch can be repaired, installed and tested before next scheduled flight? Check Maintenance Manuals for repair level (Organizational, Intermediate or Depot level) to determine who does repair for this item. - If repair can be done at the Organizational or Intermediate level, check Maintenance instructions for resources required (e.g. certified Electrical Technician, Government Support Equipment, special test equipment, special tools, etc.). Check availability and schedules for resources to determine if repair and installation can meet next flight schedule. - If it is a Depot level repair item, check with Repair Facility to see if repair can be accomplished in time to meet next flight schedule. Check average repair turn-around times from previous repair data if available. If the repair cannot be accomplished in time to meet the next flight schedule: * The Commander is notified to make a decision: - Pull the aircraft from active/operational status - Replace the aircraft with another of the same configuration/capability - Cannibalize from another aircraft The Commander directs Maintenance to cannibalize from another aircraft. * Check Maintenance Scheduling to see if an aircraft is currently grounded for repair or maintenance. If the answer is yes, can the switch be removed without impacting the current maintenance schedule? - If there is an impact, (maintenance activity has already begun on the aircraft in the hanger or a replacement switch won't be available before scheduled completion date), the Commander and Scheduling will need to negotiate new maintenance schedules and priorities for competing resources (e.g. hanger space, tools, test equipment, technicians, etc.) When new maintenance schedules have been approved and issued, the switch will be removed from the aircraft and re-installed on the aircraft that originally reported the failure. If the switch passes functional test, the aircraft will be returned to the fleet in time for the next sortie. Aircraft Maintenance records are updated to reflect the action taken. At the same time, a new switch will be ordered (or the defective switch repaired) to replace the one that was cannibalized. Maintenance will update the schedule to add the installation task. ----------------------------------------------------------------------