Peer-reviewed research · 2023–2026
Search & planning
When a heuristic gives a search no gradient to follow, the search stalls in a region it cannot see its way out of.
Overview
The problem. When a heuristic gives a search no gradient to follow, the search stalls in a region it cannot see its way out of.
Why it matters. Escaping those regions is the difference between a planner that finishes and one that does not — and the restart policies that work here carry over to test-time search in language models.
My contribution
Co-developed the restarting-random-walk planner (AAAI 2026). Lead author on the separate refactoring-heuristics work.
- Co-developed a restarting-random-walk planner for escaping uninformed heuristic regions, published at AAAI 2026.
- Separately, as lead author, built admissible search heuristics for automated code refactoring (Opti Code Pro).
Constraints
What the design had to work around.
- The planning result is scoped to unbounded heuristic regions — the situation the method was designed for, not general planning performance.
- The random-walk approach is chosen for its memory profile: linear rather than exponential worst-case memory.
- The refactoring heuristics must be admissible, which bounds how aggressive they can be.
Architecture
Models, tools, state, evaluation, and the paths the system takes when something fails.
01 · State
02 · Detect
03 · Escape
04 · Resume
Restarting random walk → Uninformed region— restart policy: abandon the walk and try again
- State
- Evaluation
- Tool
- Model
Text description of this diagram
A planning task expressed in PDDL is searched with a heuristic that estimates distance to the goal. The search detects an uninformed region — an area where the heuristic gives no gradient and therefore no guidance. Two escape strategies are compared: breadth-first search, which is exhaustive but uses exponential worst-case memory, and a restarting random walk, which uses linear worst-case memory. If a walk fails to escape, the restart policy abandons it and starts another, which is the return path in this diagram. Once the search escapes the region, informed search resumes and produces a plan. The same idea underlies the separate refactoring work: admissible heuristics guide a search through program transformations rather than through a planning state space.
Evaluation
Fields marked Not reported are absent from the source material. They are listed rather than dropped so the gaps in the evidence stay visible.
- Comparator (planning)
- Breadth-first search for region escape
- Task subset
- Unbounded-region planning tasks
- Planning result
- Faster or uniquely successful on 70.3% of those tasks
- Memory
- Linear rather than exponential worst-case memory
- Comparator (refactoring)
- Uninformed search
- Refactoring result
- 82% fewer node expansions, 74% lower runtime
- Task counts
- Not reported
- Confidence intervals
- Not reported
Results
On the planning tasks where a heuristic stops helping, the restarting random walk either got to a plan faster than breadth-first search or solved a task breadth-first search could not — on about seven of every ten such tasks, while using far less memory.
- Planning (AAAI 2026): faster or uniquely successful on 70.3% of unbounded-region tasks, with linear rather than exponential worst-case memory.
- Automated refactoring (Opti Code Pro): admissible heuristics cut node expansions by 82% and runtime by 74% against uninformed search.
- These are two separate studies with separate evaluations; the percentages are not comparable to each other.
Failure modes and limitations
What this work does not establish, and where it stops being reliable.
- The 70.3% applies to unbounded-region tasks only. It is not a claim about planning benchmarks in general.
- Exact task counts are not reported in the material available in this repository, so the precision behind each percentage cannot be stated here.
- The planning and refactoring results come from different studies with different comparators and must not be read as a single number.
- "Faster or uniquely successful" combines two different kinds of win into one figure; the split between them is not reported here.
Artifacts
Building an agent that must work outside the demo?
I work on evaluation, grounded tool use, failure recovery, and auditable agent workflows.