TY - JOUR AU - Abdulaziz, Mohammad PY - 2019/07/17 Y2 - 2024/03/28 TI - Plan-Length Bounds: Beyond 1-Way Dependency JF - Proceedings of the AAAI Conference on Artificial Intelligence JA - AAAI VL - 33 IS - 01 SE - AAAI Technical Track: Planning, Routing, and Scheduling DO - 10.1609/aaai.v33i01.33017502 UR - https://ojs.aaai.org/index.php/AAAI/article/view/4741 SP - 7502-7510 AB - <p>We consider the problem of compositionally computing upper bounds on lengths of plans. Following existing work, our approach is based on a decomposition of state-variable dependency graphs (a.k.a. causal graphs). Tight bounds have been demonstrated previously for problems where key dependencies flow in a single direction—i.e. manipulating variable <em>v</em><sub>1</sub> can disturb the ability to manipulate <em>v</em><sub>2</sub> and <em>not</em> vice versa. We develop a more general bounding approach which allows us to compute useful bounds where dependency flows in both directions. Our approach is practically most useful when combined with earlier approaches, where the computed bounds are substantially improved in a relatively broad variety of problems. When combined with an existing planning procedure, the improved bounds yield coverage improvements for both solvable and unsolvable planning problems.</p> ER -