Rintanen, Jussi2015-12-08December 7http://hdl.handle.net/1885/30606Planning-specific heuristics for SAT have recently been shown to produce planners that match best earlier ones that use other search methods, including the until now dominant heuristic state-space search. The heuristics are simple and natural, and enforce pure depth-first search with backward chaining in the standard conflict-directed clause learning (CDCL) framework. In this work we consider alternatives to pure depth-first search, and show that carefully chosen randomized search order, which is not strictly depth-first, allows to leverage the intrinsic strengths of CDCL better, and will lead to a planner that clearly outperforms existing planners.Keywords: Backward chaining; Clause learning; Depth first; Depth first search; Heuristic planning; Intrinsic strength; Randomized search; Search method; State-space; Artificial intelligence; Planning; Heuristic methods201010.1007/978-3-642-17432-2_422016-02-24