A new goal ordering for incremental planning

Goal ordering is very important for the incremental planning, and special attention has been paid to determine the ordering constraints between the atomic goals to achieve the orderings for all possible plans. However, not all goal orderings work well on most benchmarks. This paper introduces a new-class goal ordering, called the admissible goal ordering, which is less restrictive and matches with the characteristics of most benchmarks better than the existing goal orderings. Since the proposed ordering relation is hard to decide, an approximate approach for computing the admissible ordering relation that can be determined in polynomial time is presented. Furthermore, an algorithm for extraction of the total-ordered subsets of goals based on the admissible relation is developed. The total-ordered subsets lead to the partition of an original task into smaller subtasks that can be incrementally planned. The experimental results obtained by using almost all propositional STRIPS benchmarks from the international planning competitions show that the proposed goal ordering can significantly improve the planning performance compared with the state-of-the-art satisficing planning system. In comparison with the reasonable ordering and no-goal ordering, the performance improvements in the proposed ordering are substantial and almost dramatic on larger tasks.