HoneywellLaboratoriesGoalsandThreats:MotivationsinCIRCADavidJ.MuslinerHoneywellLaboratories(612)951-7599Stillworkingonmy(Michigan)thesistopic.13yearssincefirstCIRCApaper.PresentationOutlineCIRCAoverview:Motivatingdomains.Architecturalmodules.Representations,includingmotivationmechanisms.Automaticallyplanningreal-timereactiveplans.ProbabilisticCIRCA:Motivatingdomains.Representationchanges.Motivationchanges.Planningmethodschanges.LearninginCIRCAMotivatingDomainCharacteristicsTime-critical,hazardous,open-worlddomains:CIRCAguaranteesthatitwillrespondinatimelywaytothreatsinitsenvironment,avoidingfailuresandpursuinggoals.Requiresrobustnessbeyondhumanperformance.Boundedreactivity:CIRCAreasonsexplicitlyaboutthetimeneededforsensingandactions(“perceptual-motorlimits〞).Boundedrationality:CIRCAdynamicallybuildsreactiveplansforonlytheimmediatelyrelevantpartsofthesituation.CIRCAisself-aware,usingmeta-leveldeliberationschedulingtooptimizeitsonlineplanningprocess.Multi-AgentSelf-AdaptiveCIRCAApproach:Automaticsynthesisandadaptationofguaranteedreal-timecontrollers.Performance:Reactivecontrolresponsestothreatsandcontingenciesinmilliseconds.Coordinatedmulti-agentbehaviorsintensofmilliseconds.Dynamicreconfigurationofteammissionplaninlessthan10seconds.DemonstrationsinsimulatedUAVteamdomains:coordinateddefense,dynamicreplanningforcontingencies.Impact:RobustUAVsthatrebuildtheirowncontrolsystemsinresponsetocontingencies(e.g.,damage,targetofopportunity).SmartUAVteamsthatactivelycoordinatedistributedcapabilities/resourcestomaximizemissioneffectiveness.Sponsor:DARPAANTS.Teammate:Univ.ofMichiganGoal:Adaptivereal-timecoordinationandcontrolofmulti-UAVteams.IntelligentReal-TimeCyberSecurityApproach:UseCIRCAtoplanandexecutereactivesecuritycontrollers.Tailorresponsesautomaticallyaccordingtoavailableresources,varyingthreatlevels&securitypolicies.

