טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentDweck Victor
SubjectEmpowering Inference and Undirected Search for Factored
Planning
DepartmentDepartment of Industrial Engineering and Management
Supervisor Professor Carmel Domshlak
Full Thesis textFull thesis text - English Version


Abstract

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:

  1. Encoding the planning problem as a sequence of constraint satisfaction problems (CSPs), and on
  2. 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.