Transcript Strong Planning with Ordered Binary Decision Diagram (OBDD)

A Hierarchical Approach to
Model-based Reactive Planning
in Large State Spaces
Brian C. Williams
Joint with Seung H. Chung
Massachusetts Institute of Technology
Artificial Intelligence & Space Systems Laboratories
Outline
•
•
•
•
Model-based programming
A Simple model-based executive (Livingstone)
The need for model-based reactive planning
The Burton model-based reactive planner
Artificial Intelligence & Space Systems Laboratories
Massachusetts Institute of Technology
Polar Lander Leading Diagnosis:
• Legs deployed during descent.
• Noise spike on leg sensors
latched by software monitors.
• Laser altimeter registers 50ft.
• Begins polling leg monitors to
determine touch down.
• Latched noise spike read as
touchdown.
Mars Mission Failures, 2000:
•Climate Orbiter
•Polar Lander
• Engine shutdown at ~50ft.
Objective: Embedded languages that
reason from hardware models.
(Reactive Model-based Programming)
Artificial Intelligence & Space Systems Laboratories
Massachusetts Institute of Technology
Model-based Programs
Interact Directly with State
Embedded programs interact with
plant sensors and actuators:
Model-based programs
interact with plant state:
• Read sensors
• Read state
• Set actuators
• Write state
Model-based
Embedded Program
Embedded Program
Obs
Cntrl
S
Plant
Problem: Programmer must
must map between state and
sensors/actuators.
Artificial Intelligence & Space Systems Laboratories
S’
Model-based Executive
Obs
Cntrl
S
Plant
Solution: Model-based executive
maps between state and
sensors/actuators.
Massachusetts Institute of Technology
Orbital Insertion Example
Turn camera off and engine on
EngineA
EngineB
Science Camera
Artificial Intelligence & Space Systems Laboratories
EngineA
EngineB
Science Camera
Massachusetts Institute of Technology
Reactive Model-based
Model-based Program
Programming Language:
Evolves Hidden State
Asserts state
 Queries state
 Executes conditionally
 Preempts
 Iterates
 Executes concurrently

