Article Preview
Top1. Introduction
There has been made greatly advances in planning community due to the application of constraint satisfaction techniques (Alur, Henzinger and Vardi, 2015; Günay and Yolum, 2013) in recent years. Constraint-programmed planners (Bu, Zhang and Luo, 2016; Lozano-Perez and Kaelbling, 2014) code a planning problem into a constraint satisfaction problem (CSP) and then apply powerful CSP algorithm to inference and prune off. Clearly there are two benefits for this translation: one is the researchers can directly use the mature algorithms in CSP community with a constraint-programmed planner, and the second is AI planning and CSP stress on the different control theories respectively: planning emphasizes on search (Kautz and Selman, 1999) while CSP on inference (Veksler and Strichman, 2016). It has opened up a new way in planning community after the CSP technique brought in.
The method using CSP to solve planning problem rooted from an important technique (Kautz, Mcallester and Selman, 2003) that imposes a fixed bound on plan length, which converts the planning problem into NP (Non-Deterministic Polynomial) (Carnielli and Matulovic, 2014). So the resulting problem can then be solved by CSP, which is a NP-Complete formalism (Ghédira and Dubuisson, 2013). The first constraint-programmed planner is CPLAN (Van Beek and Chen, 2000) in 1999, with manually coded domain dependence constraints. Since then a lot of constraint-programmed planners have been developed which transfer kinds of classic planner such as GRAPHPLAN (Little and Thiébaux, 2006), HTN (Castillo, Fernández-Olivares and óscar, 2006), partial plan (Kapadia, Falk and Zünd, 2015) etc. into CSP formalism. Especially GP-CSP (Do and Kambhampati, 2001) can automatically converting a planning graph into a CSP encoding, which saves the human manually domain-setup and hand-coding cost.
Up to now, the research in constraint-programmed planning focuses on the coding of the translation and the extensions of CSP to meet the rich expressiveness of planning, such as: timeline (Cervantes, Rodríguez and López, 2013), possibility (Bodirsky, 2013), infinite data streams (Rosin, 2014) etc. However, considerably little work has been done in the solving method research, or CSP technique “planisation”. Without planning related guidance, the standard CSP heuristics and search methods (Stergiou, 2015; Wang and Patel, 2009) used in the planner above greatly restrict the efficiency of problem solving. In paper (Wang, 2014), a significant improvement has been made with a goal-centric CSP heuristic guidance. However, as it is stated in the paper, “a large problem comes an increased plan length (horizon), this large horizon greatly reduces the impact of the propagation resulting from the goal-state constraints.”