G-value Plateaus: A Challenge for Planning

Recent years have seen the development of several scalable planners, many of which follow the string of successes found in using heuristic, best-first search methods. While this provides positive reinforcement for continuing work along these lines, fundamental problems arise when handling objectives whose value does not change with each search operation. An extreme case of this occurs when handling the objective of generating a temporal plan with short makespan. Typically used heuristic search methods assume strictly positive edge costs for their guarantees on completeness and optimality to hold, while the usual "fattening" and "advance time" steps of heuristic search algorithms for temporal planning have the potential for zero-cost edges, resulting in "g-value plateaus". In this paper we point out some underlying difficulties with using modern heuristic search methods for optimizing makespan and discuss how the presence of these problems contributes to the poor performance of makespan-optimizing heuristic search planners. To further illustrate this, we show empirical results on recent benchmarks using a planner made with makespan optimization in mind.