Programmer specifies
abstract state evolutions
Thrust
Goals
Programmer specifies
plant model
Delta_V(direction=b, magnitude=200)
Power
Temporal planner
Attitude
Point(a)
Model specifies
OrbitInsert()::
•Mode transitions
•Mode behavior
Engine
Off
State
Off
(do-watching
((EngineA = Firing) OR
(EngineB = Firing))
goals
(parallel
(EngineA = Standby)
(EngineB = Standby)
Valve
0.01
Open
Model
0. 01
Open
(Camera = Off)
Model-based Executive
(do-watching (EngineA = Failed)
Stuck
open
Close
0. 01
Closed
Flight System Control
ObservationsStuck
0.01
closed
inflow = outflow =RT
0 Control Layer
(when-donext ( (EngineA = Standby) AND
(Camera = Off) )
(EngineA = Firing)))
(when-donext ( (EngineA = Failed) AND
Command (EngineB = Standby) AND
(Camera = Off) )
(EngineB = Firing))))
Model-based Executive
Reasons from Plant Model
Goal: Achieve
Thrust
Thrust
Goals
Delta_V(direction=b, magnitude=200)
Power
State Goals Temporal
State Estimates
Point(a)
Attitude
Estimate
& Diagnose
ŝ
planner
Off
Reconfigure
& Repair
Engine
State Estimates
Off
State Goals
Off
Observations Engine Commands
Model-based Executive
Open four
valves
Model
Observations Flight System Control
RT Control Layer
Commands
Model-based Executive
Reasons from Plant Model
Goal: Achieve
Thrust
Thrust
Goals
Delta_V(direction=b, magnitude=200)
Power
State Goals Temporal
State Estimates
Attitude
Estimate
& Diagnose
ŝ
planner
Point(a)
Off
Reconfigure
& Repair
Engine
State
Off
goals
Diagnose:
Valve fails
stuck closed
Model-based Executive
Model
Observations Flight System Control
RT Control Layer
Command
Switch to
backup
Outline
•
•
•
•
Model-based programming
A Simple model-based executive (Livingstone)
The need for model-based reactive planning
The Burton model-based reactive planner
Artificial Intelligence & Space Systems Laboratories
Massachusetts Institute of Technology
A simple model-based executive (Livingstone)
commanded NASA’s Deep Space One probe
Started: January 1996
Launch: October 15th, 1998
Remote Agent Experiment: May, 1999
Artificial Intelligence & Space Systems Laboratories
courtesy NASA JPL
Massachusetts Institute of Technology
Livingstone [Williams & Nayak, AAAI96]
State goals
State estimate
Model
Mode
Estimation
ŝ
Mode
Reconfiguration
Flight System Control
Observations
RT Control Layer
Command
Reconfigure
Thrustmodes to meet goals
Estimate current likely Modes
State goals
State estimate
Model
Mode
Estimation
ŝ
Mode
Selection
ObservationsFlight System Control Command
RT Control Layer
Mode Estimation:
Mode Selection:
Select a most likely set of
component mode transitions
that are consistent with the
model and observations
Select a least cost set of
allowed component modes
that entail the current goal,
and are consistent
State goals
State estimate
Model
Mode
Estimation
ŝ
Mode
Selection
arg max Pt(m’)
arg min Ct(m’)
s.t. M(m’) ^ O(m’) is consistent
M(m’)
ObservationsFlight System Controls.t.Command
RT Control Layer
entails G(m’)
s.t. M(m’) is consistent
OpSat:
arg min f(x)
s.t. C(x) is satisfiable
D(x) is unsatisfiable
State goals
State estimate
Model
Mode
Estimation
ŝ
Mode
Selection
arg max Pt(m’)
arg min Ct(m’)
s.t. M(m’) ^ O(m’) is satisfiable
M(m’)
ObservationsFlight System Controls.t.Command
RT Control Layer
entails G(m’)
s.t. M(m’) is satisfiable
Outline
•
•
•
•
Model-based programming
A simple model-based executive (Livingstone)
The need for model-based reactive planning
The Burton model-based reactive planner
Artificial Intelligence & Space Systems Laboratories
Massachusetts Institute of Technology
DS 1 Attitude Control System
Flight
Computer
PDE
Data
Commands
SRU
He
N2H4
PDU
z facing thrusters
x facing thrusters
GDE
BC
PASM
DSEU
1553 bus
PEPE
Livingstone reconfigured modes using one step
commands. But How does the flight computer really
open a valve?
• Requires turning on device drivers
• Requires repairing bus controllers
• Sending commands
• Powering down devices . . .
Artificial Intelligence & Space Systems Laboratories
Massachusetts Institute of Technology
How do we reconfigure a valve?
Remote
Terminal
Computer
Driver
Valve
Bus
Control
Remote
Terminal
Driver
• Device modes are changed through indirect commanding.
Valve
• Communication paths are established by reconfiguring other
devices.
• The task of reconfiguring devices in the proper order generalizes
state-space planning to handle indirect effects.
• to achieve reactivity the all possible plans for all possible goal states
should be pre-compiled (a generalization of universal plans).
• To achieve compactness we decompose these universal plans
according to a goal/sub-goal hierarchy.
Artificial Intelligence & Space Systems Laboratories
Massachusetts Institute of Technology
Model-based Execution & Reactive Planning
Burton [Williams & Nayak, IJCAI97]
State goals
State estimate
Model
ŝ
Mode
Estimation
ŝ
Mode
Selection
s goal
Reactive
Planner
Observations
Flight System Control Command
RT Control Layer
Example: Driver Valve Command Sequence
Goal: No thrust
Valve Driver dr
vcmdin
dcmdin
Commands
ME:
MS:
MRP
ME:
MRP
ME:
MRP
ME:
MRP
ME:
Valve vlv
Driver State
dr = off,
dr = off,
Valve State
vlv = open
vlv = closed
dr = on,
vlv = open
dr = reset failure,
vlv = open
dr = on,
vlv = open
dr = off,
vlv = open
dcmdin = on
dcmdin = close
dcmdin = reset
dcmdin = off
Artificial Intelligence & Space Systems Laboratories
Massachusetts Institute of Technology
To achieve reactivity we eliminate all forms of search.
Artificial Intelligence & Space Systems Laboratories
Massachusetts Institute of Technology
Model-based Reactive Planning
Achieved by:
1. Eliminate Indirect Control
. . . through Compilation
2. Eliminate Search for Goal Ordering
. . . through Reversibility and Serialization
3. Eliminate Search to find Suitable Transitions
. . . by Constructing Hierarchical Polices
Artificial Intelligence & Space Systems Laboratories
Massachusetts Institute of Technology
Model-based Reactive Planning
Achieved by:
1. Eliminate Indirect Control
. . . through Compilation
2. Eliminate Search for Goal Ordering
. . . through Reversibility and Serialization
3. Eliminate Search to find Suitable Transitions
. . . by Constructing Hierarchical Polices
Artificial Intelligence & Space Systems Laboratories
Massachusetts Institute of Technology
To Handle Indirect Control . . .
dcmdout= vcmdin
dcmdin = dcmdout
on
dcmdin = reset
inflow = outflow
resettable
stuck
open
open
dcmdin = on dcmdin = off
vcmdin = open
dcmdin = off
off
failed
vcmdin = close
stuck
closed
closed
flowin
dcmdin
vcmdin
flowout
Artificial Intelligence & Space Systems Laboratories
Massachusetts Institute of Technology
. . . Compile Out Constraints
dcmdout = vcmdin
dcmdin = dcmdout
on
dcmdin = reset
inflow = outflow
resettable
dcmdin = on dcmdin = off
dcmdin = off
off
failed
stuck
open
open
driver = on
vcmdin = open
driver = on
vcmdin = close
dcmdin = open
dcmdin = close
stuck
closed
closed
flowin
dcmdin
vcmdin
flowout
Artificial Intelligence & Space Systems Laboratories
Massachusetts Institute of Technology
. . . Compile Out Constraints
on
dcmdin = reset
resettable
dcmdin = on dcmdin = off
driver = on
dcmdin = off
off
dcmdin = open
failed
stuck
open
open
closed
driver = on
dcmdin = close
stuck
closed
dcmdin
Artificial Intelligence & Space Systems Laboratories
Massachusetts Institute of Technology
To Compile Out Constraints
• Eliminate intermediate variables.
 Transitions are conditioned on mode and control variables
