Constraint Based Reasoning over Mutex Relations in Planning Graphs during Search

Abstract. We deal with the search process of the GraphPlan algorithm in this paper. We concentrate on the problem of finding supports for a sub-goal which arises during the search. We model the problem of finding supports as a constraint satisfaction problem in which arcconsistency or singleton arc-consistency is maintained. Contrary to other works on the similar topic, we do not model the whole planning problem as a CSP but only a small sub-problem within the standard solving process. Our model is based on dual views of the problem which are connected by channeling constraints. We performed experiments with several variants of propagation in the constraint model through channeling constraints. Experiments confirmed that the dual view of the problem enhanced with maintaining of arc-consistency is a good choice.