Transcript A Factored Approach to Model-based Reactive Planning in Large

Reading
• B. Williams and P. Nayak,
“A Reactive Planner for a Model-based Executive,”
International Joint Conference on Artificial
Intelligence, 1997.
Artificial Intelligence & Space Systems Laboratories
Massachusetts Institute of Technology
States are commanded through lengthy paths
Flight
Computer
PDE
Data
Commands
SRU
He
N2H4
PDU
z facing thrusters
x facing thrusters
GDE
BC
PASM
DSEU
1553 bus
PEPE
Artificial Intelligence & Space Systems Laboratories
Massachusetts Institute of Technology
How do we command safely?
Remote
Terminal
Computer
Driver
Valve
Bus
Control
Remote
Terminal
Driver
Valve
How do we open a valve?
Artificial Intelligence & Space Systems Laboratories
Massachusetts Institute of Technology
Model-based Execution & Reactive Planning
Burton [Williams & Nayak, IJCAI97]
State estimates
Model
Goal state
specifications
ŝ
Mode
Estimation
ŝ
Goal
Interpretation
s goal
Reactive
Planning
Observations
Flight System Control
RT Control Layer
Commands
Models are Concurrent Probabilistic Automata
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
Example: Model-based Execution in Action
Valve Driver dr
Valve vlv
vcmdin
dcmdin
Goal: No thrust
Commands
ME:
GI:
RP
ME:
RP
ME:
RP
ME:
RP
ME:
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.
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 Factored Polices
Artificial Intelligence & Space Systems Laboratories
Massachusetts Institute of Technology
To achieve reactivity we eliminate all forms of search.
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 Factored 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
To achieve reactivity we eliminate all forms of search.
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 Factored 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
Achieve:
(driver = off)
Then: (valve = open)
. . . clobbers (driver = off)
 Must achieve Valve goal before Driver goal
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
– Goal:
Latch1 Closed, Latch2 Open
Latch1 and Latch2 compete for the position of Switch
if goals achieved concurrently.
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 only be used once,
– Then Latch1 must be latched before Latch2.
Artificial Intelligence & Space Systems Laboratories
Massachusetts Institute of Technology
Eliminating Type 1 Search
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
 Achieve downstream goal before upstream goal
Artificial Intelligence & Space Systems Laboratories
Massachusetts Institute of Technology
Observe: 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 component state variables.
• edge from vi to vj if vj’s transition is conditioned on vi.
– Introduce Requirement: The causal graph is acyclic.
 Achieve conjunctive goals upstream from outputs to inputs
Artificial Intelligence & Space Systems Laboratories
Massachusetts Institute of Technology
Solution
• The only variables used to set a variable (y7) is its ancestors.
y7 can be changed without affecting its descendants.
• Ancestors no longer needed once variable is set.
Affected 13
10
11
5
6
7
12
8
9
Unaffected
2
3
4
1
Its is 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
Eliminating Type 3 Search
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.
Solution: Solve Serially
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
Eliminating Type 3 Search
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
To achieve reactivity we eliminate all forms of search.
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 Factored Polices
Artificial Intelligence & Space Systems Laboratories
Massachusetts Institute of Technology
Solution: Create Factored Policies
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 each automata into a goal-directed policy
– 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
Factored, 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