, The transition t 0 has the own eect (b, R) deleting (b, g) which clearly is not needed in the rest of P + (s); it has the side eect f g = 1 deleting f g = 0 which clearly is not needed in the rest of P + (s) Thus the oDG + -relevant deletes of t 0 are P + >0 (s)-recoverable. In case (b), similarly we can reorder P + (s) so that either (1) pickup(g, b, L) is the rst operator in P + (s), or (2) its only predecessor is move(R, L). The transition t 0 has the own eect (b, g) deleting (b, L) which clearly is not needed in the rest of P + (s) It has the side eect f g = 0 deleting f g = 1, that latter fact may be needed by other pickup operators in P + (s)
, which are applicable after board(l, c); drop(g, b, R) recovers f g = 1. Thus, again, the oDG + -relevant deletes of t 0 are P + >0 (s)-recoverable. Hence, in both cases, we can apply Theorem 2. cost d * (oDG + ) = 1 in cases (a1) and (b1), so there we get the bound 0, ro) = 2 in cases (a2) and (b2) so there we get the bound 1
, PLANNING, Computational Intelligence, vol.7, issue.3, p.625655, 1995.
DOI : 10.1016/0004-3702(94)90005-1
, Fast planning through planning graph analysis, Articial Intelligence, vol.90, issue.12, p.279298, 1997.
, Planning as heuristic search, Artificial Intelligence, vol.129, issue.1-2, p.533, 2001.
DOI : 10.1016/S0004-3702(01)00108-4
URL : http://doi.org/10.1016/s0004-3702(01)00108-4
, Using component abstraction for automatic generation of macro-actions, p.181190
, Structure and complexity in planning with unary operators, Journal of Articial Intelligence Research, vol.18, p.315349, 2003.
, The computational complexity of propositional STRIPS planning, Artificial Intelligence, vol.69, issue.1-2, p.165204, 1994.
DOI : 10.1016/0004-3702(94)90081-7
, Causal graphs and structurally restricted planning, Journal of Computer and System Sciences, vol.76, issue.7, p.579592, 2010.
DOI : 10.1016/j.jcss.2009.10.013
URL : http://doi.org/10.1016/j.jcss.2009.10.013
, Multi-agent oine coordination
, Exhibiting Knowledge in Planning Problems to Minimize State Encoding Length, Recent Advances in AI Planning. 5th European Conference on Planning (ECP'99), p.135147, 1999.
DOI : 10.1007/10720246_11
, The automatic inference of state invariants in TIM, Journal of Articial Intelligence Research, vol.9, p.367421, 1998.
, The detection and exploitation of symmetry in planning problems, Proceedings of the 16th International Joint Conference on Articial Intelligence (IJCAI-99), p.956961, 1999.
, Computers and IntractabilityA Guide to the Theory of NP-Completeness, 1979.
, Amedeo Cesta, and Ioannis Refanidis, Proceedings of the 19th International Conference on Automated Planning and Scheduling (ICAPS9), 2009.
, Planning through stochastic local search and temporal action graphs, Journal of Articial Intelligence Research, vol.20, p.239290, 2003.
, Inferring state-constraints for domain independent planning, Proceedings of the 15th National Conference of the American Association for Articial Intelligence (AAAI-98), p.905912, 1998.
, The complexity of planning problems with simple causal graphs, Journal of Articial Intelligence Research, vol.31, p.319351, 2008.
, The inuence of k-dependence on the complexity of planning, Gerevini et al. [15], p.138145
, Planning over chain causal graphs for variables with domains of size 5 is NP-hard, Journal of Articial Intelligence Research, vol.34, p.675706, 2009.
, Heuristic planning with time and resources, Cesta and Borrajo, p.121132
, Reducing accidental complexity in planning problems, Proceedings of the 20th International Joint Conference on Articial Intelligence (IJCAI-07), pages 18981903, 2007.
, Complexity results for standard benchmark domains in planning, Artificial Intelligence, vol.143, issue.2, p.219262, 2003.
DOI : 10.1016/S0004-3702(02)00364-8
, A planning heuristic based on causal graph analysis, p.161170
, The fast downward planning system, Journal of Articial Intelligence Research, vol.26, 2006.
, Landmarks, critical paths and abstractions: What's the dierence anyway?, p.162169
, Local search topology in planning benchmarks: An empirical analysis, Proceedings of the 17th International Joint Conference on Articial Intelligence (IJCAI-01), p.453458, 2001.
, Utilizing Problem Structure in Planning: A Local Search Approach, volume 2854 of Lecture Notes in Articial Intelligence, 2003.
, Wherèignoring delete lists' works: Local search topology in planning benchmarks, Journal of Articial Intelligence Research, vol.24, pp.685-758, 2005.
, The FF planning system: Fast plan generation through heuristic search, Journal of Articial Intelligence Research, vol.14, p.253302, 2001.
, RIFO revisited: Detecting relaxed irrelevance, Cesta and Borrajo, p.325336
, Ordered landmarks in planning, Journal of Articial Intelligence Research, vol.22, p.215278, 2004.
, The role of macros in tractable planning, Journal of Articial Intelligence Research, vol.36, p.471511, 2009.
, Incremental planning, European Workshop on Planning, 1995.
, State-variable planning under structural restrictions: algorithms and complexity, Artificial Intelligence, vol.100, issue.1-2, p.125176, 1998.
DOI : 10.1016/S0004-3702(98)00003-4
URL : http://doi.org/10.1016/s0004-3702(98)00003-4
, Cost-optimal planning with land- marks
, New islands of tractability of costoptimal planning, Journal of Articial Intelligence Research, vol.32, p.203288, 2008.
, Structural patterns heuristics via fork decomposition, Proceedings of the 18th International Conference on Automated Planning and Scheduling (ICAPS-10), p.182189, 2008.
, Automatically generating abstractions for planning, Artificial Intelligence, vol.68, issue.2, p.243302, 1994.
DOI : 10.1016/0004-3702(94)90069-8
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.32.4337
, Automatic synthesis and use of generic types in planning, Proceedings of the 5th International Conference on Articial Intelligence Planning Systems (AIPS-00), 2000.
, Using regression-match graphs to control search in planning, Articial Intelligence, vol.109, issue.12, p.111159, 1999.
, Ignoring irrelevant facts and operators in plan generation, Recent Advances in AI Planning. 4th European Conference on Planning, p.338350, 1997.
DOI : 10.1007/3-540-63912-8_97
, Landmarks revisited, Proceedings of the 23rd National Conference of the American Association for Articial Intelligence (AAAI-08), p.975982, 2008.
, The LAMA planner: Guiding costbased anytime planning with landmarks, Journal of Articial Intelligence Research, vol.39, p.127177, 2010.
, An iterative algorithm for synthesizing invariants, Proceedings of the 17th National Conference of the American Association for Articial Intelligence (AAAI-00), p.806811, 2000.
, Learning from planner performance, Artificial Intelligence, vol.173, issue.5-6, p.636561, 2009.
DOI : 10.1016/j.artint.2008.11.009
URL : http://doi.org/10.1016/j.artint.2008.11.009
, A lookahead strategy for heuristic search planning, p.150160
, A reactive planner for a model-based executive, Proceedings of the 15th International Joint Conference on Articial Intelligence (IJCAI-97, p.11781185, 1997.
, Technopôle de Nancy-Brabois -Campus scientifique 615, rue du Jardin Botanique -BP 101 -54602 Villers-lès