Bargaining Between Goals

Introduction

The bargaining system described below Is built upon three basic ideas: the first is the use of framts, a generalized property-value representation that provides a rich description of acceptable assignments for each value. Frames are used by the scheduler to describe both people and activities. A vocabulary is developed for expressing default choices, legitimate variations, preferences and requirements. The second is the generation of a posstbtltty spact that provides a simplified overview of alternative solutions. The possibility space Is constructed from linear plans, i.e. schedules for each activity developed independently of one another. The third Is an explicit representation of various bargatntng ttellntquts that Include strategies for relaxing defaults, preferences and even requirements. These bargaining techniques are used to debug linear plans by resolving conflicts between activities scheduled at the same time. Hence, the analysis of bargaining represents an ex tension of recent work on debugging [Goldstein 7i, Sussman 73] applied to a new, non-procedural domain.

The scheduler which I shall describe plans a week's activities for an individual as well as alters his tentative scheduling in response to unexpected appointment requests. It is member of a class of AI projects generally called Personal Assistants. Personal Assi.stants are an increasingly popular domain for AI research. At MIT, Fred Kern is programming and continuing the development of the scheduler described In this paper [Kern 7i]; Mitch Marcus has considered the Information retrieval problem [Marcus 7i] and Dave McDonald has analyzed the task of English generation by the assi&tant [McDonald 7i]. Projects for programming a Travel Budget Manager and an Apartment Finder are currently underway at Bolt, Baranek and Neuman [Woods 7i] and Xerox Palo Alto Research Center [Bobrow 7i]. This popularity Is well-deserved. It is the author's opinion that in the coming years AI techniques will make a significant impact on the Personal Assistant domain and, in partic·slar, on the design of personal resource (money, time, effort) and personal information (letters, papers, notes) management systems.

Before entering into thr. details of our analysis, the reader may wish to know what this paper has to contribute to the scheduling problem th<tt is not already included in the

