Actions and events in interval temporal logic

ActionsandEventsinIntervalTemporalLogicJamesF.AllenGeorgeFergusonTheUniversityofRochesterComputerScienceDepartmentRochester,NewYork14627TechnicalReport521July1994AbstractWepresentarepresentationofeventsandactionbasedonintervaltemporallogicthatissignicantlymoreexpressiveandmorenaturalthanmostpreviousAIapproaches.Therepresentationismotivatedbyworkinnaturallanguagesemanticsanddiscourse,temporallogic,andAIplanningandplanrecognition.Theformalbasisoftherepresentationispre-sentedindetail,fromtheaxiomatizationoftimeperiodstotherelationshipbetweenactionsandeventsandtheireects.ThepoweroftherepresentationisillustratedbyapplyingittotheaxiomatizationandsolutionofseveralstandardproblemsfromtheAIliteratureonactionandchange.Anapproachtotheframeproblembasedonexplanationclosureisshowntobebothpowerfulandnaturalwhencombinedwithourrepresentationalframe-work.Wealsodiscussfeaturesofthelogicthatarebeyondthescopeofmanytraditionalrepresentations,anddescribeourapproachtodicultproblemssuchasexternaleventsandsimultaneousactions.ThismaterialisbaseduponworksupportedbytheNationalScienceFoundationunderGrantnum-berIRI-9003841.TheGovernmenthascertainrightsinthismaterial.ThisworkisalsosupportedbyONR/ARPAresearchgrantno.N00014-92-J-1512andAirForce{RomeAirDevelopmentCenterresearchcontractno.F30602-91-C-0010.ThisworkistoappearintheJournalofLogicandComputation,SpecialIssueonActionsandProcesses,1994.1IntroductionRepresentingandreasoningaboutthedynamicaspectsoftheworld|primarilyaboutac-tionsandevents|isaproblemofinteresttomanydierentdisciplines.InAI,weareinterestedinsuchproblemsforanumberofreasons,inparticulartomodelthereasoningofintelligentagentsastheyplantoactintheworld,andtoreasonaboutcausaleectsintheworld.Morespecically,ageneralrepresentationofactionsandeventshastosupportthefollowingsomewhatoverlappingtasks:Prediction:Givenadescriptionofascenario,includingactionsandevents,whatwill(orismostlikelyto)happen?Planning:Givenaninitialdescriptionoftheworldandadesiredgoal,ndacourseofactionthatwill(orismostlikelyto)achievethatgoal.Explanation:Givenasetofobservationsabouttheworld,ndthebestexplanationofthedata.Whentheobservationsareanotheragent’sactionsandtheexplanationdesiredistheagent’splan,andtheproblemiscalledplanrecognition.Ourclaiminthispaperisthatinordertoadequatelyrepresentactionsandevents,oneneedsanexplicittemporallogic,andthatapproacheswithweakertemporalmodels,suchasstatespaces(e.g.,STRIPS-basedapproaches)andthesituationcalculus,eithercannothandletheproblemsorrequiresuchdramaticextensionsthatoneineecthasgraftedanexplicittemporallogicontotheearlierformalism.Furthermore,ifoneoftheseformalismsisextendedinthisway,thetemporallogicpartwilldominateandtheoriginalformalismplayslittleroleinthesolution.Wewillprimarilydefendthispositionbyproposingaspecictemporalrepresentationandshowingthatitcanhandleawiderangeofsituationsthatareoftenproblematicforotherformalisms.Inparticular,herearesomeofpropertiesofactionsandeventsthatwefeelareessentialtoanygeneralrepresentation:1.Actionsandeventstaketime.Whilesomeeventsmaybeinstantaneous,mostoccuroveranintervaloftime.Duringthistime,theymayhavearichstructure.Forinstance,theeventofdrivingmycartoworkinvolvesawiderangeofdierentactions,statesoftheworldandothercomplications,yettheactivityoverthatstretchoftimecanbenicelydescribedasasingleevent.Becauseeventsareextendedintime,dierenteventsandactionsmayoverlapintimeandinteract.Thus,ifwhileIamdrivingtowork,arockpiercesthegastankandthegasolinedrainsout,Imayendupbeingstrandedonthehighwayratherthanarrivingatworkontime.Weshouldbeabletorepresentandreasonaboutsuchcomplexinteractions.2.Therelationshipbetweenactionsandeventsandtheireectsiscomplex.Someeectsbecometrueattheendoftheeventandremaintrueforsometimeaftertheevent.Forexample,whenIputabookonthetable,thishastheeectthatthebookisonthetableforatleastashorttimeaftertheactioniscompleted.Othereectsonlyholdwhiletheeventisinprogress.Forinstance,consideraashlightwithabuttonforashingit.Thelightisononlywhenthebuttonisbeingpresseddown.Finally,1othereectsmightstarttoholdsometimeaftertheeventhasstartedandstopholdingbeforeitnishes.Forexample,ifIamwalkingtoschoolalongmyusualroute,atsometimeduringthewalkIwillbeonthebridgecrossingtheriver.Thisisaneectoftheactioneventhoughitisnottrueattheendofit.3.Actionsandeventsmayinteractincomplexwayswhentheyoverlaporoccursimulta-neously.Insomecases,theywillinterferewithcertaineectsthatwouldariseiftheeventsweredoneinisolation.Inothercases,theeectofperformingthetwoactionsmaybecompletelydierentthattheeectsofeachinisolation.Asaradicalcaseofthis,considerawristwatchthatiscontrolledbytwobuttonsA,andB.PressingAchangesthemodeofthedisplay,whileBshowsthealarmtimesetting.PressingAandBsimultaneously,however,turnsthealarmonoro.Theeectofperformingtheactionssimultaneouslyhasnocausalrelationtotheeectsoftheactionsperformedinisolation.4.Externalchangesintheworldmayoccurnomatterwhatactionsanagentplanstodo,andmayinteractwiththeplannedactions.Possibleexternaleventsshouldbeanimportantfactorwhenreasoningaboutw