NUDGE, A Knowledge-Based Scheduling Program

Ira P. Goldstein and R. Bruce Roberts Artirieial Intelligence Laboratory Massachusetts Institute of Technology Cambridce, Massachusetts 02139

Abstract. Traditional scheduling algorithms (using thr These are not new representation techniques. Ahstractinn, fnr techniques of PERT charts, decision analysis or operations rrsrardl) example, was discussed in Quillian [68], and allachcd prncedurrs have require well -defined, quantitative, complete sets of constraints. Thry become a common property of AI languages sinr.e PLANNER [Hrwitt are insufficient for scheduling situatioM where the prnhl··m 69! However, the strengths and weakn(·sses of these rrprrsrnlatinn description is ill-defined, involving incomplete, pn .. ibly inconsistent techniques and their potential interactions is still not well undrr<tnool. and generally qualitative constraint&. The NUDGE program usr< an For this reason, we have chosen not to include as many reprr sentation extensive knowledge base to debug scheduling requests by surrlving capabilities as arc currently being implemented in KRI. [Rohrnw & typical values for qualitative constraints, supplying missing 1ktails Winograd 76] and OWL [Marlin 77]. We view t'R 1.-0 as an and resolving minor inconsistencies. The result is that an infnrmal experimental medium to study the utility of a fc,.· sprrofir. request i~ convert·ed to a complete description suitable for a capabilities and their interactions. lraditinnal scheduler.

To implement the NUDGE program, a knowledge rcpresrntatinn language -- FRI.-0 - - based on a few powerful gcnerali 7.ations of the traditional property list representation has been dcvdope<l. Thr NUDGE knowledge base defined in FRL-0 consists of a hierarchical set of concepts that provide generic de~criptions of the typical activities, agents, plans and purposes of the domain to he <r.hr.<lubl. Currently, th is domain is the management and coordination or This environment include& scheduling meetings, monitorin~ th r. personnel engaged in a group project.

NUDGE constitutes an experiment in knowlcdge-hasr.d, rathrr than power-based AI programs. It also provides an r.samplr. of an intelligent support system, in which an AI program serves as an aid to a decision maker. Finally, NUDGE has served an exp~rimrntal vehicle for testing advanced representation technique~.

l. INTRODUCTION

A classic issue in AI is the knowledge versus power r.ontrnvrrsv [Minsky & Papert 74]. The knowledge posit ion advocatrs that intelligence arises mainly from the usc of a large store of spuifi r. knowledge, while the power theory argues for a small collrr.t inn or general reasoning mechanisms. This paper reports on an ex p~ri mrnt in which a knowledge-based program NUDGF. ha~ h~en implrmrntr<l for the scheduling domain, a domain in which powcr-ha~c·l pro~:ram~ have long been the dominant paradigm.

Traditionally, scheduling programs apply simple hut. powrrful decision analysis techniques to finding the optimal schrdule umlrr a well-defined set of constraints. The performance of NliDGE confirms that for well -defined, formal situations, the traditional pnw~r-ha"'' approach is appropriate. But for the problem of defining these formal situations when given only informal spcr.ificat. ion~ , a knowledge-based approach is necessary. By an infnrmal spr.rifir.ation, we mean a scheduling request that is potentially incomplr.tr, pMsihlv inconsistent and qualitative. (See Balzer [74] for an analysis nf ~nformal program specifications.) Thus, the NUDGF. program ar.crpts mformal requests and produces a calendar containing pn<sihlc conflict& and an associated set of strategies for rf!~olving thnsr. conflicts. A domain-i!'dependent search algorithm BARGAIN then resolves these conflicts by traditional decision analysi~ techniques.

NUDGE uses a broad data base of knowledge to upand an·l debug informal scheduling requests. The database is used to surrlv missing details, resolve inconsistencies, determine available opt ions, notice necessary prerequisites and plan for expected outcomes. To manage this large store of knowledge, a representation language -­ FRL-0 -- has been implemented. FRL-0 extends the traditional attribute/value description of properties by allowing proprrli~~ to he described by comments, abstractions, defaults, constraints, indir~ct pointen from other properties, and attached procedures.

Because a knowledge-based approach requires a large storr of specific data, it was necessary to choose a particular domain to ra rrv out our experiment. Our criterion was to select a realm in wh irh scheduling requests are typically informal. This criterion rulcol nut such scheduling problems as those of an assembly line. (Sr~ Tnn~:e [63] for an AI treatment of this problem.) lnst~a·l , we sdr.ctrol nl'lil'<' scheduling; in particular, assisting a manager in ~r.h~·luling his tr.1m. progre~s of su hgoals assigned to team members, alerting the manal(r. r to deadlines, and real-time rescheduling.

In providing NUDGE with the knowledge nr.r.r.«arv for th r sr. functions, our research serves a third purpose beyond (I ) rxplorin~: the relation between knowledge-based and power-has~d schr<lulin!! and (2) exercising various representation strategic~. It prnv i·lr.s insight into the categories of knowledge that arc ncr.rssary for oHi r.e sch~duling (independent of their representat ion). i'IIJDGE contains a hierarchy for activities involving information transfer, for prop!~ in various roles related to this transfer, for thr. plans governing thrs~ transfers, and for the associated demands on time, spar. r. anol personnel. The hierarchy is on the average fivf! levels ,J~rp an·l includes approximately 100 objects, each described hy a generali1.r<l properly list called a frame. An abridged version of this hicrarrhy appears below, with specialization indicated by nf!sting.

The term "frame" as used in FRL-0 wa~ in<pire·l by Minsky'~ [7S] de·tdopment of frame theory. Frame thMry cnnt·nds that (I) intelligence ari·es from the application of larg~> amount< of highly specific knowlr.dge, u opposed to a few general infcrcnc inj.' mechanisms, and (Z) this is accomplished through the u<c of a library of frame~, packets of knowledge that providr. dc~cription< of tvpical obj~nd cnnU. These descriptioM contain both an abstra.ct template providintr a skeleton for describing any in<tance an·l a <et of defaulh for typical members of the class. Thr. defaults allnw the information system to supply missing detail, maintain u pert at i·ms, and notice anomalies.

Wr. have yet to investigate with equal carr. relater! areas of knowledge not strictly involved in scheduling thr. information flow between members of a research team -- this indudrs space allocat inn, budgeting, and travel scheduling. The last of t.hcsr. is the for." nf the GUS system developed by Bobrow ct al [76~ GIJS is a frame­ based dialog system that addresses many nf th~> i«ucs raisrtl hne. The majnr difference is that GUS focusses on the usc of frame representations to support dialog comprehension whil~> N II f)G E focusses on their use to support sophisticatlld schr.rluling.

Finally, although developed for the office scheduling rlomain, th~> NUDGE knowledge base does have a broader applicability. The usc of a hierarchy of successively more abstract concr.pts allows highly specific information to be clearly scgrr.gated from more general facts about the world. Furthermore, some of the concept hierarchies such as those for time and place apply in lolo to many other application<.

Z. SCENARIO

The following request is typical of those undcrstootl by NIJDGE.

(Sl) NUDCE, achedule a meeling lllilh Broce for nP.:rl Tue.cday.

Sl is an informal specification in that such facts as the following arc left unsaid:

Where the meeting is to be held. Which Tuesday is nell Tuesday. What time on Tuesday is prcfcrrcrl . How Jon.: the meeting is should last. Whether there are any prcrcqui·itc·. What to do if Bruce is unavailable.

As such it is typical of the requests made by people of one a not her. Gi·cn a knowledge of the individuals involv~d, their rol~· anti th~ context, NUDGE expands Sl to the more complete Sl', whrrc the added information is in italics.

(Sl') I UNDERSTAND YOUR REQUEST TO i\I~~AN : SCHEDIJJ.E A MEETING WITH BRUCE liND ME /IT 3 IN Till<: IJFTf:RNOON NEXT TUESDAY ONE WEEK FROM TOMORROIJT 1./ISTING ONE IIOUR IN MY OFFICE TO DISCUSS Tiff: PF:RSO!V/11. IJSSISTIJNT PROJECT.

When procc~sed by the the language comprehension comronr.nt or NUDGE [Bullwinkle 77], Sl causes the construction of a rramr gestalt, a data structure of instantiated framu containing all information in Sl'. (The actual text of Sl' is generated by the text output procedures associated with the frames in this gestalt.)

The knowledge-based phase of the scheduling condudes with the eonersion of the information in the frame gestalt to a calt'ntlar containing possible conflicts and 111 associated ~et of strategies f ot resolvintr those conflicts. The BARGAIN program then rcpnrts thr highest utility compromise to the user.

(RI) YOUR PREFERRED TIME FOR MEETING WITH BRiiO: 0;\1 TUESDAY IS ALREADY FILLED BY A MEETING WITH MARK. HOWEVER, MARK'S PURPOSE IS TO DISCUSS I.AN�IJ A�~: RESEARCH AND CANDY IS AVAII.ABI. F. . SHAJ.J. I RF..SCHEDULE MARK TO SEE HER INSTF.AD.

Mark's purpose is not specifically to sec Ira, and hence, a memhrr of Ira's group can be substituted to see Mark. Ob·ervc that accr« to a diverse set of 5chcduling strategies has made it unnccc«ary to juggle the pot;sible time of the meeting between Ira and Bruce, protlucing a compromise not entirely satisfactory to either. ln·tcad, a ·ufficirntly broad peupcctive has allowed NUDGE to identify the option of findintr an altcrnati·e participant by referencing the purpose nf thr conflicting appointment. A knowled.:e-ba~ed phase in the schctlulin~ thus noids the myopia a purely power-based approach can exhibit.

Continuing the scenario:

(SZ) Ye1.

(RZJ THE MEETING WITH BRUCE IS SCHEDULED. SHOIJI.D BRUCE PREPARE -A WRITTEN PA PROCRF~'IS REPORT?

(S3) Ye1.

(R3l I WILL RF.MIND BRUCE ABOUT THE RF.PORT.

Section 3 describes the frame gestalt representing N IJ DG E'· completion of the Sl request. Section 4 discu·scs the represrnt at ion techniques of FRL-0 supporting the creation of the gestalt. Srction S analyzes the underlying knowledge of activities and individual· represented with these ·techniques.

3. THE FORMATION OF FRAMF. r.F.STAJ.TS

A frame gestalt consists of a set of generic frames, instant iat.r·l appropriately for a particular scheduling request. The generic frames are selected on the basis of clues implicit in the ·rhr<luling request; knowledge-based reasoning begins with a rccognit ion process. Information missing in the request is then computrd. frnm defaults, constraints, and procedures --all u·ociatcd with thl'sc generic frames. For.Sl, the .:cstalt includes the frames shown below, with daughters of a frame representing its cpccialiutionc. Many other interrelations among these frames arc not shown.

The goal of the knowled.:e-bascd phase is to compute this frame gestalt.

The input to the gestalt formation process is a set of partially instantiatlld frames reprcsentintr the information actually prrscnt in the informal request. This input is generated by a natural language front end consistintr of the Wait-and-Sce-Par·u tlc...-loprtl hy M. Marcus [76] and a frame-based semantic· dcsi~ncd by C. Bullwinkle [77]. There are four partially instantiated framr.· : MEETING37, SCHEDULEZl, INTERVAU7, MOMENTS4.

MEETING37 is the frame for the proposed meeting and initially contains information regarding the participants and time of the .-vent eatrac.ted from the English request.

HEET1N637

MEETING37 reports that the participant~ arc Rrucc anti Ira. Bruce is known from the semantic interpretation of Sl, while Ira i< inserted on the basis of pragmatics, i.e. that the pcr<nn r~qur<t inr the meeting wishes to be included amnng the participant<. MEETING37 has been identified by pragmatic~ a~ A-KIN D-Ot" (AKO) PA-MEETING on the basis of knowledge regarding the common activities of Ira and Bruce. Had no such special knnwlrdg<> existed, the sentence would simply have triggered an instance of th~ MEETING frame.

The first clement of these frame structure< is th~ name of thr. frame name and each remaining item is a slnt. Each slot has one or more values, explicitly marked by the IVAI.II~: fac~t. A frame is thus simply a multi-level association list. The semantics of attachr.tl procedures . and inheritance is enforced by the access funr.tioM.

4. REPRESENTATION TECHNOLOGY

The formation of a frame gestalt occurs by expanding the thr frame~ extracted from the initial request in terms nf the knnwlr·lrr. stored in the FRL database. This section discusses this prncr.« in terms of the contributions made by six reprcsr.ntations techniques embedded in FRL-0: comments, abstraction, ddaults, rnn<traints, indirection and procedural attachment.

(l) Comment~. The firU generalization of property lists in FR 1.- 0 is the inclusion of comments attached to values. Comments ar~ used in these examples to record the source of the value in each slot. So far, the only ·ourcf! is the semantic and pragmatic intr.rpr<>tatinn performed by the language comprehension process. Alternative sources are inferences made by attached procedures anti inhnitr.<l properties. Other kinds of com.:ncntary provide numerical utilities fnr use by the scheduler, and ducribe differences between multiple proccd ural methods attached to the umc slot.

This commentary provides guidelines both for RARGAIN to judge the reliability and and 5lrength of various constraint< and fnr NUDGE to debug inconsistencies arising from conflicting contributions by different frames during the gestalt formation process. The former would arise if conflicts exist~d hr.twrr.n thr generic information of the IRA and BRUCE framrs, while the l.1tter is exemplified by Sl being part of a dialog. The srntenr.~ "Thr meeting should be tomorrow in my office." would override the default suggested by generic knowledge. Our usc nf commentary to guide a debugging process derives from research by Sussman [7:1] anti Goldstein [74l

Self-knowledge, in the form of machine understandable annotations, also facilitates the system's ability to explain its inferences to a user. This is critical if thr. user i~ to ber.nm~ confident in the system's capabilities.

(2) Abstraction. The second property list gcnr.rali7.ation is to allow information to be inherited between concepts. In essence, this is an implementation · of Quillian's SUPF.RCONCEPT pointer, but between property lists rather than nodes in a semantic net . ..,. example, details of the meeting between Bruce and Ira arc inhentrtl from a generic description of PA-MEF.TINGs. This tlrsr.ription includes answers to such questions as where such meetings arc typically held, when, why, who is involved, what prcrequisitrs arc required and what consequences result.

Since the answers to some of these questions is clearly applicable to a broader set of acti·itics than meetings of the PA-GROIIP, the information is d.istributed in a hierarchy of successively morr. general frames, thereby achieving both power and economy.

Each frame points to its generalization by means of its AKO slot . The p~ocesa by which information in a generic frame is acquired by a specialized instance of that frame is called inheritance. Mf:~:TIN�:l7, for example, inherits information from its generalization, the PA­ MEETINC frame.

(3) Dr.£aults. The third generalization that naturally acr.ornpanirs a hierarchy of frames is default information, a~ thr. slots of a ren,ric activity typically supply default answers to tho common qurstonns asked about such events. The utility of such default information was a major insight of Minsky's original frame< research. Their us~ is prevalent throughout the NUDGE database, and give the sr.hrtl ulrr much of its power.

For example, PA-MEETING supplies the infnrmation that sur.h activities typically involve four people, occur on Fridays in thr AI Lab Playroom and last one hour. The SD~:FAlli.T atom tlistinrui , hrs defaults from values. We shall refer to the different kirul< of information usociated with a slot as its facr.ts. The role cnmmrntary information associated with the participants of PA-l\IF.ETJi\Gs i< used by the PERSON-SWAPPING scheduling strategy nf the BARGAIN program. (Managers are optimistically dr.fin~d to know all of the team members' roles.)

In forming a frame gestalt, the defaults of superior framrs "'" used unless they arc overridden by information from a more rdiahl" source, such as the explicit constraints of the original rrqurst .. Thu<, the WHERE default would apply to the MEF.TING37 gestalt . Tlor WHEN default, however, is overridden by the explicit requrst in Sl that the meeting occur on Tuesday.

Defaults are also useful to the natural languare untlr.rst.antlinr system by supplying expectations that aid the parser and semantics in processing ambiguity and ellipsis. However, we do not develop I hat application here.

(4) Constraints. A knowledge rcpre·entation lanruagr. must accommodate descriptions of properties if it is to support thr. recognition of new instances of a generic concept. FRI.-0 allnw< constraints to be attached to a slot by means of facrts for requirements and preferences. These constraints arc illustratr·l in the MEETING frame, which is the immediate generalization of PA­ MEETINC.

HEETI116

AICO SVALUE ACTIVITY

WHO SREQUIRE (EXISTS ?WHO (HAS-ROLE 'CHAIRMAN))

WHEN $PREFER (NOT (> (DURATION ?WHEN) (HOUR 1.5}))

Requirements arc predicates which mu5l be true of thr. valurs in a slot. Preferences can be relaxed yet leave a valid slot. Thr IREQUIRE facet. of MEETING stipulates that a chairman hr prrsent at all meetings. The SPREFER facet states that me~tinj.'~ slooultl nnt last longer than 90 minutes.

It i5 possible to collapse defaults, prcfcr~ncr.s and rr.quirr.rnrnts into a single CONSTRAINT facet. However, we have fount! it con·enient to pre~cne the distinction, given the usc of thr·e f arcts by a scheduler. Requirements cannot be relaxed . Prr.f errnr.rs, however, can be negotiated. Defaults are prr.fcrcncc~ that offcr specific alternatives, rather than acting as predicates on a set.

KRL's development of "perspectives" in which a frame is described from a particular viewpoint is a more clabnratr. kintl nf con~traint than we typically employ. While a f ramc pattern matchrr can, in essence, ~pecify a perspecti·e, we have not ,;~nerally used such a device for the narrowly defined world of office scheduling. Whether an extended description mechanism will be needed for more complex applications remain& to be seen. Our current plans arc to <cl' where FRL-0 fails before we incorporate more powerful, but more complex techniques.

(5) Indirection. Not all of the relevant dc~cription of MEETING37 i~ contained in abstraction< of the merlin~: r.onr.rpt. Frames in orthogonal hierarchies also supply con~traint~. t"or example, activities involve agents, and the frame< for the<r a~:rnt< have relevant information. The frame <ystcm ha~ <rparatr hierarchies for activities and people, interconnected by in·lirrr.tion. The IRA frame exemplifies this.

The first atomic slot identifies Ira as a pcr<on. The remaininJ! non­ atomic slots (ie, slots with compound name<) provide inform.llion regarding various activities with which IRA is typically involvr·l. For example, in general IRA prefers MEETING< on Friday ahrrnoon< in his oHicc. This information is not stored directly in the arl iv itv frame since it not generically true for the activity, but only applicable when IRA is involved. IRA's default of NEH-R19 a< the place to hold meetings supplies the value of the W HER~: slot of MEETING37.

The indirect information appears in the frame gc<talt if both the agent and activity frames arc triggered. For Sl , trig~:crinl: IRA ~ml MEETING together resulted in the frame gc~talt <upplyinJ! thr missing information regarding the location of the meeting. Thu<, indirection provides links between diHercnt hierarchiC<, cdendinJ! 1 hr frame system to include a network of contingent fact<.

Indirection is a simpliried kind of mapping bet ween concept<. FRL diHcrs from MERLIN [Moore & Newell 73) (in which grnrral mapping is allowed) by providing a restricted but more <lrur.turr·l environment. Mapping occurs, in essence, only between a~:rnt ami activity framM through indirection and between conrept and superconcept frames through inheritance.

(6) Procedural attachment. A knowledge rcprc<cnt.ation mu<l allow procedural as well as declarative knowledge. Proce·lural attachment provides this capability in FRL-0.

There are typically three kinds of procedural attachment, ami all arc provided in FRL-0. Thc<c arc if-added, if -nrr·le.l, and if -rrrnO\'r.t methods. A diHcrcncc from traditional AI langua~:r< is that thr"' procedures arc attached to the slots of a frame rather than t.o a<scrtions of an arbitrary form. FRJ.-0 is thus a more <I rurturr·l environment than languages like PLANNER an·l CONNIVER [McDermott & Sussman 72l Providing a mer.hani<m for tri~:~:r.rin~: arbitrary procedures by adding a value to a slot supports the fundamental operation of FRL-0 which is instantiation; that is, creating an instance of a frame and filling in value< for it< <lots.

for example, when the time of MEETING37 is arranged (a value of the WHEN slot is assigned) its name is entered in a calendar for easy reference. The method for doing this is supplied by the W H ~:N slot of the ACTIVITY frame.

ACTIVITY also illustrates if-needed methods. Thc<c mctho·l< allow access to arbitrary procedures for supplying values. ··or eumple, eumine the WHO slot of ACTIVITY. There arc two if­ needed methods there. The first, (ASK), is a function that rcque<ts the value from the user. Its purpose is indicate·l by the comment TYPE: REQUEST. The other method, (USE TOPIC), attempt< to deduce the participants by accessing the WHO slot of the frame provided as the value of the TOPIC. The comment on ihis mrtho.t indicates that it is of TYPE: DEDUCE. The TYPE r.ommrnt< arc used by the function controlling the overall in<tantiation procrss (thr if-needed method of INSTANCE in THING, which all frames inhrrit l. Their function is to allow deductive methods to be u<e·l in prrfr.rrncr. to interactive requests if possible.

If-needed methods have widespread u<c. Defaults can he viewed as a special kind of if-needed method, so useful and widcsprra·l that a special facet of a slot is devoted to it. ldio<yncratic forms of inheritance (using other than the AKO link) can be imhrddc·l in an if­ needed method for appropriate slots.

Attached procedures are also used to maint.ain the intr~:rit. y of the database. for cumple, AKO and INSTANCE arc <lot< that provide a two-way link between a frame and its genrrali1.ation. This linkage is maintained by a pair of if-added and if-rcmovctl metho·k The procedures which implement this mechanism appear in THii\:G, the m011t general frame in NUDGE.

Subtleties. We conclude our discussion of FRI.-0 as a representation language with a consideration of fir<t some of t.hc subtleties involved in the usc of these six techniques and then .ome of FRL-O's current limitations.

I. There is more 1hon one kind of inherilanr.e.

Additive and restrictive inheritance are two kinds of inhrritarore strategies that correspond to two common forms of sper.iali1.ation. Additive inheritance is appropriate where spccialiulion ad·ls new non­ contradictory facts to the more general concept . Rrst riel 1 ve inheritance is appropriate where speciali1.ation overrides the information contained in the more general concept. Commentary is employed to inform the inheritance mechanism whether to stop or to continue up an AKO chain once the first datum is found.

2. Methods can conflict.

Procedural attachment can be troublesome. For eumple, care must be taken to noid loops: a method in slot A may atld a value to slot B that in turn adds a value to slot A. -An endless loop re<ults. We handle this by using comments to describe the source of information. It is up to the individual method to access thi< commentary.

Scheduling multiple methods associated with a <inglc <lot ma~· be required, when the methods have an a implicit order. Currently, the frame system executes the methods in a fixed order. If more <uhtle ordering is required, the user must combine t.he methods into a <illJ:II' procedure, with this method responsible for performing the proper ordering.

3. The dialinclion between mlue and requirl!ml!nl is nol ~""'1'·

Requirements have been presented as predicate< to filter out unwanted values. To the extent that NUDGE can rca<on directly from them, however, they can be used in place of values. For example, an if-needed procedure can use the requirement to select the generic category when instantiating a new frame to fill a slot.

f. IJ /rome is more than the rum of iu poru.

In our initial conception of a frame sydem, we did not provide for a SELF slot to contain idiOtlyncratic information about the r rame itself. Our hypothesis was that all of the information in the framc could be represented in the indi·idual slots. However, the need aro<c to represent global information about the frame, not local tn any slot. Two example« arc knowlcdce of how to print the frame in En,;lish and knowledge of the preferred order in which to instantiate thr. <lot < of the framl'- For the«e reasons, a SELF slot was introduc~d with a set of facets appropriate to the nrious classes of l(lohal infnrmatinn it contains. At present these include a SDISCIJSS facet which contain< a procedure lor de·cribing the frame in pr<>&.,, and an IORDER facet which contains a procedure that order< the slots at the time of instantiation.

5. Inheritance of tHJluc· and dcfaulu can conflict.

A given slot may have both a default and a value in it< gcncrali7.ation frame. Which should dominate? Currently, the frame system treats values as more important than defaults, so all of t.l1r values of superior frames are checked before a default is ac~rptrd . However, this may not be appropriate in all cases. When it is nnt , the user of the frame system can obtain complete cnntrol hy asking fnr the full heritage of the slot, i.e. all of the facets for the slot in the current frame and its superiors. The user can then select the tlcsirrtl datum.

!.imitations. The followinc are limitations of version 0 nf F'R 1..

1. No provision is made for multiple worlds in the frame system, althouch the BARGAIN program can consider ahrrnati ve calendars.
2. Procedures cannot be attached to arbitrary forms, hut nnly tn values. For example, there is no way to have a procedure trigger when a new requirement is added.
3. Arbitrary data structures cannot be asserted. Onl y infnrmation nf the form "frame, slot, facet, datum, comment" can he placed in a frame.
4. Hash codinc is not currently used. Hence, it is expensive to find all the frames with a slot of a riven name anti ev en mnr r expensive to find all the frames in which a given value appear<.
5. Comments cannot be associated with arbitrary parts nf a frarnr, but only either with individual data or the SEU" slnt nf th frame. There is no way to associate a comment with a suhs~t of the slots.
6. Mapping between frames is restricted to matching slnts. 1\ generali1.ed mapping function, as in MERLIN [73] wherein nnr <lnt can be mapped to another, is not allowed.

Eventually, we may find that the more sophisticated ~apahilit ir< of CONNIVER, MERLIN, KRL, or OWL arc needed. Rut the rapi·l rise and fall ol PLANNER argues lor caution in the introduct ion nf complex new techniques. We plan to introduce additional techniques only as the simple generali1.ed properly list scheme of FRL-0 pr""r.s inadequate. At present, FRL is adequate to represent the knnwlrdgc described in the neKt section which comprises thll basis nf its scheduling flKpertise.

5. EPISTEMOLOGY OF SCHEDUJ.ING

NUDGE's ability to expand informal schcdulin1: requests ari<c< from the recol(nition of the request as an instance nf varinus grneri~ frames. This section pro·ides snapshots of thi· generic knnwlr.tlgc, which inci!Jdcs frame hierarchies for activities, people, time, and plans.

• (l) Activities. Most acti·ities known to NUDGE invnlve information transfer. They span a set of events central tn the scheduling domain and interesting in the subtleties t.hev introduce fnr successfully debugging conflicting schedules. The "activity" suht rcc of the frame hierarchy shown earlier illustrates these infnrmatinn transfer activities and their disposition along gcncrali1.ation chains.

The use of concept hierarchies is an alternative tn the unstructured set of primiti·es proposed by Schank [73). We fintl th is approach powerful in that it facilitates the recognitinn nf new nhjccts and allows fine distinctions to be readily made. To illuuratc the fir<t point, Sl could have been treated as referring to an instant iatinn of the MEETING frame, in the absence of recognizing a meeting between Bruce and Ira as a PA-MEETING. l.ater, if additional information allnws this recognition, the AKO pnintcr of i\IEETINGJI would simply be adjusted to point to PA-1\IEETING. Othcr,.·ise no change is needed.

The line distinctions between information transfer a~t ivit ies represented in the activity hierarchy guides the time nf schrduling, the preparations required, and the pattern of the cnnsequrnres. 1\ phone call need not be scheduled for a precise time while a formal meeting must. We find a separate frame useful , rather than representing phone and mail as different instrument s to a sinr le communication activity (as might be Schank's approa~h) hrrause nther information is clustered nound the choice of means. 1\ letter requires more preparation time than a phnne call, implirs a crrt.ain delay in communication, and leaves open whether a response will hr received.

(2) People. Beyond the Uraightforward recnrd of pertinent facts about a person -- their name, addre!\s, phone number, office -- lies the need to capture the alternate roles people play in diffcrrnt situations. Roles exists in their nwn abstraction tree. t"nr scheduling purposes, the roles define an order of importance that tlir.tatrs, in thr case ol conflicting defaults and preferences, the order in which they should be relaxed. Acquiring properties by virtue of playing a rnle is identical to inheriting information u a spcciali1.ed instance nf a frame; the AKO/INSTANCE linh define the path along which thi s information flows. A particular feature of roles is that they (Ire oftr.n tran·itory and conditional on the type of ac t ivit y.

Originally, we maintained a Ktrict hierarchy in t"RL with each frame pointing to a single abstraction. Recently, we have allnwr·l multiple AKO links. The motivation was that it appeared natural fnr a person to inherit from several role·. For example, in a gi.-rn situation,lra may be both a visitor and a profcs.or. lnsnfar as t.he information inherited from multiple parents is non-cnnflicting, nn difficulty arises from this bifurcation in the ./\ KO path. If there is a conflict, it shows up in the frame gestalt with comments intlicating the urious sources of the conflicting infnrmatinn. It is up tn th~ process using the gestalt to decide on a resolution.

For example, as a professor, Ira's preferences with rcsprr.t In a meeting time would take precedence over a stud~nl. As a visitnr tn another university, they would noL The techniques for drhugl! ing schedules take account of this, treating the VIS I TOR rnle as overriding the PROFESSOR role.

People can be members of groups. A group has many nf the same characteristics as a person insofar as it can appear in t.he WHO slot of an activity and may have its own "personal" fact.: a name, an address, etc. The MEMBER and AFFILIATE slnts recnrd this dual relation in NUDGE.

(3) Time. In our earliest work on NU[)GE, time was reprr<ente·l simply as points on a real-number line. This was adequate for the formal analysis made by the scheduler, but proved insuffidr.nt tn represent the informal time specifications supplied by users. People's time specifications are generally incomplete anti ~ccasionally inconsistent. To handle these informal request~, we moved tn a frame-based repre«entation for time similar to the nne dcsr.rihrd by Winograd [75l

Below is part of the generic frame for a moment in time:

The MOMENT Jrame can reprcsr.nt an incomplr.tr. rr.qurst by rrratin1: an instance with only a few of the slots instantiated. The attachecl procedures -- WEEKDAY -EQUATION and DA YTIME-EQIIATION -- derive as many additional descriptors as possible.

A set of time predicates (BEFORE, DURING, A}Tt:R, etc.) have been implemented that allow a user to ask questions rr.l!ardinl: his calendar. For example, using the natural lan~:uage front end, the system can be asked: "Is Ira free on Monday, Fr.hruary 7?"

The predicates take instantiated time frames as input ancl perform their analysis on a "need to know" basis. That is, (8Et"ORE Ml M2.) will return T even if Ml and M2. arc incomplr.tr., provicltnl: there is suHicient information to make the required jud~:mr.nt. For example, Ml may specify a moment in January without sayin1: precisely when and M2. a moment in Fr.bruary. ln this case, the BEFORE question can be answered despite ignnrancc of the exact time involved. In this fashion, we go beyond Winograd's original discussion of frame-based time-repre·entations in that hr. did Mt consider the iuues raised by reasoning with inMmplete tim<' spr.cifications. Of course, the nature of the incomplclrncss may hr. such that no answer is possible. In this case, the timr. prrclicalcs report that the frames arc too incomplete for an answer.

The time predicates can also tolerate a certain drl:r<'e of inconsistency. For example, suppose a user asks if a mrctinr. is pos·ible with Bruce on Tuesday, January 20, 1977. In facl, January 20 is Monday. But if the frame system knows that 8ruee is on vacat inn all of January, it iR more appropriate for it to reply: "I assumr vnu mean Monday, January 2.0. Bruce will be on vacation then." ralhrr than first askinl( for a clarification and then telling the usrr his request will fail.

Inconsistency is detected by if-addr.d mr.thods which, in lhr course of deriving ~alues, observe that they have computrd a slot nlue that conflicts with a user supplied value. A commr.nt rl'gard ing the inconsistency is placed both at the slot level and at thr. f ramr. level. For example, the MOMENT frame for the inconsistent time specification given above would be:

HOI"'ENTlZ

WEEkDAY SVALUE TUESDAY [SOURCE : USER]

MONDAY [SOURCE : DERIVED]

SELF

SLOGICAL-STATE INCONSISTENT [SEE : WEEKDAY]

The time predicates report the inconsistency, and then att~mpt 1.11 answer the original question by reducinl! the incnnsi~tency tn an incompleteness. This ia done by referencing an ordering on lh~ ~lois corresponding to their relative reliability. Year dominalr~ Month which dominates Day which dominates Weekday. The infrr ior ~lot values are ignored until the inconsistency is removed. Thr question i~ then answered using the resulting incomplete frame. At hr~l, the time predicate~ have guessed correctly and the usr.r ha~ ll'arnr.cl 1 he answer to his question. At worst, he is alerted to the ~on~i~t.ency and responds with a repetition of his original request with lhr inconsistency removed. ·

(4) Plans. It is uncommon to schedule isolated event~. Typically, clusters of related activities are organized around a theme; a serir~ of meetings to discuss the state of a group's research, wnrk hv several people on a joint papr.r. These clusters embody two kinds of interrelations in addition to the AKO/INSTANCE bond alrr~dy discu11ed. First, there ia a logical ordering of activities, which in lh~ realms of scheduling nearly always entails a chronological ordering to be enforced. Second, activities can be broken down into subactivities; these represent sub-goals with resp~ct to lhc purpo.r~ of the activity itself. Opposing PREREQUISITF./POSTREQIJISIT~: links connect frames possessing a logical ordr.ring. The valurs of a PREREQUISITE slot name frames which must immr·lia'tdy prrcr.le iL Analogous SUB/SUPER links connect framr.~ ~uhordinate one to another. A EJ!!!. is a group of frames connected by lhrsc pointers. These implement a procedural net in the style of Sacerdnti [7S], which served to unify the ideas of ABSTRIPS and NOAH as ~cherne< for representing planning knowledge.

An example of using a plan is illustrated in the ~crnarin. NUDGE's R2 response alludes to a PA Progress Report, whosr frame contains the following planning links.

Interconnections describing its subgoals and the onler in which thr y must be accomplished pr.rmit the creation of an in~lanrc mirrnring this structure which satisfies the request. At R2 in the scenario, NUDGE makes a point of scheduling the prr.paration of a wrillrn progress report for Bruce which is clearly something to be accomplished before the newly scheduled mcr.ting with Ira. The generic frame for PA-MEETING has a PREREQUISITE slot containing a requirement for this a"d an If -needed procedure to accomplish it.

PA·MEETING

PREREQUISITE SREQUIRE

(AKO REPORT)

SIF-NEEDED (INSTANTIATE-AS-REQUIRED)

Frames and Knowledge. Frame systems have proved a r.onvrnirnt representation for knowledge that naturally falls into a taxonom~· of successively more general categories. Individual frames arr. convenient for representing concepts that have multi-dim<'nsinnal descriptions which may be potentially incomplr.tr. or incnnsistrnl. However, the limits of frames as a ~eprcscntatinnal schcmr. arc nol yet clearly understoOd. We plan extensions into different domains to understand these limitations.

6. BARGAINING BETWEF.N GOAl$

NUDGE translates an ill-defined, undr.r - spr.cili ed schrtlulin~ request into a complete specification, represented by th<' f ramr. gestalt. This gestalt becomes the input to a schr.tluling program, BARGAIN, that scr.ks the best time for the rr.qur.sle·l a~tivity if the desired time is unavailable. Other traditional scheduling pro~:rams could be employed as the gestalt is a complete and formal reqursl. We use BARGAIN since it improves upon traditional decision analys is programs by incorporating AI techniques to control thr. search procr.ss.

BARGAIN is power-based in the sense that its romprtr.nce is predicated on efficient search. It engages in a be~t-first srarch, as controlled by a static evaluation function that measures (I) the number of violated preferences, (2) their rr.spr.ctivr. utilit ir.s and (3) the number of remaining conflicts. BARGAIN wu nril(inall y designed by Goldstein [75) and implemented in CONNIVER hv F. Kern [75l

BARGAIN employs a set of 8 search opr.rators which conslilnlr debugging strategies for time conflicts. One set. arc "resource­ driven", i.e. they are expert& on the phy·ic· of time an·l climinalr. a conflict by alterinr the duration, interruptinl(, ·haring or moving the event. The ·ccond set are "purpose-driven" and go lluhidc the l.ime domain to eumine the topic ·or the meeting and altr.rnativ~ mr.l ltmls ror accomplishing it. An application of any one of these techn ique~ produces a new calendar with the conflict resolved, and possibly nr.w conflicts introduced. Each strategy has a cost associate·! witlt it. BARGAIN halts when it has found the best sequence of dehuggin~r strategies that generate a conrlict free calendar within variou~ computational constraints.

The applicability of a search operator -- c~p~cially th~ purro.r­ driven kind -- can depend on the overall knowledg~ cont~xt. H~ror.r , the power-based approach benefits from som~ hctrrarchy with the preceding knowledge-based phase. A given search oprrator rnav a<k the frame system whether it applieA. For example, a stratrgy to change participants must rely on knowledge of availabl~ can<li<latr~ and the goals of the activity for suggesting suitable replacemrnts.

The relative preference for differr.nt ~chr.duling strat~gi~~ i~ controlled by specific assertions in the HOW slot, which contain~ the names of strategies applicable to the activity in which it apprars. For example, PA meetings can be postponed as a last resort and only reluctantly interrupted; as can be seen in this excerpt from th~ PA­ MEETINC frame.

Our approach to power-based scheduling parall~l· th~ conservative development of the knowlcdge-ba~cd component in that the well-understood techniques of decision analy<is have been augmented only as required. This augm~ntation ha< invoiH<I applying AI search techniques to improve the efficiency with which a best compromise is found.

7. CONCLUSIONS

1. FRL-0 provides a simple, but powerful representation technology. Frames are generalized prop~rty list, sharirog much of the simplicity of traditional attribute/value representation sr.hcmr~. Yet the addition of a few capabilities -- comm~nt~, coMtrairot~, defaults, procedural attachment, inheritance -- provide~ a grrat .leal more power and economy in the representation. K R I. and OU' I. arc more ambitious and more complex, and may well apply to contexts in which FRL-0 proves insufficient. But this remains to be seen. w~ plan further uperiments with FRL-0 to identify its strrnglhs an<l weaknesses. ·
2. Whether FRL-0 or some other AI language i~ rmplo~·~·l, our experience with the nature of informal rcque~ts, the i~su~~ rai~r~l by multiple inheritance paths, the interaction between a ~earch rrogram and a rich knowledge base, and the epistemology of information transfer activities, time, place and people will surely be relevant to the design of knowledge-based AI programs.
3. FRL is an experiment in the utility of the frames. Our experience is that clustering the answers to common quc~tion~ about the frame structure for a concept provides a useful rcpr~~r.ntation paradigm. The frame ge~talt derived from this frame struct nrc supplies missing information similar to that generated by comprt~nt human schedulers to handle informal requests.
4. The entire system can be viewed from another prrsrrctivc. Since a frame's behavior is actually governed lar~cly by the attar.Jo~,J procedures, it can be viewed as an accessing scheme to the umlrrlying procedural knowledge. Thus, frames implement goal-dirr.cte<l invocation ·(a~ in PLANNER), but with pattern matching rcplac~·l by the more general process of frame instantiation.

(5) NUDGE is a step towards an AI system with common ·~n"'· By generating a complete frame gestalt, the syst~m minimius thc possibility of overlooking obvious alternatives. Defaults, prcferencr~ and requirements allow much to remain unsaid. A tolerance r or minor inconsistencies is a benchmark of a robust knowlt!<lge systrm.

1. NUDGE and BARGAIN are steps towards the ncation nf an automated office. Given the enormous information flow in a mo<lrrn office, this is an important area for applied AI research.

This paper describes research done at the Artificial lntrllig~ncc Laboratory of the Massachusetts Institute of Technology. It wa~ supported in part by the Advanced Research Projects Agency of thc Department of Defense under Office of Naval Research contract.

N00014-75-C-0643.

8. BIBLIOGRAPHY

Balzer, R. 1974. Human Use of World Knowledge, ISI/RR-73-7.

Bobrow, D.C., R.M. Kaplan, M. Kay, D. Norman, H. Thomp~nn, T. Winograd. 1976. GUS, A Frame-Driven Dialog Systcm, Xerox Research Center, Palo Alto.

Bobrow, D.C. & Winograd, T. 1976. An overview of KRI., a Knowle·ls:~ Representation Language, Xerox Research Center, Palo Alto.

Bullwinkle, C. 1977. The Semantic Component of PAl.: The Personal Assistant Languace Understanding Program, MIT-AI, Workinl! Paper 141.

Collins, A. & E. Warnock. 1974. Semantic Networks, Memo 283.1, Bnlt Beranek & Newman, Cambridge, MA.

Goldstein, I.P. 1974. Understanding Simple Picture Programs, MIT -A I, TR 294.

Goldstein, I.P. 1975. "Bargaining Between Goals," IJCAI IV, Tbili~i .

Hewitt, C. 1969. "PLANNER: A Language for Proving Theorrm< in Robots," IJCAI I.

Kern, F. 1975. A Heuristic Approach to Scheduling, M.S. Thesis, MIT.

Marcus, M. 1976. "A Design for a Parser for English," Proc. ACM Conference, Houston.

• Martin, W.A. 1977. "A Theory of English Grammar," in II Computational Approach to Modern Lingui~tics: Th..ory and /mplemenlalion, (in preparation).
• McDermott, D. & Suuman, C. 1972. The CONNIVER Rcferrnc~ Manual, MIT AI Memo 259.
• Minsky, M. 1975. "A Framework for Representing Knowlcdg~," in P.H. Winston(Ed.), Tlte P1ycltology of Compulu Vi·ion, NY :McGraw-Hill.
• Minsky, M. & Papert, S. 1974. Artificial Intelligence. Condon Lectures, University of Oregon.
• Moore, J. & Newell, A. 1973. "How Can MERLIN Understand?," in L. Cregg (Ed.), Kno111ledge and Cognition, I.awrcncc Erlhaum Assoc., Potomac, MD.
• Quillian, R. 1968. "Semantic Memory," in M. Minsky (Ed.), St>manlie Information Proceuing, The MIT Pre<s, Cambridge, l\IA.
• Sacerdoti, E. 1975. "The non-linear nature of plans," JJCAI IV, Tbilisi.
• Shank, R.C. 1973. "Identification of Conccptualir.ations llnderlyin~ Natural T..anguage," in R.C. Shank & K.M. Colby (Ed.) Computer Modell of Tltougltl and Language, San Francisco: Freeman.
• Sussman, C.J. 1973. A Computational Model of Skill Acquisition, MIT­ AI TR 297.
• Tonge, F.M. 1963. "Summary of a Heuristic Line Balancin1! Procedure," in E.A. Feigenbaum & J. Feldman (Ed.), Computer.· and Tltougltl. NY:McCraw-Hill.
• Winograd, T . 1975. "Frame Representations and the Declarative/Procedural Controversy," in R. Bobrow & A. Collins (Ed.), Reprelentation and Underllanding, NY:Acadcmic Press.