Searching for Plans with Carefully Designed Probes

author: Nir Lipovetzky, Pompeu Fabra University
published: July 21, 2011,   recorded: June 2011,   views: 3342


Related Open Educational Resources

Related content

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
Lecture popularity: You need to login to cast your vote.


We define a probe to be a single action sequence computed greedily from a given state that either terminates in the goal or fails. We show that by designing these probes carefully using a number of existing and new polynomial techniques such as helpful actions, landmarks, commitments, and consistent subgoals, a single probe from the initial state solves by itself 683 out of 980 problems from previous IPCs, a number that compares well with the 627 problems solved by FF in EHC mode, with similar times and plan lengths. We also show that by launching one probe from each expanded state in a standard greedy best first search informed by the additive heuristic, the number of problems solved jumps to 900 (92%), as opposed to FF that solves 827 problems (84%),and LAMA that solves 879 (89%). The success of probes suggests that many domains can be solved easily once a suitable serialization of the landmarks is found, an observation that may open new connections between recent work in planning and more classical work concerning goal serialization and problem decomposition in planning and search.

See Also:

Download slides icon Download slides: icaps2011_lipovetzky_designed_01.pdf (2.1┬áMB)

Help icon Streaming Video Help

Link this page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Write your own review or comment:

make sure you have javascript enabled or clear this field: