DecStar – STAR-topology DECoupled Search at its best

Daniel Gnad Alexander Shleyfman Jörg Hoffmann

Saarland University Technion - Israel Institute of Technology Saarland University
Saarland Informatics Campus Industrial Engineering & Management Saarland Informatics Campus
Saarbrücken, Germany Haifa, Israel Saarbrücken, Germany
[email protected] [email protected] [email protected]

Abstract states. In this case, we simply run standard search, instead 1 .

When running STD, we enable some of the extensions
DecStar extends Fast Downward by Star-Topology Decou- that have been developed, namely partial-order reduction
pling (STD), a technique recently introduced in classical (POR) (Gnad, Wehrle, and Hoffmann 2016), symmetry
planning. It exploits independence between components of breaking (Gnad et al. 2017), and dominance pruning (Tor-
a planning task to reduce the size of the state-space repre-
sentation. Partitioning the state variables into components,
ralba et al. 2016). POR via strong stubborn sets is a
such that the interaction between these takes the form of a technique that is well-known in standard search and origi-
star topology, decoupled search only searches over action se- nates from the model checking community (Valmari 1989;
quences affecting the center component of the topology, and Alkhazraji et al. 2012; Wehrle and Helmert 2012; 2014).
enumerates reachable assignments to each leaf component, Symmetry breaking has recently been introduced for de-
separately. This can lead to an exponential reduction in the coupled search, too. It is a widely known approach across
search-space representation size. It is not always easy to find many areas of computer science (e. g. (Starke 1991; Emer-
a partitioning for a given planning task, though, so we extend son and Sistla 1996; Fox and Long 1999; Rintanen 2003;
STD by a fallback option, that runs standard search whenever Pochter, Zohar, and Rosenschein 2011; Domshlak, Katz,
no (good) partitioning could be found. and Shleyfman 2012)). Dominance pruning identifies states
that can be safely discarded, without affecting completeness
(and optimality). POR and symmetry breaking can be used
Introduction in any given factoring type 2 , dominance pruning, however,
Star-Topology Decoupling (STD) is a recently introduced is only applicable if the generated factoring takes the form
method to reduce the representation size of search spaces of a fork, i. e., the leaves have dependencies on the center,
(Gnad and Hoffmann 2015; Gnad, Hoffmann, and Domsh- but not vice versa.
lak 2015; Gnad and Hoffmann 2018). By exploiting the In the fallback case, i. e., when no good factoring could
structure of the problem within the search – as opposed to be detected and we run standard search, we make use
doing that within a heuristic function guiding the search – of the variety of techniques that are implemented in Fast
the size of the decoupled state space can be exponentially Downward (Helmert 2006). In the optimal and bounded-
smaller than that of the standard state space. Decoupled cost tracks, this includes a pattern database heuristic gener-
search achieves that by partitioning the task into several ated using a genetic algorithm (Edelkamp 2006), the LM-
components, called factors, trying to identify a star topol- cut heuristic (Helmert and Domshlak 2009), a Merge-&-
ogy, with a single center factor that interacts with multiple Shrink heuristic (Helmert, Haslum, and Hoffmann 2007;
leaf factors. By enforcing such a star structure, and thereby Helmert et al. 2014), and a landmark-count heuristic (Por-
restricting the dependencies between the components, de- teous, Sebastia, and Hoffmann 2001; Richter, Helmert, and
coupled search has proven to be very efficient and competi- Westphal 2008). In the agile and satisficing tracks, we
tive to state-of-the-art planners. mostly use the hFF heuristic (Hoffmann and Nebel 2001)
The performance of STD is highly influenced by the out- and a search configuration similar to the LAMA planning
come of the factoring process, i. e., the process of find- system (Richter, Westphal, and Helmert 2011).
ing a partitioning of the state variables. Just, how to find In all tracks, we extend the standard preprocessor of Fast
a good factoring, and what qualifies a factoring as being Downward by the h2 -based task simplification of Alcázar
good? These questions have partially been answered by and Torralba (2015), which removes irrelevant and unreach-
Gnad, Poser, and Hoffmann (2017), who devised two al- able facts and actions from the task.
gorithms that can detect star topologies on a wide range of 1
This limitation is merely due to the factoring strategies that we
planning domains. Still, the proposed algorithms can fail use to identify suitable partitionings. In general, every task has a
to find a factoring, or succeed, but return a factoring with star topology and can be tackled by decoupled search.
undesired properties, e. g. large leaf components that incur 2
We use a so-far unpublished extension of strong stubborn sets
a prohibitive runtime overhead when generating new search that supports general star factorings
 Preliminaries 2003; Pochter, Zohar, and Rosenschein 2011; Domshlak,
