Lifted Heuristics

: Towards more scalable Planning Systems

Abstract

In this work we present a new lifted forward-chaining planning system which uses new heuristics and introduces novel pruning techniques which can solve problem instances which - until now - cannot be solved by contemporary planners due to grounding. State-of-the-art planning systems rely on grounding, enumerating all possible actions, before search can begin. Grounding is a necessary step for these planners because their domain analysis, heuristic computation, pruning strategies and even search strategies need this information as a prerequisite. This grounding step is an essential step for most (if not all) state-of-the-art planning systems. A few planning systems use lazy evaluation which means that an action is only grounded when it is needed. But in these strategies, for most domains, the set of actions that need to be grounded are all the actions so this does not solve the underlying problem.
This thesis presents two new heuristics - called lifted relaxed planning graph heuristic and lifted causal graph heuristic - that do not require the planning domain to be grounded. This makes our planning system applicable to larger problem instances because we have smaller memory constraints compared to state-of-the-art forward chaining planners. Heuristics have been presented in the past which did not require grounding (for example least-commitment planners like Partial-Order Planners), but the weakness of their heuristics prevents them to compete with the state of the art. The heuristics presented in this thesis compare favourably to the state-of-the-art. We build on previous work done on symmetry breaking in order to abstract the planning problem and prune the search space. Symmetry relationships explored in the past are quite restrictive and are only useful in problems which are highly symmetrical. We relax this definition and build upon almost symmetry which finds more symmetrical relationships and allows us to construct the data structures like the lifted relaxed planning graph and lifted transition graph using less memory and time.

Date of Award	Jan 2014
Original language	English
Awarding Institution	King's College London
Supervisor	Maria Fox (Supervisor) & Derek Long (Supervisor)