(PDF) Learning by analogy: formulating and generalizing plans from past experience

See discussions, stats, and author profiles for this publication at: https://www.researchgate.net/publication/239577648 Learning by Analogy: Formulating and Generalizing Plans from Past Experience Article · December 1983 DOI: 10.1007/978-3-662-12405-5_5 CITATIONS READS 333 19 1 author: Jaime G. Carbonell Carnegie Mellon University 369 PUBLICATIONS 11,919 CITATIONS SEE PROFILE Some of the authors of this publication are also working on these related projects: History of Computer Science at Carnegie Mellon University View project All content following this page was uploaded by Jaime G. Carbonell on 19 September 2014. The user has requested enhancement of the downloaded file. All in-text references underlined in blue are added to the original document and are linked to publications on ResearchGate, letting you access and read them immediately. Carnegie Mellon University Research Showcase Computer Science Department School of Computer Science 1-1-1982 Learning by analogy : formulating and generalizing plans from past experience Jaime G.(Jaime Guillermo) Carbonell Carnegie Mellon University Follow this and additional works at: htp://repository.cmu.edu/compsci Recommended Citation Carbonell, Jaime G.( Jaime Guillermo), "Learning by analogy : formulating and generalizing plans from past experience" (1982). Computer Science Department. Paper 2442. htp://repository.cmu.edu/compsci/2442 his Technical Report is brought to you for free and open access by the School of Computer Science at Research Showcase. It has been accepted for inclusion in Computer Science Department by an authorized administrator of Research Showcase. For more information, please contact research-

