Model-based Programming
of Fault Aware Systems
Brian C. Williams
CSAIL, MIT
Three Challenges
1. Creating Fault-Aware Systems
2. Elevating Programming to Coaching
3. Programming Robust Dexterous Explorers
2. Elevating Programming to Coaching
Day 2 Traverse
Estimated Error Circle
Day 2
Initial Position;
Followed by
“Close
Approach”
Target
Day 2 Traverse Estimated
Error Circle
During the Day
Autonomous OnBoard Navigation
Changes, as needed
Day 1
Long-Distance Traverse
(<20-50 meters)
Day 3
Science Prep
(if Required)
Day 4
During the Day
Science Activities
Three Days to Find a Rock
Courtesy JPL, NASA ARC
3. Programming Robust
Dexterous Explorers
Creating Fault-Aware Systems:
“Grabbing Success From the Jaws of Failure”
Mars Exploration Rovers:
• Uploaded software patch shortly
before entry, descent and landing.
• Memory leak crashes processor
shortly after landing.
• Dragging wheel
• Stuck in sand trap.
• Subtle interactions between
software, digital hardware, analog
hardware and environment.
• Frequent novel failures.
Courtesy JPL
• Couplings are too vast to
pre-enumerate.
Executable Specifications Offer
A Starting Point For Robustness
Embedded programs interact with
plant sensors and actuators:
• Read sensors
Executable specifications:
• Specification formally verified.
• Code synthesized from spec.
• Set actuators
Embedded Program
Obs
Specification
Cntrl
S
Plant
Programmer must map between
state and sensors/actuators.
Issue:
State mapping implicit in specification.
• Difficult to catch specification errors
• Limited flexibility to adapt at run-time
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
Programmer must map between
state and sensors/actuators.
S’
Model-based Executive
Obs
Cntrl
S
Plant
Model-based executive maps
between state and sensors/actuators.
 Produces executable specifications that are state and fault aware.
Model-based Programming
of Fault Aware Systems
• Model-based programming languages elevate the programming
task to state-based storyboarding and modeling.
– System engineers program their high-level intentions in terms of
how they would like the state of the world to evolve.
– Programmers describe the embedded world using
commonsense models of normal and faulty behavior.
• Model-based Executives implement these intentions
by reasoning on the fly and at compile time.
– They continually hypothesize the likely states of the world,
given what they observe.
– They continually plan and execute actions in order to achieve the
programmer’s intentions robustly.
Example:
Cassini and
Deep Space One
Orbital Insertion Example
Turn camera off and engine on
EngineA
EngineB
Science Camera
EngineA
EngineB
Science Camera
RMPL Model-based Program
Titan Model-based Executive
Control Program
Executes concurrently
 Preempts
 Queries (hidden) states
 Asserts (hidden) state

OrbitInsert()::Model
System
(do-watching ((EngineA = Firing) OR
(EngineB = Firing))
(parallel
(EngineA = Standby)
(EngineB = Standby)
(Camera = Off)
Generates target goal states
Control on
Sequencer
conditioned
state estimates
MAINTAIN (EAR OR EBR)
State estimates
EAS
EBS
CO
EAS
EAF
EAR
EBS
EBF
EBR
CO
State goals
LEGEND:
(EngineA = Standby)
(EngineA = Failed)
(EngineA = Firing)
(EngineB = Standby)
(EngineB = Failed)
(EngineB = Firing)
(Camera = Off)
Deductive Controller
(EAS AND CO)
(do-watching (EngineA = Failed)
MAINTAIN (EAF)
EAS AND CO
(when-donext ( (EngineA = Standby) AND
(Camera = Off) )
(EngineA = Firing)))
EAR
(EAF AND EBS AND CO)
(when-donext ( (EngineA = Failed) AND
(EngineB = Standby)Observations
AND
(Camera = Off) )
(EngineB = Firing))))
Plant
EAF AND EBS
AND CO
EBR
Commands
hierarchical constraint
automata over abstract state s
RMPL Model-based Program
Titan Model-based Executive
Control Program
Executes concurrently
 Preempts
 Queries (hidden) states
 Asserts (hidden) state
