Introducing Simulated Annealing in Partial Order Planning

摘要

One of the most popular algorithms in the field of domain independent planning is POP - partial order planning. POP considers a least commitment strategy to solve planning problems. Such strategy delays commitments during the planning phase until it is absolutely necessary. In consequence, the algorithm provides greater flexibility for solving planning problems, but with a higher cost in performance. POP-based techniques do not consider search states, instead, search nodes represent partial plans. Recent advances in planning on distance based heuristics and reach ability analysis have helped POP planners to solve more planning problems than before. Although such heuristic techniques have demonstrated to boost performance for POP algorithms, they still remain behind state space planners. We believe that this is mainly due to the partial order representation of the search nodes in POP. In this article, instead of proposing additional heuristics for POP, we enable POP to consider different areas of its search space. We think that the basic POP algorithm follows a greedy path in its search space suffering from local optima problems, from where it cannot recover. To this extent, we have augmented POP with a simulated annealing procedure, which considers worst solutions with certain probability. The augmented algorithm produces promising results in our empirical evaluation, returning up to 19% more solutions in the problems being considered.