Recovering from failure in temporal planning

Ho-JinChoi,VassilisLiatsos,AminEl-Kholy,andBarryRichards1

Abstract.Thispaperdescribesanopenproblemintemporalplan-ning,namelytheproblemofrecoveringfromfailureincollapsingtimeintervals.WeillustratethisprobleminthecontextoftheparcPLANplanningsystemandshowitsfullcomplexitybycombiningtheprob-lemwithresourcereasoning.Wealsosummarisesomeoftheprogressmadetotacklethisproblem.

1Introduction

Apracticalplanningsystemshouldconcerntwolevelsofoptimalityinitsoutputplans:(1)obtaininganoptimalplaninthenumberofactionsgenerated;and(2)obtaininganoptimalscheduleintheusageoftimeandresources.TheseissuesofoptimalityhavebeencentraltothedesignofparcPLAN[8],atemporalplanningsystemwhichiscurrentlyunderdevelopmentatIC-Parc.

parcPLANfollowsaninterval-basedplanningparadigm[1].2Bothactionsandpropertiesareindexedexplicitlytointervals.More-over,thetraditional“oneactionatatime”assumptiondisappears.parcPLANaimstoproduceplanswhichmaximiseconcurrencyinactionexecutionsubjecttoavailableresources(e.g.,numberofrobotarms)andspecifictemporalconstraints.Thetaskofintegratingactionschedulingandresourceallocationpresentsaformidablecomputa-tionalproblem.

Inthispaperwedescribesomeofthedifficultproblemsfacedinplangeneration.Weshallfocus,inparticular,ontheareaofrecoveringfromcollapsingfailures[1,2,4,6].Forexample,AllenandKoomen’splanner[1]hasnostrategyforintroducingnewactionswhenthesetoftemporalconstraintsbecomesinconsistent.Whenthishappens,thereisnoclueastowhichsubgoalshaveledtothetemporalcon-tradiction.Heretheplannerhastoresorttoblindsearch.Plainlythisisanintractableprocess.Thereseemstobenodomain-independentstrategytosolvethisproblem.Theaimofthispaperistoclarifythisproblemwithaviewtoseekingastrategy.

Wefirstpresentinsection2therepresentationandplangenerationframeworkusedinparcPLAN;insection3wedescribetheproblemofrecoveringfromcollapsingfailure.Section4summarisestheprogresswehavemadesofartowardssolvingthisproblem.

2TheparcPLANArchitecture2.1Representation

InparcPLANbothpropertiesandactionsarerepresentedbytermsindexedtotimeintervals.Weusethenotationp@[start,end)tosaythatproperty(oraction)pholds(oroccurs)overthetimeinterval

action:move(Block,From,To,Arm)@[Start,End)conditions:1.on(Block,From)@[T1,Start),2.clear(To)@[T2,End),3.

clear(Block)@[T3,T4)effects:4.on(Block,To)@[End,T5),5.

clear(From)@[Start,T6)constraints:6.designates(Block,block),7.designates(Arm,arm),

8.

