Research map / Architectures and efficiency / Pruning and efficient tuning
Block-Level Goal Recognition Design
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 block-level goal recognition design, where grouped environment modifications (blocks, possibly hierarchical) replace single action removals, with a block-based pruned-reduce and a design subtree pruning rule to speed up WCD minimization.
Problem
Goal recognition design (GRD) seeks environment modifications that minimize worst case distinctiveness (WCD), but existing modifications (action removal, action conditioning) cannot express multi-edge design constraints and cause exhaustive enumeration over large design spaces.
Approach
Replace atomic modifications with blocks that substitute regional vertices in the search space and can contain child blocks, forming a hierarchical design model; extend pruned-reduce to blocks via possible invalidation and add a design subtree pruning rule based on lower and upper bounds of relative WCD.
Key results
- Block-based BFS with pruned-reduce and design subtree pruning is about an order of magnitude faster than the original BFS (e.g., LOGISTICS 23.67s vs 2.48s; GRID 37.64s vs 3.24s) with the same WCD.
- Local search is fastest (e.g., LOGISTICS 0.43s, GRID 0.52s) with slightly larger minimum WCD (LOGISTICS 8.5 vs 8.0).
- Pruned-reduce gives most of the speedup; design subtree pruning yields a smaller additional gain (e.g., LOGISTICS 2.61s to 2.48s with pruning rules combined).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the hierarchical design model with pruned-reduce and design subtree pruning instead of the original BFS | BFS · LOGISTICS | execution time (s): 23.67 -> 2.48 | Helped |
| Use the hierarchical design model with pruned-reduce and design subtree pruning instead of the original BFS | BFS · DEPOTS | execution time (s): 17.29 -> 0.80 | Helped |
| Use the hierarchical design model with pruned-reduce and design subtree pruning instead of the original BFS | BFS · GRID | execution time (s): 37.64 -> 3.24 | Helped |
| Use the hierarchical design model with pruned-reduce and design subtree pruning instead of the original BFS | BFS · DRIVERLOG | execution time (s): 16.80 -> 0.77 | Helped |
| Add pruned-reduce to BFS without pruning (ablation) | BFS · LOGISTICS | execution time (s): 20.80 -> 2.61 | Helped |
| Add design subtree pruning to BFS with pruned-reduce (ablation) | BFS · LOGISTICS | execution time (s): 2.61 -> 2.48 | Helped |
| Add pruned-reduce to BFS without pruning (ablation) | BFS · DEPOTS | execution time (s): 5.25 -> 0.89 | Helped |
| Add design subtree pruning to BFS with pruned-reduce (ablation) | BFS · DEPOTS | execution time (s): 0.89 -> 0.80 | Helped |
| Add pruned-reduce to BFS without pruning (ablation) | BFS · GRID | execution time (s): 33.02 -> 3.55 | Helped |
| Add design subtree pruning to BFS with pruned-reduce (ablation) | BFS · GRID | execution time (s): 3.55 -> 3.24 | Helped |
| Add pruned-reduce to BFS without pruning (ablation) | BFS · DRIVERLOG | execution time (s): 5.17 -> 0.82 | Helped |
| Add design subtree pruning to BFS with pruned-reduce (ablation) | BFS · DRIVERLOG | execution time (s): 0.82 -> 0.77 | Helped |
Surprising findings
- Design subtree pruning contributes much less speedup than block-based pruned-reduce, attributed to few junctions satisfying its condition.
Limitations
- Design subtree pruning gives limited gains in the experiments
- Local search returns suboptimal designs with somewhat higher WCD
- Only deterministic, fully observable classical planning settings are covered
Experimental setup
Datasets: IPC LOGISTICS IPC GRID IPC DEPOTS IPC DRIVERLOG
Benchmarks: LOGISTICS GRID DEPOTS DRIVERLOG
Metrics: execution time (s) minimum worst case distinctiveness (WCD)
Baselines: original BFS with pruned-reduce (Keren et al. 2014)
Builds on: goal recognition design (Keren et al. 2014) pruned-reduce strong stubborn sets for GRD hierarchical task network planning
Closest papers by meaning
- Extended Goal Recognition Design with First-Order Computation Tree Logic (AAAI 2022 · similarity 0.88)
- Landmark-Based Heuristics for Goal Recognition (AAAI 2017 · similarity 0.85)
- Stochastic Goal Recognition Design Problems with Suboptimal Agents (AAAI 2022 · similarity 0.85)
- Learning Domain-Independent Heuristics for Grounded and Lifted Planning (AAAI 2024 · similarity 0.82)
- Efficient Lookahead Encoding and Abstracted Width for Learning General Policies in Classical Planning (NeurIPS 2026 · similarity 0.81)
- Learning Planning Domains from Non-redundant Fully-Observed Traces: Theoretical Foundations and Complexity Analysis (AAAI 2024 · similarity 0.81)
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.