Performance:Fullyautonomousoperationsdefeatingattacksinmicroseconds.Rapidreconfigurationfordynamicnetworkassets,securitystate,threatprofile.Demonstrationsinrealcomputernetworks.Impact:Real-timeresponsesdefeatmanualandautomatedattackscripts.Automatictradeoffsofsecurityvs.servicelevelandaccessibility.Systemderivesresponsesfornovelattacksbuiltfromknowncomponents.Sponsor:DARPACyberPanel.Teammate:SecureComputingGoal:Automaticreal-timeresponsetocomputersecurityintrusions.ComputingservicesActiveSecurityControllerExecutiveControllerSynthesisModuleCIRCADIANetworks,ComputersAttacks,intrusionsIntrusionAssessmentSecurityTradeoffPlannerCIRCAArchitectureAdaptiveMissionPlanner:Dividesanoverallmissionintomultiplephases,withlimitedperformancegoalsdesignedtomaketheplanningproblemsolvablewithavailabletimeandavailableexecutionresources.Deliberationscheduling.ControllerSynthesisModule:Foreachmissionphase,plansasetofreal-timereactionsaccordingtotheconstraintssentfromAMP.Planning.RealTimeSubsystem:Continuouslyexecutesplannedcontrolreactionsinhardreal-timeenvironment;doesnot“pause〞waitingfornewplans.Execution.AdaptiveMissionPlannerControllerSynthesisModuleRealTimeSystemGeneratecontrollerHowCIRCAWorksAdaptiveMissionPlannerControllerSynthesisModuleRealTimeSystemBreakdownmissionGeneratecontrollerExecutecontrollerif(state-1)thenaction-1if(state-2)thenaction-2...GeneratecontrollerStartGoalExtendingPerformanceGuaranteestoMulti-AgentTeamsAdaptiveMissionPlanner:Negotiatesrolesandresponsibilitiesbetweenagentsincollaborativeteam.ControllerSynthesisModule:Buildscontrollersthatincludecoordinatedactionsbymultipleagents.RealTimeSubsystem:Executescoordinatedcontrollerspredictably,includingdistributedsensingandacting.Onlysystemtoguaranteetimingofend-to-endmulti-agentcoordinatedbehaviorsAdaptiveMissionPlannerControllerSynthesisModuleRealTimeSystemRoles,GoalsReal-TimeReactionsPlannedActions,PlannedNegotiationsAdaptiveMissionPlannerControllerSynthesisModuleRealTimeSystemRealTimeSubsystem(RTS)TheRTSexecutesloopsofTest-ActionPairs(TAPs).TheRTSexecutesinparallelwiththeotherCIRCAmodules.Parallelexecutionpermitsre-planningusingcomputationally-expensivealgorithmswhilepreservingplatformsafety.Special-purposeTAPsusedtodownloadandswitchtonextcontroller.RTSincludesmultipleTAPschedulecachestoholdcontrollersbeforetheyareactivated.ExampleTAP:If(radar-missile-trackingT)thenbegin-evasiveswithmax-delay:300msec.action1action2action1action3action1test1test2test1test3test1test4action4Availableactions“Non-volitional〞transitionsGoalstatedescriptionInitialstatedescriptionTimedAutomataWorldModel&ExecutableReactiveControllerPlanningReal-TimeReactionsTransition-basedinputmodelsimilartoclassicalplanners,butwithtemporalcharacteristicsandnon-volitionaltransitions.TAPCompilerSchedulerStateSpacePlannerVerifierCSMCSMFunctionalComponentsStateSpacePlannerpredictsfuturethreatsandopportunities,plansactionswithtimingconstraintsforfuturestates.Verifierreasonsaboutcomplextemporalmodeltoensurethatallfailuresarepreempted.TAPcompilerreducestimedautomatacontrollermodeltotime-constrainedreactions(Test-ActionPairs).SchedulerbuildsexecutablecycleofTAPstomeettimeconstraints.ControllerSynthesisModuleTAPCompilerSchedulerStateSpacePlannerVerifierCSMAlgorithmCSMessentiallydeterminesastrategyinatimedgameagainstaworst-caseadversary.

