---
title: "Computing Upper Bounds on Lengths of Transition Sequences"
authors:
  - "Jussi Rintanen"
  - "Charles Orgill Gretton"
doi: ""
url: "https://ijcai.org/proceedings/2013/348"
pdf: "https://ijcai.org/proceedings/2013/0348.pdf"
venue: "Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence"
year: 2013
pages: "2365-2371"
track: ""
keywords:
---

# Computing Upper Bounds on Lengths of Transition Sequences

Jussi Rintanen, Charles Orgill Gretton

*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.