image/svg+xml
Experiments
dynamic smallstatic smallFast Downwardquick skip
1071113111441140
strategy
solved
Quick Skip Strategy
Fast Downward Strategy
Pruning Rate (higher value = more pruning)
ComplexityAnalysis
Action-centric
Atom-centric
Precomputation
Per node
time
Action-centric
Atom-centric
Precomputation
Per node
space
Atom Selection StrategyQuick Skip
StrongStubborn Sets
contains at least one action fromat least one plan from
For every inapplicable , contains anecessary enabling set for and .
For every applicable , contains all actionsthat interfere with in any state from .
‒ all strongly optimal plans for the state‒ states that are visited by such a plan
is a strong stubborn set if
C1
C2
C3
contains at least one action fromat least one plan from
C1
For every inapplicable , contains anecessary enabling set for and .
C2
Include action from every plan
For every applicable , contains all actionsthat interfere with in any state from .
C3
Include achievers of unsatisfied precondition
Include potentially interfering actions
Observation 1
Potential interference can be determinedfrom the occurence of individual atomsin preconditions and effects.
Observation 2
This is also true fornecessary enabling sets.
Observation 3
The order in which the actions are processed is not important for the fixed-point computation.
PotentialInterference
Interference
a
b
a
b
a
b
a
b
a
b
=
atom
atom
siblings:
achieves
depends on
goal
precondition
effect
atoms
actions
Atom-centric Algorithm
SAS Planning
+
Action-centric Algorithm
a
b
c
a
b
c
An Atom-centric Perspective on Stubborn Sets
Gabriele Röger
Malte Helmert
Jendrik Seipp