Research map / Learning theory and algorithms / Combinatorial and search optimization
Suboptimal Search with Dynamic Distribution of Suboptimality
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 DSWA*, a bounded-suboptimal search that dynamically assigns suboptimality weights to regions of the h-g plane at runtime while avoiding re-expansions.
Problem
Bounded-suboptimal heuristic search where the distribution of suboptimality across the search is fixed in existing re-expansion-free priority functions (XDP, XUP, PWXD, PWXU), which performs poorly when costs are not captured by the heuristic.
Approach
Builds a piecewise priority function Φ incrementally: each region of the h-g plane (bounded by rays from the origin) gets its own weight chosen by a runtime policy (Greedy, Half Edge Drop, Dynamically Weighted, Moving Average) based on search properties, under a never-re-open constraint that keeps the overall bound w.
Key results
- DSWA* policies show robust performance across domains and suboptimality bounds, with ranking rarely changing as bound increases.
- In DW Random 10% and DW STP, DSWA* performs almost ten times better than the best baseline across all suboptimality bounds (95% confidence).
- With a differential heuristic on DW maze maps, MAP and DWP significantly outperform other baselines, indicating octile heuristic weakness limits DSWA* there.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use DSWA* with DWP instead of the strongest baseline | DSWA* · DW Random 10% and DW STP | node expansions: almost ten times better | Helped |
| Use DSWA* with DWP or MAP instead of baseline algorithms | DSWA* · DW Mazes32 with differential heuristic | node expansions | Helped |
| Use DSWA* with DWP instead of baseline algorithms | DSWA* · Dynamically weighted domains | node expansions | Helped |
| Use DSWA* with MAP instead of baseline algorithms | DSWA* · DW Random 10 | node expansions | Helped |
| Replace the octile heuristic with a differential heuristic using 10 pivots (ablation) | DSWA* with MAP and DWP · DW Mazes32 | node expansions | Helped |
| Use constant-time region lookups instead of linear scans (ablation) | DSWA* · Grid domains | expansion rate: from 50% slower than the baseline algorithms to 20% slower | Helped |
| Use constant-time region lookups instead of linear scans (ablation) | DSWA* · DW STP | runtime | No clear effect |
| Use the Half Edge Drop Policy instead of the Greedy Policy (ablation) | DSWA* · Search domains discussed in the policy evaluation | node expansions | Helped |
| Use the Greedy Policy instead of the other proposed policies (ablation) | DSWA* · Search domains discussed in the policy evaluation | node expansions | Hurt |
| Use DSWA* instead of fixed-weight or fixed-distribution baselines | DSWA* · Across evaluated domains and suboptimality bounds | node expansions | Helped |
| Use DSWA* with DWP in domains without dynamic costs | DSWA* · Domains without dynamic costs | node expansions | Mixed |
Surprising findings
- The HEDP policy, which seemed promising, was not as strong as other proposed policies.
- DSWA* performs poorly in DW Mazes32+Octile because weak heuristics with very low h values trap the search in local minima where weights cannot be adjusted.
Limitations
- Performance depends on heuristic accuracy; weak heuristics in mazes cause local minima that cannot be escaped by weight adjustment.
- No single policy is uniformly best across domains.
- Runtime overhead of region lookup in grid domains (up to 50% slower per expansion with linear scan).
Experimental setup
Datasets: MovingAI grid maps (Dragon Age 2, Random, Mazes) Korf 100 sliding tile puzzle instances RaceTrack maps
Benchmarks: MovingAI DA2 maps Random maps Mazes maps Sliding Tile Puzzle (unit, squared, square-root costs) RaceTrack dynamically weighted DW Random 10%, DW STP, DW Mazes
Metrics: average node expansions to find solutions within suboptimali
Baselines: WA* XDP XUP PWXD PWXU DPS
Builds on: Weighted A* XDP BFS-NR Dynamic Potential Search
Closest papers by meaning
- Anchor Search: A Unified Framework for Suboptimal Bidirectional Search (AAAI 2025 · similarity 0.85)
- Runtime Analysis for Multi-Objective Evolutionary Algorithms in Unbounded Integer Spaces (AAAI 2025 · similarity 0.82)
- Corporate Needs You to Find the Difference: Revisiting Submodular and Supermodular Ratio Optimization Problems (NeurIPS 2025 · similarity 0.82)
- Consistent Submodular Maximization (ICML 2024 · similarity 0.82)
- A Dynamic Algorithm for Weighted Submodular Cover Problem (ICML 2024 · similarity 0.81)
- This Too Shall Pass: Removing Stale Observations in Dynamic Bayesian Optimization (NeurIPS 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.