Maintaining Arc-consistency over Mutex Relations in Planning Graphs during Search

Pavel Surynek, Roman Bartak

We deal with the search process of the GraphPlan algorithm in this paper. We concentrate on a 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 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.

Subjects: 1.11 Planning; 15.7 Search

Submitted: Feb 8, 2007

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.