Date and time: 11.30am - 12.30pm, Friday 29th January, 2010
Venue: Floor 8, Building 14 (IS Common Area)
Abstract:
Decomposition methods that exploit bounded tree-width to achieve polynomial runtime have been successful in constraint satisfaction, inference in probabilistic networks, and combinatorial optimisation problems. However, attempts to apply such methods to (classical) AI planning - termed "factored planning" - have been far less successful. In part, this is because planning is a harder problem: bounding tree-width alone is not sufficient to obtain tractability. In part, it is because many planning problems - or at least many of the standard benchmark problems - are not well suited to decomposition. Previously proposed factored planning methods all impose some bound in addition to that on tree-width (typically, one related to plan length); moreover, those bounds are inextricably linked with the representations used, so that it is not possible to even consider the impact of relaxing these bounds within those methods. We examine a more general, not intrinsically bounded, form of factored planning, and show that the kind of length bounds previously considered are sufficient, but not necessary, to obtain tractability. We also examine a number of benchmark planning problems, and show that in a few cases, we can obtain decomposable problems by reformulating their (PDDL) encoding. However, we also find that even when this is the case, the factored planning method can still be very ineffective: examining the causes in detail leads us to some (as yet untried) ideas for how it can be improved.
About the speaker:
From Patrik's web page:
Now a researcher in the AI group,
College of Engineering and Computer Science at the
Australian National University,
Canberra.
(I also belong to the
Computer Science Lab,
insofar as it still exists as an organisational unit.)
I am also part-time seconded to
NICTA's
AI for the Smart Grid project.
Previously with NICTA, also in
Canberra.
And before that a PhD student at
Linköpings Universitet.
...and still working on planning.
Seminar Organisation
Seminars are free and open to the general public. No booking is necessary. If you are interested in giving a presentation in this seminar series, or to make suggestions for speakers, please contact Sebastian Sardina, the seminar co-ordinator.