一种冲突导向的基于模型的自治方法

Graph-basedPlanningBrianC.Williams

Sept.25th&30th,200216.412J/6.834JOutlineIntroductionTheGraphPlanPlanningProblemGraphConstructionSolutionExtractionPropertiesTerminationwithFailureGraphPlanGraphplanwasdevelopedin1995byAvrimBlumandMerrickFurst,atCMU.RecentimplementationsbyotherresearchershaveextendedthecapabilityofGraphplantoreasonwithtemporallyextendedactions,metricsandnon-atomicpreconditionsandeffects.Approach:GraphPlanConstructscompactencodingofstatespacefromoperatorsandinitialstate,whichprunesmanyinvalidplans–PlanGraph.Generatesplanbysearchingforaconsistentsubgraphthatachievesthegoals.PropositionInitStateActionTime1PropositionTime1ActionTime2PlangraphsfocustowardsvalidplansPlangraphsexcludemanyplansthatareinfeasible.Plansthatdonotsatisfytheinitialorgoalstate.Planswithoperatorsthatthreateneachother.Plangraphsareconstructedinpolynomialtimeandareofpolynomialinsize.Theplangraphdoesnoteliminateallinfeasibleplans.Plangenerationstillrequiresfocusedsearch.Example:GraphandSolutionnoGarbcleanHquietdinnerpresentcarrydollycookwrapcarrydollycookwrap

cleanHquiet