• Generate transitions as prime implicates:
Fi  next(yi = ei)
where Fi is a conjunction of mode and control variable
assignments.
• Prime implicates for transitions enumerated using OpSAT
– 40 seconds on SPARC 20 for 12,000 clause spacecraft model.
Artificial Intelligence & Space Systems Laboratories
Massachusetts Institute of Technology
Model-based Reactive Planning
Achieved by:
1. Eliminate Indirect Effects
. . . through Compilation
2. Eliminate Search for Goal Ordering
. . . through Reversibility and Serialization
3. Eliminate Search to find Suitable Transitions
. . . by Constructing Hierarchical Polices
Artificial Intelligence & Space Systems Laboratories
Massachusetts Institute of Technology
Why Search is Needed
1) An achieved goal can be clobbered by a subsequent goal.
Driver
Valve
command
• Example
– Current State: driver = on, valve = closed
– Goal State: driver = off, valve = open
– Achieving (driver = off) and then (valve = open) clobbers (driver = off)
 Achieve Valve goal before Driver goal
Artificial Intelligence & Space Systems Laboratories
Massachusetts Institute of Technology
Note: Component schematics tend not to have loops
Remote
Terminal
Computer
Bus
Control
Driver
Valve
Remote
Terminal
Driver
Valve
Driver
dcmdin
Valve
– Define: Causal Graph G of compiled transition system S
• vertices are state variables.
• edge from vi to vj if vj’s transition is conditioned on vi.
– Requirement: The causal graph is acyclic.
 Work conjunctive goals upstream from outputs to inputs