'BltR~ltlRlR~ 'BlTWl[R ~01tL:S

Ira P. Goldstein Massachusetts Institute of Technology Cambridge, Massachusetts

various scheduling programs that ex1st for allocating time, money or space resources. The answer hes in the use of a much larger amount of knowledge in order to reach more Intelligent accomodations between conflicting goals. The traditional scheduling situation is one in which there are a great many items to be scheduled, but, for each item, the system knows oniy a small number of absolute requirements. An example is allocating classrooms for lectures at a university, where for each lecture the system has been told the required length of time and frequency. This kind of problem Is basically one of fitting together a jigsaw puzzle from pieces of predetermined shape. Our interest, however, is in a different kind of bargaining situation: namely one in which the number of events to be scheduled is smaller; but where, for each event, we have available a rich set of knowledge regarding the relevant constraints. We do not expect to meet all of these constraints, but rather come to some compromise between conflicting goals. In our bargaining domain, the pieces of the jigsaw puzzle ue over-specified and part of the solution lies in changing the1r shape.

A final caveat for the reader : the design of the scheduler described in this paper is as yet only tentative and the program is only partly written. I believe the paper should be of interest as a study of the kinds of knowledge and techniques that play a role in the common sense process of satisfying conflicting constraints. But there inevitably will ~e some funy points in the ensuing discussion, especially with respect to the overall control structure, that represent the gap . between design and implementation.

Scheduling Frames

Frarnts are data structures that provide expectations regarding assignments of values to various Important properties [Minsky 197i, Winograd 197il For our scheduling system, frames are provided which describe the time requirements of various activities and the particular preferences of individuals.

Let IRA be a hypothetiCal individual using our scheduling system. In order to produce a plan for the expected activities in IRA's week, without excessive specification on the part of the user, default assignments are prov lded for the important properties or the expected activities such as the desired TIM~: and DURATION of meetings of the Personal Assistant Research Group.

(pa-mcelinc (rcqur.ney (tlr.fauh (day 1)))

(pa-meellnc duration (ddauiL (hour J)))

Similar advice is prov1ded regardmg other activities such as LUNCH, RJo:s~:ARCH, and n :ACHINC.

Figure 0

(leaehinc (prep lime) (rcquirr.mMl (bdorr. (prep lime) (lecture lime))))

(ira (prr.p duration) (dcf auiL (h11ur 6)))

(ira (prr.p duralilln) (range (br.lwr.r.n (h11ur I) (hour 6))))

(ira (prr.p lime) (prderencr. (durin~: (prep lime) (day (lecture lime)))))

However, conflicts may arise such as those caused by the unexpected arrival of an important visitor. To cope with them, additional information is provided regarding acceptable ranges in which a property's value may fall, preferences which are desirable but not necessary and rtqutrtmtnts which must be met if the activity is to be successfully scheduled at all . The following assertions provide such information regarding the scheduling of preparation time for IRA's lectures. (Fig. O) Further examples of each of these different kinds o( advice regarding value assignments Is provided in Figure I. This type of Information allows the system to engage In various kinds of bargaining which we shall describe In greater detail In a later section.

Linear Plans and Possibility Spaces

In order to generate a reasonable default plan for the week's expected activities, the scheduler collects IRA's requirements, defaults and preferences for each of his activities. Figure I Illustrates a subset of the database concerning Personal Assistant Meetings viewed from this perspective. The advice regarding each activity Is collected rrom the person's frame. the activity's frame, and superiors of these frames pointed to by a-ltinol-of pointers.

Jlpn l - Schcdullnr Ad·iee for lhe Wnr.Uy Peraonal Auialanl Croup Meeli111

From tAt frame for PA·MEETINGS

(pa-meetinr time (prderenee (durinr lime :ahe,_)))

(pa..,._tinr frequr.ncy (defaull (day 7)))

(pa-tneelinc frequr.ney (ranne (olay 6), (day 7), (day I)))

(pa-moollnr duralion (ddauh (hour I)))

(pa-meellnr duralion (ran~:r. (between (hoar .75) (hour 1.5))))

From tltt frame for IRA

(Ira (mr.elinr time) (prdr.rrner. (durinc lime :friday)))

A llntar plan is then constructed for each activity, i.e. it is scheduled at some time, independently of the existence of other activities. The time is chosen on the basis of advice extracted from the frame for that activity. from superiors of that frame linked to it by chains of "a-kind-of" relations and from advice about that frame contained any person frames Involved as participants.

The set of linear plans for each of an individual's activities forms a posstbtiii'J space of alternative calendars for the week. Figure 2 shows such a possibility space for IRA. (Teaching actually consists of two activities, lecturing and preparation. However, for simplicity, it Is shown as a single block of time.)

This structure is built by considering each activity of IRA Independently of the others. u.s~:ARC:H , for example occurs on every day because of the preference that its total duration be maximized . J.IINC:H is scheduled at the default time of II rather than 12 because IRA's preference for an early lunch overrides the default time of 12 given in the lunch frame. TF.ACHJNG includes both classtime and preparation and is therefore intended to last the entire day. The conjunction of a preference for meetings on Fridays and pa·meetings in the afternoon causes the PA-Mn:TJNG to be scheduled on Friday at I.

The possibility space, viewed as a con JUnction of linear plans, has bugs in the form of conflicting activities. Lunch and research, lunch and teaching, research and teaching, research and meetings ·· all of these pairs of activities conflict. Thus, we have found the first instance in which bargaining techniques must be applied.

Bargaining Techniques

Bargaining techniques are required to debug conflicts between activities in the weekly plan of a single individual as well as to schedule appointments given conflicting constraints of the participants. These techniques fall into two classes. The first , which I shall call rtSourct·drtvtn, are experts at altering the particular interval chosen by some goal, while still satisfying the goal. They include relaxing defaults, rtlaxl'llg prtftrtncts, sruapptng Intervals, ttme shartng and tnttrrrtpttng. These strategies are expert at manipulating the "time" resource. They have obvious analogues for manipulating other resources like space and effort. These strategies do not question the justtfication for pursuing the goal, but rather attempt relatively local alterations of the various kinds of advice -- defaults, range, preferences ·· that allow the interval to be altered without actually violating the overall goal.

The second class of techniques are purpou·drtvtn. These strategies, as opposed to the resource·driven techniques, are capable of eliminating or modifying requirements. They do so by altering the least important goals, as chosen by analyzing the overall purpose of the event. The resource· driven techniques are ignorant of the relative importance of competing goals and _are therefore unable to be as radical as the purpose·driven strategies.

These bargaining techniques can b~ viewed as dtbuggtng strattgtts for resolving unforseen interactions between linear plans. As such, they represent a further analysis of the stmpltf1 and dtbug problem solving paradigm explored in recent papers by [Goldstein 7i] and [Sussman 73l

The following paragraphs describe each of the techniques that we currently plan on implementing in the scheduler. The control algorithm which administers these techniques is discussed in a later section on Control Structure.

Compromtu by Relaxing Defaults

Default choices represent only estimates. Conflicts can sometimes be resolved by changing the default, while still remaining within the required range.

Figure 2 - - Possibil it~ Space teaching [9 51 for the ~eek's Activities pa-Meeting [1 21 teaching [9 51 Meeting [9 51 research 19 51 research 19 51 research 19 51 research 19 51 research (9 51 lunch Ill 121 lunch Ill 121 lunch Ill 121 lunch Ul 121 lunch Ill 121 M T ~ A F

Compromtst by lnstrtlon

Some activilie~ are indicated as being interruptible, e.g. research . For such activities, the negotiation strategy is available of interruptmg one activity long enough to insert another. A heuristic restriction hmit~ any activity to at most two interruption~ (A more adaptable ~y~tem m1ght inquire of the person being modeled how many interruptiOns he is prepared to tolerate for each of his "interruptible" activities.) The conflict cau~ed by lunch in the previous example of scheduling IRA's week (figure 2) can be resolved either by interrupting R~:s~:ARC:II and M~:~:TIN�S for lunch or by use of the sltartng strategy introduced in the next paragraph.

Compromtu by Sltartng

Some activities are indicated as bemg sharable, e.g. lunch. Conflicts between such activities can be eliminated by scheduling them at the same time, 1.e. the conflict is dismis~ed . A more intelligent scheduler might be able to reason that some activities like eating and meeting can be shared while others like eating and sleeping cannot. For simplicity, the current design handles this by simply grouping activities into two classes: sharable and unsharable. A sharable activity can share time with any activity not explicitly labeled unsharable. However, a desirable extension would be to represent In the frame for a given activity, exactly those other activities with which it can share time and those with which it cannot.

Compromtst by Swapping

Sometimes the requirements and preferences of some activity imply only a duration and a frequency, but do not actually specify the day. Hence, some conflicts can be resolved by swapping one such activity with another. The virtue of the swap is that the new activity scheduled in the blocked time may be relaxable, interruptible or sharable, whereas the previous occupant of the time slot was not. A swap is prevented if the event is scheduled at the original time due to requirements of the activity or the participants that entail a specific day.

Compromtst by Rtlaxtng Prr(arnets

Conflicts betweeri competing requ~rements and preferences are resolved in favor of requirements while conflicts between competmg preferences are decided in favor of maximizing the number of satisfied preferl'nces. This strategy of relaxing preferences is tried only after the others listed above. It generally fails when requirements make removing the block impossible.

Possibly a more subtle use of numerical utilities will be necessary. For example, a common sense system ought to be able to take account of the advice that a particular individual prefers a meeting (I) as early in the day as possible, (2) as soon as possible and (3) in the event that these two preferences conflict due to pre-existing appointments, to consider one day earlier to be worth making the meeting one hour later in the day.

For the example of planning a week discussed in the previous section, the conflicts between research and teaching on Tuesdays and Thursdays (figure 2) are resolved in favor of teaching since the requirement that teaching take place on those days dominates over the preference to maximize research time. Time-sharing, insertions and relaxation are sufficient to remove all of the conflicts from the possibility space for the week and the result is the debugged plan of figure 3.

Compromtst by Rrqrust

This and the following two strategies represent techniques that can relax or eliminate requrrements. They do this by questioning not simply the local choice of time, but the overall justification for the activity or for some of the participants. I shall call these techniques purpou-drtvtn bargaining.

A measure is provided for the relative importance of various participants . When absolute requirements of individuals conflict and there is no resource-driven settlement possible, the system asks the less important individual to compromise by relaxing his requirements. Figure i illustrates the frames which define the MOR~:-JMPORTANT relation.

;Framt for a rtlatton (comparison a-kind-of relation) lcomparision 2-place relation) (comparison transitive) lco~parison anti-symmetric) ;Framt for tltt MORE-IMPORTANT rtlatton (more-important a-kind-of comparison) (more-important argl person) (more-important arg2 person) (more-important leader participant) (more-important teacher student)

This static partial ordering represents, of course, a gross simplification. Ultimately, we would like to see the system be able to change the "importance" with which the preferences of an individual are regarded in accordance with the context­ dependent role that he happens to be playing, e.g. host versus employer versus friend . Purpose-reasoning is introduced in the next section to partly meet this need of a more dynamic importance relatron.

Compromise by Elimination

Again the strategy is to relax requirements, except in this case, the BARGAINER attempt~ to decide which requirements can be eliminated, rather than asking the participants involved. This is accomplished by utilizing the MOR~:-

Figure 3 -- The loleekly Plan

pa-mee t i ng 11 21 research [9 51 teaching 19 51 research 19 51 teaching [9 51 meeting 19 111,112 Sl lunch [11 121 lunch Ill 121 lunch Ill 121 lunch Ill 121 lunch 111 121 M T lol R F

IMPORTANT metric descr ibed above plus purpost chtcktng. Purpose checkmg is necessary to prevent the pre-defined importance relation from causmg a person to be dropped from a meeting even though without him the meeting is pointless.

An example is the problem of scheduling an Oral Examination for three professors and a student. The pre­ defined ordering of importance rleclares professors to be more Important to students, 1n the sense that given conflicting desires for a meeting lime, the preferences of the professor are maximized. Hence, wllhout purpose reasonmg, conflicts in scheduling the Oral Examination would probably result in the student being dropped from the list of participants. This is prevented by declaring that the purpose of the group meeting is for the student to be present.

Currently, the system is capable of only very elementary purpose reasoning based on "required participants". Such requirements are recorded ellher as assertions in the appropriate awvity frames or as addttional advice given to the system at the time of the appointment request . Typical examples are shown in Figure 4.5. ·

Purpose reasonmg ts a type of common sense logic that AI programs must have to be able to debug conflicts. The scheduler, as currently planned, will be capable of it in only an elementary way. This is clearly an area which merits further study.

Compromlst by Substitution

Substitution applies the swapping technique described above for mtervals to participants. Again, purpose reasoning Is involved . If a visitor requests an appointment with a faculty member of the laboratory, the request is generally routed to some particular mdivtdual . If he cannot schedule an appointment , then the bargainer seeks a substitute participant from its list of known people and requests that he accept the appointment.

CompromiSe 1>y DiviSion

Resolve a conflict between parttcipants by attempting to schedule the meeting twice for different subsets of the Intended participants. This represents an instance of the general planning strategy of breaking a goal into sub-goals whose conjunction satisfies the original purpose. In the scheduling context, it ts often an ineffictent technique because some subset of the participants usually must attend both meetings. Hence, it is generally not preferred. Some activities such as oral-exams are not divisible into separate meetings. This is indicated in the frame for this activity under the TYPJo: property.

Figure 4.5

Comparison to Traditional Schtdultng Algorithms

Recall our earlier reference to traditional scheduling programs. We can now bt> more precise in stating their limitations. Because such algorithms are knowledge-poor and do not know anything but the baste requirements of the various items to be scheduled, they cannot relax defaults or prtftrtncts, nor know whether a particular item is tnttrruptlblt or sharablt. Simtlarly, they are not knowledgable enough to examine purposes and decide upon eliminations or substitutions. On the other hand, the bargaining system that we have designed has available to it a richer set of strategies for reaching an accomodation because it has far more knowledge about each item. knowing both preferences, ranges and defaults in addition to requirements.

A Meeting Scenano

I shall further illustrate the use of these bargaining techniques by noting that an individual's weekly plan is not absolute. An unexpected visttor may arrive and request an appointment on a day previously planned for some other activity. In such a case, we would like the system to consider its options and reschedule its planned activies if possible. The scheduler's strategy for accomphshmg this is again to build a possibility space of linear plans. This space is then examined for the least blocked times and bargaining techniques are applied in an attempt to remove the constramts responsible for the conflict.

Suppose a visttor sends IRA a telegram requesting an appointment on the next Monday . This results in the following posstbllll'j space of appointments. "(· <PJo:RSON>)" indicates that the person can make an appointment during the Indicated time while "(- <PJo:RSON>)" indicates that he cannot. The first line of Figure 5 is tht> linear plan for when IRA can make the appointment and the second line is the linear plan expressing MV's choice of meeting time.

The BARGAINER examines this Possibility Space and looks for the best point at which to consider a compromise. This is the least blocked interval. Monday and Friday are least blocked intervals with blockage equal to I. The followin~ paragraphs trace the alternative bargaining strategies that are considered in an effort to find an acceptable appointment time. Ultimately, the BARGAINER chooses the strategy that violates the fewest preferences and requirements. (If there is more than one such "best" solution, tht> user is asked to choose among them.)

Resource-driven compromise by relaxing defaults, swapping. sharing, mterrupling and relaxing preferences are all possible if the blocking event event is not occupying its interval as a result of a requirement. Hence, all of these strategies are applicable to the block to the appointment on Monday caused by II' A'~ R·:.s~o:ARCH . On the other hand, the Friday block is due to the requirement, at least as expressed to IRA'R scheduler, that the visitor wtll only be in town on Monday. To this block, only purpose-driven strategies, i.e.

!meeting participant (requirement (> (number participant) 2111 lpa-meeting participant (requirement !participant leader))) loral-eKam participant (requirement !participant eKa~ineelll Figure 5 -- Possibi I ity Space of Appointments for IRA and MV 1- IRA I 1- IRAI 1- IRAI 1- JRAI I+ IRA! I+ MVI 1- MVI 1- MVJ 1- MVI 1- MVI M T IJ R F

compromise by request, by elimination, or by substitution, are possible.

Three of the strategies which can be apphed to eliminate the Monday block are bargaming by relaxing dtfaults, by insertions and by swappmg. That rtsearch on Monday has a duration of all day 1s a dtfault . Hencl', the boundaries of the research interval can be rc/axrd by one hour to make room for the appointment. This products the plan: schedule tnt appointment from f? /Of or /4 5/. Research is also tnttrrupttblt . Therefore, it is possible to insert the appointment into the Monday research, producing the plan: sclttdult tilt appointment for I hour any timt cluring Monday. Once this is done, the restarch is marked H no longer interruptible. Currently, the bargaining system prefers relaxing boundanes to mterruptmg an activity, in the absence of any governing preferences or rt>quirements. (This is based on the introspectivl' obst>rvauon that peoplt> prefer not to be interrupted once engaged 111 an actiVity. Another user, however, could obv10usly altl'r this default choice.)

Swapping produces the plan of Interchanging research time on Mondays with meeting time on Fridays . This approach would be preferred to either of the first two if none of the affected Friday activitil's had governing preferences that tied them to that day of the week . For t>xample, using Friday as an appo1ntmt>nt day IS a default but not a preference for IRA. Ht>nce, thl' swapp111g plan would be chosen to avoid violating the preference for maximizing research time since the first two plans decrease research time by an hour.

Purpou-Drtvcn Bargaining

The above resource-dnven techniques would be inapplicabll' if IRA had a requirl'menr that research occur all day on Monday (l'.g. a funding deadhne 1s drawing nigh). In such an evl'nt, the bargamer would apply various purpose­ driven techniques to altt>r either Ira's or the Visitor's requirements . The following paragraphs illustrate the application of such tl'chniques to the VISitor's request .

The strategy of attt>mptmg to compromise by request results in the Monday Visitor bt>ing asked by IRA's scheduler if he can rescht>dule his trip to be in town on Friday. In a world of ptrsonal assistant programs. this would involve a call to the visitor's personal assistant program.

Compromise by wbstitu/lon IS possible if the visitor's orginal appointment request did not R~:QIJIR~: a specific faculty member. If so, thl' plan would be to reschtdult tilt appointment with anotha tquivaltnt participant.

The two bargaining strategies of compromise by Eltmtnatton or DiviSion are inapplicable. There are only two participants so thl' number of people atttnding the mel'ting cannot be relaxed. Similarly, sub-divisiOn dol's not apply with only two partiCipants.

Control Structure

This sect1on dt>velops in greater dt>tail how the BARGAINER mt>diatl's bt>tWI'I'n tts vanous relaxation and reformulation stratt>git>s. Undl'r thl' current design, all of the applicable strategies are tnl'd, t>ach produc111g an alternative plan for elim111ating a givl'n scht>duhng conflict. The fmal solution is chosen on the basis of which plan violates the fewest preferences and requirements. This presl'rVE'S the philosophy of maintainmg a global ptnpectiVE' in the form of a Possibility SpacE' of alttrnative plans and not becoming trapped by an txcessivtly local ptrspectlve.

In those cHes where there are many conflicts (such as arise in planning an l'ntire week for a ~ingle mdivadual or a meeting among a group of people), our current Implementation plan as to apply the bargammg strategaes as search operators. Each strategy operates on the current calendar, producing a new cahmdar wath fewer conflicting events. Terminal nodes of the resultong tree are those with calendars containmg no conflicts. Procedurally, the current plan is to use a Coroutine Srarch whach initially e~plores the search space breadth first, but suspends those paths whose "utility" is less than the current maxamum, where the utility is defined simply as the sum of satasfaed preferences. If the paths currently being explored encountrr difficulties and their utility drops below that of some of the suspended nodes, then those nodes are reactivated. (This is the same kind of search as was used to find the plan of uncommented sample programs in [Goldstein 7i) and is also similar to thr parsmg algorithm used by Woods in tht> LUNAR system [Woods 71].)

Conch<sions ----

Our general approach has been one of generating a global overview and then debuggmg conflicts until a possible solution is obtained; rather than searching through a space of solutions by generating single pombihties until some choice meets all of the constaints. Thas latter approach, common in many AI programs, is non-optimal m the sense that the first plan derived which satisfies all of the R·:QIJIR·:MKNTS may very well not maximize the PRHER·:Nr.~:s. The use of a posstbtltt'j spaet both for the weekly plan and for possible meeting times a voids this myopia .

The bargaining techniques described above are an attempt to represent a kind of common sense reasoning that people commonly engage in as they jUggle the various demands being placed upon their limited resources of time, money, and energy. Few AI programs in the past have evinced any kind of robustness when the initial request is "unsolvable" and either the problem must be relaxed or reformulated . Combining bargaining with a rich frame­ oriented description of ordinary activities and people is a beginning towards permitting this new dimension of problem solving.

Finally, the last point which should be made about the scheduler is that it is a knowledge-rich system. Its success in finding a reasonable solution to organazmg a week's activities is fundamentally based upon a detailed description of the various people and actavatii'S 111volved. Future extensions of the scheduler will include a natural language discourse component . The knowledge-base will then be doubly important, as we expect it to support the required natural language ability of having reasonable expectations about what the speaker will say. Such expectations are necessary to provide a guide for the parsing and generation processes.

Ack nowleclgments

This research was conducted at the Artificial Intelligence Laboratory, a Massachusetts Institute of Technology research program and supported in part by the Advanced Research Projects Agency of the Department of Defense and monitored by the Office of Naval Resear.:h under Contract Number NOOOii-?o-A -0362-0005.