Research map / Multi-agent systems and games / Human-AI and goal-conditioned
Generalising Planning Environment Redesign
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 a metric-agnostic environment redesign approach (BFS over action removals, pruned by top-quality planning plan-libraries) with new metrics for distance-based and privacy objectives, outperforming GRD-LS on goal transparency.
Problem
Planning environment redesign is usually metric-dependent and intractable, focusing on goal/plan recognition; the paper targets a general, metric-agnostic redesign that also supports other objectives such as privacy and distance-based constraints.
Approach
An anytime breadth-first search over action removals whose action space is pruned by a plan-library computed with top-quality planning (SYM-K), applicable to any metric; new metrics include goal/plan privacy (wcnd, wcpnd) and min/max average and min/max distance metrics.
Key results
- On goal transparency (wcd), the approach yields the same redesigned environments as GRD-LS but is about two orders of magnitude faster (e.g., 1.1s vs 119.9s on ipcgrid).
- The approach improved/optimised roughly 16% of problems for transparency and privacy metrics and 27.5% for distance-related metrics within 900 s.
- Across problems where a metric improvement was found, the approach returned on average 14.35 solutions.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use plan-library pruning and BFS redesign search instead of GRD-LS | General Environment Redesign vs. GRD-LS · IPC Grid | wcd planning time (s): 119.9/145.5 vs 1.1/0.2 | Helped |
| Use plan-library pruning and BFS redesign search instead of GRD-LS | General Environment Redesign vs. GRD-LS · Grid Navigation | wcd improvement: 2.2/1.0 vs 1.8/1.3 | Mixed |
| Redesign the environment to optimise goal transparency (minimise wcd) | General Environment Redesign · Blocks, Depots, Grid Navigation, IPC Grid | wcd improvement: 3.7/1.9; 4.0/0.0; 1.8/1.3; 8.5/10.4 | Helped |
| Redesign the environment to optimise plan transparency (minimise wcpd) | General Environment Redesign · Blocks, Depots, Grid Navigation, IPC Grid | wcpd improvement: 3.8/2.0; 5.2/1.0; 1.8/1.3; 7.7/10.1 | Helped |
| Redesign the environment to optimise goal privacy (maximise wcnd) | General Environment Redesign · Blocks, Depots, Grid Navigation, IPC Grid | wcnd improvement: 4.4/1.8; 4.0/1.5; 1.4/0.6; 3.0/0.0 | Helped |
| Redesign the environment to optimise plan privacy (maximise wcpnd) | General Environment Redesign · Blocks, Grid Navigation, IPC Grid | wcpnd improvement: 4.4/1.8; 1.4/0.6; 4.0/2.6 | Helped |
| Redesign the environment to minimise average distance | General Environment Redesign · Blocks, Depots, Grid Navigation, IPC Grid, Logistics | minAvgD improvement: 7.9/0.9; 6.6/1.0; 4.0/1.0; 13.2/3.8; 9.6/1.0 | Helped |
| Redesign the environment to maximise average distance | General Environment Redesign · Blocks, Depots, Grid Navigation, IPC Grid, Logistics | maxAvgD improvement: 8.9/1.1; 7.5/0.8; 4.9/1.1; 11.6/3.8; 10.5/1.4 | Helped |
| Redesign the environment to minimise maximum distance | General Environment Redesign · Blocks, Depots, Grid Navigation, IPC Grid | minMaxD improvement: 11.2/1.6; 9.8/0.4; 6.7/1.5; 17.7/3.2 | Helped |
| Redesign the environment to maximise minimum distance | General Environment Redesign · Blocks, Depots, Grid Navigation, IPC Grid, Logistics | maxMinD improvement: 4.8/0.7; 4.0/1.9; 2.0/1.1; 4.2/3.0; 5.0/1.0 | Helped |
| Use the proposed approach rather than GRD-LS | General Environment Redesign vs. GRD-LS · Blocks, Depots, Grid Navigation, IPC Grid | wcd improvement: 3.7/1.9 vs 3.7/1.9; 4.0/0.0 vs 4.0/0.0; 1.8/1.3 vs 2.2/1.0; 8.5/10.4 vs 8.5/10.4 | Mixed |
Surprising findings
- Redesigning for distance-based metrics was easier to improve than transparency and privacy metrics, which struggled in domains with many actions such as depots and logistics.
Limitations
- Only action removal is allowed as environment modification.
- Many optimal plans (e.g., gridnavigation) cause plan-library computation to consume the whole time budget.
- Transparency and privacy metrics improve for only a minority of problems in larger domains.
Experimental setup
Datasets: blocks world depots grid navigation ipc grid logistics
Benchmarks: environment redesign benchmark across blocks, depots, gridnavigation, ipcgrid, logistics
Metrics: wcd wcpd wcnd wcpnd minAvgD maxAvgD minMaxD maxMinD planning time improvement
Baselines: GRD-LS
Builds on: Goal Recognition Design Plan Recognition Design SYM-K Fast Downward
Closest papers by meaning
- Improving Environment Novelty Quantification for Effective Unsupervised Environment Design (NeurIPS 2024 · similarity 0.82)
- Leveraging Environment Interaction for Automated PDDL Translation and Planning with Large Language Models (NeurIPS 2024 · similarity 0.82)
- PathWise: Planning through World Model for Automated Heuristic Design via Self-Evolving LLMs (ICML 2026 · similarity 0.81)
- TodoEvolve: Learning to Architect Agent Planning Systems (ICML 2026 · similarity 0.81)
- When CEGAR Meets Regression: A Love Story in Optimal Classical Planning (AAAI 2024 · similarity 0.81)
- Marginal Benefit Driven RL Teacher for Unsupervised Environment Design (AAAI 2025 · 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.