Heuristically guided constraint satisfaction for AI planning
Mark Judge · STAX · 2015
Constraint satisfaction techniques have been used in Artificial Intelligence planning for many years. As with the original planning problem formulation, the CSP model’s complexity can lead to a very large search space for all but the simplest of problems. Without additional guidance, the CSP solver will rely on standard CSP heuristics and search methods. Better use can be made of the CSP framework if the search is informed by the structure of the planning problem. This paper discusses a goal-centric, variable / value selection heuristic method of guiding the search for a solution to a constraint encoding of classical planning problems. Also, meta-CSP methods that provide further propagation are introduced. The prototype uses an extensional encoding of the problem, goal ordering, the variable / value ordering heuristic and the metaCSP variables. Preliminary results on a number of test domains are presented. These show an improvement over the same encoding without heuristic guidance.