Maintaining Arc-Consistency over Mutex Relations in Planning Graphs during Search.
Pavel Surynek, Roman Barták · 2007
We deal with the search process of the GraphPlan algorithm in this paper. We concentrate on a problem of finding sup-ports for a sub-goal which arises during the search. We model the problem of finding supports as a constraint satis-faction problem in which 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 con-nected by channeling constraints. We performed experi-ments with several variants of propagation in the constraint model through channeling constraints. Experiments con-firmed that the dual view of the problem enhanced with maintaining of arc-consistency is a good choice.