Artificial Intelligence & Space Systems Laboratories
Massachusetts Institute of Technology
Solution
• The only variables used to set some variable (y7) is its
ancestors,
 y7 can be changed without affecting its descendants.
Affected 13
10
11
6
7
12
8
9
Unaffected
5
2
3
4
1
• Safe to achieve goals in an upstream order.
• Simple check:
– Number causal graph depth first
– achieve goals in order of increasing depth first number.
Artificial Intelligence & Space Systems Laboratories
Massachusetts Institute of Technology
Why Search is Needed
2) Two goals can compete for the same variable in their
subgoals.
Switch
1
Latch1
data
2
Latch2
• Example
– Latch1 and Latch2 compete for the position of Switch if achieved
concurrently.
Artificial Intelligence & Space Systems Laboratories
Massachusetts Institute of Technology
• Sibling goals (7,4) may both need shared ancestors.
Not Shared 13
10
11
8
2
3
4
9
Unaffected
6
7
12
Shared
5
1
• But ancestors no longer needed once goal (7) is satisfied.
13
10
11
8
9
Unaffected
6
7
12
Not Shared
5
2
3
4
1
• Solution: Solve one goal before starting next sibling (Serialization).
• Feature: Generates first control action of plan first!
Artificial Intelligence & Space Systems Laboratories
Massachusetts Institute of Technology
Why Search is Needed
3) A state transition of a subgoal variable has irreversible effect.
Switch
1
Latch1
data
2
Latch2
• Example
– Assume Switch can be used once,
– Then Latch1 must be latched before Latch2.
• But irreversible effects aren’t desirable for reactive planners
 Don’t allow irreversible actions