Generates target goal states
Control on
Sequencer
conditioned
state estimates

System Model
State estimates
State goals
Deductive Controller
Valve
Open
0.01
0. 01
Open
Stuck
open
Close
0. 01
Closed
Stuck
closed
inflow = outflow = 0
0.01
Observations
Probabilistic constraint automata (PCA)
Plant
Commands
Example: The model-based program sets engine = firing, and the
deductive controller . . . .
Mode Estimation
Oxidizer tank Fuel tank
1. Estimates that
thrust is off, and
the engine is healthy
Mode Reconfiguration
2. Selects valve
configuration;
3. plans actions
to open
six valves
Estimates that a valve
failed - stuck closed
Selects valves
on backup engine that
will achieve thrust;
plans needed actions.
Mode Reconfiguration
Mode Estimation
RMPL Model-based Program
Control Program
Titan Model-based Executive
Control Sequencer:
Generates
goal states
Control
Sequencer
conditioned on state estimates
Executes concurrently
 Preempts
 Asserts and queries states
 Chooses based on reward

State estimates
System Model
State goals
Mode
Estimation:
Tracks likely
States
Mode
Reconfiguration:
Tracks least-cost
state goals
Deductive Controller
Commands
Observations
Plant
Valve fails
stuck closed
X0
Fire backup
engine
X1
S
Current Belief State
XN-1
XN
X0
T
X1
S
First Action
XN-1
XN
T
least cost reachable
goal state
ThePossible
Plant’sBehaviors
Behavior
Visualized by a Trellis Diagram
X0
X1
S
•Assigns a value to each
variable (e.g.,3,000 vars),
•consistent with all state
constraints (e.g., 12,000).
Intractable
XN-1
XN
T
Probability clustered around few states.
• Encode trellis diagram symbolically.
• Enumerate only k most likely states,
by exploiting conditional independence.
 Enumeration framed as Optimal CSP.
Diagnosing Complex Systems
Mars Polar Lander
Earth Observing One
Mission lost due to interaction
between software monitors and
Hall effect sensors.
Software failures vastly
more frequent than
hardware failures. [Chien ASE]
Challenges:
1. Monitor complex hardware/software behaviors
Hierarchical PCA Estimation
2. Delayed symptoms
[Mikaelian, Williams, Sachenbacher AAAI-05]
3. Monitoring efficiency
[Williams, Chung, Gupta IJCAI-01]
Vision-based Navigation Scenario
MERS Rover Testbed
Power=off
Nominal
Probability
Battery=low
Cam=Broken
Sensor=Broken
Battery=low
Cam=Broken
Battery=low
Sensor=Broken
Cam=Broken
Sensor=Broken
Time
0
1
Power On and Take Picture
Observe
Sensor
voltage = low
2
………………..……………. 6
S/W =>
Image not corrupt
Modeling Complex Processes
[Mikaelian, Williams & Martin, AAAI 05]
[Williams, Chung, Gupta 2001]
Complex
Behavior
S/W specs
H/W models
PHCA
Embedded Program (Esterel)

Hierarchical Automata
Probabilistic Constraint
Program (RMPL)

