Computing Upper Bounds on Lengths of Transition Sequences

Rintanen, Jussi; Gretton, Charles Orgill

Computing Upper Bounds on Lengths of Transition Sequences

Download BibTeX Cite

Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. Pages 2365-2371.

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.

Jussi Rintanen, and Charles Orgill Gretton. 2013. Computing Upper Bounds on Lengths of Transition Sequences. In Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13. IJCAI, 2365–2371. https://ijcai.org/proceedings/2013/348

@inproceedings{ijcai2013p348,
  title     = {Computing Upper Bounds on Lengths of Transition Sequences},
  author    = {Rintanen, Jussi and Gretton, Charles Orgill},
  booktitle = {Proceedings of the Twenty-Third International Joint Conference on
               Artificial Intelligence, {IJCAI-13}},
  publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
  editor    = {Francesca Rossi},
  pages     = {2365--2371},
  year      = {2013},
  month     = {8},
  url       = {https://ijcai.org/proceedings/2013/348},
}

TY  - CPAPER
TI  - Computing Upper Bounds on Lengths of Transition Sequences
AU  - Rintanen, Jussi
AU  - Gretton, Charles Orgill
T2  - Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13
PB  - AAAI Press / International Joint Conferences on Artificial Intelligence
PY  - 2013
SP  - 2365
EP  - 2371
UR  - https://ijcai.org/proceedings/2013/348
ER  -