M.Sc Student | Dweck Victor |
---|---|

Subject | Empowering Inference and Undirected Search for Factored Planning |

Department | Department of Industrial Engineering and Management |

Supervisor | Professor Carmel Domshlak |

Full Thesis text |

The field of *automated, domain-independent
planning* aims on building algorithms able to *synthesize a course of action* to achieve certain
goals and/or exhibit desirable behaviors. In general, planning algorithms
perform reachability analysis in large-scale state models that are implicitly
described in a concise manner via some intuitive declarative language. The
classical case attempts to transform a system with deterministic dynamics from
a given initial state into a goal state. Such a planning problem is defined by
four elements: (1) a set of state variables and their domains, describing the
possible states of the system, (2) a set of actions, or operators, defining
which ways we have of changing the state of the system, (3) an initial state,
given by a complete assignment to the state variables, and (4) a description of
goal states.

*Factored planning *suggests exploring
independence within a planning problem in order to decompose the domain into
sub-domains, and workout a global solution piecing together the sub-plans
obtained for each sub-domain. The state spaces of such problems are huge,
exponential in the number of state variables. Treating subspaces as factors may
turn cost of solution to sub-plans exponentially cheaper at the expense of
adding a new cost to combine the sub-plans into a global solution. Following
Brafman and Domshlak [4], in this work we apply a vertical factorization to
solve deterministic planning problems, transforming each state space variable
into a factor itself. We develop an undirected-search algorithm for factored
planning that is based on:

- Encoding the
planning problem as a sequence of
*constraint satisfaction problems*(CSPs), and on - Solving the resulting CSPs while exploiting the specificities of the planning problems for effective branching and propagation.

The latter encompasses new methods of inference and search for this type of CSP, and is the major contribution of this thesis. Our empirical evaluation testifies for the effectiveness of the suggested techniques, resulting in orders of magnitude speedups in solving factored planning problems.