. . . Except to repair failure modes
Artificial Intelligence & Space Systems Laboratories
Massachusetts Institute of Technology
Solution: Mark Allowed Transitions/Assignments
dcmdin
3
Driver
on
dcmdin = on
2
dcmdin = reset
Valve
resettable
dcmdin = off
off
dcmdin = open
failed
stuck
open
open
driver = on
dcmdin = off
1
closed
driver = on
dcmdin = close
stuck
closed
• Mark all control variable assignments allowed:
Artificial Intelligence & Space Systems Laboratories
Massachusetts Institute of Technology
Solution: Mark Allowed Transitions/Assignments
dcmdin
3
Driver
on
dcmdin = on
2
dcmdin = reset
Valve
resettable
dcmdin = off
off
dcmdin = open
failed
stuck
open
open
driver = on
dcmdin = off
1
driver = on
dcmdin = close
stuck
closed
closed
• Mark all control variable assignments allowed:
• For each mode variable v, in decreasing order of DF number:
• Select each transition of v, whose guard has only allowed assignments.
Artificial Intelligence & Space Systems Laboratories
Massachusetts Institute of Technology
Solution: Mark Allowed Transitions/Assignments
dcmdin
3
Driver
on
dcmdin = on
2
dcmdin = reset
Valve
resettable
dcmdin = off
off
dcmdin = open
failed
stuck
open
open
driver = on
dcmdin = off
1
driver = on
dcmdin = close
stuck
closed
closed
• Mark all control variable assignments allowed:
• For each mode variable v, in decreasing order of DF number:
• Select each transition of v, whose guard has only allowed assignments.
• Given current assignment v = I for v:
• Find strongly connected component of selected transitions that contains I.
• Mark assignments and transitions in SCC allowed.
Artificial Intelligence & Space Systems Laboratories
Massachusetts Institute of Technology
Solution: Mark Allowed Transitions/Assignments
dcmdin
3
Driver
2
1
stuck
open
open
on
dcmdin = on
Valve
dcmdin = off
driver = on
dcmdin = open
off
driver = on
dcmdin = close
stuck
closed
closed
• Mark all control variable assignments allowed:
• For each mode variable v, in decreasing order of DF number:
• Select each transition of v, whose guard has only allowed assignments.
• Given current assignment v = I for v:
• Find strongly connected component of selected transitions that contains I.
• Mark assignments and transitions in SCC allowed.
Artificial Intelligence & Space Systems Laboratories
Massachusetts Institute of Technology
Solution: Mark Allowed Transitions/Assignments
dcmdin
3
Driver
2
1
stuck
open
open
on
dcmdin = on
Valve
dcmdin = off
driver = on
dcmdin = open
off
driver = on
dcmdin = close
stuck
closed
closed
• Mark all control variable assignments allowed:
• For each mode variable v, in decreasing order of DF number:
• Select each transition of v, whose guard has only allowed assignments.
• Given current assignment v = I for v:
• Find strongly connected component of selected transitions that contains I.
• Mark assignments and transitions in SCC allowed.
Artificial Intelligence & Space Systems Laboratories
Massachusetts Institute of Technology
Solution: Mark Allowed Transitions/Assignments
dcmdin
3
Driver
2
1
open
on
dcmdin = on
Valve
dcmdin = off
driver = on
dcmdin = open
off
driver = on
dcmdin = close
closed
• Mark all control variable assignments allowed:
• For each mode variable v, in decreasing order of DF number:
• Select each transition of v, whose guard has only allowed assignments.
• Given current assignment v = I for v:
• Find strongly connected component of selected transitions that contains I.
• Mark assignments and transitions in SCC allowed.
Artificial Intelligence & Space Systems Laboratories
Massachusetts Institute of Technology
Model-based Reactive Planning
Achieved by:
1. Eliminate Indirect Effects
. . . through Compilation
2. Eliminate Search for Goal Ordering
. . . through Reversibility and Serialization
3. Eliminate Search to find Suitable Transitions
. . . by Constructing Hierarchical Polices
Artificial Intelligence & Space Systems Laboratories
Massachusetts Institute of Technology
Solution
Goal
Current
open
driver = on
cmd = open
Open
driver = on
cmd = close
closed
Closed
Stuck
Open
Closed
idle
driver = on
cmd = close
driver = on
cmd = open
idle
fail
fail
• Convert automata into hierarchical policies, one per automaton
– Policy selects first transition towards achieving each automata goal
state, given current state.
– Policy maps goals to subgoals and commands, in proper order
– Ensures only reversible transitions are taken,
by only using transitions marked allowed.
Artificial Intelligence & Space Systems Laboratories
Massachusetts Institute of Technology
Plan by passing sub-goals up causal graph
Goal: Driver = off, Valve = closed
Current: Driver = off, Valve = open
Driver
Valve
2
Goal
Current
Goal
On
Off
On
idle
cmd = off
Off
cmd = on
idle
cmd = reset
cmd = off
Resettable
1
Artificial Intelligence & Space Systems Laboratories
Current
Open
Closed
Stuck
Open
Closed
idle
driver = on
cmd = close
driver = on
cmd = open
idle
fail
fail
Massachusetts Institute of Technology
Plan by passing sub-goals up causal graph
Goal: Driver = off, Valve = closed
Current: Driver = off, Valve = open
Driver
Valve
2
Goal
Current
Goal
On
Off
On
idle
cmd = off
Off
cmd = on
idle
cmd = reset
cmd = off
Resettable
1
Artificial Intelligence & Space Systems Laboratories
Current
Open
Closed
Stuck
Open
Closed
idle
driver = on
cmd = close
driver = on
cmd = open
idle
fail
fail
Massachusetts Institute of Technology
Plan by passing sub-goals up causal graph
Goal: Driver = off, Valve = closed
Current: Driver = off, Valve = open
Driver
Send:
cmd = on
Valve
2
Goal
Current
Goal
On
Off
On
idle
cmd = off
Off
cmd = on
idle
cmd = reset
cmd = off
Resettable
1
Artificial Intelligence & Space Systems Laboratories
Current
Open
Closed
Stuck
Open
Closed
idle
driver = on
cmd = close
driver = on
cmd = open
idle
fail
fail
Massachusetts Institute of Technology
Plan by passing sub-goals up causal graph
Goal: Driver = off, Valve = closed
Current: Driver = resettable, Valve = open
Driver
Failed
Resettable
2
Valve
Goal
Current
Goal
On
Off
On
idle
cmd = off
Off
cmd = on
idle
cmd = reset
cmd = off
Resettable
1
Artificial Intelligence & Space Systems Laboratories
Current
Open
Closed
Stuck
Open
Closed
idle
driver = on
cmd = close
driver = on
cmd = open
idle
fail
fail
Massachusetts Institute of Technology
Plan by passing sub-goals up causal graph
Goal: Driver = off, Valve = closed
Current: Driver = resettable, Valve = open
Driver
Valve
2
Goal
Current
Goal
On
Off
On
idle
cmd = off
Off
cmd = on
idle
cmd = reset
cmd = off
Resettable
1
Artificial Intelligence & Space Systems Laboratories
Current
Open
Closed
Stuck
Open
Closed
idle
driver = on
cmd = close
driver = on
cmd = open
idle
fail
fail
Massachusetts Institute of Technology
Plan by passing sub-goals up causal graph
Goal: Driver = off, Valve = closed
Current: Driver = resettable, Valve = open
Driver
Valve
2
1
Send
cmd = reset
Goal
Current
Goal
On
Off
On
idle
cmd = off
Off
cmd = on
idle
cmd = reset
cmd = off
Resettable
Artificial Intelligence & Space Systems Laboratories
Current
Open
Closed
Stuck
Open
Closed
idle
driver = on
cmd = close
driver = on
cmd = open
idle
fail
fail
Massachusetts Institute of Technology
Plan by passing sub-goals up causal graph
Goal: Driver = off, Valve = closed
Current: Driver = on, Valve = open
Driver
Valve
2
1
Send
cmd = close
Goal
Current
Goal
On
Off
On
idle
cmd = off
Off
cmd = on
idle
cmd = reset
cmd = off
Resettable
Artificial Intelligence & Space Systems Laboratories
Current
Open
Closed
Stuck
Open
Closed
idle
driver = on
cmd = close
driver = on
cmd = open
idle
fail
fail
Massachusetts Institute of Technology
Plan by passing sub-goals up causal graph
Goal: Driver = off, Valve = closed
Current: Driver = on, Valve = closed
Driver
Send
cmd = off
Valve
2
Goal
Current
Goal
On
Off
On
idle
cmd = off
Off
cmd = on
idle
cmd = reset
cmd = off
Resettable
1
Artificial Intelligence & Space Systems Laboratories
Current
Open
Closed
Stuck
Open
Closed
idle
driver = on
cmd = close
driver = on
cmd = open
idle
fail
fail
Massachusetts Institute of Technology
Plan by passing sub-goals up causal graph
Goal: Driver = off, Valve = closed
Success
Current: Driver = off, Valve = closed
Driver
Valve
2
Goal
Current
Goal
On
Off
On
idle
cmd = off
Off
cmd = on
idle
cmd = reset
cmd = off
Resettable
1
Artificial Intelligence & Space Systems Laboratories
Current
Open
Closed
Stuck
Open
Closed
idle
driver = on
cmd = close
driver = on
cmd = open
idle
fail
fail
Massachusetts Institute of Technology
Hierarchical, Model-based Reactive Planning
• Compile-time Analysis:
– Compile-out interactions
– Confirm schematics are loop free.
– Depth first number variables.
• Periodic, Run-time Analysis:
– Given initial state
• Identify allowed transitions and assignments
– Given autonomous jump to failure state
• Identify allowed transitions and assignments
• Run-time Plan Execution:
–
–
–
–
Work conjunctive goals from outputs to inputs.
Achieve goals serially.
Only perform reversible transitions.
Lookup control actions and sub-goals in policies
Artificial Intelligence & Space Systems Laboratories
Massachusetts Institute of Technology
Complexity of Reactive Planning
• Worst Case per action: Depth * Sub-goal branch factor
• Average Cost per action: Sub-goal branch factor
Valve1 = open
Driver1 = on
Valve2 = open
Driver2 = on
CU = on
CU = on
Driver1 = off
Driver2 = off
CU = on
CU = on
CU = on
CU = on
Artificial Intelligence & Space Systems Laboratories
Massachusetts Institute of Technology
What If Plan is Not Serializable?
Antenna
Computer
Bus
Control
K-band
Transmitter
Amplifier
Antenna
K-band
Transmitter
Amplifier
• What if causal graph G contains cycles?
• Solution:
– Isolate the cyclic components (compute SCCs)
– compose each cycle into a single component.
• New causal graph G’ is acyclic,
• Goals of G’ are serializable
Artificial Intelligence & Space Systems Laboratories
Massachusetts Institute of Technology
Composing Cyclic Components
Transmitter
on
A = off
cmdT = on
off
Amplifier
onT
onA
on
A = off
cmdT = off
T = on
cmdA = on

