Searching for plans with carefully designed probes

Lipovetzky, Nir; Geffner, Héctor

Searching for plans with carefully designed probes

Citation

Lipovetzky N, Geffner H. Searching for plans with carefully designed probes. In: Proceedings of the Twenty-First International Conference on Automated Planning and Scheduling; 2011 Jun 11-16 2011; Freiburg, Germany. Palo Alto: AAAI Press; 2011. p. 154-61.

Abstract

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.

Description

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.