Plan deordering removes unnecessary ordering constraints between actions in a plan, facilitating plan execution flexibility and several other tasks, such as plan reuse, modification, and decomposition. Block deordering is a variant of plan deordering that encapsulates coherent actions into blocks to eliminate further ordering constraints from a partial-order plan (POP) and is useful in many applications (e.g., generating macro-actions and improving the overall plan quality). The existing block deordering strategy is formulated in propositional encodings. Finite-domain state variable encodings (e.g., SAS+ representation), in contrast with propositional encodings, can capture the internal structure and the behavior of state variables of a planning instance through concise constructs such as causal graphs (CGs) and domain transition graphs (DTGs). This work redefines the semantics of block deordering terminologies and related plan deordering concepts in finite domain representation (FDR). Our proposed semantics also resolves some limitations of the existing block semantics and further enhance plan flexibility. In addition, this work exploits block deordering to eliminate redundant actions from a POP. A comparative analysis is also performed on block deordering with various deordering/reordering techniques using explanation-based order generalization (EOG) and MaxSAT. Our experiments on the benchmark problems from International Planning Competitions (IPC) show that our FDR formalism of block deordering significantly improves the plan execution flexibility while maintaining good coverage and execution time.
T.-C.Au, O.Ilghami, U.Kuter, J.W.Murdock, D.S.Nau, D.Wu and F.Yaman, SHOP2: An HTN planning system, Journal of Artificial Intelligence Research20 (2003), 379–404. doi:10.1613/jair.1141.
2.
C.Bäckström, Computational aspects of reordering plans, Journal of Artificial Intelligence Research9 (1998), 99–137. doi:10.1613/jair.477.
3.
P.Bercher, G.Behnke, D.Höller and S.Biundo, An admissible HTN planning heuristic, in: Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI-17, 2017, pp. 480–488. doi:10.24963/ijcai.2017/68.
4.
P.Bercher, D.Höller, G.Behnke and S.Biundo, More than a name? On implications of preconditions and effects of compound HTN planning tasks, in: Proceedings of the Twenty-Second European Conference on Artificial Intelligence, ECAI’16, IOS Press, NLD, 2016, pp. 225–233. doi:10.3233/978-1-61499-672-9-225.
5.
A.Bit-Monnot, M.Ghallab, F.Ingrand and D.E.Smith, FAPE: A constraint-based planner for generative and hierarchical temporal planning, 2020, arXiv:2010.13121.
6.
A.Bit-Monnot, D.E.Smith and M.Do, Delete-free reachability analysis for temporal and hierarchical planning, in: ICAPS Workshop on Heuristics and Search for Domain-Independent Planning (HSDIP), London, United Kingdom, 2016.
7.
A.L.Blum and M.L.Furst, Fast planning through planning graph analysis, Artificial Intelligence90(1) (1997), 281–300. doi:10.1016/S0004-3702(96)00047-1.
8.
B.Bonet and H.Geffner, Planning as heuristic search, Artificial Intelligence129(1) (2001), 5–33. doi:10.1016/S0004-3702(01)00108-4.
9.
L.Chrpa and F.H.Siddiqui, Exploiting block deordering for improving planners efficiency, in: Proceedings of the 24th International Conference on Artificial Intelligence, IJCAI’15, AAAI Press, 2015, pp. 1537–1543.
10.
A.Coles, A.Coles, M.Fox and D.Long, Forward-chaining partial-order planning, in: Proceedings of the International Conference on Automated Planning and Scheduling, Vol. 20, 2021, pp. 42–49. doi:10.1609/icaps.v20i1.13403.
11.
C.Domshlak, J.Hoffmann and M.Katz, Red–black planning: A new systematic approach to partial delete relaxation, Artificial Intelligence221 (2015), 73–114. doi:10.1016/j.artint.2014.12.008.
12.
C.Domshlak, M.Katz and A.Shleyfman, Symmetry breaking: Satisficing planning and landmark heuristics, in: Proceedings of the International Conference on Automated Planning and Scheduling, Vol. 23, 2013, pp. 298–302. doi:10.1609/icaps.v23i1.13595.
13.
R.E.Fikes and N.J.Nilsson, STRIPS: A new approach to the application of theorem proving to problem solving, Artificial Intelligence2(3) (1971), 189–208. doi:10.1016/0004-3702(71)90010-5.
14.
D.Fišer, Lifted fact-alternating mutex groups and pruned grounding of classical planning problems, Proceedings of the AAAI Conference on Artificial Intelligence34(06) (2020), 9835–9842. doi:10.1609/aaai.v34i06.6536.
15.
D.Fišer and A.Komenda, Fact-alternating mutex groups for classical planning, Journal of Artificial Intelligence Research61 (2018), 475–521. doi:10.1613/jair.5321.
16.
M.Fox and D.Long, Hybrid S.T.A.N.: Identifying and managing combinatorial optimisation sub-problems in planning, in: Proceedings of the 17th International Joint Conference on Artificial Intelligence – Volume 1, IJCAI’01, 2001, pp. 445–450.
17.
D.Gnad and J.Hoffmann, Red–black planning: A new tractability analysis and heuristic function, in: Proceedings of the 8th Annual Symposium on Combinatorial Search (SOCS’15), 2015, pp. 44–52.
18.
D.Gnad, M.Wehrle and J.Hoffmann, Decoupled strong stubborn sets, in: Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI’16, AAAI Press, 2016, pp. 3110–3116.
19.
P.Haslum, A.Botea, M.Helmert, B.Bonet and S.Koenig, Domain-independent construction of pattern database heuristics for cost-optimal planning, in: AAAI Conference on Artificial Intelligence, 2007.
20.
P.Haslum, N.Lipovetzky, D.Magazzeni and C.Muise, An Introduction to the Planning Domain Definition Language, Synthesis Lectures on Artificial Intelligence and Machine Learning, Morgan & Claypool, 2019.
21.
M.Helmert, The fast downward planning system, Journal of Artificial Intelligence Research26 (2006), 191–246. doi:10.1613/jair.1705.
22.
M.Helmert, Concise finite-domain representations for PDDL planning tasks, Artificial Intelligence173(5) (2009), 503–535, advances in Automated Plan Generation. doi:10.1016/j.artint.2008.10.013.
23.
M.Helmert, The fast downward planning system, Journal of Artificial Intelligence Research26 (092011). doi:10.1613/jair.1705.
24.
M.Helmert and C.Domshlak, LM-Cut: Optimal planning with the landmark-cut heuristic, 2009.
25.
M.Helmert and C.Domshlak, Landmarks, critical paths and abstractions: What’s the difference anyway? in: Proceedings of the International Conference on Automated Planning and Scheduling, Vol. 19, 2009, pp. 162–169. doi:10.1609/icaps.v19i1.13370.
26.
M.Helmert, P.Haslum, J.Hoffmann and R.Nissim, Merge-and-shrink abstraction: A method for generating lower bounds in factored state spaces, Journal of the ACM3 (052014). doi:10.1145/2559951.
27.
S.Hickmott, J.Rintanen, S.Thiébaux and L.White, Planning via Petri net unfolding, in: Proceedings of the 20th International Joint Conference on Artificial Intelligence, IJCAI’07, 2007, pp. 1904–1911.
28.
D.Höller and P.Bercher, Landmark generation in HTN planning, Proceedings of the AAAI Conference on Artificial Intelligence35(13) (2021), 11826–11834. doi:10.1609/aaai.v35i13.17405.
29.
International Conference on Automated Planning and Scheduling, Competitions, 2022, https://www.icaps-conference.org/competitions/.
30.
S.Kambhampati, Multi-contributor causal structures for planning: A formalization and evaluation, Artificial Intelligence69(1–2) (1994), 235–278. doi:10.1016/0004-3702(94)90083-3.
31.
S.Kambhampati and J.A.Hendler, A validation-structure-based theory of plan modification and reuse, Artificial Intelligence55(2) (1992), 193–258. doi:10.1016/0004-3702(92)90056-4.
32.
S.Kambhampati and S.Kedar, A unified framework for explanation-based generalization of partially ordered and partially instantiated plans, Artificial Intelligence67(1) (1994), 29–70. doi:10.1016/0004-3702(94)90011-6.
33.
M.Katz, Red–black heuristics for planning tasks with conditional effects, in: Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence and Thirty-First Innovative Applications of Artificial Intelligence Conference and Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, AAAI’19/IAAI’19/EAAI’19, AAAI Press, 2019. doi:10.1609/aaai.v33i01.33017619.
34.
M.Katz and C.Domshlak, Implicit abstraction heuristics, Journal of Artificial Intelligence Research39 (2010), 51–126. doi:10.1613/jair.3063.
35.
M.Katz and J.Lee, K* and partial order reduction for top-quality planning, in: Proceedings of the International Symposium on Combinatorial Search, Vol. 06, 2023. doi:10.1609/socs.v16i1.27293.
36.
M.Katz, S.Sohrabi and O.Udrea, Top-quality planning: Finding practically useful sets of best plans, Proceedings of the AAAI Conference on Artificial Intelligence34(06) (2020), 9900–9907. doi:10.1609/aaai.v34i06.6544.
37.
H.Kautz and B.Selman, BLACKBOX: A new approach to the application of theorem proving to problem solving, AIPS98 Workshop on Planning as Combinatorial Search (06 1998).
38.
J.Koehler, Handling of conditional effects and negative goals in IPP, Technical Report, University of Freiburg, 1999.
39.
R.E.Korf, Macro-operators: A weak method for learning, Artificial Intelligence26(1) (1985), 35–77. doi:10.1016/0004-3702(85)90012-8.
40.
C.Muise, J.Beck and S.McIlraith, Optimal partial-order plan relaxation via MaxSAT, Journal of Artificial Intelligence Research57 (2016), 113–149. doi:10.1613/jair.5128.
41.
X.Nguyen and S.Kambhampati, Reviving partial order planning, in: Proceedings of the 17th International Joint Conference on Artificial Intelligence – Volume 1, IJCAI’01, 2001, pp. 459–464.
42.
S.B.Noor and F.H.Siddiqui, Plan deordering with conditional effects, in: Intelligent Systems and Applications, Springer International Publishing, 2022, pp. 852–870.
43.
J.S.Penberthy and D.S.Weld, UCPOP: A sound, complete, partial order planner for adl, in: Proceedings of the Third International Conference on Principles of Knowledge Representation and Reasoning, KR’92, 1992, pp. 103–114.
44.
P.Regnier and B.Fade, Complete determination of parallel actions and temporal optimization in linear plans of action, in: European Workshop on Planning, Lecture, Vol. 522, Springer-Verlag, 1991, pp. 100–111. doi:10.1007/BFb0052953.
45.
S.Richter and M.Westphal, The LAMA planner: Guiding cost-based anytime planning with landmarks, Journal of Artificial Intelligence Research39(1) (2010), 127–177. doi:10.1613/jair.2972.
46.
J.Rintanen, An iterative algorithm for synthesizing invariants, in: Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence, AAAI Press, 2000, pp. 806–811.
47.
G.Röger, S.Sievers and M.Katz, Symmetry-based task reduction for relaxed reachability analysis, in: Proceedings of the International Conference on Automated Planning and Scheduling, Vol. 28, 2018, pp. 208–217. doi:10.1609/icaps.v28i1.13904.
48.
E.D.Sacerdoti, The nonlinear nature of plans, in: Proceedings of the 4th International Joint Conference on Artificial Intelligence – Volume 1, IJCAI’75, 1975, pp. 206–214.
49.
J.Seipp and M.Helmert, Counterexample-guided Cartesian abstraction refinement, in: Proceedings of the International Conference on Automated Planning and Scheduling, Vol. 23, 2013, pp. 347–351. doi:10.1609/icaps.v23i1.13605.
50.
A.Shleyfman and P.Jonsson, Computational complexity of computing symmetries in finite-domain planning, Journal of Artificial Intelligence Research70 (2021), 1183–1221. doi:10.1613/jair.1.12283.
51.
A.Shleyfman, M.Katz, M.Helmert, S.Sievers and M.Wehrle, Heuristics and symmetries in classical planning, Proceedings of the AAAI Conference on Artificial Intelligence29(1) (2015). doi:10.1609/aaai.v29i1.9649.
52.
F.H.Siddiqui and P.Haslum, Block-structured plan deordering, in: AI 2012: Advances in Artificial Intelligence, Springer, Berlin Heidelberg, 2012, pp. 803–814. doi:10.1007/978-3-642-35101-3_68.
53.
F.H.Siddiqui and P.Haslum, Continuing plan quality optimisation, Journal of Artificial Intelligence Research54 (2015), 369–435. doi:10.1613/jair.4980.
54.
S.Sievers, G.Röger, M.Wehrle and M.Katz, Theoretical foundations for structural symmetries of lifted PDDL tasks, in: Proceedings of the International Conference on Automated Planning and Scheduling, Vol. 29, 2021, pp. 446–454. doi:10.1609/icaps.v29i1.3509.
55.
R.Simmons and H.Younes, VHPOP: Versatile heuristic partial order planner, Journal of Artificial Intelligence Research20 (062011). doi:10.1613/jair.1136.
56.
A.Tate, Generating project networks, in: Proceedings of the 5th International Joint Conference on Artificial Intelligence –Vol. 2, IJCAI’77, 1977, pp. 888–893.
57.
M.Veloso, M.Perez and J.Carbonell, Nonlinear planning with parallel resource allocation, in: Proceedings of the Workshop on Innovative Approaches to Planning, Scheduling and Control, Vol. 02, 2002.
58.
M.Waters, B.Nebel, L.Padgham and S.Sardina, Plan relaxation via action debinding and deordering, in: Proceedings of the International Conference on Automated Planning and Scheduling, Vol. 28, 2018, pp. 278–287. doi:10.1609/icaps.v28i1.13901.
59.
M.Waters, L.Padgham and S.Sardina, Optimising partial-order plans via action reinstantiation, in: Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI’20, 2020.
60.
M.Wehrle and M.Helmert, About partial order reduction in planning and computer aided verification, in: Proceedings of the International Conference on Automated Planning and Scheduling, Vol. 22, 2012, pp. 297–305. doi:10.1609/icaps.v22i1.13526.
61.
M.Wehrle and M.Helmert, Efficient stubborn sets: Generalized algorithms and selection strategies, in: Proceedings of the International Conference on Automated Planning and Scheduling, Vol. 24, 2014, pp. 323–331. doi:10.1609/icaps.v24i1.13638.
62.
D.S.Weld, An introduction to least commitment planning, AI Magazine15(4) (1994), 27. doi:10.1609/aimag.v15i4.1109.
63.
F.Wilcoxon, Individual Comparisons by Ranking Methods, Springer, New York, NY, 1992, pp. 196–202. doi:10.1007/978-1-4612-4380-9_16.
64.
E.Winner and M.Veloso, Analyzing plans with conditional effects, in: AIPS, 2002, pp. 23–33.
