Learning Search Policies for Planning with Exponentially Less Space

Summary

Heuristic planning search can require exponentially large memory even when its heuristic is nearly perfect. This paper proposes learning one indexical policy per domain, using registers to hold objects and modes to sequence rules. A new choose rule selects one candidate and creates a backtracking point, while other rules must handle all of their outcomes without search. The authors show that structural termination bounds every execution by a polynomial in the number of objects. A depth-first procedure can therefore find a plan in polynomial space without maintaining a list of visited states, although its time can remain exponential in the choice depth, the number of genuine choices made during an execution. The solved problem classes fall within NP, and within P when choice depth is constant. The policies are learned with a language model in a counterexample-guided loop that checks termination, verifies training tasks, and seeks low choice depth. On the IPC 2023 Learning Track and Autoscale Agile suite, the resulting policies solve 1,709 of 1,890 test tasks, outperforming LAMA, BFWS, and Levitron; most are solved within one second and 100 MiB.