Research map / Learning theory and algorithms / Combinatorial and search optimization
An Automatic Sound and Complete Abstraction Method for Generalized Planning with Baggable Types
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes an automatic abstraction from classical planning instances with baggable types into bounded QNP (BQNP, numeric variables change by one), with a sound-but-incomplete BQNP termination test and solver, and proves soundness and completeness for proper baggable domains.
Problem
Generalized planning needs abstractions that are both sound and complete, but existing automatic abstraction methods for generalized planning cannot guarantee soundness, let alone completeness. Also, QNP cannot encode numeric constraints among counters.
Approach
Introduce a counter for each bag (extended attribute-value vector over indistinguishable objects of baggable types) and restrict numeric updates to ±1 (BQNP), yielding a sound and complete abstraction for proper baggable domains; add a sound-but-incomplete termination test for BQNP policies built on SIEVE.
Key results
- ABS produces BQNP abstractions quickly; e.g. Nomystery with about 10^8 ground actions abstracted in seconds, with abstract actions and variables reduced by 50% to 99% relative to ground actions and atoms.
- The naive BQNP solver BQS solves small instances such as Gripper-HL prob1-1 in about 16 s, but runs out of time or memory on larger ones (Logistics, Transport, Elevators, Floortile, Nomystery, Zenotravel).
- The paper claims the BQNP abstraction is sound and complete for proper baggable domains, though the BQNP solver is incomplete and scales poorly.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use ABS to generate BQNP abstractions from planning instances | ABS · the evaluated planning domains | abstraction time | Helped |
| Use BQS to solve the generated BQNP problems | BQS · the evaluated planning domains | solving completion | Mixed |
| Solve policies with actions affecting many variables | BQS · Gripper-Sim, Gripper-HL, and Ferry | memory use | Hurt |
| Remove unchanged facts and conflicting numeric variables and actions during abstraction | ABS · domains including Transport and Elevators | number of abstract actions and variables: reduced by 50% to 99% | Helped |
Surprising findings
- BQS can solve some BQNP problems that QNP solvers such as DSET or FONDASP cannot solve.
- The BQNP solver does not scale: it hits timeouts or memory limits on most of the larger benchmark problems.
Limitations
- BQNP is undecidable, so the termination test and solver are sound but incomplete.
- The naive BQNP solver BQS scales poorly and fails on many larger domains.
- Soundness and completeness are shown only for proper baggable domains, where every action schema is atomic.
Experimental setup
Datasets: Gripper TyreWorld Ferry Logistics Transport Elevators Floortile Nomystery Zenotravel
Benchmarks: Gripper-Sim Gripper-HL Gripper-HLWB TyreWorld Ferry Logistics Transport Elevators Floortile Nomystery Zenotravel
Metrics: abstraction time number of abstract variables and actions BQNP solving time reduction in ground actions and atoms
Baselines: DSET FONDASP
Builds on: QNP SIEVE DSET Cui et al. uniform abstraction framework for generalized planning Golog
Closest papers by meaning
- Towards Practical Classical Planning Compilations of Numeric Planning (AAAI 2025 · similarity 0.87)
- Symbolic Numeric Planning with Patterns (AAAI 2024 · similarity 0.87)
- PDBs Go Numeric: Pattern-Database Heuristics for Simple Numeric Planning (AAAI 2025 · similarity 0.85)
- On the Computational Complexity of Plan Verification, (Bounded) Plan-Optimality Verification, and Bounded Plan Existence (AAAI 2024 · similarity 0.85)
- Planning Anything with Rigor: General-Purpose Zero-Shot Planning with LLM-based Formalized Programming (ICLR 2025 · similarity 0.84)
- Thought of Search: Planning with Language Models Through The Lens of Efficiency (NeurIPS 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.