TY - GEN
T1 - Computing upper bounds on lengths of transition sequences
AU - Rintanen, Jussi
AU - Gretton, Charles Orgill
PY - 2013
Y1 - 2013
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84896064226&partnerID=8YFLogxK
M3 - Conference contribution
SN - 9781577356332
T3 - IJCAI International Joint Conference on Artificial Intelligence
SP - 2365
EP - 2372
BT - IJCAI 2013 - Proceedings of the 23rd International Joint Conference on Artificial Intelligence
T2 - 23rd International Joint Conference on Artificial Intelligence, IJCAI 2013
Y2 - 3 August 2013 through 9 August 2013
ER -