. N O T I C E W A R N I N G C O N C E R N I N G C O P Y R I G H T R ES TR I CTI ON S : The copyright law of the United States (title 17, U.S. Code) governs the making o f photocopies or other reproductions of copyrighted material. Any copying of this document without permission of its author may be prohibited by law. CM U - CS- 8 2 - 1 2 6 Le a rning by Ana logy: Form ula ting and Ge ne ra lizing Pla ns from Past Expe rie nce Ja i m e G. Ca r b o n e l l 19 Ju n e 1982 To a p p ea r in Machine Learning, an Artificial Intelligence Approach R. S. Michalsk i, J . G. Ca rb on el l a n d T. M. Mit chell (Ed s.), Ti o g a Press, Palo Al t o, CA, 1982 t ^£?£^ZF* ^* P 3 r t ° ° b V ° m e f N 3 V a 9 l R 6 S e N0 0 1 4 -7 9 -C-0 6 6 1 . a nd in a r C h ( O part by the De fe nse Adva nce d Re se a rch Proje cts Age ncy (D OD ). AR P A order num ber 3 5 9 7 , m onitored by t he Ai Force N R ) u n d e r r a n t n u m b e r llZ S^Z T « « * ~ M 3 8 1 M 1 -K -1 5 3 B . Th e v^ w s a nd c o n c i s i o n s in this docum e nt 3 ^ R e ^^^^^^^ « - «* * * <* - - Adva nce d Con cl u d i n g Rem ark Ta b l e of Con t e n t s 1. Int roduct i on 2. Probl em Solving b y An a l ogy 2.1. Th e Pl an-Transf orm at i on Probl em Sp a c e 2.2. Som e exam pl es 3 . Evaluat ing t he An a l ogi ca l Reasoni ng Pr o cess 4. Learni ng Gen era l i zed Plans 4.1. Acqui ri ng Gen era l i zed Sol ut i ons Pr o ced u r es 4 .2 . Ep i sod i c Mem ory Or ga n i za t i on 4.3. Ep i sod i c Mem ory Rest ruct uri ng 4.4. T-Op e r a t o r Ref inem ent 4 .5 . Th e Acq ui si t i on of New T-Op e r a t o r s 5. Co n cl u d i n g Rem ark 1 Le a rning by Ana logy: Form ula ting a nd Ge ne ra lizing Pla ns from Pa st Expe rie nce Ja i m e G. Ca r b o n e l l Ab st r a ct Anal ogi cal reasoning is a powerf ul m echanism f or exploit ing past exp er i en ce in planning and problem sol vi ng. Th i s paper out lines a t heory of analogical problem sol vi ng based on an ext ensi on t o m eans-ends analysis. An analogical t ransf orm at ion p r ocess is devel oped t o ext ract k now l edge f rom past su ccessf u l problem solving sit uat ions t hat bear st rong sim ilarit y t o t he curren t problem . Th e n , t he invest igat ion f ocu ses on exploit ing and ext ending t he analogical reasoning m odel t o generat e usef ul exem plary sol ut i ons t o relat ed problem s f rom w h i ch m ore gen eral plans ca n be i n d u ced and ref ined. St art ing wit h a general analogical inf erence en gi n e, problem solving exp eri en ce is, in essen ce, com piled increm ent ally into ef f ect ive p roced u res t hat sol ve vari ous cl asses of problem s in an increasingly reliable and di rect m anner. 1. I nt roduct ion Anal ogi cal reasoning has been a sparsel y-i nvest i gat ed phenom enon in Art if icial Int elligence [ 1 1 ,2 0 ,1 3 , 3 1 ]. Nonet heless, anal ogy prom ises t o be a cent ral inf erence m et hod in hum an cogni t i on as well as a powerf ul com put at ional m echanism . Th i s paper d i scu sses a com put at ional m odel of problem solving b y anal ogy based on an ext ensi on of m eans-ends analysis (M EA). My cent ral hypot hesis (based in part on Sch a n k ' s t heory of m em ory organi zat i on [28, 27]) is t he f ollowing: Wh en encount eri ng a new problem sit uat ion, a person is rem inded of past sit uat ions t hat bear st rong sim ilarity t o t he present problem (at dif f erent levels of abst ract ion). Th i s t ype of rem inding exp er i en ce serves t o ret rieve behavi ors t hat w ere appropriat e in earlier problem solving epi sodes, w h ereu p on past behavi or is adapt ed t o m eet t he dem ands of t he cu rren t sit uat ion. Com m onalit ies am ong previ ous and cu rren t sit uat ions, as well as su ccessf u l applicat ions of m odified- plans can serve as t he basis f or general i zat i on. Sim ilarly, perf orm ing an inappropriat e act ion in a new sit uat ion can provi de inf orm at ion usef ul in reorgani zi ng epi sodi c m em ory. If t he inappropriat e act ion result ed from t he applicat ion of a recent ly acqui red general plan, an analysis of t he t ype of error m ay t rigger a discrim inat ion p rocess t hat const rai ns t he range of applicabilit y f or t hat plan. In eit her ca se, a reactive environm ent t hat inf orm s t he problem sol ver of su ccess, f ailure, o r partial su cce ss is an absolut e requirem ent f or any generalizat ion or discrim inat ion p rocess t o apply. Whereas hum ans exhibit a universal abilit y t o learn f rom exp eri en ce no m atter what t he task [2 2 ], Al 2 Learni ng and Problem Sol vi ng b y An a l ogy syst em s are seldom desi gn ed t o m odel t hi s adapt i ve qualit y. Co n ce p t acqui si t i on, i.e., i nduci ng st ruct ural or at t ribut e descri pt i ons of n on -p r oced u r a l obj ect s from exam ples, has recei ved subst ant ial at t ent ion in t he Al lit erat ure [ 1 0 ,8 ,1 8 , 29, 3 0 ], but wit h f ew excep t i on s, t he t ech n i q ues d evel op ed t herein have not been t ransf erred t o learning in problem -solving sce n a r i o s. Si n ce t he p r o ce ss of2 acquiring and ref ining problem solving a n d planning sk ills is indisput ably a cent ral com p on en t in hum an cogn i t i on , its invest igat ion f rom an Al perspect i ve is clearly just if ied. Th i s paper present s an analogical i nf erence engi ne a n d invest igat es t w o f undam ent al h ypot h eses: H y p o t h e s i s : Problem solving and learning are inalienable aspects of a unified cognitive m echanism . In ot her w or d s, one ca n n ot acqui re t he requisit e cogni t i ve sk ills wit hout solving problem s — a n d , t he very p r ocess of sol vi ng problem s provi des t he inf orm at ion n ecessa ry t o a cq u i r e a n d t u n e problem solving sk ills. Th e se co n d hypot hesis post ulat es a unif ied learning m echani sm . H y p o t h e s i s : The sam e learning m echanism s that account for concept form ation in declarative dom ains, operate in acquiring problem -solving skills and form ulating generalized plans. On e m et hod of verif ying t h e seco n d hypot hesi s is t o devel op a problem sol vi ng m echanism int o w h i ch one ca n int egrat e t he t ech n i q ues d evel op ed in co n cep t f orm at ion — wit h a result ant syst em t hat learns f rom problem solving exp eri en ce. Th e analogical problem solving m et hod d i scu ssed bel ow provi des a f ram ework f or aut om at ed exam ple generat i on t hat enabl es on e t o apply l earni ng-f rom - exam ples t ech n i q ues in order t o acqui re general i zed plans. In essen ce, t he object ive is ak in t o An za i and Si m on' s l earn i n g-by-doi n g m et hod [2 ]. First , t he basic analogical probl em -sol vi ng m et hod is d i scu ssed , a n d subsequent l y an experient ial learning com p on en t is i n corporat ed as an int egral part of t he general analogical i nf erence p r ocess. 2 . P roble m Solving b y Ana logy Tradit ional Al m odels of problem sol vi ng (e.g., GPS [2 1 ], STRI PS [ 9 ] , and N OA H [2 4 ]) a p p r oa ch every problem alm ost wit hout benef it of pri or exp er i en ce in solving ot her problem s in t he sam e or sim ilar problem sp a c e s. Con si d er , f or inst ance, t w o relat ed problem s: 3 2 Exce pt ions include Anza i a nd Sim on's Le a rning-by-D oing Pa ra digm [2 ], M itche ll's LEX system [1 9 ], S TR I P S with M ACR OP S [9 ], a nd indirectly Le na t's A M [1 5 ]. 3 A problem space e ncode s the inform ation ne ce ssa ry to solve a proble m , including goa ls, initial sta te, a nd legal a ctions that m ay b e ta ken in solution attem pts. Means-Ends Analysis is a problem solving m ethod that consists of selecting a ctions that re duce k nown differences between the curre nt situa tion a nd a de sire d sta te. Both of these conce pt s a re ela bora ted in the course of the present discussion. Howe ve r, the re a de r not fam iliar with M e a ns Ends Ana lysis is e ncoura ge d to review the te chnique in a ny sta nda rd Al text, such as W inston's Artificial Intelligence [3 2 ] or Nilsson's Principles of Artificial Intelligence [2 3 ], or rea d the m uch m ore t horough trea tm ent in [2 1 ]. Problem Solving b y An a l ogy 3 T h e m o n k e y-a n d -b a n a n a s p r o b l e m : A (hungry) m onk ey is pl aced in a room wit h bananas su sp en d ed f rom t he ceiling b eyo n d its r ea ch . A w ood en b ox of suf f icient si ze to serve as a plat form f rom w h i ch t he m onk ey ca n reach u p to t he bananas is pl aced el sewhere in t he room . T h e e x p e r i m e n t e r -a n d -b a n a n a s p r o b l e m : An experim ent er w i shes to set up the m onk ey-and-bananas problem . He has som e bananas, a h ook in t he ceiling just b eyon d his rea ch , and a w ood en b ox el sew here in t he experim ent al room , a n d , of cou r se, a m onk ey. A m eans-ends-anal ysi s problem sol ver, su ch as GPS, will sol ve eit her probl em , given suf f icient tim e a n d a reasonable en cod i n g of t he perm issible act i ons a n d t heir con seq u en ces. How ever, sol vi ng on e problem d oes not provi de any inf orm at ion usef ul in solving t h e ot her. On e w oul d t hink t hat pract i ce solving a gi ven t yp e of problem sh ou l d help in sol vi ng sim ilar f ut ure problem s. Fo r i nst ance, an int elligent m onk ey observing t he experi m ent er m ove t he b ox beneat h t h e hook , hang t he bananas, and ret urn t he b ox t o its original l ocat i on, m ay inf er w h i ch part s of t he experim ent er's behavi or it sh ou l d replicat e in order t o reach t he bananas. Sim ilarly, if t he experim ent er t ires of wat chi ng an unenl i ght ened m onk ey repeat edly fail in its at t em pt s t o sol ve t he problem , he sh oul d k now how t o tak e d o w n t he bananas by m odif ying part s of his earlien pl an, rat her t han replanning f rom gr o u n d zer o. In general , t ransf er of exp er i en ce am ong relat ed problem s appears t o be a t heoret ically signif icant p h en om en on , as well as a pract ical necessit y in acquiring t ask -dependent expert ise I necessary t o sol ve m ore com plex real -worl d problem s. Indeed, t he prem ise that hum ans t r a n sf er ; problem -solving expert i se am ong cl osel y relat ed sit uat ions is inext ricably w oven into t he pedagogi cal pract i ces of our educat ional inst it ut ions. Th e bulk of hum an problem solving t ak es pl ace in problem sp a ces t hat are eit her well k nown or vary onl y slight ly f rom fam iliar sit uat ions. It is rare f or a p erson to en cou n t er-a problem t hat bears no relat ion t o sim ilar problem s sol ved or ob served in past exp eri en ce. New abst ract p u zzl es (su ch a s Rubi k ' s m agic cu b e) a re su ch except i on al problem s, w h ere initially t he on l y t ract able solut ion p roced u re is t he applicat ion of st andard weak m et hods [2 1 ] wit hout benef it of (non-exist ent ) past exp eri en ce. Th eref ore, m y invest igat ions cent er on sim plif ied versi ons of real-world problem s, rat her t han m ore abst ract , sel f -cont ai ned p u zzl es. Now , let us t urn to problem solving in fam iliar problem sp a ces. What m ak es a problem sp a ce " f am iliar" ? Cl earl y, a m ajor aspect consi st s of m em ory of past problem s and t heir correspon di n g solut ions that bear st rong sim ilarit y t o t he new probl em . Su ch k now l edge, o n ce a cq u i red , ca n be expl oi t ed in t he problem solving p r ocess. Th er e is no ot her w ay t o a ccou n t f or t he f act t hat hum ans sol ve problem s in fam iliar sit uat ions m uch f ast er, and wit h m ore sel f -assurance t han in unfam iliar abst ract sit uat ions. A com put er m odel sh ou l d exhibit t he sam e sk ill-acquisit ion p rocess; i.e., it sh ou l d 4 Learni ng and Problem Solving b y An a l ogy learn t o adapt its problem -solving beh avi or by relying on past exp er i en ce w h en available - falling back on t he applicat ion of st andard weak m et hods w h en m ore di rect recal l -and-m odi f i cat i on of exist ing solut ions fails t o provi de an an sw er. Ho w m ight a problem sol ver b e augm ent ed t o exhibit su ch adapt ive behavior? First , let us review t he st andard M EA p r ocess; t hen w e see how t he analogical t ransf orm at ion p rocess augm ent s M EA t o expl oi t prior exp er i en ce. 2 .1 . Th e P l a n -Tr a n sf o r m a t i o n P r o b l e m S p a c e Co n si d e r a t radit ional M ea n s-En d s Anal ysi s (M EA) problem sp a ce [2 1 ], consi st i ng of : • A set of possible problem st at es. • On e st at e desi gnat ed as t h e Initial State • On e or m ore st at e(s) designat ed as goal states - f or sim plicit y, assum e t here is only on e goal st at e. • A set of operat ors wit h k nown precondi t i ons t hat t ransf orm on e st at e int o anot her st at e in t he sp a ce. • A di f f erence f unct ion t hat com put es di f f erences bet w een t w o st at es (t ypically applied t o com put e t he di f f erence bet ween t he cu r r en t st at e and t he goa l st at e). • A m et hod f or indexing operat ors as a f unct ion of t he di f f erence(s) t hey r ed u ce (e.g., t he t able of di f f erences in GP S) . • A set of global pat h const raint s t hat m ust be sat isf ied in order f or a solut ion t o b e vi a b l e . 4 A pat h const raint is essent ially a predi cat e on a part ial solut ion seq u en ce, rat her t han on a single st at e or operat or. Th e i nt roduct i on of pat h const raint s in t his m anner const it ut es a slight m odif icat ion of t he st andard M EA problem sp a ce. Problem solving in t his sp a ce consi st s of st andard M EA: 1. Com p a re t he cu rren t st at e t o t he goa l st at e 2. Ch o o se an operat or t hat red u ces t he di f f erence 3 . Appl y t he operat or if possible - if not , sa ve t h e curren t st at e and appl y M EA t o t he subprobl em of est ablishing t he unsat isf ied precondi t i on(s) of t hat operat or. 4. Wh en a subprobl em is sol ved , rest ore t he sa ved st at e and resum e work on t he original problem . 4 F o r insta nce, a pa th constra int m ay disa llow pa rticula r subse que nce s of ope ra tors, or prevent an ope ra tor that consum e s K a m ount of a re source from a pplying m ore tha n N tim es, if there is only N xK a m ount of the re source a va ila ble to the problem solve r. Problem Solving by An a l ogy 5 How ca n o n e exploit k now l edge of sol ut i ons t o previ ous problem s in t his t ype of problem space? First , con si d er t he sim plest ca se; k nowf edge consi st s only of solut ions t o previous problem s. Ea ch solut ion consist s of a seq u en ce of operat ors and int erm ediat e st at es, including t he initial and final st at es, t oget h er wit h t he pat h const rai nt s t hat t he sol ut i on w as desi gn ed t o sat isf y. On e rat her sim ple i dea is t o creat e " m a cr o-op er a t or s" f rom seq u en ces and su b -seq u en ces of at om ic operat ors t hat have proven usef ul as solut ions t o earlier problem s. For inst ance, STRI PS wit h M A CROP S exploit ed t his idea [9 ] using its " t riangle t abl e" t o st ore all partial seq u en ces of operat ors en cou n t er ed in a solut ion t o a previ ous problem . How ever, t he sim ple creat ion of m acro-operat ors suf f ers t hree seri ous short com i ngs. First , t he com bi nat ori cs i nvol ved in st oring and searchi ng all possible su b seq u en ces of all solut ions ever en cou n t ered becom es rapidly unm anageable. Searchi ng f or appl i cabl e m acro- operat ors ca n becom e a m ore cost l y p r ocess t han applying M EA t o t he original probl em . Se c o n d , pat h const raint s are i gnored in t his process. If t he new problem m ust sat isf y a dif f erent set of pat h const raint s, m ost previ ous m acro-operat ors m ay prove invalid. Th i r d , no provi si on is m ade f or subst it ut ing, delet ing, o r insert ing addit ional operat ors int o recalled solut ion seq u en ces. Th e se operat i ons p r ove cru ci a l in t he anal ogi cal t ransf orm p rocess d escr i b ed below. Th eref ore, let us t hink not in t erm s of creat ing m ore and m ore powerf ul operat ors t hat apply t o f ew er and f ewer sit uat ions, but rat her t hink in t erm s of gradually t ransf orm ing an exist ing solut ion into on e t hat sat isf ies t he requirem ent s of t he new problem . Con si d er a rem inding p rocess (a sea rch f or solut ions t o problem s sim ilar t o t he on e at hand) t hat com pares dif f erences am ong t he f ollowing: 1. Th e initial st at e of t he new problem and t he initial st at e of previ ousl y-sol ved problem s 2. Th e final st at e of t h e new problem and t he final st at e of previ ousl y-sol ved problem s 3 . Th e pat h const raint s under w h i ch t he new problem m ust be sol ved and pat h const raint s present w h en previ ous sim ilar problem s w ere so l ved . 4. Th e proport i on of operat or precondi t i ons of t he ret rieved operat or seq u en ce sat isf ied in t he new problem sit uat ion. Th i s m easure is called t he applicability of a candi dat e sol ut i on. Th e di f f erence f unct i on used in com paring initial and final st at es m ay be t he very sam e f unct ion used f or dif f erence reduct ion in st andard M EA. Here, I advocat e using t he di f f erence f unct ion as a sim ilarity m etric to ret rieve t he solut ion of a previ ousl y-sol ved problem cl osel y resem bling t he present problem . Th e dif f erence f unct ion applied t o pat h const raint s is an augm ent ed versi on of t he problem - st at e di f f erence f un ct i on , as it m ust a ddress op era t or-seq u en ce dif f erences in addit ion to st at e inf orm at ion. Hen ce, rem inding in our problem -solving con t ext consi st s of recalling a previ ousl y 6 Learning and Problem Solving b y An a l ogy sol ved problem w h o se solut ion m ay t ransf er t o t he new problem un der consi derat i on. A m ore sophi st i cat ed m et hod of com put ing sim ilarit ies am ong epi sodi c m em ory st ruct ures is ba sed o n a relative-invariance hierarchy am ong dif f erent com p on en t s of recalled problem solut ions, as d i scu ssed in [5 ]. Rem inding is only t he first ph ase in anal ogi cal problem sol vi n g. Th e se c o n d phase con si st s of t ransf orm ing t he old solut ion seq u en ce int o one sat isf ying t h e crit eria f or t he new problem . How d o es t his t ransf orm at ion p r ocess proceed? I subm it t hat it is equivalent t o problem solving in t h e sp a ce of so l u t i o n s. 5 Original Space T-Space (Retrieved Solution ) Fi g u r e 2 -1 : A sol ut i on pat h in t h e original problem sp a ce becom es a st at e in t h e analogy transform problem space. Finding an appropriat e analogical t ransf orm at ion is itself a problem solving p rocess, but in a dif f erent problem sp a ce. Th e st at es of t he t ransf orm probl em spacebars sol ut i ons t o problem s in t he original problem sp a ce. Th u s, t he initial st at e in t he solut ion t o a sim ilar probl em , and t he goal st at e is a solut ion sat isf ying t he crit eria f or t he new problem . Th e operat ors in t he t ransf orm problem sp a ce are t h e at om ic com pon en t s of all solut ion t ransf orm at ions (e.g., subst it ut e an operat or in t he sol ut i on seq u en ce f or anot her operat or t hat red u ces t he sam e di f f erence, but requires a dif f erent set of precondi t i ons or ent ails dif f erent si de ef f ect s, et c. - see 5 H e r e I a pply my pre vious definition of a solution to be a se que nce of ope ra tors a nd interm edia te sta tes t oge t he r with t he set of pa th constra ints that se que nce is k nown to sa tisfy. Th u s, I a dvoca t e a pplying M EA to the spa ce of potential solution se que nce s ra ther tha n the origina l problem spa ce . Howe ve r, the rem inding proce ss should genera te an initial solution se que nce close to the goa l solution se que nce , whe re close ne ss is de te rm ine d by the difference m etric a bove . Problem Solving by An a l ogy 7 bel ow ). Th e di f f erences t hat t he probl em sol ver at t em pt s t o r ed u ce in t he new problem sp a ce are preci sel y t hose com put ed by t h d sim ilarit y m et ric in t he rem inding p r ocess. In ot her w or d s, progress t owards a goal is det erm ined by t ransit ions in t he solut ion sp a ce t ow ards " sol ut i on se q u e n ce s" cor r esp on d i n g t o problem s i ncreasi ngl y sim ilar t o t he new probl em . Int erm ediat e st at es in t he t ransf orm sp a ce need not cor r esp on d t o viable sol ut i ons in t he original (object ) sp a ce, in t hat int erm ediat e solut ion seq u en ces m ay not be execut abl e d u e t o unsat isf ied operat or precondi t i ons. Th e diagram in f igure 2-1 gi ves an int uit ive f lavor of t his probl em -sol vi ng p r ocess. M ore preci sel y, t he analogy transform problem space (T-sp a ce) is def ined as f ollows: • St at es in t he t ransf orm sp a ce are pot ent ial solut ions t o problem s in t he original problem sp a ce (i.e., seq u en ces of st at es a n d operat ors including t he initial and final st at es, plus t he pat h const rai nt s under w h i ch t h ose solut ions w ere com put ed.) • Th e initial st at e in t he t ransf orm sp a ce is t he sol ut i on t o a sim ilar problem ret rieved b y t he rem inding p r ocess. • A goal st at e in t he t ransf orm sp a ce is t he speci f i cat i on of a sol ut i on t hat sol ves t he new probl em , sat isf ying its pat h const rai nt s. • An operat or in t he t ransf orm sp a ce (labeled a " T-o p e r a t o r " t o avoid con f u si on ) m aps an ent ire solut ion seq u en ce into anot her pot ent ial solut ion seq u en ce. Th e f ollowing is a list of t he m ost usef ul T-op er a t or s: o General Insertion. Insert a new operat or int o t he solut ion seq u en ce. o General deletion. Delet e an operat or from t he solut ion seq u en ce. o Subsequence Splicing. Spl i ce a solut ion t o a new subprobl em into t he l arger est ablished sol ut i on seq u en ce. Th i s T-o p er a t o r is usef ul in t he f ollowing sit uat ion: If an operat or in t he original problem seq u en ce can n ot be applied under t he new problem specif icat ion b eca u se on e of its precondi t i ons is not sat isf ied, sol ve t he subprobl em of est ablishing t hat precon di t i on . Th i s subprobl em m ay be sol ved eit her in T-sp a c e or in t he original (object ) sp a ce. If su ccessf u l , spl i ce t he precondit ion-f ulf illing su b seq u en ce int o t he original solut ion seq u en ce. o Subgoal-preserving substitution. Subst it ut e an operat or in t he original sol ut i on seq u en ce by anot her operat or (or seq u en ce of operat ors) t hat red u ces t he sam e di f f erence. Th i s T-op er a t or is part icularly usef ul if eit her a precondi t i on of an operat or in t he original seq u en ce ca n n ot b e sat isf ied, or if t he p resen ce of a part icular operat or in t he solut ion seq u en ce violat es a pat h con st r a i n t . 6 o Final-segment concatenation. Trea t t he sol ut i on seq u en ce as a m acro-operat or Note that a subgoa l-pre se rving substitution is m uch m ore restrictive tha n a ge ne ra l delete T-ope ra t or followe d by a ge ne ra l insert T-ope ra t or. The re f ore , this T-ope ra t or is m ore apt to yield useful tra nsform a tions, a fa ct reflected in the. ordering of ope ra tors under e a ch a ppropria te entry in the diffe re nce ta ble. 8 Learni ng a n d Problem Solving b y An a l ogy in t he original problem sp a ce a n d apply M EA t o red u ce t he di f f erence bet ween t he old final st at e and t h e new final st at e. If su ccessf u l , con cat en at e t he sol ut i on t o t his subprobl em at t he en d of t h e original solut ion seq u en ce. o Initial-segment concatenation. Ap p l y t he p r o cess a b ove t o f ind a pat h in t h e original probl em sp a ce f rom t he new initial st at e t o t he old initial st at e. If su ccessf u l , concat enat e t h e sol ut i on t o t his subprobl em at t h e begi nni ng of t he original solut ion. [ Not e t hat in t his ca se w e start wit h t h e initial st at e f or t he new problem and seek a pat h t o t he initial st at e f or t he ret rieved sol ut i on, w h erea s in t he f inal segm ent -concat enat i on operat or t he i nverse p rocess applies.] o Sequence meshing. M erge t he operat or seq u en ces of t w o com plem ent ary solut ions ret rieved in t he rem inding process. Th e result ant sol ut i on seq u en ce sh ou l d dif f er f rom a com plet e sol ut i on t o t h e new problem b y t he int ersect ion of t he di f f erences bet ween ea ch ret rieved sol ut i on and t he new problem sp eci f i ca t i o n . If 7 t he di f f erences bet ween t he t wo ret rieved solut ions and t he n ew probl em specif icat ion f orm disjoint set s, seq u en ce m eshing yields a com pl et e sol ut i on . o Operator reordering. Reor d er t he operat ors in a solut ion seq u en ce. Of t en a pat h const raint in t h e new proble/ n speci f i cat i on ca n b e sat isf ied by sim ple reorderi ng of operat ors (w h en allowed b y t heir precondi t i ons) in t he ret rieved sol ut i on . o Parameter substitution. Subst it ut e t he obj ect s to w h i ch operat ors w ere applied in t h e ret rieved sol ut i on by t he cor r esp on d i n g obj ect s in t he new problem speci f i cat i on. o Solution-sequence truncation. Elim inat e u n n ecessa ry operat ors. Tw o signif icant special ca ses of t his T-o p er a t o r are initial-segment truncation and final-segment truncation. For i nst ance, if t he final st at e of an operat or su b seq u en ce of t he ret rieved sol ut i on exhibit s a sm aller di f f erence t o a goal st at e of t h e n ew probl em , use t his su b seq u en ce as t h e n ew basis f or m apping int o t he desi red sol ut i on seq u en ce. o Sequence inversion* Reverse t he operat or seq u en ce, invert ing ea ch individual operat or, if a problem f orm ulat ion is su ch t hat its goal st at e m at ches t he initial st at e of a sol ved probl em , and its initial st at e m at ches t he goal st at e of t hat sam e previously sol ved probl em . Invert ing a p rocess is not always possi bl e, and seldom direct ly achi evabl e. In t he present ca se, t he i nverse of ea ch operat or m ust b e f ou n d , a n d its precon di t i on s sat isf ied, in order t o apply global i n versi on . How ever , t he general not ion is at t ract ive -- con si d er solving t he problem of driving bet ween t wo point s in an u n k n ow n cit y. On c e t his problem is so l ved , t he su b seq u en t problem of ret urning t o t h e depart ure sit e is easily sol ved by operat or seq u en ce i nversi on. 7 M e rgi n g two partial ope ra tor se que nce s is a n interesting a nd potentia lly com ple x problem in itself. Proce dura l network s, de ve lope d in the N OAH system [2 4 ], facilitate com puta tions of ope ra tor intera ctions whe n m eshing two pla ns. It is not a lwa ys the ca se that two partial solution se que nce s ca n be m erged effectively (e.g., e a ch subse que nce m ay viola te ne ce ssa ry pre condit ions for the other subse que nce ). Non-a lgorithm ic T-ope ra t ors, such as sequence meshing, de fine their own interna l proble m spa ce . Probl em Solving b y An a l ogy • Th e difference m etric in t he t ransf orm sp a ce ( D ) is a com bi nat i on of t he di f f erence T m easures bet w een initial st at es (o f t h e ret rieved a n d d esi red sol ut i on seq u en ces), final st at es, pat h const rai nt s, and d egr ee of applicabilit y of t he ret rieved solut ion in t he new problem scen a ri o. Hen ce, t h e values of D are 4 -vect ors, w i t h t h e int erpret at ion t hat all T f ou r com p on en t di f f erences m ust b e r ed u ced (i ndependent l y or joint ly) in t he t ransf orm sp a ce (T-sp a ce) probl em -sol vi ng p r ocess. D S S ) D ( S S ) T? V l 1' l,2 » 0 F 1' F 2 - < i f i D p f P C^ P C^ , D ( S OL , S OL ) > A 1 2 D Q is t h e di f f eren ce f unct i on bet w een st at es in t h e original sp a ce . Dp com put es di f f erences bet ween pat h const rai nt s (PC' s). D m easures t he applicabilit y of t he ol d sol ut i on in t he new scen a r i o b y A det erm ining t he f ract ion of operat ors in t h e initial solut ion seq u en ce ( S OL ^ w h o se precondi t i ons a re not sat isf ied u n d er t he n ew probl em speci f i cat i on . S, den ot es an initial st at e. S den ot es a final (goal) st at e. p Th e su b scri p t 1 i n dexes t he ret rieved sol u t i on . Th e su b scr i p t 2 i n d exes t he speci f i cat i ons o n t h e desi red sol ut i on t o t h e new probl em . D is r ed u ced w h en a n y of its f our com p on en t s is independent ly r e d u ce d . Th e problem - y sol vi ng p r ocess in T-sp a c e su c c e e d s w h en D = < NIL, NIL, NIL, NIL> . Int erest ing sea r ch T probl em s o c c u r w h e n , in or d er t o r ed u ce on e com p on en t in t h e di f f eren ce vect or, o n e or m ore of t he ot her com p on en t s m ust b e i n crea sed . Fo r exam pl e, t he insert ion of new operat ors int o t he solut ion seq u en ce m ay have t h e unf ort unat e si de-ef f ect of violat ing an est abl i shed precon di t i on of a n operat or in t h e original seq u en ce. In t his ca se reduci ng D ( I ) or D ( F) result s in increasing D . Ou r f i rst -pass solut ion is t o def ine a (linear) Q Q A com bi nat i on of t h e f our com p on en t s and ch o o se t h e opera t or that m axim ally r ed u ces t his val ue, back t rack ing w h en n ecessa ry. Fort unat el y, it is oft en t he ca se t hat di f f erences in t h e 4 -vect or ca n be r ed u ced in a com p on en t w i se-i n d ep en d en t m anner. M oreover, a m odif ied versi on of t he A-M IN m et hod [4 ] m ay appl y, f ocusi n g t he back t rack ing p r ocess w h en back t rack ing proves n ecessa ry. • A di f f erence t able f or i n dexi n g t he T-o p er a t o r s is n eed ed . Ent ri es in t he dif f erence t able t ak e t h e f orm " To reduce < D I FFEREN CE> , apply a m em ber of < T-OP ERA TOR-SET> " . Th e operat ors in t h e appl i cabl e set are usually ordered as a f unct i on of t h e heurist ic m easure of t heir utility in redu ci n g t h e gi ven di f f erence. A sam ple di f f erence t able ent ry w ou l d b e : o If t he precon di t i on s t o an operat or in S OL a re n ot sat isf ied (i.e., D is n on -n u l l ), t ry 1 A subgoal-preserving substitution on t he inapplicable operat or, o r t ry solution-sequence splicing t o sat isf y t he violat ed precon di t i on s. • Th e r e are n o pat h const raint s in t he t ransf orm sp a ce. Si n ce w e a re m apping from on e 10 Learning a n d Probl em Sol vi ng b y An a l ogy sol ut i on seq u en ce t o anot her, t h e int erm ediat e st at es and T-o p er a t o r s d o not necessari l y co r r esp o n d t o act ual operat i ons perf orm ed on an ext ernal w o r l d , a n d t heref ore are not su b j ect t o its rest rict ions. Th i s sim plif icat ion is of f set b y t he m ore com p l ex di f f eren ce m et ric in T-sp a c e . 2 .2 . S o m e e xa m p l e s Co n si d e r a sim ple probl em w h ere anal ogi cal problem sol vi ng m ay p r ove quit e appropri at e: Jo h n is locat ed in Pit t sburgh a n d m ust t ravel t o New Yo r k Ci t y. Ho w ever , w h en he cal l ed t he airlines, he d i sco ver ed t hat all t h e f light s w er e b o o k ed . Jo h n n ever t ook t he int ercit y t rain (Am t rak ) b ef ore, but k n ow s it is a possi bl e m eans of l on g-d i st a n ce t ravel . Jo h n ' s plan m ight b e t he f ollowing: Cal l Am t rak t o m ak e a reservat i on. Mak e su r e he has suf f icient m oney f or t h e t ick et . Fi n d out w h ere t o b u y t he t ick et ; b u y it; and lat er g o t o t he st at ion and b oa r d t he t rain. W h y is t his a reasonabl e pJan? Ho w cou l d Jo h n h a ve syn t h esi zed his plan? W e ca n n ot really say t hat Jo h n had a " s c r i p t " f or t ak ing t rains, as he had not previ ousl y t raveled b y t rai n, n or h a d he 8 a cq u i red t he requisit e, det ailed inf orm at ion enabling him t o d o so . A reasonabl e w a y of f orm ulat ing t he plan is by a n a l ogy wit h t ak ing an airplane (or p erh a p s an int ercit y b u s). Th e f irst st ep is f or Jo h n t o b e rem inded of t ak ing an airplane (t hus recalling: m ak ing reservat i ons, t ick et s bei ng cost l y, of t en purchasi ng t he t ick et s in a d va n ce, lat er t raveling t o t he ai rport , et c.) Not e t hat it is cru ci a l f or Jo h n t o b e rem inded of an exp er i en ce (or a general p r oced u r e) w h er e he w a s fulfilling a sim ilar goa l (int ercit y t ravel) a n d not on e w h er e superf i ci al sim ilarit ies a b o u n d (e.g., t ak ing a su b w a y, w h er e bot h m eans of co n ve ya n ce a re cal l ed " t r a i n s" , t h ey t ravel on t rack s, have m any st op s, et c.). Su b w a y t ravel w ou l d not su ggest t he pot ent ial necessi t y of m ak ing a reservat i on, n or w ou l d it su ggest t he requirem ent f or a reasonabl e sum of m oney t o p u r ch a se t he t ick et . Hen ce, a com p a ri son of goa l st at es, as su ggest ed in ou r gen era l m et h od, is i ndeed a cru ci a l com p on en t in t h e sim ilarit y j udgem ent s n ecessa ry f or m odeling a reason abl e rem inding p r ocess. Th e sol ut i on t ransf orm at ion p r o cess p r o ceed s b y appl yi ng t he subgoal-preserving substitution T-o p er a t o r , subst it ut ing TR A I N -TR A VEL f or A I R-TRA VEL , as bot h operat ors r ed u ce t he sam e di f f erence. Th e n , t h e parameter-substitution T-o p er a t o r repl aces " a i r p or t " b y " t rain st a t i on " , " ai rl i ne t i ck et " by " t rai n t i ck et " , et c. Jo h n m ust rely on his k n ow l ed ge of h o w t o sat isf y t he precon di t i on s of A I R-TRA VEL , and h op e t hat t he sam e m et hods appl y t o TR A I N -TR A VEL . If t his w er e not t h e ca se, f urt her probl em solving w ou l d be n ecessa ry. 8 B y "script " I m ea n a slight va ria tion of Scha nk a nd Abe lson's te rm inology [2 6 ,7 ], i.e., a f roze n pla n: one or m ore norm a tive se que nce s of pla nne d a ctions w hose purpose is to sa tisfy the pre condit ions of (a nd ca rry out) a high-le ve l ope ra tor. Problem Solving by An a l ogy 11 Now , let us recon si der t he m on k ey-an d-ban an as and experi m ent er-and-bananas problem s, in light of t he analogical probl em -sol vi ng m odel. A m onk ey w a t ch es a behavioral psych ol ogi st (i.e., t he experim ent er) pick up a w o o d en b o x and place it u n d er a hook in t he ceiling. Next , t he experim ent er clim bs on t he b ox, pl aces som e bananas on t he hook , clim bs off t he b ox, and ret urns it t o its original l ocat i on. Th e n , t h e experim ent er releases t h e (h u n gry) m onk ey and leaves t he room . Ho w d o es t h e m onk ey plan t o reach t he bananas? Ca n he benef it f rom having observed t he experim ent er? As w e m ent ioned earlier, a " sm art m onk ey" ou gh t t o learn f rom his observat i ons of t he experim ent er. Let us see h ow analogical problem solving applies here. For sim plicit y, assum e t he m onk ey d oes not have prior exp eri en ce solving sim ilar problem s b eyon d his recent observat i on of t he experim ent er. Th e m onk ey's problem is: in it ia l st a t e = m onk ey on t he f loor, bananas on t he ceiling, b ox in t he room ; f i n a l st a t e = m onk ey in possessi on of t he bananas; p a t h c o n st r a i n t s = physi cal abilit ies of t he m onk ey. How ever, t he sol ut i on t o t he experim ent er's problem ca n n ot be applied direct ly. (His problem w a s init ia l st a t e = possessi on of t he bananas, b o x in t he room , experim ent er on t he f loor; f i n a l st a t e = Bananas on t h e ceiling, b ox not under t h e bananas; p a t h c o n st r a i n t s = physical abilit ies of t he experim ent er.) Assum ing t he pat h const raint s m at ch, t he di f f erences bet ween t he initial st at es (and t he di f f erences bet ween t he final st at es) are so large as t o precl ude any reasonable attem pt at di rect analogical t ransf orm at ion. Th er ef or e, t he m onk ey m ust resort t o st andard M EA (in t he original problem sp a ce). He select s t he operat or GET-OB JECT (applied to bananas). Th i s operat or suf f ers an unsat isf ied precon di t i on : Th e m onk ey can n ot reach t h e bananas. Th er ef or e, t he act ive su b goa l becom es: Rea ch t he ceiling w here t he bananas are l ocat ed. How m ay t he m onk ey proceed at t his junct ure? Th e ent ire problem ca n , of co u r se, b e sol ved by recursi vel y applying st andard M EA. How ever, t here is a m ore di rect solut ion m et hod. If t he m onk ey recalls his observat ion of t he experim ent er, he m ay realize t hat t he problem of reaching t he ceiling has already been sol ved (by t he experim ent er, as a su b goa l t o placing t he bananas t here - al t hough t he m onk ey need not underst and t he experim ent er's hi gher-l evel goal s). Th e m onk ey ca n apply t he parameter-substitution T-o p er a t o r (subst it ut ing " m on k ey" f or " exp eri m en t er" ), and opt ionally t he solution-sequence truncation T- operat or (elim inating t he need t o ret urn t he b ox t o its original locat ion aft er having used it ). Th i s problem -solving p r ocess in T-sp a c e result s in a plan t hat t he m onk ey ca n apply direct ly t o reach t he bananas, and t hus achi eve his original* goal of having t he bananas. Th e signif icant aspect of t he experi m en t er-m on k ey-an d-ban an as exam ple is t hat st andard M EA 12 Learning and Problem Solving b y An al ogy and T-sp a c e M EA w ere com bi n ed int o a unif orm probl em -sol vi ng p rocess w h ere st andard M EA calls on analogical problem sol vi ng t o sol ve a subprobl em m ore direct ly. Th e con ver se p r o cess is also possi bl e, and pot ent ially signif icant . For i nst ance, in t he Am t rak exam pl e, if Jo h n cou l d not have sat isf ied on e of t he precondi t i ons f or t ak ing t he t rain by anal ogy wit h t he cor r esp on d i n g A I R-TRA VEL precon di t i on , he cou l d have resort ed t o st andard M EA t o sol ve t his su b p rob l em . Hen ce, Analogical reasoning adds a powerful dim ension to standard problem solving when prior experience can be brought to bear, but rem ains largely unobstrusive when no relevant prior knowledge suggests itself. It w ou l d be usef ul f or t h e problem sol ver t o rem em ber his new probl em -sol vi ng exp er i en ces t o use as a basis f or f ut ure analogical reasoni ng. Th ese cou l d b e rem em bered di rect l y or abst ract ed int o epi sodi c t races, m uch lik e Schank a n d Ab el son ' s scri pt s [ 2 6 ,7 ] , and hierarchically orga n i zed as a f unct ion of t he goal s t hey f ulf ill. An int erest ing observat ion co n ce r n s t he recursi ve cl osu r e of analogical M EA . 9 If t he t -operat or seq u en ce of an analogical problem sol vi ng t ransf orm at ion is rem em bered, t he anal ogi cal M EA p rocess can b e applied t o t hese t ransf orm at ions t hem selves. Th a t is, on e ca n con st ru ct an analogical m apping bet ween t w o solut ion seq u en ces by recyling a past analogical m apping am ong sim ilar solut ions -- o r b y t ransf orm ing a past , alm ost useable m apping b y recursi ve applicat ion of analogical M EA t o t he analogical m apping itself. A signif icant point is t hat no infinit e regress requiring new " h yp er -a n a l ogi ca l " m et hods o ccu r s. Th e sam e analogical t ransf orm at ion p r ocess t hat appl i es t o obj ect -l evel solut ion seq u en ces applies di rect l y t o t ransf orm ing anal ogi cal m appings. 3 . Eva lua t ing t he Ana logica l Re a soning P roce ss In an inform al experim ent , not m eant to wit hst and st at ist ical si gni f i cance t est s, I ga ve t he f ollowing problem t o f ive undergraduat e h i st ory-a n d-a rt st udent s: Prove that the product of two even num bers is even. Som ew hat t o m y su rpri se and dism ay, n o n e of t he f ive w as able t o sol ve t his sim ple algebraic problem , alt hough all f ive m ade seri ou s at t em pt s. I had int ended t o gi ve t he subj ect s sim ilar but m ore dif f icult problem s in subseq uen t st ages of t h e experim ent , m easuring w h et h er t hey im proved in sp eed or a ccu r a cy f rom t heir recen t l y-a cq u i red exp er i en ce solving analogically-relat ed problem s. Nevert heless, t he experim ent p roved usef ul in dem onst rat ing t he reliance of hum an problem s sol vers on analogical m echanism s, as di scu ssed below. Con t i n ui n g wit h t he experim ent , I expl ai ned t he proof p rocess caref ully en o u gh t o i nsure t hat all f ive subj ect s un derst ood it: Vhis observation is due in part to Mitchell, personal com m unication. Evaluat ing t h e Anal ogi cal Reasoning Pr ocess 13 First , recall t he def init ion of an even num ber: a num ber t hat is divisible by 2 . Se c o n d , writ e d o w n an expressi on t hat represent s an even num ber: Yo u m ay writ e " 2 N " w h ere N is a n y int eger, t o r e p r e se n t s num ber divisible b y 2. Next , m ult iply t wo even num bers, writ ing: 2 N x 2 M , w h er e M is also any int eger. Mult iplying w eget 4 NM . Now , recall t he represent at ion of an even num ber: 2 x any int eger. Th er ef or e yo u can writ e 4 NM = 2 x 2 NM , w h i ch by cl osu re of int egers under m ult iplicat ion m at ches t he represent at ion of an even num ber. Hen ce, t he product of t wo even num bers is even . At t his point , all five subj ect s claim ed t hey underst ood t he proof , and m oreover exp ressed som e f eeling of em barrassm ent f or not having deri ved su ch an " o b vi o u s" proof t hem selves. Th e n , I su ggest ed t hey t ry t he f ollowing probl em : Prove that the product of two odd num bers is odd. Wit h grim det erm inat ion t o redeem t heir previ ous p oor perf orm ance all five at t em pt ed t he problem a n d t hree of t hem su cce e d e d . Brief ly: Od d num bers can be represent ed as " even + 1" = 2 N +1 f or any int eger N. Th e product is: (2 N + 1) x (2 M + 1) = 4 NM + 2 N + 2 M + 1 = 2 (2 NM + N + M) + 1, w h i ch is t he represent at ion of an o d d n u m b e r . 10 Th i s inform al experim ent st rongly indicat es t hat t he seco n d problem w a s sol ved by anal ogy f rom t he solut ion to t he first problem . Th e scr a t ch papers col l ect ed f rom t he subject s su ggest di rect attem pts at t ransf erring and m odif ying st eps of t he first sol ut i on. Th e insert ion of an ext ra algebraic s t e p 11 illust rat es an applicat ion of t he subsequence splicing T-op er a t or . Th e gl obal subst it ut ion of a represent at ion f or odd num bers in pl ace of a represent at ion f or even num bers st rongl y su ggest s parameter substitution. M oreover, t he m ere f act t hat t hree of five su bj ect s were able t o sol ve a problem m ore com plex t han t he on e w h ere all five failed previously, argues very con vi n ci n gl y f or an analogical p rocess exploit ing t he previ ous solut ion (or som e abst ract ion t hereof ). How ever, it sh ou l d b e not ed t hat t his t ype of experim ent d oes not in itself dem onst rat e dom i nance of analogical reasoning in hum an problem solving, but rat her it provi des st rong evi d en ce for t he exi st ence of Interestingly, one subje ct chose to re pre se nt odd num be rs as 2 N + 3 , which is corre ct but requires a bit of a dditiona l a lgebra ic m a nipula tion. W h e n a sked why she chose such a representa tion, her reply was "4 is a nice e ve n num ber, a nd 7 is a nice odd num ber. The diffe re nce between them is 3 . Th e next e ve n num ber is 6; the next od d is 9 ; a nd the difference is always 3 . So, I took 2 N a nd a dde d 3 ." W ha t a gra phic illustra tion of m e a ns-e nds-a na lysis to solve the subproble m of m apping from a representa tion of e ve n num be rs to a representa tion of odd num bers! Of the two subje cts who did not present a n a dequa te proof, one erred in an a lgebra ic m a nipula tion step, the othe r e rrone ously chose 3 N a s his representa tion for odd num be rs. 1 1 I.e., distributing the product of the two odd num be rs is required to fulfill a pre condition for fa ctoring the consta nt "2 " from three of the four term s in: 4 NM + 2 N + 2 M + 1. 14 Learning and Problem Solving b y An a l ogy analogical processes in cogni t i ve act ivit ies. Dem onst rat ing t he con j ect u re t hat an al ogy is t he cent ral inf erence m echanism f or hum an problem solving w ou l d require a m uch m ore t h or ou gh (and perhaps m ore cont rolled) set of psych ol ogi cal observat i ons. As a t est of t he com put at ional feasibilit y of t he analogical problem sol vi ng p r ocess, a sim ple versi on of M EA w a s program m ed t o operat e on t he t ransf orm sp a ce, and gi ven a subset of t he T-op er a t or s wit h a correspon di n g dif f erence t able. It sol ved t he p r od u ct -of -t w o-od d s problem st art ing f rom t he solut ion f or t wo even n u m b e r s. 12 Th e initial com put er im plem ent at ion of analogical M EA is not of part icular int erest - it dem onst rat es t hat t he analogical problem solving p r ocess act ually w ork s, but d oes little else. Th e t ruly int erest ing i ssues will arise w h e n : • a m uch f uller im plem ent at ion is available allowing com pari sons am ong dif f erent problem solving m et hods over a represent at ive co r p u s of problem s, • t he learning f rom exp eri en ce p r ocess d i scu ssed in t he f ollowing sect i on is f ully int egrat ed wit h t he analogical t ransf orm p r ocess, • and t he analogical problem sol ver is int egrat ed wit h a dynam i cal l y-changi ng long t erm m em ory m odel. 4 . Le a rning Ge n e ra lize d Pla ns Th e analogical t ransf orm at ion p r ocess provi des a m et hod of exploit ing pri or exp er i en ce in a f lexible m anner. Th a t is, it requires only t hat t h e new problem be st ruct urally sim ilar, rat her t han ident ical, t o on e or m ore previously sol ved p r o b l e m s. 13 Hen ce, sim ply st oring solut ions t o new problem s const it ut es a f orm of learning — as t hese ca n serve as a basis f rom w h i ch solut ions t o yet newer problem s m ay be anal ogi zed. How ever, t here are ot her aspect s t o learning t hat present m ore int erest ing chal l enges. To wit , if a t yp e of problem recurs wit h suf f icient f req u en cy, a hum an planner is apt t o f orm ulat e a general i zed plan f or dealing wit h f ut ure inst ances of t hat problem , rat her t han reasoning analogically f rom a part icular m em ber of t hat cl ust er of sim ilar exp eri en ces. A general i zed ^plan is, in essen ce, sim ilar t o Sch a n k ' s not ion ^of a scri pt [2 6 ,2 8 cull7 7 ], i.e., a param et erized Th e progra m use d 2 N-1 to represent a n odd num ber, since the SUB1 ope ra tor wa s ina dvertently listed before ADD1 in the obje ct -spa ce difference ta ble, a nd the re fore the progra m ha d to splice in an a dditiona l a lgebra ic step in the solution: (2 N-1 )(2 M -1 ) = 2 (2 NM - N - M ) + 1, which doe s not corre spond to the 2 N-1 representa tion for odd num be rs, a nd the re fore ha d to a pply subsequence splicing to a dd two a lge bra ic ope ra tors that tra nsform ed the e xpre ssion into 2 (2 NM - N - M + 1) -1 . In f a ct m ost of the com puta tiona l effort w a s spe nt finding those two ope ra tors (a dding a nd subtra cting the sa m e qua ntity, a nd refa ctoring the e xpre ssion). This a lloca tion of effort roughly corre sponds to the substa ntia l tim e spe nt by the subje ct who chose 2 N + 3 as a representa tion with the resuftant product being 2 (2 NM + 3 N + 3 M ) + 9 , which did not e xa ctly m a tch the origina l re pre se nta tion, a nd wa s eventua lly re fa ctore d into 2 (2 NM + 3 N + 3 M + 3 ) + 3 . Th e M ACR OP S fa cility in STR I P S re quire d corre sponding initial sta tes a nd goa l sta tes to be identica l m odulo pa ra m eteriza tion of ope ra tors in orde r to re use portions of pa st solution se que nce s [9 ], Learning Gen eral i zed Plans 15 y branchi ng seq u en ce of event s wit h exp ect ed goal s and def ault act i ons. 4 .1 . A c q u i r i n g Ge n e r a l i z e d S o l u t i o n s P r o c e d u r e s How is a general i zed plan acqui red f rom past problem solving experi ence? Con si d er an induct ive engi ne, su ch as t hose devel oped t o f orm ulat e general i zed con cep t s from seq u en ces of posit ive and negat ive exem plars of t he t arget con cep t , as d i scu ssed in [1 0 ,2 9 , 3 0 ,8 ,1 8 ] . Inst ead of acquiring disem bodied con cep t s f rom an ext ernal t eacher providing t raining seq u en ces of exem plars labeled " p osi t i ve" or " n ega t i ve" , in experient ial learning t he exem plars con si st of past problem s and t heir respect i ve solut ions. Th ese solut ions are gr ou p ed t oget her as exem pl ars of a general i zed plan by virt ue of being derived from a com m on ancest or in t he analogical t ransf orm p rocess. Th u s, as in learning from observat i on, t he con cep t s t o be acqui red are not k now n a priori b y an ext ernal t eacher, but cor r esp on d to cl ust ers of experient ially relat ed sol ut i ons to a com m on t ype of probl em . Th e " t yp e " is not art ificially def i ned, but d ep en d s on t he act ual exp eri en ce of t he individual problem solver. More specif ically, general i zed plans are acqui red by t he f ollowing p r ocess: • Wh en ever t h e analogical problem sol ver generat es a solut ion t o a n ew problem , tha t sol ut i on is t est ed in t he ext ernal w o r l d . If it w ork s, it b ecom es a m em ber of t h e posit ive exem pl ar set , t oget her wit h t he prior solut ion f rom w h i ch it was anal ogi zed and ot her su ccessf u l sol ut i ons to problem s f rom t he sam e anal ogi cal root . • If t he anal ogi zed sol ut i on fails t o work w h en applied in t he ext ernal w orl d , t he ca u se of t he f ailure is st ored and t his sol ut i on becom es a m em ber of t he corresp on d i n g negat ive exem pl ar set . • Th e posit ive and negat ive exem plar set s are gi ven t o an induct ion en gi n e that generat es a plan encom passi ng all t he posit ive solut ions and n on e of t he negat ive exem plars. Th u s, t he t raining seq u en ce is provi ded by past exp er i en ce sol vi ng sim ilar problem s, rat her t han b y an ext ernal t eacher. An d , t h e co n cep t a cq ui red is a general i zed solut ion p r oced u r e rat her t han t he d escri p t i on of a st at ic object* as i s t ypically t he ca se in t he co n ce p t acquisit ion lit erat ure. If t h e descri pt i on l a n gu a ge f or t he ob j ect -sp a ce operat ors is ext en ded, addit ional generalizat ion ca n o c c u r (e.g., in select ing m ore general operat ors t hat co ver disjunct ive su b seq u en ces in t he general i zed solut ion plan). • M oreover, negat ive exem plars are n e a r -m i sse s, si n ce t he anal ogi cal p r ocess generat ed 14 t hem b y m ak ing a sm all num ber of ch a n ges to k nown posit ive inst ances (i.e., t ransf orm at ions t o past solut ions of t he sam e general problem t ype, ret aining t he bulk of t h e solut ion st ruct ure invariant ). Hen ce, near-m i ss analysis can point out t h e relevant discrim inant f eat ures bet ween posit ive and negat ive exem plars of t he gen era l planning st ruct ure under con st ru ct i on . In ot her w or d s, t he problem sol ver serves as an aut om at ed W inston [3 0 ] defines a near-miss as a nega tive e xe m pla r that differs from positive exem pla rs in a sm all num ber of significa nt fea tures. Ne a r m isses are crucia l in isola ting defining cha ra cte ristics of a conce pt in the le a rning-from -e xa m ple s pa ra digm . 16 Learning a n d Problem Solving b y An a l ogy exam ple generat or, p rod u ci n g near-m i sses as a side ef f ect w h en failing t o generat e an ef f ect ive plan. • Finally, in ca ses w h ere t h e anal ogi cal problem sol ver fails t o generat e a sol ut i on f or t he new problem (as op p osed t o generat ing an er r on eou s solut ion t hat b ecom es a negat ive exem plar f or t he general i zed plan f orm at ion p rocess), dif f erent inf orm at ion can be a cq u i red . Th e sit uat ions w h ere a solut ion w a s recal l ed and a plan w a s f orm ed analogically (i ndependent of w h et h er t he plan w ork ed) serve as posit ive exem pl ars t o reinf orce and perhaps general i ze t he sim ilarity m et ric used t o search m em ory. Th e ca ses w h ere a recalled solut ion cou l d not be anal ogi zed int o a candi dat e plan f or t he new problem su ggest t hat t he ol d and new problem s dif f ered in som e cru ci a l aspect not adequat ely t ak en int o a cco u n t in t he sim ilarit y m et ric, and t hus serve as negat ive reinf orcem ent t o ref ine a n d const rai n t he sim ilarit y cri t eri on. Graphi cal l y, t he inf orm at ion f low in t he learning p rocess is illust rat ed in f igure 4 -1 . Th e f orm ula A n a l o g y: S . / C. --> P ./ C. sh ou l d be int erpret ed as Th e anal ogi cal t ransf orm p r ocess m aps plan P. appl i cabl e u n d er con di t i on s ,r C.i n t o plan P. applicable un der condi t i ons C.." An d , t h e f orm ula En vi r o n m e n t : P ./ C. - > + ( or -) sh ou l d read as " Pl a n P. su cceed ed (or f ailed) w h en execu t ed in t he ext ernal environm ent u n d er condi t i ons C.." Fi gure 4-1 sum m arizes t he p r ocess of acquiring general i zed plans and updat ing t he sim ilarity crit erion f rom exp eri en ce. Th e anal ogi zed plans along wit h t heir condi t i ons of applicabilit y, f orm t he input t o a learning-f rom -exam ples en gi n e. Su ccessf u l solut ions a re classif ied a s posit ive exem pl ars; un successf ul ones are classif ied as near-m iss negat ive exem pl ars. M oreover, t he ca ses w h ere t he anal ogy t ransf orm p r ocess f ailed t o yield a candidat e plan b ecom e negat ive reinf orcem ent inst ances t o a param et er-t uning p rocess, w h i ch is posit ively rei nf orced by t h ose ca ses w h ere a (successf ul or unsuccessf ul ) plan w a s f orm ulat ed. Updat ing t he sim ilarit y crit erion sh ou l d m ak e f ut ure m em ory sea rch es f or solut ions t o sim ilar problem s m ore responsi ve t o t he f eat ures t hat enabl e t he analogical t ransf orm syst em t o m ap a recalled sol ut i on int o a pot ent ial solut ion f or t he new problem . Th u s, w e see t hat analogical problem solving int erf aces nat urally wit h a l earni ng-f rom -exam pl es m et hod in t hat it provi des an int ernal exam ple generat or requiring no ext ernal t eacher. Present ly, I am ext endi ng t he problem solving engi ne t o ext ract and use inf orm at ion from t he planning p r ocess itself (not j ust problem descri pt i ons and corresp on d i n g sol ut i ons), su ch as viable alt ernat ives not ch o sen , ca u ses of f ailure t o be wary of in sim ilar sit uat ions, et c. Th e obj ect i ve of t his endeavor is t o enable t he l earni ng-f rom -exam pl es com pon en t t o learn, or at least ref ine, t he problem solving st rat egies t hem selves, in addit ion t o f orm ing general i zed plans. Th u s, general pat t erns of Learning General i zed Plans 17 Th e a n a l o g i ca l p r o b l e m so l vi n g p r o c e s s An a l ogy: S / C , Envi ronm ent : P / C »> + "> P 2 / C 2 2 2 An a l ogy: S / C2 2 Envi ronm ent : P 3 / C -> 3 + "> P 3 / C 3 An a l ogy: S / C --> P4,'/ C. 1 "4 Envi ronm ent : P 4 / C ~> 4 - An a l ogy: S / C -> 3 3 Envi ronm ent : P 5 / C --> 5 - P 5 / C 5 An a l ogy: S / C 3 3 --> < n o-p l a n > / C 6 An a l ogy: S / C 1 1 • >- < n o -p l a n > / C ? Acq u irin g ge n e ra lize d pla ns f ro m so l u t i o n s a t t e m p t s t o si m i l a r p r o b l e m s Input to a learning-from -exam ples process Posit ive exem pl ars: P / C P / C , P / C r 2 2 3 3 Negat ive exem pl ars: P / Q , P / C (near m isses) 4 4 5 5 Output from the learning-from -exam ples process Gen era l i zed pl an: P / C G Q Up d a t i n g t h e si m i l a r i t y c r i t e r i o n u se d t o re ca l l r e l e va n t p r i o r e xp e r i e n c e Input to a param eter-tuning process Present sim ilarit y m et ric Posit ive reinf orcem ent t rials: C C , C , C , C r 2 3 4 5 Negat ive reinf orcem ent t rials: C , C Q ? Output from the param eter-tuning process Updat ed sim ilarit y m et ric Fi gu r e 4 -1 : Acqui ri ng general i zed plans and updat ing t he sim ilarit y m et ric inf erence m ay be a cq u i red from exp er i en ce [6 ]. Part s of t he plan generalizat ion p r ocess are current ly being im plem ent ed t o t est t he viabilit y of t he p rop osed k nowl edge acquisit ion m et hod, and prelim inary result s are en cou ra gi n g. Al t h ou gh , m uch of t he t heoret ical a n d experim ent al work in acquiring problem sol vi ng sk ills is st ill ahead of us, t here is suf f icient evi den ce t o su pport t he t wo original hypot heses: t he int egrat ion of learning a n d problem solving m et hods int o a unif ied cogni t i ve m echanism , and t he utility of t he learning-f rom -exam ples t echni que f or acquiring planning sk ills as well as m ore st at ic con cep t s. As ou r di scussi on has dem onst rat ed, learning can o c c u r in bot h phases of analogical problem Learning a n d Problem Sol vi ng b y An a l ogy 18 sol vi ng: 1) t he rem inding p r ocess t hat orga n i zes a n d sea r ch es past exp eri en ce, a n d 2) t he anal ogi cal t ransf orm at ion p r ocess itself. Addit ional issues in t h e experient ial adapt at ion of t he rem inding p rocess are d i scu ssed b e l o w . 15 4 .2 . Ep i so d i c M e m o r y Or g a n i z a t i o n Mem ory of sol ut i ons t o previous probl em s, w het her observed or di rect l y exp er i en ced , m ust b e organ i zed by sim ilarit ies in goa l st at es, initial st at es, a n d m eans available (or pat h const raint s present ). Ot herw i se, t here can b e no reasonable rem inding p rocess w h en solving f ut ure problem s of a sim ilar nat ure. Hen ce, a hi erarchi cal indexing st ruct ure on an epi sodi c m em ory m ust be dynam ically con st ru ct ed and ext en ded as t h e syst em gradually accum ul at es new experi ence.. Gi ven an ef f ect ive m em ory m odel , t he p r ocess of con t i n uousl y expandi ng and st ruct uring past exp er i en ce becom es a relat ively sim ple, but absolut ely essent ial, aspect of learning t hat p r oceed s co n cu r r en t wit h analogical reasoning. M oreover, t he m em ory m odel sh ou l d ret rieve general plans w h en t hese have been proven reliable to t he excl u si on of t he original epi sodi c m em ory t ra ces, w h i ch t h en ef f ect ively " f a d e" f rom m em ory. " Fa d i n g" m eans t hat t he m em ory indexing st ruct ure is alt ered so t hey are no l onger easily recalled in t he rem inding process. (Th i s not ion is ak in t o Sch a n k ' s " m u sh i n g" p rocess [2 7 ] a n d An d er son ' s m ask ing b y decl i ni ng relat ive act ivat ion [1 ].) 4 .3 . Ep i so d i c M e m o r y R e st r u c t u r i n g It is con cei va b l e t hat in t he lifetim e of an adapt ive problem sol ver, t he nat ure of t he problem s it is called u pon t o sol ve m ay ch a n ge gradually. Th e ch a n ge m ay m anifest itself as d ecr ea sed reliabilit y of t he di f f erence f unct i on com pari ng new a n d ol d problem specif icat ions, causi ng t he rem inding p r ocess t o ret rieve inappropriat e sol ut i ons, or t o m iss relevant past exp eri en ces. Hen ce, a m eans of t uning t he dif f erence m et ric in a f ailure-driven m anner is a requisit e p r ocess f or long-t erm adapt ive behavi or. M ore specif ically, t h e heurist ic com bi ni ng t he f ou r val ues in t he D 4 -vect or m ay b e t u n ed t o yi el d T appropriat e values f or cert ain cl asses of problem s m ost com m only en cou n t er ed . For inst ance, dif f erences in pat h const raint s are less m eaningf ul t o a probl em -sol ver w h o has am ple resou rces t han t o a m ore sp a rt a n l y-en d ow ed problem sol ver. If a graduat e st udent lat er b ecom es a m illionaire, t he f act t hat he now com m ands m ore subst ant ial resou rces sh ou l d lessen t he im pact of r esou r ce-b a sed pat h const raint s in his problem sol vi n g. Con seq u en t l y, t he sim ilarit y m et ric will cea se t o con si der past 1 6 T h e rea der is referred to Scha nk [2 7 , 2 8 ], Le bowit z [1 4 ] a nd Kolodne r [1 2 ] for va rious discussions on the t ype of ba sic e pisodic m em ory m odel im plicit in this pa per. Th e m em ory orga niza tion sche m e m ust be structure d a ccording to sim ilarity criteria instrum enta l to the task indexing a nd reca lling pa st problem solving e xpe rie nce [5 ]. Learning General i zed Plans 19 solut ions of ot herwise sim ilar problem s t hat w ere sol ved w h en operat ing under m ore sever e resou rce const raint s. Th i s is not a part icularly desi rabl e st at e of af f airs, as resource-l i m i t ed solut ions are cert ai nl y viable, if not al ways desi rabl e, t o a problem sol ver com m anding m ore resou rces. Th er ef or e, t h e rem inding heurist ic sh ou l d n o l on ger w ei gh pat h-const raint di f f erences as heavily. (Not e t hat rem inding is a const rai ned sea r ch p rocess, w h erea s analogical m apping or inst ant iat ing a general sol ut i on pat t ern are generat i ve p rocesses. Hen ce, t he rem inding p r o cess need only ret rieve approxim at e, plausible solut ions.) Ret urning t o ou r exam ple, if t hat sam e m illionaire later files f or bank rupt cy, t he rel evance of r esou r ce-b a sed pat h const raint s assum es signif icant proport i ons o n ce again. A pauper will not be able t o sol ve m ost problem s by em ulat ing a m illionaire. Th u s, t he pat h- const raint com pon en t of t he sim ilarit y/ dif f erence m et ric sh ou l d reest ablish its cent ral role in t he rem inding heurist ic. In t his m anner, t he rel evance of ea ch com ponent in t he sim ilarity m easure is subj ect t o long-t erm f l u ct u a t i o n . 16 JHow can t he relat ive w ei ght s in t he sim ilarit y heurist ic be t uned? When t he rem inding p r ocess fails t o ret rieve a viable initial st at e t o t he T-sp a c e problem sol ver, but t he problem is later sol ved in t he original problem sp a ce, t he sol ut i on can b e com pared t o epi sodi c m em ory. If a solut ion t o a previ ous problem is f ound t o b e very sim ilar, t hen t he problem descri pt i ons sh ou l d also have been f ound sim ilar by t he rem inding heurist ic. Th e com p on en t cont ribut ing t he largest dif f erence is t hen red u ced in im port ance. Th e con ver se p rocess al so applies. If a sol ut i on ret rieved as sim ilar d oes not lead t o a solut ion in T-sp a c e , t he dif f erence(s) t hat cou l d not be red u ced b y t he T-sp a c e problem sol ver are m ade m ore im port ant in t he dif f erence heurist ic. Th ese com plem ent ary processes regulat ing t he di f f erence m et ric are d esi gn ed t o m ak e all ch a n ges very gradually t o insure against pot ent ially unst able behavior. Th i s form of experient ial param et er t uning is a new applicat ion of a t echni que dat ing back t o Sam uel [2 5 ]. 4 . 4 . T-O p e r a t o r R e f i n e m e n t If epi sodi c m em ory is ext en d ed t o cont ai n T-sp a c e probl em -sol vi ng t races, in addit ion t o exp eri en ced event s and solut ions t o past problem s, t hen learning ca n o c c u r in t he T-op er a t or dom ain. For inst ance, con si d er a T-o p e r a t o r present wit h high f req u en cy in u n su ccessf u l T-sp a c e solut ion attem pts. It is con cei va b l e t hat t he ent ry (or ent ries) in t he di f f erence t able indexing that T-op er a t or are insuf f icient ly con st ra i n ed, suggest i ng t he need f or a discrim inat ion p r ocess su ch as This proce ss is a na logous to Be rline r's a pplica tion coefficients in S N AC [3 ], whose va lues cha nge gra dua lly ove r the course of a ga m e. Here cha nge occurs m ore gra dua lly ove r the lifetim e of the problem solve r, but I am proposing an a da ptive ra ther tha n a pre -progra m m e d conte xtua l-we ighting proce ss. Note that whe re a s individua l pa th constra ints differ from problem to proble m , I am discussing gra dua l cha nge s in the relative significa nce of path constra ints vis a vis other criteria in the sim ilarity m etric on a ve ra ge ove r m any individua l problem solving e pisode s. 20 Learni ng a n d Problem Sol vi ng b y An a l ogy t he f ollowing: ~ 1. Com p a re T-sp a c e sol ut i on at t em pt s w h er e t he T-o p er a t o r in quest ion w a s present onl y in f ailure pat hs, wit h solut ion at t em pt s w h ere it w as present in su ccessf u l sol ut i on pat hs. 2 . If t here are m ult iple ent ries in t he di f f erence t able f or t hat T-o p er a t o r , and som e ent ries cor r esp on d onl y t o f ailure i nst ances of t he operat or, delet e t hese ent ries, as t he operat or is being applied t o red u ce a di f f erence it p r oved i ncapabl e of red u ci n g. 3 . If a single ent ry cor r esp on d s t o m any m ore f ailures t han su ccesses, t he descri pt i on of t h e di f f erence being red u ced m ay b e t oo general and ou gh t t o b e f act ored int o a di sj unct i ve set of m ore specif ic dif f erences. Lat er exp er i en ce ca n help isolat e w h i ch of t hese su b - dif f erences t he T-op er a t or is act ually capabl e of redu ci n g. Th e n , t he m ore speci f i c dif f erences (t hose t hat t he T-o p er a t o r in quest i on proved capabl e of red u ci n g) repl ace t he previ ous m ore general ent ry in t he di f f erence t able. Ot h er di f f erences in t he f act ored disjunct ive set t hat (as exp eri en ce sh ow s) can n ot b e red u ced by t he T-o p er a t o r are d i sca r d ed . It sh ou l d be not ed t hat t he operat ion of f act oring an arbit rary co n cep t int o a disjunct ive set of su b -co n cep t s is, in gen era l , not a t ract able p rocess. How ever, gi ven a hi erarchi cal m em ory m odel and a n on -m on ot on i c i nf erence ca p a b i l i t y, approxim at ely 17 cor r ect f act orings ca n be a ch i eved . 4 .5 . Th e A c q u i s i t i o n o f N e w T-Op e r a t o r s If t h e rem inding p r ocess ret rieved on e or m ore sol ut i ons, but t he anal ogy t ransf orm p r ocess f ailed t o m ap t hese into a solut ion sat isf ying t he speci f i cat i ons of t he new probl em , and t he original- probl em -space problem sol ver f oun d a sol ut i on , t hen w e have a cl ea r i ndi cat or t hat t he T-sp a c e problem sol ver is m issing som e essent ial T-op er a t or s. On e a p p r oa ch t o rem edy t his sit uat ion is t he f ollowing p rocess: 1. Com p a re t he sol ut i on com put ed b y t he problem sol ver in t he unt ransf orm ed sp a ce wit h t he vari ous at t em pt ed t ransf orm at ions in T-sp a c e . 2. Fi nd t he int erm ediat e st at e in t h e f ailed T-sp a c e sol ut i on at t em pt t hat m inim izes t h e di f f erence m et ric ( D ) t o t he solut ion com put ed b y st andard M EA. T 3 . Hypot h esi ze a T-o p er a t o r inst ance t o b e t he t ransf orm at ion f rom t he cl osest st at e (rea ch ed in t he T-sp a c e sol ut i on at t em pt s) t o t h e act ual sol ut i on. Sa ve t his T-o p er a t o r inst ance. 4. If lat er problem -solving im passes ca u se f ailure-driven creat ion of m ore T-o p er a t o r inst ances, t hen t he applicat ion of a l earni ng-f rom -observat i ons t ech n i q ue, su ch as t he conceptual clustering m et hod [1 7 ] m ay p rove f ruit f ul. If t he exem pl ars a re suf f icient ly sim ilar, or f orm clust ers of cl osel y sim ilar exem pl ars, new T-op er a t or s ca n be hypot hesi zed a ccord i n g t o t he charact erist ic descri pt i on of ea ch con cep t u a l clust er. 1 7 N o n -m o n o t o n i c inference is a pla usible infe re nce te chnique ba sed on tenta tive de duct ions a nd a ssum ptions that m ay prove inva lid a s a dditiona l k nowle dge is a cquire d [1 6 ]. Learning General i zed Plans 21 " Suf f icient ly sim ilar" in t his con t ext m eans that t he com m on st ruct ure shared b y t he clust er of T-op er a t or inst ances is not present in ot her act ive T-op er a t or s. Hen ce, t he new operat or will perf orm t ransf orm at ions dif f erent f rom t hose of any previously exist ing T- operat or -- i.e., t he new operat or m ay p rove generat i vel y usef ul. 5. Th e new l y-creat ed T-op er a t or m ay t hen b e added t o t he set of act ive T-op er a t or s (subject t o t he ref inem ent p rocess a bove if t he new operat or proves unreliable). 6. Th e ent ry in t he dif f erence t able indexing t he new T-op er a t or is a b o u n d ed generalizat ion of t he dif f erences that ea ch T-op er a t or inst ance red u ced at t he tim e it was crea t ed . If t hese dif f erences d o not share a com m on com pon en t not present in ot her ent ries, m ore t han on e (disjunct ive) ent ry m ust b e m ade in t he di f f erence t able. Th u s, new T-op er a t or s can be a cq u i red if t he problem sol ver is gi ven a set of problem s f or w h i ch t he sam e (previ ousl y un k n ow n ), general T-sp a c e t ransf orm at ion w as required. M oreover, t he operat or acquisit ion and discrim inat ion p rocesses are equally applicable to ref ining and ext ending set s of operat ors in t he original unt ransf orm ed problem sp a ce (if t he problem sol ver ca n t ap an ext ernal sou r ce of k n ow l edge u pon f ailure, or relax processi ng const raint s upon resource-lim it ed f ailure). Acquiring T-op er a t or s, h ow ever, requires learning from observat i on , rat her t han t he bet t er underst ood a n d general l y sim pler p r ocess of learning-f rom -exam ples used t o acqui re general i zed plans. Th e learning m echanism s d i scu ssed in t his sect i on ca n prove ef f ect ive if and only if t he reasoning syst em is capable of rem em bering, indexing and ret rieving past exp er i en ce, including aspect s of its int ernal processing in previ ous problem -solving at t em pt s (e.g., hypot hesi zed T-op er a t or inst ances). Th er ef or e, t he necessit y f or b o t h dynam ic m em ory organizat ion p rocesses and a problem solving m echanism ca pa bl e of exploit ing epi sodi c m em ory is clearly m anif est . 5 . Con clu din g Rem a rk Th e prim ary object ive of t his paper has been t o lay a unif orm f ram ework f or analogical problem solving capabl e of int egrat ing sk ill ref inem ent and plan acquisit ion p rocesses. Most work in m achine learning has not addressed t he issue of int egrat ing learning and problem solving into a unif ied p rocess. (How ever, Mit chell [1 9 ] and Len a t [ 1 5 ] are part ial count er-exam pl es.) Past and present invest igat ions of anal ogi cal reasoning have f ocu sed on disjoint aspect s of t he probl em . Fo r inst ance Wi nst on [3 1 ], invest igat ed analogy as a powerf ul m echanism f or classif ying and st ruct uring epi sodi c descri pt i ons. Kling [1 1 ] st udi ed anal ogy as a m eans of reduci n g t he set of axiom s and f orm ulae t hat a t heorem prover m ust con si d er w h en deriving new proof s to t heorem s sim ilar t o t hose en cou n t ered previ ousl y. In his o w n w ord s, his syst em " ...deri ves t he analogical relat ionship bet ween t wo [ gi ven] Learning and Probl em Solving b y Anal ogy 22 problem s and out put s t he kind of inform ation t hat c a n b e usef ully em pl oyed b y a problem -solving syst em t o expedi t e its se a r ch ." How ever, a n a l ogy t ak es no di rect part in t he probl em -sol vi ng p rocess itself. Hen ce, t he ext ensi on of m eans-ends analysis t o an anal ogy t ransf orm sp a ce is, in it self, a new, pot ent ially-signif icant problem -solving m et h od, in addit ion to support i ng vari ous learning m echanism s in an int egrat ed m anner. R e f e re n ce s 1. An d er so n , J . R. a n d Gr een o , J . G., " Acq u i si t i on of Probl em -Sol vi ng Sk i l l ," in Cognitive Skills and Their Acquisition, J . R. An d e r so n , e d ., Hillsdale, N J: Erl baum Assoc., 1981. 2. An za i , Y. and Si m on , H. A., " Th e Th e o r y of Learning b y Doi n g," Psychological Review, Vo l . 86, 1 9 7 9 , pp. 124-140. 3. Berliner, H., " On t he Con st ru ct i on of Eval uat i on Fu n ct i on s f or La r ge Dom ai n s," Proceedings of the Sixth International Joint Conference on Artificial Intelligence, 1979 , p p . 5 3 -5 5 . 4/ Ca r b on el l , J . G., " A -M I N: A Sea r ch -Co n t r o l M et h od f or Inf orm at ion-Gat hering Prob l em s," Proceedings of the First AAAI Conference, Au gu st 1 9 8 0 . 5. Ca r b on el l , J . G., " M et aphor: An Inescapabl e Phenom enon in Nat ural La n gu a ge Co m p r eh en si o n ," in Knowledge Representation for Language Processing System s, W. Lehnert and M. Ri ngl e, eds., New Jer sey: Erl baum , 1982. Ca r b on el l , J . G., " To w a r d s a Com put at i onal M odel of M et aphor in Com m on Sen se Rea son i n g," Proceedings of the Fourth Annual Meeting of the Cognitive Science Society, 1982 , An n Ar b or , M l . 7. Cu l l i n gf ord , R., Script Application: Com puter Understanding of Newspaper Stories, PhD dissert at ion, Ya l e Uni versi t y, Sep t . 1977. \ $. Diet t erich, T. a n d Michalsk i, R., " In d u ct i ve Learni ng of St r u ct u r a l -Descr i p t i on s," Artificial Intelligence, Vo l . 16,1981 . 9. Fik es, R. E. a n d Ni l sson , N. J. , " STRI PS: A New Ap p r o a ch t o t he Applicat ion of Th eorem Provi ng t o Problem Sol vi n g," Artificial Intelligence, Vo l . 2,1971 , pp. 189-208. ^JO. Ha yes-Rot h , F. and McDerm ot t , J. , " Kn o w l ed ge Acqui si t i on f rom St ruct ural Descri pt i on s," Proceedings of the Fifth International Joint Conference on Artificial Intelligence, 1977 , pp. 3 5 6 -3 6 2 . 11. Kling, R. E., " A Paradigm f or Reasoni ng b y An a l o gy," Artificial Intelligence, Vo l . 2, 1971 , pp. 147-178. 12. Kol odn er, J . L., Retrieval and Organizational Strategies in Conceptual Mem ory: A Com puter Model, PhD dissert at ion, Ya l e Uni versi t y, Nov. 1980. \ 13. Korf , R. E., " To w a r d a M odel of Represent at ion Ch a n g e s," Artificial Intelligence, Vo l . 14, No. 1, 1 9 8 0 , pp. 4 1 -7 8 . Con cl u d i n g Rem ark 23 14. Lebow i t z, M., Generalization and Mem ory in an Integrated Understanding System , PhD dissert at ion, Ya l e Universit y, Oct . 1980. 15. Lenat , D., AM: Discovery in Mathem atics as Heuristic Search, PhD dissert at ion, St anf ord Universit y, 1977. 16. McDerm ot t , D. V. and Doyl e J. , " No n -M o n o t o n i c Logi c I," Artificial Intelligence, Vo l . 13, 1980 , p p . 4 1 -7 2 . 17. Michalsk i, R. S., and St ep p , R. E., " Learn i n g f rom Ob serva t i on : Con cep t u a l Cl u st eri n g," in Machine Learning, An Artificial Intelligence Approach, R. S. Michalsk i, J. G. Ca rb on el l and T. M. Mit chell, ed s., Ti o g a Press, Palo Alt o, CA , 1982. 18. Mit chell, T. M., Version Spaces: An Approach to Concept Learning, PhD dissert at ion, St anf ord Universit y, Decem ber 1978. 19. Mit chell, T. M., Ut gof f , P. E. and Banerji, R. B., " Lea rn i n g b y Experi m ent at i on: Acqui ri ng and Ref ining Probl em -Sol vi ng Heu ri st i cs," in Machine Learning, An Artificial Intelligence Approach, R. S. Michalsk i, J . G. Ca r b on el l and T. M. Mit chell, eds., Ti o g a Press, Palo Alt o, CA, 1982. 20. M oore, J . a n d Newel l , A., " Ho w ca n M ERLI N Un d erst a n d ?," in Knowledge and Cognition, L. Gr e gg, ed ., Hillsdale, N J: Erlbaum Assoc., 1974, p p . 2 5 3 -2 8 5 . 21. Newel l , A. and Si m on , H. A., Hum an Problem Solving, New Jer sey: Prent i ce-Hal l , 1972. 22. New el l , A. and Rosen bl oom , P., " M ech an i sm s of Sk ill Acqui si t i on and t he Law of Pr a ct i ce," in Cognitive Skills and Their Acquisition, J . R. An d er so n , e d ., Hillsdale, N J: Erlbaum Assoc., 1981. 23. Ni l sson, N. J. , Principles of Artificial Intelligence, Ti o g a Press, Palo Alt o, CA, 1980. 24. Sa cerd ot i , E. D., A Structure for Plans and Behavior, Am st erdam : Nort h -Hol l a n d , 1977. 25. Sam uel , A. L., " Som e St udies in M achi ne Learning Usi ng t he Gam e of Ch e ck e r s," in Com puters and Thought, E. A. Fei genbaum and J . Fel dm an , ed s., M cGr a w Hill, New Yor k , 1963, pp. 7 1 -1 0 5 . 26. Sch a n k , R. C. a n d Ab el son , R. P., Scripts, Goals, Plans and Understanding, Hillside, N J: La w r en ce Erl baum , 1977. 27. Sch a n k , R. C , " Rem inding and Mem ory Orga n i za t i on : An Int roduct ion t o M OPS," Te c h . report 170, Ya l e Universit y Co m p . Sc i . Dept ., 1979. 28. Sch a n k , R. C , " La n gu a ge and M em ory," Cognitive Science, Vo l . 4, No. 3 ,1 9 8 0 , p p . 243-284. 29. Ver e, " In duct i ve Learning of Relat ional Pr od u ct i on s," in Pattern-Directed Inference System s, Wat erm an and Ha yes-Rot h , 1978, eds., New Yor k : Academ i c Press, 1978. 30. Wi n st on , P., Learning Structural Descriptions from Exam ples, Ph D dissert at ion, M IT, Sept em ber 1970. Learni ng and Problem Sol vi ng b y An a l ogy Wi n st on , P . H. , " Lea rn i n g a n d Reasoni ng by An a l o gy," CACM, Vo l . 2 3 , No . 12, 1979 , p p . 6 8 9 -7 0 3 . Wi n st on , P., Artificial Intelligence, Readi n g, M A: Ad d i son Wesl ey, 1977. U N Ci A SSI FI ED SECURITY CL A SSI FI CA TI ON OP ~ " i S P * CE Q m fm Entered) REA D IN STRU CTIO N S REPORT DOCUMENTATION PAGE B E F O R E CO M P LETIN G FORM [K REPORT NUM BER 2. GOVT ACCESSI ON NO 3. RECIPIENT'S CATALOG NUM BER CM U - CS- 8 2 - 1 2 6 ONR [4 . TI TLE (ond Subtitle) 5. TYP E OF REPORT * PERIOD COVER ED LEARNING BY ANALOGY: FORMULATING AND Interim GENERALIZING PLANS FROM PAST EXPERIEN CE «. PERFORM ING ORG. REPORT NUM BER 17. A U T H O R S t. CON TR ACT OR GRANT N U M 8 E R C «> JA IME G. CARBONELL N 0 0 1 4 - 7 9 - C- 0 6 6 1 PERFORM ING ORGANIZATION NAM E AND AOORESS 10. P R OGR AM EL EM EN T. P R OJECT. TA SK Carnegie-Me lion University A R E A * W ORK U N I T NUM BERS Computer Science Department ' Pittsburgh, PA. 15213 111. CON TR OLLI N G OFFI CE NAM E A N O AOD RESS 12. REPORT OATE Ju n e 12, 1982 13. NUM BER O F PAGES 27 14. M ON I TORI N G AGENCY NAM E a AOOR ES S C1 / dilioront from Controlling Qtiic.) IS. SECURITY CLASS, (of this roport) UNCLASSIFIED IB* . D ECLASSI FI CATI ON/ OOW NGRAOI NG SCH ED ULE I D ISTRIBUTION STATEM EN T (oi'thtm Rm port) J1 7 . D I STRI BUTI ON STATEM EN T (oi thm obm trm ct entered in Stock 2 0 . it diiloront f r o m R.pTrT) .. Approved for public release; distribution unlimited I SUP P LEM EN TARY NOTES I It . K E Y W O R O S (Continue on referee etao il nece em ery and identify by block num ber) 120. ABSTRACT (Continue on r ewer m e m i do I I neceeeory ond identity by block num bor) An al ogi cal reasoning is a powerf ul m echanism f or exploit ing past exp er i en ce in planning a n d problem sol vi ng. Th i s paper out lines a t heory of analogical problem sol vi ng based on an ext ensi on t o m eans-ends analysis. An analogical t ransf orm at ion p rocess is d evel op ed to ext ract k nowl edge from past su ccessf u l problem solving sit uat ions that bear st rong sim ilarit y to t he current problem . Th e n , t he invest igat ion f ocu ses on exploit ing and ext ending t he anal ogi cal reasoning m odel t o generat e usef ul exem pl ary sol ut i ons t o relat ed problem s f rom w h i ch m ore gen eral plans can be i n d u ced a n d OD , JA N 7 3 M 1473 C O I T I O N O F 1 N O V es is O B S O L E T E UNCLASSI FI ED S/ « 0 1 0 2 -0 1 4 -6 6 0 1 I ' SECURITY C L A S S I F I C A T I O N O F T H I S P A G E (+nen Oeto Entered) U N CLA SSIFIED S E C U R I T Y C L A S S I F I C A T I O N 0 * T H I S P A G C fTh— Dm* ref ined St art ing wit h a general analogical inf erence en gi n e, problem solving exp eri en ce is. in essen ce, com piled increm ent ally into ef f ect ive p roced u res t hat sol ve vari ous cl asses of problem s in an increasingly reliable and direct m anner. S N 01 0 2 - Lr- 0 1 4 - 6 6 0 1