An Action Guided Constraint Satisfaction Technique for Planning Problem

An Action Guided Constraint Satisfaction Technique for Planning Problem

Xiao Jiang (Key Laboratory of Autonomous Navigation and Control for Deep Space Exploration, Ministry of Industry and Information Technology, School of Aerospace Engineering, Beijing Institute of Technology, Beijing, China), Pingyuan Cui (Key Laboratory of Autonomous Navigation and Control for Deep Space Exploration, Ministry of Industry and Information Technology, School of Aerospace Engineering, Beijing Institute of Technology, Beijing, China), Rui Xu (Key Laboratory of Autonomous Navigation and Control for Deep Space Exploration, Ministry of Industry and Information Technology, School of Aerospace Engineering, Beijing Institute of Technology, Beijing, China), Ai Gao (Key Laboratory of Autonomous Navigation and Control for Deep Space Exploration, Ministry of Industry and Information Technology, School of Aerospace Engineering, Beijing Institute of Technology, Beijing, China) and Shengying Zhu (Key Laboratory of Autonomous Navigation and Control for Deep Space Exploration, Ministry of Industry and Information Technology, School of Aerospace Engineering, Beijing Institute of Technology, Beijing, China)
DOI: 10.4018/IJSSCI.2016070103
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

This paper presents an action guided constraint satisfaction technique for planning problem. Different from the standard algorithms which are almost domain independence and cannot reflect the characteristics of the planning progress, this paper discusses how the action rules in planning act in constraint satisfaction problems. Based on the conclusion, an action directed constraint is proposed to guide the variable selected procedure in constraint satisfaction problems. Through theoretical analysis, this technique is prior an order of magnitude in variable select procedure over the ordinary heuristic technique and can be used in constraint-programmed planning problem generally. With the simulation experiments it shows that the algorithm with action guided constraint can effectively reduce the number of constraint checks during the planning procedure and has a better performance on total running time over the standard version.
Article Preview

1. 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.”

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 9: 4 Issues (2017): 3 Released, 1 Forthcoming
Volume 8: 4 Issues (2016)
Volume 7: 4 Issues (2015)
Volume 6: 4 Issues (2014)
Volume 5: 4 Issues (2013)
Volume 4: 4 Issues (2012)
Volume 3: 4 Issues (2011)
Volume 2: 4 Issues (2010)
Volume 1: 4 Issues (2009)
View Complete Journal Contents Listing