Thumbnail
Access Restriction
Open

Author Bryce, Daniel ♦ Kambhampati, Subbarao
Source CiteSeerX
Content type Text
File Format PDF
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Reachability Heuristic ♦ Agent Goal ♦ Considerable Work ♦ Many Different Way ♦ Sophisticated Reachability Heuristic ♦ Revolutionary Shift ♦ Informative Look-ahead Heuristic ♦ Impressive Scaleup ♦ Reasonable Length Plan ♦ Classical Planning ♦ Expressive Scenario ♦ Extensible Data Structure ♦ State-of-the-art Heuristic Search Planner ♦ Multiple Search Regime ♦ Large Part ♦ Graph Heuristic ♦ Goal State ♦ Primary Revolution ♦ Last Decade ♦ Bit Player ♦ Reachability Analysis ♦ Current Search State ♦ Wide Variety ♦ Planning Graph ♦ Powerful Reachability Heuristic ♦ Planner Performance ♦ Plan-synthesis Problem ♦ Modern Reachability Heuristic ♦ Automated Planning ♦ Action Cost ♦ Stringent Restriction ♦ Center Stage ♦ Central Endeavor ♦ Goal Utility ♦ Numeric Resource ♦ Graph-based Reachability Heuristic
Description ■ 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. Synthesizing plans capable of achieving an agent’s goals has always been a central endeavor in AI. Considerable work has been done in the last 40 years on modeling a wide variety of plan-synthesis problems and developing multiple search regimes for driving the synthesis itself. Despite this progress, the ability to synthesize reasonable length plans under even the most stringent restrictions remained severely limited. This state of affairs has changed quite dramatically in the last decade, giving rise to planners that can routinely generate plans with hundreds of actions. This revolutionary shift in scalability can be attributed in large part to the use of sophisticated reachability heuristics to guide the planners’ search. Reachability heuristics aim to estimate the cost of a plan between the current search state and the goal state. While reachability analysis can be carried out in many different ways
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Learning Resource Type Article
Publisher Date 2007-01-01
Publisher Institution AI Magazine 28(1): 47–83. Defense Advanced Research Projects Agency (DARPA