Computing Upper Bounds on Lengths of Transition Sequences
Abstract
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.
Cite
Text
Rintanen and Gretton. "Computing Upper Bounds on Lengths of Transition Sequences." International Joint Conference on Artificial Intelligence, 2013.Markdown
[Rintanen and Gretton. "Computing Upper Bounds on Lengths of Transition Sequences." International Joint Conference on Artificial Intelligence, 2013.](https://mlanthology.org/ijcai/2013/rintanen2013ijcai-computing/)BibTeX
@inproceedings{rintanen2013ijcai-computing,
title = {{Computing Upper Bounds on Lengths of Transition Sequences}},
author = {Rintanen, Jussi and Gretton, Charles Orgill},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2013},
pages = {2365-2372},
url = {https://mlanthology.org/ijcai/2013/rintanen2013ijcai-computing/}
}