Artificial Intelligence—15-381Real-Time AI: What is it?Real-Time AI: What is it?The SMOKEY SystemKnowledge Sources for SMOKEYAgenda-Based ControlSlide 7Agenda-Based Control- Individual Task-Execution MethodAgenda-Based Control Task Selection MethodsAnytime PlanningAnytime PlanningArtificial Intelligence—15-381Real-Time AI SystemsJaime Carbonell20-November-2001OUTLINE-What exactly is "Real Time"?-Real-Time Planning-Agenda-Control Methods-A Case Study of RT Rule-Based AIReal-Time AI: What is it?Possible Operational DefinitionsAI system that runs very efficientlyAve. Decision-cycle (AI) < Ave. Action-cycle (World)MAX Decision-cycle (AI) < MIN Action-cycle (World)Forall(xEvents)[time(d(x),AI) + time(a(x), AI) < time(a(x),W)]Forall(x E Exists(y) DC Exists(z) AC[time(y(x)) + time(z(y(x))) < time(a(x),W)] Note: Above is 2nd-order logic expressionReal-Time AI: What is it?Need for Real-Time AIRobotic applications (most kinds)Autonomous driving (no-hands across America)Sensor-based warning/action systems (Smokey)Self-repairing telephone or electric networksATM or Credit-card fraud detectionThe SMOKEY SystemTask DefinitionSensor-based location, prediction, control of onboard fires in aircraft carriers.Sensors: smoke, heat chemical analysisKnowledge: sensor topology, ship map, location of flammables, type of flammables,…Actions: evacuate and/or seal-off section, equip and send firefighters, sprinkler on/off flood compartments, all-clear,…ObjectivesReal-time reactionBetter performance than humansRobust behavior (e.g. function correctly with burnt sensors)Knowledge Sources for SMOKEYStaticShip topology (graph data structure)Ventilation System topologySensor system topologySensor system types (smoke, heat, chemical)Flammable materials (paint, paper, fuel, electrical, insulation, munitions,…)Fire suppressants (water, O2-denial gas/foam,…)DynamicLocation of crew membersLocation of fire-control team(s)Settings of hatches (open, closed, locked)Settings of ventilation system (air flow)Agenda-Based ControlAgenda Data StructureLevel-1: T1,1, T1,2, …, T1,jLevel-2: T2,1, T2,2, …, T2,k...Level-n: Tn,1, Tn,2, …, Tn,m..Agenda-Based ControlFields in each Ti,jName Domain RangeTRIGGER:DYNAMIC:pat X WM X Apat X WM X sen{F, T(bindings)}{F, T(bindings)}WM-UPDATE:A-UPDATE+:A-UPDATE-:A-FLUSH:WM X bindingsA X bindingsA X bindingsBindingsWMAAAACT: Bindings(X sen X WM) WorldAgenda-Based Control- Individual Task-Execution MethodIf Active (Ti.j, A)& Match (Ti,j.TRIGGER, WM)& Match (Ti,j.DYNAMIC, WM, f(sensors))THEN Execute (Ti.j.ACT, bindings)& Update (Ti,j.WM, WM, binding)& Add (Ti.j.A-UPDATE+, A)& Delete (Ti,j.A-UPDATE-, A)ELSE-IF Match (Ti,j.A-FLUSH, A)THEN Delete (Ti,j.ID, A)Note: Ti,j.A-UPDATE+ := (<bindings.level, bindings.task>…)Agenda-Based Control Task Selection MethodsOther Agenda DisciplinesLinear order with interruptsDeclining time guarantees per level (e.g. min of 50% for L1, 25% L2, 12% L3,…)And more…N-Level Priority-Queue Fail(Ti,j) > Ti,j+1 Succ(Ti,j) > Ti,1 j+1 > jmax > Ti+1,1 i+1 > imax > T1,1Global Priority-Queue Fail(Ti,j) > Ti,j+1 Succ(Ti,j) & t < tthreshold > Ti,1 Succ(Ti,j) & t > tthreshold > T1,1 j+1 > jmax > Ti+1,1 i+1 > imax > T1,1Anytime PlanningDefinitions:Deliberative Planning—Think first (full plan of action), act later, without hard time constraintsbReactive "Planning"—No thinking, reflex-action only.Anytime Planning—Think exactly as long as external world permits, or you reach final conclusion (whichever comes first), but have always tentative answer ready. Deliberative planner with interrupts that always has a best-so-far plan.Probabilistic Planner—Accounts for uncertain consequences of actions and uncertain states of the world; can be part of probabilistic planer.Anytime PlanningPropertiesDeliberation potential for subgoaling, backtracking, weighing alternatives, but no time bounds.Reactivity potential for real-time but far-from-optimal behavior.Any-time [At least some of] both advantages.Anytime probabilistic planning Optimal, but difficult. Best robotic agents are anytime planners.Applications include Robo-Soccer (Veloso et
View Full Document
Unlocking...