Width and serialization of classical planning problems

Geffner, Héctor; Lipovetzky, Nir

doi:http://dx.doi.org/10.3233/978-1-61499-098-7-540

Width and serialization of classical planning problems

Citació

Lipovetzky, Nir, Geffner, Hector. Width and serialization of classical planning problems. Frontiers in artificial intelligence and applications. ECAI 2012; 242: 540-545. DOI 10.3233/978-1-61499-098-7-540

Resum

We introduce a width parameter that bounds the complexity of classical planning problems and domains, along with a simple but effective blind-search procedure that runs in time that is exponential in the problem width. We show that many benchmark domains have a bounded and small width provided thatgoals are restricted to single atoms, and hence that such problems are provably solvable in low polynomial time. We then focus on the practical value of these ideas over the existing benchmarks which feature conjunctive goals. We show that the blind-search procedure can be used for both serializing the goal into subgoals and for solving the resulting problems, resulting in a ‘blind’ planner that competes well with a best-first search planner guided by state-of-the-art heuristics. In addition, ideas like helpful actions and landmarks can be integrated as well, producing a planner with state-of-the-art performance.