designates([From,To],[block,table

3

Theterm“collapsing”originatesfrom[1].

istocollapseallthesegoalssubjecttomaintainingtheconsistencyofcodesignationconstraintsandtemporalconstraints.Theresultofsuccessfulcollapsingisasetofactions,whichareusuallypartiallyspecifiedandpartiallyordered(representedbyasetofcodesignationandtemporalconstraints).Atthispointtheplannermovesintotheschedulingandresourcereasoningstep,wherethetaskistodeter-minewhethertheactionscanbemadefullyspecificandscheduledsubjecttotheavailableresources.

2.3Example

Toillustratetheplanningprocess,letusseehowtheproblempre-sentedinfigure1issolvedinparcPLAN.

Intheinitialstatethefollowinggoalshavenopotentialcollapser.

on(a,b)@[T7,20)on(b,c)@[T8,20)on(c,t1)@[T9,20)

Letussupposethatthegoal,on(a,b)@[T7,20),isselectedfirstandthattheactionmove(a,1,b)@[S1,E1)isintroducedtoachievethisgoal.X1isanobjectvariablewhichcanbeeitherablockoratableposition,butcannotcodesignatewithblocka(X1a).

Facts:

Goals

F1.on(a,t2)@[0,T1)G1.on(b,c)@[T8,20)F2.on(b,t1)@[0,T2)G2.on(c,t1)@[T9,20)F3.on(c,a)@[0,T3)G3.on(a,X1)@[T12,S1)F4.clear(b)@[0,T4)G4.clear(b)@[T13,E1)F5.clear(c)@[0,T5)G5.clear(a)@[T14,T15)

F6.clear(t3)@[0,T6)F7.on(a,b)@[E1,20)

F8.clear(X1)@[T10,T11)

Figure3.Planstateafterintroducingmove(a,X1,b)@[S1,E1)

Bythisactionintroduction,thestateoffactsandgoalsisupdatedbyaddingtheeffectsandconditionsoftheactionappropriately.Theupdatedstateispresentedinfigure3.Sincethestateoffactsandgoalshaschanged,someofthegoalswhichpreviouslyhadnopotentialcollapsermayhaveoneintheupdatedstate;andsomeofthenewlyaddedgoalsmayhavenopotentialcollapser.

Intheupdatedstate,thefollowinggoalshavenopotentialcollapser.

on(b,c)@[T8,20)on(c,t1)@[T9,20)clear(a)@[T14,T15)

Continuingactionintroduction,theplannerreachesapotentiallycol-lapsiblestateafterintroducingtheactions,

move(b,X2,c)@[S2,E2)(wheremove(c,3,t1)@[S3,E3)(whereX2X3b)cand).

Thepotentiallycollapsiblestateispresentedinfigure4.Inthisstateeverygoaliscollapsible,asindicatedinthefollowinglist.1.G1cancollapsewithF1(ifX1=t2)orF7(ifX1=b)

2.G2cancollapsewithF4orF8(ifX1=b)orF12(ifX3=b)3.G3cancollapsewithF10(ifX2=a)orF12(ifX3=a)4.G4cancollapsewithF2(ifX2=t1)orF9(ifX2=c)

5.

G5cancollapsewithF5orF8(ifX1=c)orF10(ifX2=c)

Facts:

Goals

F1.on(a,t2)@[0,T1)G1.on(a,X1)@[T12,S1)F2.on(b,t1)@[0,T2)G2.clear(b)@[T13,E1)F3.on(c,a)@[0,T3)G3.clear(a)@[T14,T15)F4.clear(b)@[0,T4)G4.on(b,X2)@[T18,S2)F5.clear(c)@[0,T5)G5.clear(c)@[T19,E2)F6.clear(t3)@[0,T6)G6.clear(b)@[T20,T21)F7.on(a,b)@[E1,20)

G7.on(c,X3)@[T24,S3)F8.clear(X1)@[T10,T11)G8.clear(t1)@[T25,E3)F9.on(b,c)@[E2,20)

G9.clear(c)@[T26,T27)

F10.clear(X2)@[T16,T17)F11.on(c,t1)@[E3,20)F12.clear(X3)@[T22,T23)

Figure4.Collapsibleplanstate

6.G6cancollapsewithF4orF8(ifX1=b)orF12(ifX3=b)7.G7cancollapsewithF3(ifX3=a)orF11(X3=t1)

8.G8cancollapsewithF8(ifX1=t1)orF10(ifX2=t1)orF12(ifX3=t1)

9.G9cancollapsewithF5orF8(ifX1=c)orF10(ifX2=c)Duringthecollapsingsteptemporalconstraintsaregeneratedtomakeintervalsassociatedwithconflictingpropertiesdisjointandtoensureeachgoalintervalislocatedintheintervalofoneofitspotentialcollapsers.Thetaskhereistocollapseallthesegoalsconjunctivelysubjecttomaintainingtheconsistencyofthetemporalandthecodes-ignationconstraints.(Asonecansee,collapsingisanintractabletaskduetotheneedtosolveanexponentialnumberoftemporalcon-straintnetworks[3].)InourexamplecollapsingsucceedswiththeassignmentX1=t2,X2=t1,andX3=a.

Finally,parcPLANmovestotheschedulingandresourcereasoningsteptocheckwhetherthegeneratedplanisexecutablewiththere-sourcesavailable.Ifthreerobotarmsareavailable,theplanshowninfigure5canbeobtained,whichlocatesthethreeactionsconcurrently.

arm1c a t1arm2b t1 carm3

a t2 b1

2

3

4

5

6

Figure5.Asolutionusing3arms

3TheProblemofFailureRecovery

Therearebasicallytwotypesoffailureintheplanningprocessde-scribedabove.

1.Failureincollapsing

2.FailureinschedulingwithrespecttoavailableresourcesCollapsingfailsbecauseofaninconsistencyinthetemporalconstraintnetworkorinthecodesignationconstraints;schedulingfailsbecauseitisimpossibletofindaviableschedulefortheactionssubjecttotheavailableresources.TheproblemwithanearlierversionofparcPLANisthatitwouldgiveupplanningwheneitherofthesetwofailuresoccurred.

3.1Failureincollapsing

Whentheplannerentersthecollapsingstep,everygoalinthegoallisthasatleastonepotentialcollapser.Thiscondition,althoughnec-essary,isnotsufficienttoguaranteethatallthegoalscanbeachievedconjunctivelybytemporalpersistence.Thereasonisthatinteractionsarenottakenintoaccountwhencheckingpotentialcollapsers;col-lapsingagoalwithafactmayruleoutcollapsingothergoals.Belowwepresenttwoexamplesofcollapsingfailure:acaseoffailureduetoaninconsistencyincodesignationconstraintsandacaseoffailureduetoaninconsistencyintemporalconstraints.

Inconsistencyincodesignationconstraints

Theplanningprobleminfigure6addressesthefirstcase.Itshowsanexamplewherecollapsingrequiresanobjectvariabletocodesignatewithtwodifferentvalues.

a

abcbct1

t2

t3

t1

t2

t3

Initial State

Goal State

Figure6.Anotherblocksworldexample

Theplannerreachesapotentiallycollapsiblestate(showninFigure7)afterintroducingthefollowingactions,

move(b,X1,c)@[S1,E1)(whereX1bmove(c,X2,t1)@[S2,E2)(whereX2

b)).

andFacts:

Goals

F1.on(a,b)@[0,T1)G1.on(a,b)@[T7,20)F2.on(b,t3)@[0,T2)G2.on(b,X1)@[T12,S1)F3.on(c,t2)@[0,T3)G3.clear(b)@[T13,T14)F4.clear(a)@[0,T4)G4.clear(c)@[T15,E1)F5.clear(c)@[0,T5)G5.on(c,X2)@[T18,S2)F6.clear(t1)@[0,T6)G6.clear(c)@[T19,T20)F7.on(b,c)@[E1,20)

G7.clear(t1)@[T21,S2)

F8.clear(X1)@[T10,T11)F9.on(c,t1)@[E2,20)

F10.clear(X2)@[T16,T17)

Figure7.Apotentiallycollapsiblestateduringsolvingtheproblemin

figure6

Althougheachgoalisindividuallycollapsible,aninconsistencyarisesinthecodesignationconstraintswhenconsideringallthegoals.1.(X1=t3)(X1=c)topotentiallycollapseG22.(X2=b)topotentiallycollapseG3

3.(X2=t2)(X2=t1)topotentiallycollapseG5

CollapsinggoalG3withF10requiresvariableX2tobeboundtob,whilecollapsinggoalG5withF3requiresthesamevariableX2tobeboundeithertot2ortot1.Noconsistentlabellingexistsfortheobjectvariablesintroduced.Hence,collapsingfailsevenwithoutcheckingtemporalconstraints.

Whenafailureoccurs,theplannercaneither(1)backtracktoapre-viouschoicepointtochooseadifferentactionoperatorforachievingagoal,or(2)introducenewactionsintothefailedplan.Wearepar-ticularlyinterestedinthesecondcase,wheretherelevantgoalsarethosewhichwereinvolvedincollapsing;oneormoreofthemmustbeachievedbyintroducingnewactions.Thedifficultyistoidentifygoalswhichneedtobeachievedbyactionintroductionsinceeverygoalinthefailedstatehasapotentialcollapser.

Inconsistencyintemporalconstraints

Theexampleinfigure8addressesthecaseoffailureduetoanincon-sistencyintemporalconstraints.

acabbct1

t2

t3

t1

t2

t3

Initial State

Goal State

Figure8.Yetanotherblocksworldexample

Forthesakeofthisexample,supposethatweaddtothemoveactioninfigure2temporalconstraintswhichrestrictthedurationoftheactiontorangefrom2to4timeunitsasfollows.

EndStartStart++24(sets(setsthethelowerupperbound)End

bound)

Forthisexampletheplannerreachesapotentiallycollapsiblestateafterintroducingthefollowingactions.

move(a,X1,b)@[S1,E1)move(b,X2,t1)@[S2,E2)move(c,X3,t2)@[S3,E3)

Inthiscasethereexistsaconsistentlabellinginvolvedinthecodes-ignationconstraints,e.g.,1223,underwhicheverygoalhasapotentialcollapser.Thisassignmentresultsinassertingthefollowingtemporalconstraints(amongothers).

1.S3S1+1(blockchastobeclearbeforeitismoved)2.S2S3+1(blockbhastobeclearbeforeitismoved)3.E2S2+2(lowerboundonactionduration)

4.

E1E2+1(blockacannotbeplacedonblockbuntilblockbhasbeenmoved)

5.S1+4E1(upperboundonactionduration)

From(1),(2),(3),(4)wecandeducethatE1S1+5,whichcon-tradicts(5).Thesetoftemporalconstraintsisinconsistent;therefore,collapsingfails.

Again,wewishtohavetheplannerproceedbyintroducingfurtheractionstorecoverfromthefailure.Butwhichgoal(s)tochooseisthequestion.Itisanopenissuewhetherthereisadomain-independentstrategytorecoverfromsuchanimpasseduringatemporalplanningprocess.

3.2Failureinschedulingwithavailableresources

Theresultofsuccessfulcollapsingisasetofactions,whichareusu-allypartiallyspecified(e.g.,duetothechoicesremainingincodesig-nationconstraints)andpartiallyordered(e.g.,asrepresentedbythe

minimalnetworkofthetemporalconstraints).Atthispointthetaskistodeterminewhethertheactionscanbemadefullyspecificandscheduledsubjecttotheavailableresources.Thetaskisessentiallyadisjunctiveschedulingproblemcomplicatedbythreeinterdependentfactors,viz.thenumberofavailableresources,actionoverlap,andactionduration.

Asolutiontothisresourcefeasibilityproblemhasbeenprovidedin[5]withanapproachwhichusesBooleanmeta-variablestolinktemporalandresourcereasoning.ThisisimplementedintheCLPlanguageECLPS.Empiricalstudiesindicatethattheproposedtechniquesignificantlyenhancesthesearchforplanfeasibilityandservestominimisetheeffortofgeneratingaplanusingleastnumberofactions.Returningtoourearlierexampleinfigure1,thethreeactionsappear-ingintheprevioussolution(seefigure5)canbere-scheduledasinfigure9ifonlytwoarmsareavailable.

arm1c a t1a t2 barm2

b t1 c1

2

3

4

5

6

7

Figure9.Asolutionusing2armsfortheprobleminfigure1

However,aproblemverysimilartothecollapsingfailureariseswhenitisimpossibletofindaviableschedulefortheintroducedactionssubjecttotheavailableresources.Intheplanningproblempresentedinfigure1suchacaseariseswhenonlyonearmisavailable.

Usingthemethodproposedin[5],resourcereasoningquicklydetectsthatitisnotpossibletofindaschedulewheretheactionscouldbeexecutedbyasinglerobotarm.Afailureisthensignalled,andcontrolisreturnedtotheactionintroductionstep.Againwefacethesameproblemofdecidingwhichgoal(s)tochoosetotriggerthenextcycleofactionintroduction.

4On-goingProgress4.1ControllingtheSearch

WehaveenhancedtheparcPLANimplementationtotakerecoveryactions(althoughrudimentaryatthisstage)incaseoneofthedis-cussedfailuresoccur.Inthissection,wedescribethesearchstrategywehaveusedforthisenhancedversionofparcPLAN.

Duringtheactionintroductionphase,ifagoalisfoundwhichtwoormoreactionoperatorscanachieve,achoicepointiscreatedontheactionoperatorselection.Choosingdifferentactionsrequirestheplannertoreturntosuchchoicepointsandtryalternativeactionoperatorstoachievethegoals.

Addingmoreactionstotheplanrequirestheplannertochooseoneofthegoals(whosecollapsewasunsuccessfullyattempted),applyactionintroductionandcontinueplanning.Currently,theplannerselectsagoalnon-deterministicallybycreatingachoice-pointongoalselection.

TheenhancedversionofparcPLANusesthedepthfirstiterativedeepening(DFID)searchstrategydescribedin[7],toexplorealltheoptionsavailable.Thedepthcutoffvalue,inourcase,isthenumberofactionsintroducedforaplan.Thus,theplannerwillsearchforallpossibleplanswithagivennumberofactionsfirst,andonlyifnoneoftheseplansisvalid,thecutoffvaluewillbeincrementedbyone;planningwillstartagain,thistimelookingforplanswithoneextraaction.

arm1

b t1 t3c a t1b t3 ca t2 b1

2

3

4

5

6

7

8

9

10

11

12

13

Figure10.Asolutionusing1armfortheprobleminfigure1

Fortheplanningproblemspecifiedinfigure1,planningforasinglerobotarmwouldfindallpossibleplanswith3actionsinconsistentduetofailureinresourcereasoning.Thereforethecutoffvaluewouldbeincreasedbyone,andplanningwillstartagain,thistimelookingforaplanwith4actions.Thistimeoneoftheseplans(seefigure10)isfoundtohaveascheduleofactionsexecutablebyasinglerobotarm.

Researchisnowfocusedonreducingthebranchingfactorongoalselectionbyanalysingfailureintemporalplanningandextractingthesetofconflictinggoals.

4.2UtilisingDecompositionMethod

In[3]anefficienttechniqueisdevelopedfortemporalreasoningdur-ingcollapsingthroughastrategyofconstructingdecomposedcon-straintnetworks.Thedecompositionstrategyusesanotionofincom-patibilityconnection,whichreferstoamaximalsubgraphconnectedthroughincompatibilityrelations(e.g.,domainrules)specifiedintheplanningdomain.Sincethecollapsingtaskisbasicallytheproblemofdeterminingsatisfiabilityofatemporaldatabasequery(TDBQ),theproposedmethoddividesaTDBQsuchthatfactsandgoalsofincompatibleoridenticalpropertytypesbelongtothesameparti-tion.Temporalconstraintsareclusteredaccordingtothesepartitions.Then,collapsingcanproceedbyfirstdecomposingaTDBQintonearly-independentsub-TDBQ’s,checkingeachofthemlocally,thentestingglobalconsistencyofthelocalresults.Topreservethecorrect-ness,thestrategyimposessomerestrictionsontemporalspecificationofactionoperatorsandplanningproblems.

Thismethodenhancestheperformanceofconstraintsolving,(1)bycontrollingthecombinatoricsoftemporalconstraintnetworks,and(2)byreducingthesizeoftemporalconstraintnetworksinvolved.Thedecompositionstrategyprovidesthebasisforreducingthenumberofactualnetworkstosolvebya“first-fail”principle.Ifasubnetworkisfoundunsatisfiable,forinstance,wecanimmediatelyconcludethatthenetworkisunsatisfiableregardlessoftheremainingsubnetworks.Theproposedmethodutilisesanumberof“smaller”networksinsteadofsolvingaglobalnetwork.Asaresult,constraintpropagationwasconcentratedmostlyonthepartsofanetworkthatarerelevanttoproblemsolving.Unnecessarypropagationofconstraintsisreducedandperformanceofcollapsingisenhanced.

Thedecompositionmethodprovidesanewpossibilitytowardstheproblemofrecoveringfromfailuresdescribedinthispaper.Sincecollapsingisperformedthroughdecomposedsubproblems,whenafailureoccursthereisabetterchancetoselectrightgoalsbynarrow-ingdowntheproblematicregionsatleast.Withoutsuchamethod,allpendinggoalsareequallyplausibletobechosenbecausetheprob-lematicregioncannotbeidentifiedeasily.Choosingawronggoalmayresultinintroducingredundantactionsandmakingproblemsolvingmoredifficult.Thedecompositionmethod,possiblywiththesupportofsomeheuristics,helpstheplannertoperformaglobalanalysisoverthefailedsituationandtodecidewhichlocalareastoresolveconflictsinanoptimalway.Thus,theadvantagesgainedbyanalysingconflictresolutioninaglobalmannerstudiedby[9]canbeentertainedsimilarlyinourframework.

5Conclusion

InthispaperwehavepresentedthefailurerecoveryprobleminthecontextoftheparcPLANtemporalplanningarchitecture.Inpartic-ular,wehaveexaminedtwodifferenttypesoffailurewhichariseinourtemporalframework.

FailureFailureinincollapsing

schedulingwithavailableresources

Althoughitisalwayspossibletofindsolutionswhenabruteforcesearchstrategy(likedepthfirstiterativedeepening)isapplied,ex-ploringtheentiresearchspaceisimpracticalevenformediumsizeproblems.

Wearehopingthattechniqueslikethenetworkdecompositionmethodcanbeusedtoidentifytheproblematicgoalsandhelptomakemore“informed”decisionsonwhichgoalsshouldberegardedasunachieved.

REFERENCES

[1]JamesF.AllenandJ.A.Koomen,‘Planningusingatemporalworld

model’,inProceedingsoftheEighthInternationalJointConferenceonArtificialIntelligence,IJCAI-83,pp.741–747,Karlsruhe,Germany,(1983).

[2]J.F.Allen,H.A.Kautz,R.N.Pelavin,andJ.D.Tenenberg,Reasoning

aboutPlans,MorganKaufmannPub.,1991.

[3]HoJinChoi,ControllingTemporalConstraintsinPlanning,Ph.D.dis-sertation,ImperialCollege,UniversityofLondon,1995.

[4]ThomasL.Dean,R.JamesFirby,andDavidMiller,‘Hierarchicalplan-ninginvolvingdeadlines,traveltimeandresources’,ComputationalIn-telligence,4(4),381–398,(1988).

[5]A.El-KholyandB.Richards,‘TemporalandResourcereasoningin

Planning:thePLANapproach’,inProceedingsofthe12thEuropeanConferenceonArtificialIntelligene,pp.614–618.JohnWileyandSons,Ltd.,(1996).

[6]J.C.Hogge,‘TPLAN:Atemporalinterval-basedplannerwithnovelex-tensions’,TechnicalReportUIUCDCS-R-87-1367,Dept.ofComputerScience,UniversityofIllinoisatUrbana-Champaign,(1987).

[7]R.E.Korf,‘Depth-firstiterative-deepening:Anoptimaladmissibletree

search’,ArtificialIntelligence,27,97–109,(1985).

[8]J.M.LeverandB.Richards,‘

PLAN:aplanningarchitecturewithparallelactions,resourcesandconstraints’,inProceedingsofthe9thInternationalSymposiumonMethodologiesforIntelligentSystems,pp.213–222,(1994).

[9]Q.Yang,‘Atheoryofconflictresolutioninplanning’,ArtificialIntelli-gence,58,361–392,(1992).