Searching for plans with carefully designed probes

Comunicació presentada a: 21st International Conference on Automated Planning and Scheduling (ICAPS) celebrada de l'11 al 16 de juny de 2011 a Freiburg, Alemanya.We define a probe to be a single action sequence computedgreedily from a given state that either terminates in the goalor fails. We show that by designing these probes carefullyusing a number of existing and new polynomial techniquessuch as helpful actions, landmarks, commitments, and con-sistent subgoals, a single probe from the initial state solvesby itself 683 out of 980 problems from previous IPCs, a num-ber that compares well with the 627 problems solved by FFin EHC mode, with similar times and plan lengths. We alsoshow that by launching one probe from each expanded statein a standard greedy best first search informed by the addi-tive 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 probessuggests that many domains can be solved easily once a suit-able serialization of the landmarks is found, an observationthat may open new connections between recent work in plan-ning and more classical work concerning goal serializationand problem decomposition in planning and search.This work is partially supported by grants TIN2009-10232, MICINN, Spain, and EC-7PM-SpaceBook