Hierarchical Probabilistic
Constraint Automata
PHCA =
PCA
+
from plant model
HCA
from control program
Mapping Probabilistic Embedded Programs (RMPL)
to Hierarchical Probabilistic Constraint Automata
Diagnostic Process
[Mikaelian, Williams & Martin, AAAI 05]
parameter N
[Williams, Chung, Gupta 2001]
Complex
Behavior
Delayed
Symptoms
S/W specs
H/W models
PHCA
N-Stage
OCSP/VCSP
(code)
Offline compilation phase
Online solution phase
Delayed Symptoms: Encode PHCA as an
N-stage Filter Based on an Optimal CSP
t=0
command turnOn
t=1
t=2
turnOff
none
Power
zero
Off
MA
UM
T1
DIS
DIS
T2
DIS
DIS
T3
EN
DIS
On
UM
MA
T4
DIS
DIS
T5
DIS
EN
T6
DIS
DIS
Broken
UM
DIS
UM
T7
Power=zero
nominal
DIS
T7
UM
UM
turnOn
T4
turnOff
T5
T3
On
MA
T6
Power=nominal
Observable variables: command, Power
State (location) variables: Off, On, Broken
Auxiliary variables encoding transition constraints (multiple simultaneous transitions may be possible per PHCA): T1->T7
Edges/brackets indicate constraints among variables
Diagnostic Process
[Mikaelian, Williams & Martin, AAAI 05]
[Gottlob, Leone, Scarcello 2000;
Efficiency
Kask, Dechter, Larossa 2003]
Cost based
on Viterbi
observations
commands
S/W specs
H/W models
PHCA
N-Stage
OCSP/COP
Tree Decomp
Implicate Gen
Dynamic update of OCSP/COP
Optimal
Constraint
Solver
(code)
Offline compilation phase
Online solution phase
1.
2.
3.
Lazy Dynamic Programming
Set-based B&B w ADDs
Forward Conflict-directed BF Search
Demonstration Scenarios
MIT SPHERES Testbed Models
-Global Metrology Subsystem
SPHERES 1 (5 components)
SPHERES 2 (18 components)
NASA Earth Observing One
(EO-1) Models
- Advanced Land Imager
- Hyperion Instrument
- Wideband Advanced Recorder Processor
EO-1 (12 components)
(1.6 GHz Pentium M)
Results: Online
Solver: [Sachenbacher and Williams, CP 2004]
Recovering From Failure
Hybrid Estimation
Hybrid case: estimate hybrid state
from noisy observations
Hybrid probabilistic constraint automata
– Stochastic transitions between discrete modes
actuator
Continuous
state
0.001
0.999
1
failed
nominal
0
Discrete
mode
– Different continuous dynamics for each mode
x t 1  f nominal ( x t , u t , t )   nominal ( t )
x t 1  f failed ( x t , u t , t )   failed ( t )
y t 1  g nominal ( x t 1 , u t )   nominal ( t )
y t 1  g failed ( x t 1 , u t )   failed ( t )
Kalman Filters Track Subset of Trajectories
[Blackmore, Funiak, Williams AAAAI 05]
t=0
t=1
t=2
ok
0
ok
0
…
ok
1
…
failed
…
failed
…
0
1
ok
0
ok
1
ok
0
…
ok
1
…
failed
0
failed
0
failed
1
…
…
(i)
~
p ( x c , 2 | x d , 0 :2 , y c ,1:t )
failed
1

…
x c,2
p ( x d , 0 :2 | y c ,1:t )  0 . 01
(i )
Mixed Greedy/Stochastic
Sampling
1. K-best: performs best for concentrated priors.
2. Rao-Blackwell particle filtering performs best for flat prior.
3. Mixed strategy, balances best of both.
• Concentrated Posterior
• Flat Posterior
Estimation Results
1. Transfer scenario
empty
both
WAM2
Commanding as Coaching:
Finding a Rock in Less than Three Days
Day 2 Traverse Estimated
Error Circle
Day 2
Initial Position;
Followed by “Close
Approach”
Target
Day 2 Traverse Estimated Error
Circle
During the Day
Autonomous On-Board
Navigation Changes, as
needed
Day 3
Science Prep
(if Required)
Day 1
Long-Distance Traverse (<2050 meters)
Day 4
During the Day
Science Activities
Courtesy JPL, NASA ARC
Model-Predictive Method Selection
To ensure safe, optimal execution, the control sequencer:
 Receives descriptions of possible contingencies.
 Dynamically selects consistent methods over future horizon,
 Adapts to uncertainty by selecting execution times dynamically,
 Monitors outcomes and plans contingencies.
Control
Program
RMPL
imageScienceTargets(Rover1, Rover2)
{
Continuous Temporal Planner
Plan Runner
control sequencer
{ [5,10] Rover1.goto(p4);
[5,10] Rover1.goto(p5);
[2,5] Rover1.imageTargets();
Model of
},
Subsystems
{ [5,10] Rover2.goto(p1);
[5,10] Rover1.goto(p3);
Commands
Mode
Estimation
Mode
Reconfiguration
[5,10] Rover2.goto(p2);
[2,5] Rover2.findTargets();
[5,10] Rover2.goto(p3);
}
}
Temporal Plan Network
deductive controller
Observables
Control Sequencer Continually Searches for
Optimal Consistent Threads of Execution
imageScienceTargets(Rover1, Rover2)
p4
{
{
p5
1
[5,10] Rover1.goto(p4);
choose {
2
{
do { [5,10] Rover1.goto(p5); }
maintaining( site1 =  obstructed);
[2,5] Rover1.imageTargets();
p1
}
{
p2
[2,5] Rover1.imageTargets();
p3
[5,10] Rover1.goto(p5);
}
Ask site1 =  obstructed
};
[5,10] Rover1.goto(p3);
Rover1.goto(p5)
Rover1.imageTargets
},
Rover1.goto(p3)
{
[5,10] Rover2.goto(p1);
Start
Rover1.goto(p4)
Rover1.imageTargets
End
Rover1.goto(p5)
choose {
{
Throw:
Type: imageTargets
Reason: site1 = obstructed
Ask site1 =  obstructed
do { [2,5 ]Rover2.imageTargets(); }
maintaining ( site1 =  obstructed);
[5,10] Rover2.goto(p2);
[5,10] Rover2.goto(p3);
Failure
Rover2.goto(p1)
Rover2.imageTargets
Rover2.goto(p2)
Rover2.goto(p3)
}
{
[5,10] Rover2.goto(p2);
[5,10] Rover2.goto(p3);
[2,5] Rover2.imageTargets();
}
}
Catch:
Type: imageTargets
Handler:
Rover1.goto(p4)
Tell: site1 = obstructed
Rover2.goto(p2)
Rover2.goto(p3) Rover2.imageTargets
Tell site1 = obstructed
obstructed
A Walk on Mars
Model-based Programs Specify Qualitative Gaits
G a it P o se s
l1
r2
r1
l1
l1
• [Muybridge, 1955]
• Stop-action
photographic study
of human and
animal motion
• Gaits depicted as
sequences of
distinct qualitative
poses
l2
r2
r2
sta rt
C M  R1
[t_ lb , t_ u b ]
fin ish
CM
le ft
to e -o ff
le ft
h e e l-strike
L e ft F o o t
rig h t
to e -o ff
rig h t
h e e l-strike
R ig h t F o o t
F o o t p la ce m e n t
l1
Lat
l2
2
CP  CM 
Fwd
r1
r2
Flexible spatial and temporal constraints
d CM  M

2

dt
tot

K 
Hybrid executive coordinates controllers
- to sequence biped through qualitative state plan
S ta te P la n
M o d e l-b a s e d
E x e c u tiv e
H y b rid T a s k -le v e l
E x e c u tiv e
Lf_1
Rf_2
Rf_1
Lf_1
P la n t
s ta te
Lf_1
Rf_2
Rf_2
Lf_2
C o n tro l
p a ra m e te rs
S IS O
L in e a r
S y s te m s
L in e a riz in g M u ltiv a ria b le
C o n tro lle r
P la n t
s ta te
P la n t c o n tro l
in p u ts
M IM O N o n lin e a r
P la n t
Executive is like
a marionetteer
Feasible trajectories must
go through goal regions
l1
r1
l1
r2
l1
r2
r2
l2
[0 ,1 .5 ]
t
[0 ,0 .5 ]
[0 ,0 .5 ]
[0 ,0 .5 ]
[0 ,0 .5 ]
[0 ,0 .5 ]
l2
r2
fw d
l1
r1
la t
S u p p o rt
p o ly g o n s
F o o t p la c e m e n t
l1
Lat
l2
2
CP  CM 
Fwd
r1
r2
d C M  M tot 

2
K 

dt
Flow tubes denote all
feasible trajectories
l1
r1
l1
r2
l1
r2
r2
l2
[0 ,1 .5 ]
t
[0 ,0 .5 ]
[0 ,0 .5 ]
[0 ,0 .5 ]
[0 ,0 .5 ]
[0 ,0 .5 ]
l2
r2
fw d
l1
r1
la t
S u p p o rt
p o ly g o n s
F o o t p la c e m e n t
l1
Lat
l2
2
CP  CM 
Fwd
r1
r2
d CM  M

2

dt
to t

K 
Center of Mass CM
tube constrained by
foot position tubes:
• Foot positions define
support polygon..
• Center of foot Pressure
CP constrained to be
inside support polygon.
• CM coupled to CP.
l1
r1
l1
r2
l1
r2
r2
l2
[0 ,1 .5 ]
t
[0 ,0 .5 ]
[0 ,0 .5 ]
[0 ,0 .5 ]
[0 ,0 .5 ]
[0 ,0 .5 ]
l2
r2
fw d
l1
r1
la t
S u p p o rt
p o lyg o n s
F o o t p la ce m e n t
l1
Lat
l2
2
CP  CM 
Fwd
r1
r2
d CM  M

2

dt
to t

K 
Disturbance displaces trajectory in state space
D istu rb a n ce
d isp la ce s
tra je cto ry
• Dispatcher selects trajectory within tubes online.
• If disturbance not too large, displacement stays in tube.
• Activity still executes successfully.
Disturbance displaces trajectory in state space
D istu rb a n ce
d isp la ce s
tra je cto ry
• If disturbance too large, trajectory pushed outside tube.
• Goal region not achievable at the required time.
• Plan failure detected immediately leaving more room for
recovery.
Self-repairing
Coached
RMPL Model-based Program
Agile
Model-based Executive
MAINTAIN (EAR OR EBR)
Control Program
EAS
EBS
EAS
EAF
EAR
EBS
EBF
EBR
CO
LEGEND:
(EngineA = Standby)
(EngineA = Failed)
(EngineA = Firing)
(EngineB = Standby)
(EngineB = Failed)
(EngineB = Firing)
(Camera = Off)
Executes concurrently
MAINTAIN (EAF)
 Preempts
 Queries (hidden) states
 Asserts (hidden) state

CO
(EAS AND CO)
EAS AND CO
EAR
Control Sequencer
(EAF AND EBS AND CO)
EAF AND EBS
AND CO
EBR
System Model
hierarchical timed
hybrid constraint automata
Valve
Open
0.01
0. 01
Open
Stuck
open
Close
State estimates
Mode
Estimation
State goals
Mode
Reconfiguration
0. 01
Closed
Stuck
closed
inflow = outflow = 0
0.01
Biomimetic hybrid
constraint automata
Observations
Plant
Commands
Model-based Programming
• Provides a programmer idealization in which
state is directly observable, while managing robustness
automatically.
• A wide range of systems can be modeled and reasoned
about using variants of constraint automata
– Probabilistic, decision-theoretic,
timed, hierarchical, hybrid.
• Execution reasons over abstract descriptions of
possible trajectories over a limited horizon.
– Symbolic trellis, temporal plan networks, flow tubes.
• High performance achievable through Forward,
Conflict-directed Optimal Search
Descargar

Document