noGarbcleanHquietdinnerpresent1Prop1Action2Prop2Action3PropOutlineIntroductionTheGraphPlanPlanningProblemGraphConstructionSolutionExtractionPropertiesTerminationwithfailure8GraphPlanPlanningProblemStateAconsistentconjunctionofpropositions(positiveliterals)E.g.,(and(cleanhands)(quiet)(dinner)(present)(noGarbage))Doesn’tcommittothetruthofallpropositionsInitialStateProblemstateattimei=0E.g.,(and(cleanHands)(quiet))GoalStateApartialstate,representedbyaconjunctionofliterals.E.g.,(and(noGarbage)(dinner)(present))Theplannermustputthesysteminafinalstatethatsatisfiestheconjunction.9GraphPlanPlanningProblemActionsE.g.,(:operatorcarry

:precondition

:effect(:and(noGarbage)(not(cleanHands)))Preconditions:propositionsthatmustbetruetoapplyoperator.Aconjunctionofpropositions(nonegatedpropositions).Effects:Propositionsthatoperatorchanges,givenpreconditions.Aconjunctionofpropositions(adds)andtheirnegation(deletes).carrynoGarb

cleanHParameterizedschemasandobjectsareusedtocompactlyencodeactions.AddEdgeDeleteEdge10GraphPlanPlanningProblem(:operatorcook :precondition(cleanHands)

:effect(dinner))(:operatorcarry:precondition

:effect(:and(noGarbage)(not(cleanHands)))ActionExecutionattimei:Ifallpropositionsof:preconditionappearinthestateati,Thenstateati+1iscreatedfromstateati,byaddingtoi,all“add”propositionsin:effects,removingfromi,all“delete”propositionsin:effects.carrynoGarb

cleanHcookdinnercleanHands11GraphPlanPlanningProblemNoopsEverypropositionhasano-opaction,

whichmaintainsitfromtimeitoi+1.E.g.,(:operatornoop-P:precondition(P):effect(P))Noop-PPPExample:DinnerDateProblemInitialConditions:(and(cleanHands)(quiet))Goal: (and(noGarbage)(dinner)(present))Actions: (:operatorcarry:precondition

:effect(and(noGarbage)(not(cleanHands))) (:operatordolly:precondition

:effect(and(noGarbage)(not(quiet))) (:operatorcook:precondition(cleanHands)

:effect(dinner)) (:operatorwrap:precondition(quiet)

:effect(present)) +noops

dinnerpresentcookwrapcarry

cleanHquietnoGarbcleanH

dinnerpresentPropat1Actionat1Propat2Actionat2Propat2noop-dinnernoop-presentSetsofconcurrentactionsperformedateachtime[i]Usesmodelofconcurrencyasinterleaving.Ifactionsaandboccurattimei,thenitmustbevalidto

performeitherafollowedbyb,ORbfollowedbya.APlaninGraphPlan<Actions[i]>ACompleteConsistentPlanGiventhattheinitialstateholdsattime0,aplanisasolutioniff:Complete:Thepreconditionsofeveryoperatorattimei,

issatisfiedbyapropositionattimei.Thegoalpropositionsallholdinthefinalstate.Consistent:Theoperatorsatanytimeicanbeexecutedinanyorder,

withoutoneoftheseoperatorsundoingthe:preconditionsofanotheroperatorattimei.effectsofanotheroperatorattimei.

dinnerpresentcookwrapcarry

cleanHquiet

noGarbcleanH

dinnerpresentPropat1Actionat1Propat2Actionat2Propat3(noopdinner)(nooppresent)Exampleofa

CompleteConsistentPlanInitialConditions:(and(cleanHands)(quiet))Goal: (and(noGarbage)(dinner)(present))GraphPlanAlgorithmPhase1–PlanGraphExpansionCreatesgraphencodingpairwiseconsistencyandreachabilityofactionsandpropositionsfrominitialstate.Graphincludes,asasubset,allplansthatarecompleteandconsistent.Phase2-SolutionExtractionGraphtreatedasakindofconstraintsatisfactionproblem(CSP).Selectswhetherornottoperformeachactionateachtimepoint,byassigningCSPvariablesandtestingconsistency.OutlineIntroductionThePlanningProblemGraphConstructionSolutionExtractionPropertiesTerminationwithfailureGraphPropertiesAPlangraphcompactlyencodesthespaceofconsistentplans,whilepruning...partialstatesandactionsateachtimei

thatarenotreachablefromtheinitialstate.pairsofactionsandpropositions

thataremutuallyinconsistentattimei.plansthatcannotreachthegoals.Constructingtheplanninggraph…(Reachability)InitialpropositionlayerContainspropositionsininitialstate.Example:InitialState,Layer0

cleanHquiet

1Prop1Action2Prop2Action3PropConstructingtheplanninggraph…(Reachability)InitialpropositionlayerContainspropositionsininitialstateActionlayeriIfallaction’spreconditionsareconsistentini-1ThenaddactiontolayeriPropositionlayeri+1ForeachactionatlayeriAddallitseffectsatlayeri+1Example:AddActionsandEffectsnoGarbcleanHquietdinnerpresentcarrydollycookwrap

cleanHquiet

1Prop1Action2Prop2Action3PropConstructingtheplanninggraph…(Reachability)InitialpropositionlayerWritedownjusttheinitialconditionsActionlayeriIfallaction’spreconditionsappearconsistentini-1ThenaddactiontolayeriPropositionlayeri+1ForeachactionatlayeriAddallitseffectsatlayeri+1RepeatuntilallgoalpropositionsappearCanasolutionexist?noGarbcleanHquietdinnerpresentcarrydollycookwrap

cleanHquiet

1Prop1Action2Prop2Action3PropDoallgoalpropositionsappear?Constructingtheplanninggraph…(Consistency)InitialpropositionlayerWritedownjusttheinitialconditionsActionlayeriIfaction’spreconditionsappearconsistentini-1(non-mutex)ThenaddactiontolayeriPropositionlayeri+1ForeachactionatlayeriAddallitseffectsatlayeri+1IdentifymutualexclusionsActionsinlayeriPropositionsinlayeri+1Repeatuntilallgoalpropositionsappearnon-mutex26MutualExclusion:ActionsActionsA,Baremutually

exclusiveatleveli

ifnovalidplancouldpossiblycontainbothati:TheyInterfereAdeletesB’spreconditions,orAdeletesB’seffects,orViceversaorOR....Whatcausestheexclusion?noGarbcleanHquietdinnerpresentcarrydollycookwrap

cleanHquiet

1Prop1Action2Prop2Action3PropnoGarbcleanHquietdinnerpresentcarrydollycookwrap

cleanHquiet

Whatcausestheexclusion?1Prop1Action2Prop2Action3PropnoGarbcleanHquietdinnerpresentcarrydollycookwrap

cleanHquiet

Whatcausestheexclusion?1Prop1Action2Prop2Action3PropnoGarbcleanHquietdinnerpresentcarrydollycookwrap

cleanHquiet

Whatcausestheexclusion?1Prop1Action2Prop2Action3Prop31MutualExclusion:ActionsActionsA,Baremutually

exclusiveatleveli

ifnovalidplancouldpossiblycontainbothati:TheyInterfereAdeletesB’spreconditions,orAdeletesB’seffects,orViceversaorTheyhavecompetingneeds:A&BhaveinconsistentpreconditionsLayer0:completeactionmutexsnoGarbcleanHquietdinnerpresentcarrydollycookwrap

cleanHquiet

1Prop1Action2Prop2Action3Prop33MutualExclusion:PropositionLayerPropositionsP,QareinconsistentatiifnovalidplancouldpossiblycontainbothatiIfati,allwaystoachievePexcludeallwaystoachieveQPQA1A2MNLayer1:addpropositionmutexsnoGarbcleanHquietdinnerpresentcarrydollycookwrap

cleanHquiet

1Prop1Action2Prop2Action3PropNone!Canasolutionexist?noGarbcleanHquietdinnerpresentcarrydollycookwrap

cleanHquiet

1Prop1Action2Prop2Action3PropDoallgoalpropositionsappearnon-mutex?OutlineIntroductionThePlanningProblemGraphConstructionSolutionExtractionPropertiesTerminationwithfailure37GraphplanCreateplangraphlevel1frominitialstateLoopIfgoal

propositionsofthehighestlevel(nonmutex)ThensearchgraphforsolutionIfsolutionfound,thenreturnandterminateElseextendgraphonemorelevelAkindofdoublesearch:forwarddirectionchecksnecessary(butinsufficient)conditionsforasolution,...Backwardsearchverifies...38SearchingforaSolutionRecursivelyfindconsistentactionsachievingallgoalsatt,t-1,...:ForeachgoalpropositionGattimetForeachactionAmakingGtrueattIfAisn’tmutexwithpreviouslychosenactionatt,ThenselectitFinally,IfnoactionofGworks,ThenbacktrackonpreviousG.FinallyIfactionfoundforeachgoalattimet,Thenrecurseonpreconditionsofactionsselected,t-1,Elsebacktrack.Searchingforasolution

noGarb

cleanHquietdinnerpresentcarrydollycookwrap

cleanHquiet

1Prop1Action2Prop2Action3PropSelectactionachievingGoalnoGarbSearchingforasolution

noGarb

cleanHquiet

dinnerpresentcarrydollycookwrap

cleanHquiet

1Prop1Action2Prop2Action3PropSelectactionachievingGoaldinner,ConsistentwithcarryBacktrack

onnoGarbSearchingforasolution

noGarbcleanH

quietdinnerpresentcarrydollycookwrap

cleanHquiet

1Prop1Action2Prop2Action3PropSelectactiondollyBacktrack

onnoGarbSearchingforasolution

noGarbcleanH

quiet

dinnerpresentcarrydollycookwrap

cleanHquiet

1Prop1Action2Prop2Action3PropSelectactionachievingGoaldinner,ConsistentwithdollySearchingforasolution

noGarbcleanH

quiet

dinner

presentcarrydollycookwrap

cleanH

quiet

1Prop1Action2Prop2Action3PropSelectactionachievingGoalpresent,Consistentwdolly,cookSearchingforasolution

noGarbcleanH

quiet

dinner

presentcarrydollycookwrap

cleanH

quiet

1Prop1Action2Prop2Action3PropRecurseonpreconditionsofdolly,cook&wrapAllsatisfiedbyinitialstateAvoidingredundancyNo-opsarealwaysfavoured.guaranteesthattheplanwillnotcontainredundantactions.SupposethePlanGraphwasExtendednoGarbcleanHquietdinnerpresentcarrydollycookwrapcarrydollycookwrap

cleanHquiet

noGarbcleanHquietdinnerpresent1Prop1Action2Prop2Action3PropCanavalidplanusecarry?noGarbcleanHquietdinnerpresentcarrydollycookwrapcarrydollycookwrap

cleanHquiet

noGarbcleanHquietdinnerpresent1Prop1Action2Prop2Action3PropUsingcarryatlevel2isvalidnoGarbcleanHquiet

dinner

presentcarrydollycookwrapcarrydollycookwrap

cleanHquiet

noGarbcleanHquiet

dinner

present1Prop1Action2Prop2Action3PropUsingcarryatlevel2isvalidnoGarbcleanHquiet

dinner

presentcarrydollycookwrapcarrydollycookwrap

cleanH

quiet

noGarbcleanHquiet

dinner

present1Prop1Action2Prop2Action3PropOutlineIntroductionThePlanningProblemGraphConstructionSolutionExtractionPropertiesTerminationwithfailurePlanGraphPropertiesPropositionsmonotonicallyincreaseoncetheyareaddedtoalayertheyareneverremovedinsuccessivelayers;Mutexesmonotonicallydecreaseonceamutexhasdecayeditcanneverreappear;Memoizedsets(tobediscussed)monotonicallydecreaseifagoalsetisachievableatalayer

Thenitwillbeachievableatallsuccessivelayers.Thegraphwilleventuallyreachafixpoint,thatis,

alevelwherefactsandmutexesnolongerchange.FixpointExample:

DoorDomainABFixpointExample:

DoorDomainMovefromroomAtoroomBpre:robotisinAandthedoorisopenadd:robotisinBdel:robotisinAOpendoorpre:doorisclosedadd:doorisopendel:doorisclosedClosedoorpre:doorisopenadd:dooriscloseddel:doorisopennoopnoopMoveMoveOpennoopClosenoopIn(B)In(A)ClosedOpenedLayer4NMoveMoveOpenIn(A)ClosedLayer1OpennoopnoopIn(A)ClosedOpenedLayer2In(B)noopnoopMoveOpennoopCloseIn(A)ClosedOpenedLayer3Layer4isthefixedpoint(calledlevelout)ofthegraphGraphSearchPropertiesGraphplanmayneedtoexpandwellbeyondthefixpointtofindasolution.Why?GripperExampleMovefromoneroomtoanotherpre:robotinthefirstroomadd:robotinthesecondroomdel:robotinthefirstroomPickaballupinagripperpre:robothasafreegripperandisinsameroomasballadd:robotholdingtheballdel:gripperfree,ballinroom.Dropaballinaroompre:robotholdingtheball,robotindestinationroomadd:ballindestinationroom,gripperfree.del:ballbeingheld.GripperExampleInGripper,thefixpointoccursatlayer4,allfactsconcerningthelocationsoftheballsandtherobotarepairwisenon-mutexafter4steps.Thedistancetothesolutionlayerdependsonthenumberofballstobemoved.ForlargenumbersofballsGraphplansearchescopiesofthesamelayersrepeatedly.Forexample,for30ballsthesolutionlayerisatlayer59,54layerscontainidenticalfacts,actionsandmutexes.SearchProperties(cont)Plansdonotcontainredundantsteps.BypreferringNo-opsGraphplanguaranteesparalleloptimality.Theplanwilltakeasshortatimeaspossible.Graphplandoesn’tguaranteesequentialoptimalityMightbepossibletoachieveallgoalsatsomelayerwithfeweractionsatthatlayer.Graphplanreturnsfailureifandonlyifnoplanexists.OutlineIntroductionThePlanningProblemGraphConstructionSolutionExtractionPropertiesTerminationwithfailureSimpleTerminationIfthefixpointisreachedandeither:OneofthegoalsisnotassertedorTwoofthegoalsaremutexThenGraphplancanreturn"Nosolution"withoutanysearchatall.ElsetheremaybehigherorderexclusionswhichGraphplancannotdetectRequiresmoresophisticatedadditionaltestfortermination.WhyContinueAfterthe

FixPoint?facts,actionsandmutexesnolonger

changeafterthefixpoint,N-aryexclusionsDOchange.Newlayersaddtimetothegraph.TimeallowsactionstobespacedsothatN-arymutexeshavetimetodecay.Whilenewthingscanhappenbetweentwosuccessivelayersprogressisbeingmade.Trackn-arymutexes.Terminateontheirfixpoint.MemoizationandTerminationAgoalsetatalayermaybeunsolvableExample,inGripper.Ifagoalsetatlayerkcannotbeachieved,

Thenthatsetismemoizedatlayerk.TopreventwastedsearcheffortCheckseachnewgoalsetatkagainstmemosofkforinfeasibility.Ifanadditionallayerisbuiltandsearchingitcreatesnonewmemos,thentheproblemisunsolvable.Recap:GraphPlanGraphplanwasdevelopedin1995byAvrimBlumandMerrickFurst,atCMU.Graphplansearchesacompactencodingofthestatespacefromtheoperatorsandinitialstate,whichprunesmanyinvalidplans,viola