cmdA = off
off
Artificial Intelligence & Space Systems Laboratories
cmdA = off
cmdA = on
cmdT = on
offT
onA
cmdA = off
onT
offA
cmdT = off
offT
offA
Massachusetts Institute of Technology
Policy for Composed Components
• Problem: Composition grows
exponential in space usage.
onT
onA
• Solution: Use BDD encoding
(in progress).
cmdA = off
cmdA = on
cmdT = on
Goal
Current
OnT, OnA
OnT, OffA
OffT, OffA
OffT, OnA
OnT, OnA
idle
cmdA = off
cmdA = off
fail
OnT, OffA
cmdA = on
idle
cmdT = off
fail
OffT, OffA
cmdT = on
cmdT = on
idle
fail
OffT, OnA
fail
fail
cmdA = off
idle
Artificial Intelligence & Space Systems Laboratories
offT
onA
cmdA = off
onT
offA
cmdT = off
offT
offA
Massachusetts Institute of Technology
Model-based Reactive Planning
1.
2.
3.
4.
Compile away constraints from the model
Compile away cyclic components
Plan serially pursuing causal graph upstream
Generate actions using hierarchical policies
Only performs reversible actions
Responds to failure at each step
Average cost per step = subgoal branching factor
Artificial Intelligence & Space Systems Laboratories
Massachusetts Institute of Technology
Current Demonstration Testbeds
• Air Force Tech Sat 21 flight
• NASA NMP ST-7 Phase A
• NASA Mercury Messenger
on ground.
• MIT Spheres on Space Station
• NASA Robonaut, X-37, ISPP
• Multi-Rover Testbed
• Simulated Air Vehicles
Artificial Intelligence & Space Systems Laboratories
Massachusetts Institute of Technology
Model-based Programming
of Embedded Systems
• To survive decades embedded systems orchestrate
complex regulatory and immune systems.
• Future systems will be programmed with models,
describing themselves and their environments.
• Runtime kernels will be agile, deducing and planning by
solving optimization problems with propositional
constraints.
• Model-based reactive planners respond quickly to failure,
while using compile-time analysis of structure to respond
quickly and concisely to indirect effects.