|
The primary revolution in automated planning in the last decade has been the very impressive scaleup
in planner performance. A large part of the credit for this can be attributed squarely to the invention
and deployment of powerful reachability heuristics. Most, if not all, modern reachability heuristics are
based on a remarkably extensible data structure called the planning graph, which made its debut as
a bit player in the success of GraphPlan, but quickly grew in prominence to occupy the center stage.
Planning graphs are a cheap means to obtain informative look-ahead heuristics for search and have
become ubiquitous in state of the art heuristic search planners. We present the foundations of planning
graph heuristics in classical planning and explain how their flexibility lets them adapt to more expressive
scenarios that consider action costs, goal utility, numeric resources, time, and uncertainty.
| |
