Metraipolis › archive › dc_ac49641af90e

Learning How to Search for Plans with Exponentially Less Space — arXiv:2610.10954

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.10954
License (as archived)
CC0-1.0
Archived
2026-10-09T05:47:20.912Z
SHA-256 of the archived text
b54db2461a105516f63138752b3bf0bff1540198135312d0f7a4efa03e9fdef8
Stable URL of this page
https://metraipolis.com/documento/dc_ac49641af90e

How to cite

Learning How to Search for Plans with Exponentially Less Space — arXiv:2610.10954 — arXiv (en), https://arxiv.org/abs/2610.10954 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_ac49641af90e (Metraipolis archive dc_ac49641af90e, sha256 b54db2461a105516f63138752b3bf0bff1540198135312d0f7a4efa03e9fdef8)
BibTeX
@misc{dcac49641af90e,
  title = {Learning How to Search for Plans with Exponentially Less Space — arXiv:2610.10954},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.10954},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_ac49641af90e; sha256 b54db2461a105516f63138752b3bf0bff1540198135312d0f7a4efa03e9fdef8},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.10954. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Heuristic search for a plan can store exponentially many states, even when its heuristic is almost perfect. We instead learn search control, one specification per domain, written as an indexical policy: a generalized policy with registers that hold objects and modes that sequence its rules. We add the choose rule, which loads an object into a register and marks a backtracking point, where one candidate suffices; every other rule must work for all of its outcomes and needs no search. Our main result is that structural termination, which rules out infinite executions, also bounds every execution by a polynomial in the number of objects. A depth-first procedure then finds a plan in polynomial space, however large the state space, with no list of visited states. The cost is time, exponential only in the choice depth, the number of real choices along an execution. Any class that such a policy solves therefore lies in NP, and in P at constant choice depth. We learn these policies with a language model in a counterexample-guided loop that certifies termination, verifies the training tasks, and keeps the choice depth small. With the learned policies, the procedure solves 1,709 of 1,890 test tasks of the IPC 2023 Learning Track and the Autoscale Agile suite, more than LAMA, BFWS, and Levitron, and most of them within one second and 100 MiB.

Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.AI, nuovi lavori del giorno).
Categorie arXiv: Artificial Intelligence (cs.AI).
Pagina del lavoro: https://arxiv.org/abs/2610.10954 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-09T05:47:00.504Z dalla pagina https://arxiv.org/list/cs.AI/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).