Research map / Learning theory and algorithms / Combinatorial and search optimization
Rectangle Search: An Anytime Beam Search
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 rectangle search, an interruptible anytime heuristic search built on beam-style breadth-first exploration that iteratively widens and deepens a monobead-like search, and evaluates it against best-first anytime algorithms and fixed-width beam search on classic benchmarks.
Problem
Anytime heuristic search has been dominated by best-first methods (weighted A*, ARA*, AEES); it is unclear whether a breadth-first, beam-based anytime search is a better architecture, especially in domains with deep local minima.
Approach
Rectangle search iteratively widens and deepens a monobead-style beam search: each iteration expands one node at every previously explored depth level and i nodes at a new depth level, so the explored region forms a rectangle; an aspect parameter controls how many new depth levels are added per iteration, and it is complete and returns optimal solutions with an admissible heuristic.
Key results
- Rectangle(1) reaches full coverage first in all sliding-tile cost models and provides better solution cost thereafter.
- Rectangle(500) is not clearly inferior to other anytime algorithms in any tested domain and is the clear winner in heavy-cost pancake problems.
- Rectangle search performs worst in grid pathfinding on non-random maps (orz100d, room64), where ARA* gives best results.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use rectangle(1) instead of the competing anytime algorithms | rectangle search · 15-puzzle and 24-puzzle, all tested cost models | coverage and solution cost | Helped |
| use rectangle search instead of the competing anytime algorithms | rectangle search · Blocks World, both action models | coverage and solution cost | Helped |
| increase aspect from 1 to 500 (ablation) | rectangle search · Pancake problem, unit cost | time to solve | Helped |
| use rectangle(1) instead of the competing algorithms | rectangle search · Pancake problem, unit cost | solution cost | Helped |
| increase aspect from 1 to 500 (ablation) | rectangle search · Pancake problem, heavy cost | performance | Helped |
| use rectangle(1) instead of ARA* | rectangle search · Vacuum World, smaller unit-cost problems | coverage | Hurt |
| increase aspect from 1 to 500 (ablation) | rectangle search · Vacuum World, 500×500 grids with 60 dirts | coverage | Helped |
| use rectangle(500) instead of the competing algorithms | rectangle search · Vacuum World, heavy cost | coverage and solution quality | Helped |
| use rectangle search instead of ARA* | rectangle search · Grid pathfinding, structured maps | coverage | Hurt |
| increase aspect from 1 to 500 (ablation) | rectangle search · Platform game | performance | Hurt |
| use rectangle(1) instead of the other algorithms | rectangle search · Dynamic Traffic | time to solve | Hurt |
| use rectangle(500) instead of the competing algorithms | rectangle search · Dynamic Traffic | solution quality over time | Helped |
Surprising findings
- Rectangle(500) performs worse than rectangle(1) in the platform game, suggesting reconsidering earlier steps matters more than quick deep exploration.
- Rectangle search lags on coverage in grid pathfinding and on large unit-cost vacuum problems despite being based on beam search.
Limitations
- Performs poorly on grid pathfinding with non-random maps where local minima are small and sequential (room64, orz100d).
- Aspect parameter must be set by hand (1 or 500) and tuning is not solved.
- Rectangle(1) is inefficient when heuristic is accurate and solutions are deep (d much greater than s).
Experimental setup
Datasets: 15-puzzle 24-puzzle 100 pancake blocks world deep blocks world vacuum world grid pathfinding (grid-random, life, room64, orz100d) platform game dynamic traffic
Benchmarks: 15-puzzle 24-puzzle pancake blocks world vacuum world grid pathfinding platform game dynamic traffic
Metrics: average quality over time coverage
Baselines: ARA* AEES CABS DFS* ILDS* fixed-width bead search GBFS
Builds on: monobead beam search anytime weighted A* AEES CABS ILDS
Closest papers by meaning
- Anytime Recursive Best-First Search for Bounding Marginal MAP (AAAI 2019 · similarity 0.85)
- Bidirectional Search That Is Guaranteed to Meet in the Middle (AAAI 2016 · similarity 0.84)
- From Exact to Anytime Solutions for Marginal MAP (AAAI 2016 · similarity 0.84)
- Anchor Search: A Unified Framework for Suboptimal Bidirectional Search (AAAI 2025 · similarity 0.84)
- Distance Adaptive Beam Search for Provably Accurate Graph-Based Nearest Neighbor Search (NeurIPS 2025 · similarity 0.83)
- Parallel Beam Search Algorithms for Domain-Independent Dynamic Programming (AAAI 2024 · similarity 0.83)
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.