Symmetry Breaking: Satisficing Planning and Landmark Heuristics
Carmel Domshlak, Michael Katz, Alexander Shleyfman · Proceedings of the International Conference on Automated Planning and Scheduling · 2013
Searching for computational tools that can further push the boundary of satisficing planning, we show that reasoning about state-space symmetries can substantially improve even the most effective heuristic-search satisficing planners, with respect to all standard performance measures. The improvement comes from the state-space pruning, as well as from transparent cost-to-state updates and heuristic enhancement by information obtained during the search at different symmetric states.