TY - GEN
T1 - Cost-optimal factored planning
T2 - 20th International Conference on Automated Planning and Scheduling, ICAPS 2010
AU - Fabre, Eric
AU - Jezequel, Loïg
AU - Haslum, Patrik
AU - Thiébaux, Sylvie
PY - 2010
Y1 - 2010
N2 - Factored planning methods aim to exploit locality to efficiently solve large but "loosely coupled" planning problems by computing solutions locally and propagating limited information between components. However, all factored planning methods presented so far work with representations that require certain parameters to be bounded (e.g. number of coordination points between local plans considered); the satisfaction of those bounds by a given problem instance is difficult to establish a priori, and the influence of those parameters on the problem complexity is unclear. We present an instance of the factored planning framework using a representation of the (regular) sets of local plans by finite automata, which does not require any such bound. By substituting weighted automata, we can even do factored cost-optimal planning. We test an implementation of the method on the few standard planning benchmarks that we have found to be amenable to factoring. We show that this method runs in polynomial time under conditions similar to those considered in previous work, but not only under those conditions. Thus, what constitutes an essential measure of "factorability" remains obscure.
AB - Factored planning methods aim to exploit locality to efficiently solve large but "loosely coupled" planning problems by computing solutions locally and propagating limited information between components. However, all factored planning methods presented so far work with representations that require certain parameters to be bounded (e.g. number of coordination points between local plans considered); the satisfaction of those bounds by a given problem instance is difficult to establish a priori, and the influence of those parameters on the problem complexity is unclear. We present an instance of the factored planning framework using a representation of the (regular) sets of local plans by finite automata, which does not require any such bound. By substituting weighted automata, we can even do factored cost-optimal planning. We test an implementation of the method on the few standard planning benchmarks that we have found to be amenable to factoring. We show that this method runs in polynomial time under conditions similar to those considered in previous work, but not only under those conditions. Thus, what constitutes an essential measure of "factorability" remains obscure.
UR - http://www.scopus.com/inward/record.url?scp=78650592149&partnerID=8YFLogxK
M3 - Conference contribution
SN - 9781577354499
T3 - ICAPS 2010 - Proceedings of the 20th International Conference on Automated Planning and Scheduling
SP - 65
EP - 72
BT - ICAPS 2010 - Proceedings of the 20th International Conference on Automated Planning and Scheduling
Y2 - 12 May 2010 through 16 May 2010
ER -