Computing Upper Bounds on Lengths of Transition Sequences

摘要

We describe an approach to computing upper bounds on the lengths of solutions to reachability problems in transition systems.It is based on a decomposition of state-variable dependency graphs (causal graphs).Our approach is able to find practical upper bounds in a number of planning benchmarks.Computing the bounds is computationally cheap in practice,and in a number of benchmarks our algorithm runs in polynomial time in the number of actions and propositional variables that characterize the problem.