Searchloopiterativelyselectsastateandchoosesactionforthatstate.Heuristicsguidechoiceforsafetyandgoalachievement.Approximationsindicatethattimingwillwork.Formalreachabilityanalysiscalledaftereachactionchoice,toconfirmthatallplannedpreemptionswilloccur.Iffailurereachable,pathtofailurecanbeusedtobackjumptomostrecentdecisionrelatedtoanystateonthepath.CIRCAMotivations:ThreatsThreatsrepresentedbytemporaltransitionstofailure(TTFs).CSMonlyreturnsplansthatmakefailureunreachable,using:Prevention:plannedactionsneverallowTTFpreconditionstobecometrue.Preemption:plannedactionswilldefinitelyhappenbeforeTTFs.OKThreatenedFailureSafeRadarThreatDomain-1;;Radar-guidedmissilethreatscanoccuratanytime.(make-instance'event:name"radar_threat":preconds'((radar_missile_trackingF)):postconds'((radar_missile_trackingT)));;Youdieifdon'tdefeatathreatby1200timeunits.(make-instance'temporal:name"radar_threat_kills_you":preconds'((radar_missile_trackingT)):postconds'((failureT)):min-delay1200)RadarThreatDomain-2;;Ittakesnomorethan10timeunitstostartevasives.(make-instance'action:name"begin_evasive":preconds'((pathnormal)):postconds'((pathevasive)):max-delay10);;Wedefeatmissileinbetween250and400timeunits.(make-instance'reliable-temporal:name"evade_radar_missile":preconds'((radar_missile_trackingT)(pathevasive)):postconds'((radar_missile_trackingF)):delay(make-range250400))FAILURERadar-threat-kills-youRadar-missile-trackingTPathnormalRadarThreatKeyConcept:PreventFailurePreemptionasKeyPlanningStructureRadar-missile-trackingFPathnormalBegin-evasiveRadar-missile-trackingTPathevasivepreemptionFAILURERadar-threat-kills-youRadar-missile-trackingTPathnormalRadarThreatNon-MarkovTemporalModelRadar-missile-trackingFPathnormalBegin-evasiveRadar-missile-trackingTPathevasiveRadar-threat-kills-youEvade-radar-missileRadar-missile-trackingFPathevasiveWhynon-Markov?Efficientreactiveplanconstruction.CIRCAMotivations:GoalsRepresentedbydesignationofspecificdesirablefeature/valuepairs.CSMheuristicguidessystemtochooseactionsthattrytoachieve(andre-achieve)maximumnumberofgoalfeatures.Allgoalsare:Conjunctive.Optional.RadarThreatDomain-3;;Yourgoalistocontinueflyingnormalpath.(make-instance‘goal:condition'((pathnormal)))Optionalelementsfordifferentplanners::reward:priorityFAILURERadar-threat-kills-youRadar-missile-trackingTPathnormalRadarThreatGoalsDriveStabilizationRadar-missile-trackingFPathnormalBegin-evasiveRadar-missile-trackingTPathevasiveRadar-threat-kills-youEvade-radar-missileRadar-missile-trackingFPathevasiveRadar-missile-trackingFPathnormalEnd-evasiveDynamicAbstractionPlanningStartwithabstractstatesomittingallnon-goalfeatures.Incrementallyandnon-uniformlyaddfeaturestostateswhenrequired:Whennosafeactionsareapplicable.Whengoalachievementheuristicindicates.Result:plannerdecideswhatitneedstothinkabout,when.Futuredirection:usethistoguidewhatyouattendtoforlearning.non-failurefailureRadar-threat-kills-younon-failurePathnormalPathevasivefailureRadar-threat-kills-youAMPResponsibilitiesDividemissionintophases,subdividingthemasnecessarytohandleresourcerestrictions.NegotiatewithotherAMPstoallocategoalsandthreatsineachphase.Buildproblemconfigurationsforeachphase,todriveCSM.Modifyproblemconfigurations,bothinternallyandvianegotiationwithotherAMPs,tohandleresourcelimitations.Tasksrepresent:Contractstohandlethreatsandgoals.Needtoannounce,bid,award,andplanforthem.Needtogenerateplanforaproblemconfiguration.NeedtodownloadplanforaconfigurationtotheRTS.OneachAMPdecisioncycle,selectandexecutehighest-prioritytask.Newcapability:deliberationscheduling.Estimatecosts/benefitsofdifferenttasks:tieprioritytoutility.NegotiatedAllocationofMissionGoalsAdaptiveMissionPlannersnegotiatetodistribute:Long-termmissiongoals.Roles:predefineresponsibilities/concernsascontextfornegotiation.Performanceevaluationresponsibilities.EnhancedContract-Netstylenegotiation.Adaptivity/dynamics.AMPDeliberationSchedulingMissionphasescharacterizedby:Probabilityofsurvival/failure.Expectedreward. Expectedstarttimeandduration.Agentkeepsrewardfromallexecutedphases.DifferentCSMproblemconfigurationoperatorsyielddifferenttypesofplanimprovements.Improveprobabilityofsurvival.Improveexpectedreward(numberorlikelihoodofgoals).Configurationoperatorscanbeappliedtosamephaseindifferentways(viaparameters).Configurationoperatorshavedifferentexpectedresourcerequirements(computationtime/space).ExtensibleCIRCAArchitectureWell-definedAPIforeachCIRCAmoduleandcomponentswithinmodules.Eg:CSM:problemspecification,algorithmcontrolsin,reactiveplansandplanningprocessmonitoringout.Well-definedAPIforcomponentswithinmodules.Eg:APIforstate-spaceplannerinteractionwithverifier:Statespacemodelintoverifier.Safetyassessmentplusoptionalculpritstatetraceoutfromverifier.Hasallowedustoplugindifferentplannersandverifiersfordifferentdomainrepresentationsandverifierapproaches:Timedautomata:Kronos,RTA,CSV,RTA-incremental,CSV-incremental;DAP,pDAP,regularplanners.Safety-orientedGeneralizedsemi-Markov:MonteCarlosampler.Maximizingexpectedutility:MCsampler;evolutionaryreaction-spacesearchengine.Differentexecutives:RTS,CLIPS.MemoryandModelsinCIRCAAdaptiveMissionPlannerControllerSynthesisModuleRealTimeSystemMissionmodel:phaseswiththreats&goals.Mappingsfromthreats/goalstopartialCSMinputmodels(setsoftransitions).CSMperformanceprofiles.TransitionmodelsfromAMP.TimingmodelofRTS.CachedTAPcontrollers.Currentlysensedstatefeatures.ProbabilisticReactivePlanningAddtransitionprobabilitiestostatemodel.Worldtransitionsandcontrolledactions.Samplesimulatedexecutionsofthecurrentplantoestimateprobabilityofreachingdifferentstates.Buildplansthathandlemost-probablestates.AllowsCIRCAtotradeoffplanningtimeandplancomplexityagainstsystemsafety.AllowsCIRCAtooptimizeexpectedutilityofplans,tradingoffsafetyagainstmissionobjectives(goals,rewardmodel).ProbabilisticWorldModelDynamicsTheworldmodelisageneralizedsemi-Markovprocess(GSMP).Theworldoccupiesasinglestateatanypointintime.Enabledtransitionsinthecurrentstatecompetetotrigger.Onetransitiontriggersineachstate,determiningthenextstate.Non-Markovianbecausetriggerdistributionsdependonholdingtimes.TherearenoanalyticsolutionsforunrestrictedGSMPs.Mustuseasampling-basedapproachtoestimatestateprobabilities.Simpler:estimatewhetherfailureistoolikely.AcceptanceSamplingLetpFbethefailureprobabilityofaplan.Wanttospecifyfailurethresholdqsuchthat:PlanisacceptedifpF

￡

q.PlanisrejectedifpF

>

q.Useacceptancesamplingtodecidewhethertoacceptaplan.Exhaustivesamplingisimpossible,sowemustexpecterrors:TypeIerror:rejectacceptableplan.TypeIIerror:acceptrejectableplan.Wanttoboundprobabilityoferror.SequentialSamplingSinglesamplingplanalwaysrequiresfixednumberofsamples.Sequentialsamplingplandecideswhethertogeneratemoresamplesbasedonsamplesseensofar.Defineacceptancenumberanandrejectionnumberrnatstagen.AcceptplanifobservedfailuresareatmostanRejectplanifobservedfailuresareatleastrnIntuitivesequentialsampling:Ifyou’vealreadyseencfailuresatanyiteration,thenreject(rn=c).Ifyoucannotpossiblyseecfailuresinremainingiterations,thenaccept(an=c+i-n-1).NumberofSamplesRequiredWaldacceptancesamplingrequiressignificantlyfewersamples.ActualfailureprobabilityStaticsamplingplanWaldsequentialsamplingplanthresholdPerformanceExpectednumberofrequiredsamplesonlydependsonfailureprobabilityandthreshold,notstatespacesize!Domain-dependentfactorsaffectingtimetogenerateeachsample:Timeperiodconsidered(tmax).MeanvaluesofthedistributionfunctionsF.Inpractice,thisallowsustogenerateprobabilistically-verifiedplansforverylargedomainsthatcannotbehandledbycomplete(non-probabilistic)model-checkingapproaches.OptimizingPlansinGSMPsAddingprobabilisticdelaydistributionstotimedautomatayieldsGeneralizedSemi-MarkovProcessmodel:Efficientforrepresentingrealworld.Noanalyticsolutionsavailable.Addingrewardmodelgivesopportunityfordecision-theoreticsolutioncriterion:maximizeexpectedutility.Approach:generateplansandassessEUdominanceusingMonteCarlosamplingofGSMPexecutions.Backjumpbasedonsampletraces.Newideas:localsearch;evolutionarysearchinreactionspace.LearninginCIRCA:NotAboutSpeedupUniquerequirementsonlearningformission-