We use a finite-domain state variable formalization (FDR) of Katz, and Shleyfman 2012). We use an extension to decou-
planning (e. g. (Bäckström and Nebel 1995; Helmert 2006)), pled search, introduced by Gnad et al. (2017), which is build
where a planning task is a quadruple Π = hV, A, I, Gi. V is on orbit search (Domshlak, Katz, and Shleyfman 2015;
a set of state variables, where each v ∈ V is associated with Wehrle et al. 2015). An orbit is a set of states all of which are
a finite domain D(v). We identify (partial) variable assign- symmetric to each other. In the search, each state is mapped
ments with sets of variable/value pairs. A complete assign- to a canonical representative of its orbit. In case another state
ment to V is a state. I is the initial state, and the goal G is from the same orbit has already been generated (with lower
a partial assignment to V . A is a finite set of actions. Each g-cost), the new state can safely be pruned. Decoupled orbit
action a ∈ A is a triple hpre(a), eff(a), cost(a)i where the search extends this concept to decoupled states.
precondition pre(a) and effect eff(a) are partial assignments
to V , and cost(a) is a’s non-negative cost. Decoupled Strong Stubborn Sets
We use the usual FDR semantics. The planning prob- Partial-order reduction is a well-known technique that re-
lem is to decide if there exists a sequence of actions that duces the size of the search space by pruning transitions
transforms the initial state I of Π to a state that satisfies the that correspond to different permutations of actions (Val-
goal condition G. In the optimal and bounded-cost tracks of mari 1989; Godefroid and Wolper 1991; Edelkamp, Leue,
the competition, we are looking for an action sequence with and Lluch-Lafuente 2004; Alkhazraji et al. 2012; Wehrle et
minimal, respectively bounded, summed-up cost. al. 2013; Wehrle and Helmert 2014). A variant of strong
stubborn sets, decoupled strong stubborn sets (DSSS), has
Decoupled Search also been introduced for decoupled search. We will employ
DSSS in the optimal and bounded-cost tracks. For fork fac-
We perform decoupled search like introduced by Gnad and
torings, we use DSSS as defined by Gnad, Wehrle, and Hoff-
Hoffmann (2018), in its integration in the Fast Downward
mann (2016). For non-fork factorings, we use a yet unpub-
planning system (Helmert 2006). We use the improved
lished extension that is able to handle arbitrary factorings.
fork and inverted-fork, as well as the incident-arcs factor-
To avoid the runtime overhead when DSSS are not effective,
ing methods from Gnad, Poser, and Hoffmann (2017). The
we implemented a “safety belt” mechanism, that disables
outcome of the factoring process is a partitioning F of the
DSSS if after the first 1000 expansions less than 20% of the
variables of the planning task Π, such that |F| > 1 and
transitions have been pruned.
there exists F C ∈ F such that, for every action a where
V(eff(a))∩F C = ∅, there exists F ∈ F with V(eff(a)) ⊆ F
Decoupled Dominance Pruning
and V(pre(a)) ⊆ F ∪ F C . We then call F a star factoring,
with center factor F C and leaf factors F L := F \ {F C }. Another extension that has recently been introduced is domi-
Given a factoring F, decoupled search is performed as nance pruning (Torralba et al. 2016), where decoupled states
follows: The search will only branch over center actions, that are dominated by other – already generated – states
i. e., those actions affecting (with an effect on) a variable in can be safely discarded. We only deploy a very lightweight
F C . Along such a path of center actions π C , for each leaf pruning method, namely frontier pruning. The standard way
factor F L , the search maintains a set of leaf paths, i. e., ac- of performing duplicate checking in decoupled search can
tions only affecting variables of F L , that comply with π C . already detect certain forms of dominance, in particular if
Intuitively, for a leaf path π L to comply with a center path two decoupled states have the same center state and all leaf
π C , it must be possible to embed π L into π C into an overall states reachable in one state are (at most as costly) also
action sequence π, such that π is a valid path in the projec- reachable in the other. Frontier pruning improves this by
tion of the planning task Π onto F C ∪ F L . A decoupled only comparing a subset of the reached leaf states, those that
state corresponds to an end state of such a center action se- can possibly make so far unreached leaf states available. It
quence. The main advantage over standard search originates has originally been developed for optimal planning, but can
from a decoupled state being able to represent exponentially be easily adapted to become more efficient, when optimal
many explicit states, avoiding their enumeration. A decou- solutions do not matter, by replacing the real cost of reach-
pled state can “contain” many explicit states, because by in- ing a leaf state by 0, if a state has been reached at any cost.
stantiating the center with a center action sequence, the leaf Additionally, we also employ a leaf simulation, originally
factors are conditionally independent. Thus, the more leaves proposed by Torralba and Kissmann (2015), to remove irrel-
in the factoring, the more explicit states can potentially be evant leaf states and leaf actions. In some domains, this can
represented by a single decoupled state. tremendously reduce the size of the leaf state spaces.
We will next describe a couple of extensions that have As indicated before, the techniques described in this sub-
been developed for decoupled search and that we use in section are only applicable if F is a fork factoring.
some of our configurations.
Implementation & Configurations
Symmetry Breaking in Decoupled Search Decoupled Search has been implemented as an extension of
Symmetry Breaking has a long tradition in planning and the Fast Downward (FD) planning system (Helmert 2006).
many other sub-areas of computer science (Starke 1991; By changing the low-level state representation, many of
Emerson and Sistla 1996; Fox and Long 1999; Rintanen FD’s built-in algorithms and functionality can be used with
only minor adaptations. Of particular interest for the Dec- and DOSS. This is the main component running for 15min.
Star planner are the A∗ search algorithm, and the hLM-cut Both decoupled search components use the LM-cut heuris-
heuristic (Helmert and Domshlak 2009) for optimal, and tic (Helmert and Domshlak 2009), currently the strongest
bounded-cost planning. In the satisficing and agile tracks, admissible heuristic that supports decoupled search.
we run greedy best-first search (GBFS) using the hFF heuris-
L
tic (Hoffmann and Nebel 2001). The search algorithms and Search Factoring |Fmax | Heuristic Pruning Runtime
∗
heuristics can be adapted to decoupled search using a com- DA F 10M hLM-cut DSSS,FP,IP 100s
pilation defined by Gnad and Hoffmann (2018). Our imple- DA∗ F/IF/IA 10/10/1M hLM-cut DSSS,DOSS 800s
mentation does not support conditional effects. On top of the A∗ - - hLM-cut SSS,OSS 180s
∗
standard FD preprocessor, we perform a relevance analysis A - - hGA-PDB SSS 180s
based on h2 , to eliminate actions and simplify the planning A∗ - - hM&S - 180s
task prior to the search (Alcázar and Torralba 2015). A∗ - - hLMc - 180s
In all tracks of the competition, star-topology decoupling A∗ - - blind - 180s
is the main component of our planner. However, since, as
outline before, our factoring strategies are not guaranteed to Figure 1: Portfolio configuration in the optimal track. Com-
find good task decompositions, we need a fallback method. ponents are launched top to bottom.
Given the implementation of decoupled search in FD, we
In case no matching factoring could be found, or when
can easily make use of the many techniques that FD ships
decoupled search fails, DecStar is supported by standard
with. Thus, in the case that no good factoring could be ob-
search with different heuristics. If the heuristic does not
tained, we run standard search using some heuristics and
support conditional effects, we also enable strong stubborn
pruning methods that are implemented in FD.
sets pruning and/or orbit search, which both do not support
We will use the following notation to describe our tech-
these, either. DecStar tries the pattern database heuristic
niques: the decoupled variant of search algorithm X is de-
with patterns generated using a genetic algorithm (hGA-PDB )
noted DX. We denote fork (inverted-fork) factorings by F
(Edelkamp 2006), a Merge&Shrink heuristic with linear
(IF), and factorings generated using the incident-arcs algo-
merge order and bisimulation (hM&S ) (Helmert, Haslum, and
rithm by IA. To combine the power of the factoring strate-
Hoffmann 2007; Helmert et al. 2014; Sievers, Wehrle, and
gies, we use a portfolio approach that runs multiple strate-
Helmert 2014), the landmark-count heuristic (hLMc ) (Porte-
gies and picks the one with the maximum number of leaf
ous, Sebastia, and Hoffmann 2001; Richter, Helmert, and
factors. Further more, we restrict the size for the per-leaf
Westphal 2008), and finally blind search.
domain-size product to ensure that the leaf state spaces are
reasonably small and do not incur a prohibitive runtime Satisficing Track
overhead when generating new decoupled states. We denote
L In the satisficing track, DecStar runs three different com-
this size limit by |Fmax | := maxF L ∈F L Πv∈F L |D(v)|. If
ponents. The first, similar to the optimal track, runs de-
a fork factoring is detected, we sometimes perform frontier
coupled search with a fork factoring, since these typically
dominance pruning, denoted FP and reduce the size of the
perform better, in particular when combined with the strong
leaf state spaces removing irrelevant transitions and states
leaf pruning methods (FP,IP). The second component tries
(IP). Decoupled strong stubborn sets will be abbreviated as
all factoring strategies, and additionally enables decoupled
DSSS, where we always use the safety belt with a mini-
orbit search. The “D” in paranthesis indicates that, if none of
mum pruning ratio of 20%. In standard search, the use of
the factoring strategies succeeds, the component falls back
strong stubborn sets pruning is denoted SSS. (Decoupled)
to standard search using the same options. Both components
orbit search is abbreviated (D)OSS. The use of preferred op-
use the hFF heuristic and perform preferred operator prun-
erator pruning is denoted PO.
ing, using FD’s dual queue mechanism.
In all but the optimal track, we start by ignoring the ac-
tion costs. Costs are ignored altogether in the agile track, L
Search Factoring |Fmax | Heuristic Pruning Runtime
and only re-introduced in the bounded-cost track if no plan DGBF S F 1M hFF FP,IP,PO 100s
below the cost bound could be found. In the satisficing track, (D)GBF S F/IF/IA 1/1/0.1M hFF (D)OSS,PO 1000s
we re-introduce the real costs upon finding the first plan. GBF S - - hLM ,hFF PO 700s
In the following sub-sections, we detail the configurations
employed in each competition track. We provide the search Figure 2: Portfolio configuration in the satisficing track.
configurations, as well as the time each of the components Components are launched top to bottom.
is allotted (in seconds).
If all is lost, DecStar gets help from his experienced friend
Optimal Track LAMA, adopting its first iteration (Richter, Westphal, and
DecStar starts by running decoupled search with a fork fac- Helmert 2011).
toring with a maximum leaf size of 10 million, if one ex-
ists. In this case, it employs frontier pruning, removes ir- Bounded-Cost Track
relevance in the leaves, and performs partial-order reduc- The components that DecStar uses in the bounded-cost track
tion (DSSS). The next component tries all factoring methods are a mix of the components described above for the opti-
with different size constraints, and prunes states with DSSS mal and satisficing track. DecStar starts by running each
satisficing-track component for 100s. It then uses a weighted References
A∗ search (weight 3), in case none of the previous compo- Alcázar, V., and Torralba, Á. 2015. A reminder about the im-
nents could find a plan within the given bound. This is fol- portance of computing and exploiting invariants in planning.
lowed by the components used in the optimal track. In Brafman, R.; Domshlak, C.; Haslum, P.; and Zilberstein,
L
S., eds., Proceedings of the 25th International Conference
Search Factoring |Fmax | Heuristic Pruning Runtime
on Automated Planning and Scheduling (ICAPS’15), 2–6.
DGBF S F 1M hFF PO,FP,IP 100s
(D)GBF S F/IF/IA 1/1/0.1M hFF (D)OSS,PO 100s
AAAI Press.
GBF S - - hLM ,hFF PO 100s Alkhazraji, Y.; Wehrle, M.; Mattmüller, R.; and Helmert,
∗
DW A F/IF/IA 10/10/1M hFF DOSS 400s M. 2012. A stubborn set algorithm for optimal planning. In
DA∗ F 10M hLM-cut DSSS,FP,IP 100s Raedt, L. D., ed., Proceedings of the 20th European Confer-
DA∗ F/IF/IA 10/10/1M hLM-cut DSSS,DOSS 400s ence on Artificial Intelligence (ECAI’12), 891–892. Mont-
A∗ - - hLM-cut SSS,OSS 120s pellier, France: IOS Press.
∗
A - - hGA-PDB SSS 120s
A∗ - - hM&S - 120s Bäckström, C., and Nebel, B. 1995. Complexity results
A∗ - - hLMc - 120s for SAS+ planning. Computational Intelligence 11(4):625–
A∗ - - blind - 120s 655.
Domshlak, C.; Katz, M.; and Shleyfman, A. 2012. En-
Figure 3: Portfolio configuration in the bounded-cost track. hanced symmetry breaking in cost-optimal planning as for-
Components are launched top to bottom. ward search. In Bonet, B.; McCluskey, L.; Silva, J. R.;
and Williams, B., eds., Proceedings of the 22nd Interna-
tional Conference on Automated Planning and Scheduling
Agile Track (ICAPS’12). AAAI Press.
L Domshlak, C.; Katz, M.; and Shleyfman, A. 2015. Sym-
Search Factoring |Fmax | Heuristic Pruning Runtime
metry breaking in deterministic planning as forward search:
DGBF S F 10K hFF FP,IP,PO 60s
Orbit space search algorithm. Technical Report IS/IE-2015-
(D)GBF S F/IF/IA 10/10/1K hFF (D)OSS,PO 120s
GBF S - - hLM ,hFF PO 120s
02.
Edelkamp, S.; Leue, S.; and Lluch-Lafuente, A. 2004.
Figure 4: Portfolio configuration in the agile track. Compo- Partial-order reduction and trail improvement in directed
nents are launched top to bottom. model checking. International Journal on Software Tools
for Technology Transfer 6(4):277–301.
In the agile track, DecStar uses the same search compo- Edelkamp, S. 2006. Automated creation of pattern database
nents as in the satisficing track, but with different timeouts search heuristics. In Proceedings of the 4th Workshop on
and leaf space size limits. The latter is due to the fact that Model Checking and Artificial Intelligence (MoChArt 2006),
the larger the leaves, the bigger the runtime overhead per 35–50.
decoupled state. Since the time limit is significantly smaller Emerson, E. A., and Sistla, A. P. 1996. Symmetry
in the agile track, we try to keep the leaves as small as pos- and model-checking. Formal Methods in System Design
sible. In spite of the tight time constraint, we still run the 9(1/2):105–131.
h2 -preprocessor for 10s.
Fox, M., and Long, D. 1999. The detection and exploitation
Conclusion of symmetry in planning problems. In Pollack, M., ed., Pro-
ceedings of the 16th International Joint Conference on Ar-
DecStar is the best that star-topology decoupling currently tificial Intelligence (IJCAI’99), 956–961. Stockholm, Swe-
has to offer. Many extensions have been developed, allowing den: Morgan Kaufmann.
the use of various search algorithms, heuristic functions, and
pruning techniques. Decoupled search has proved to be a Gnad, D., and Hoffmann, J. 2015. Beating LM-cut with
method that can beat other state-of-the-art planners, also in hmax (sometimes): Fork-decoupled state space search. In
the unsolvability IPC 2014, if the given planning task can be Brafman, R.; Domshlak, C.; Haslum, P.; and Zilberstein,
nicely decoupled. Even outside the planning area, namely in S., eds., Proceedings of the 25th International Conference
proving safety properties in model checking, star-topology on Automated Planning and Scheduling (ICAPS’15), 88–96.
decoupling has shown its merit (Gnad et al. 2018). AAAI Press.
And still, there are many possible ways of further extend- Gnad, D., and Hoffmann, J. 2018. Star-topology decoupled
ing it. In classical planning, where it is crucial to use strong state space search. Artificial Intelligence 257:24 – 60.
heuristics, the next steps are to do research on how to apply Gnad, D.; Torralba, Á.; Shleyfman, A.; and Hoffmann,
abstraction and LP heuristics in decoupled search. In model J. 2017. Symmetry breaking in star-topology decoupled
checking, an interesting research question is the extension search. In Proceedings of the 27th International Conference
of star-topology decoupling to prove liveness properties. on Automated Planning and Scheduling (ICAPS’17). AAAI
Acknowledgments. This work was partially supported by Press.
the German Research Foundation (DFG), under grant HO Gnad, D.; Dubbert, P.; Lluch-Lafuente, A.; and Hoffmann,
2169/6-1, “Star-Topology Decoupled State Space Search”. J. 2018. Star-topology decoupling in spin. In del Mar Gal-
lardo, M., and Merino, P., eds., Proceedings of the 25th Association for Artificial Intelligence (AAAI’08), 975–982.
International Symposium on Model Checking of Software Chicago, Illinois, USA: AAAI Press.
(SPIN’18), Lecture Notes in Computer Science. Springer. Richter, S.; Westphal, M.; and Helmert, M. 2011. LAMA
Gnad, D.; Hoffmann, J.; and Domshlak, C. 2015. From fork 2008 and 2011 (planner abstract). In IPC 2011 planner ab-
decoupling to star-topology decoupling. In Lelis, L., and stracts, 50–54.
Stern, R., eds., Proceedings of the 8th Annual Symposium Rintanen, J. 2003. Symmetry reduction for SAT represen-
on Combinatorial Search (SOCS’15), 53–61. AAAI Press. tations of transition systems. In Giunchiglia, E.; Muscet-
Gnad, D.; Poser, V.; and Hoffmann, J. 2017. Beyond tola, N.; and Nau, D., eds., Proceedings of the 13th Interna-
forks: Finding and ranking star factorings for decoupled tional Conference on Automated Planning and Scheduling
search. In Sierra, C., ed., Proceedings of the 26th Interna- (ICAPS’03), 32–41. Trento, Italy: Morgan Kaufmann.
tional Joint Conference on Artificial Intelligence (IJCAI’17). Sievers, S.; Wehrle, M.; and Helmert, M. 2014. Gener-
AAAI Press/IJCAI. alized label reduction for merge-and-shrink heuristics. In
Gnad, D.; Wehrle, M.; and Hoffmann, J. 2016. Decoupled Brodley, C. E., and Stone, P., eds., Proceedings of the
strong stubborn sets. In Kambhampati, S., ed., Proceedings 28th AAAI Conference on Artificial Intelligence (AAAI’14),
of the 25th International Joint Conference on Artificial In- 2358–2366. Austin, Texas, USA: AAAI Press.
telligence (IJCAI’16), 3110–3116. AAAI Press/IJCAI. Starke, P. 1991. Reachability analysis of petri nets using
Godefroid, P., and Wolper, P. 1991. Using partial orders symmetries. Journal of Mathematical Modelling and Simu-
for the efficient verification of deadlock freedom and safety lation in Systems Analysis 8(4/5):293–304.
properties. In Proceedings of the 3rd International Work- Torralba, Á., and Kissmann, P. 2015. Focusing on what
shop on Computer Aided Verification (CAV’91), 332–342. really matters: Irrelevance pruning in merge-and-shrink. In
Helmert, M., and Domshlak, C. 2009. Landmarks, criti- Lelis, L., and Stern, R., eds., Proceedings of the 8th Annual
cal paths and abstractions: What’s the difference anyway? Symposium on Combinatorial Search (SOCS’15), 122–130.
In Gerevini, A.; Howe, A.; Cesta, A.; and Refanidis, I., AAAI Press.
eds., Proceedings of the 19th International Conference on Torralba, Á.; Gnad, D.; Dubbert, P.; and Hoffmann, J. 2016.
Automated Planning and Scheduling (ICAPS’09), 162–169. On state-dominance criteria in fork-decoupled search. In
AAAI Press. Kambhampati, S., ed., Proceedings of the 25th Interna-
tional Joint Conference on Artificial Intelligence (IJCAI’16).
Helmert, M.; Haslum, P.; Hoffmann, J.; and Nissim, R.
AAAI Press/IJCAI.
2014. Merge & shrink abstraction: A method for gener-
ating lower bounds in factored state spaces. Journal of the Valmari, A. 1989. Stubborn sets for reduced state space gen-
Association for Computing Machinery 61(3). eration. In Proceedings of the 10th International Conference
on Applications and Theory of Petri Nets, 491–515.
Helmert, M.; Haslum, P.; and Hoffmann, J. 2007. Flexi-
ble abstraction heuristics for optimal sequential planning. In Wehrle, M., and Helmert, M. 2012. About partial order
Boddy, M.; Fox, M.; and Thiebaux, S., eds., Proceedings of reduction in planning and computer aided verification. In
the 17th International Conference on Automated Planning Bonet, B.; McCluskey, L.; Silva, J. R.; and Williams, B.,
and Scheduling (ICAPS’07), 176–183. Providence, Rhode eds., Proceedings of the 22nd International Conference on
Island, USA: Morgan Kaufmann. Automated Planning and Scheduling (ICAPS’12). AAAI
Press.
Helmert, M. 2006. The Fast Downward planning system.
Wehrle, M., and Helmert, M. 2014. Efficient stubborn sets:
Journal of Artificial Intelligence Research 26:191–246.
Generalized algorithms and selection strategies. In Chien,
Hoffmann, J., and Nebel, B. 2001. The FF planning system: S.; Do, M.; Fern, A.; and Ruml, W., eds., Proceedings of the
Fast plan generation through heuristic search. Journal of 24th International Conference on Automated Planning and
Artificial Intelligence Research 14:253–302. Scheduling (ICAPS’14). AAAI Press.
Pochter, N.; Zohar, A.; and Rosenschein, J. S. 2011. Ex- Wehrle, M.; Helmert, M.; Alkhazraji, Y.; and Mattmüller,
ploiting problem symmetries in state-based planners. In Bur- R. 2013. The relative pruning power of strong stubborn sets
gard, W., and Roth, D., eds., Proceedings of the 25th Na- and expansion core. In Borrajo, D.; Fratini, S.; Kambham-
tional Conference of the American Association for Artificial pati, S.; and Oddi, A., eds., Proceedings of the 23rd Interna-
Intelligence (AAAI’11). San Francisco, CA, USA: AAAI tional Conference on Automated Planning and Scheduling
Press. (ICAPS’13). Rome, Italy: AAAI Press.
Porteous, J.; Sebastia, L.; and Hoffmann, J. 2001. On the Wehrle, M.; Helmert, M.; Shleyfman, A.; and Katz, M.
extraction, ordering, and usage of landmarks in planning. In 2015. Integrating partial order reduction and symmetry
Cesta, A., and Borrajo, D., eds., Proceedings of the 6th Eu- elimination for cost-optimal classical planning. In Yang, Q.,
ropean Conference on Planning (ECP’01), 37–48. Springer- ed., Proceedings of the 24th International Joint Conference
Verlag. on Artificial Intelligence (IJCAI’15). AAAI Press/IJCAI.
Richter, S.; Helmert, M.; and Westphal, M. 2008. Land-
marks revisited. In Fox, D., and Gomes, C., eds., Pro-
ceedings of the 23rd National Conference of the American