Planning As CSP : A Transition Based Encoding

Abstract

Domain independent automated planning is hard. It has been shown that classical planning is PSPACE complete (Bylander 1994). But the bounded planning problem is in NP. Here bounded means restricting the planning problem by some means, such as plan length (number of actions in the solution) or the number of time steps (makespan). Kautz and Selman (1992) were the first to describe a polynomial reduction of a bounded planning problem to a SAT problem, which is also in NP. Since then the bounded planning problem has been compiled to other substrates such as CSP ( (Do & Kambhampati 2001), (Vidal & Geffner 2006)) and IP (Vossen et al. 1999). Most of these compilation approaches are based on the bounded horizon encoding, where a problem is bounded by the plan length or the makespan. The main problem with the bounded horizon encoding is that it is hard to guess an initial bound which is close to the solution. Usually the initial encoding is bounded by a lower bound. If it doesn’t have a solution then the bound is increased by a minimum amount and this process is repeated until the encoding has a solution. This approach is not very efficient for problems where the estimated lower bound is too far from the solution. So two questions remain: “Can we bound a problem, other than bounding the length or makespan, such that the initial encoding will likely to have a solution?” and “If the initial encoding fails, can we choose the next bound more intelligently?”. By intelligently, we mean guessing the next bound, which will increase the chance of having a solution, through analyzing the recent failures or the problem structures. Here we propose a technique for compiling a bounded planning problem into a CSP, which aims to answer the first question and set a direction for the second. In the proposed approach we construct a CSP from the Transition Based Encoding of the planning problem which is bounded by the number of times each action can occur in the plan. Initially we start with a bound of 1, which implies that each action can occur at most once in the plan. Many planning problems can be solved using each action at most once (Vidal & Geffner 2006). So the initial CSP encoding has a high chance of being solvable. If the initial CSP has no solution,

Topics

0 Figures and Tables

    Download Full PDF Version (Non-Commercial Use)