Skip to content
Algorithm Atlas
PathfindingAll categories
SpecializedSource checked

Anytime Repairing A*

Quickly finds a usable path and improves it as more time is available.

Explore relationshipsOpen constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category
Pathfinding
Difficulty
Advanced
Family
Anytime Heuristic Search
Tier
Specialized
Status
Verified
Review
Source Checked
Sources
1
Formulas
1
Relationships
2
Code example
Ready
Visualization
Ready
Aliases
ARA*

Overview

Anytime Repairing A* starts with an inflated heuristic for speed, then reduces the inflation factor and repairs the search to improve path quality.

Core Concepts

anytime searchheuristic inflationsearch repairbounded suboptimality

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(E log V)

Average

O(E log V)

Worst

O(E log V)

Space

O(V)

When to Use

  • Use when route planning needs anytime search.
  • Use when the input matches the assumptions behind anytime Heuristic Search.

When Not to Use

  • Avoid when edge costs or movement rules change faster than the search can update them.
  • Avoid when a simpler algorithm gives the required result with less setup.

What It Does

  • Quickly finds a usable path and improves it as more time is available
  • Uses anytime search and heuristic inflation to guide the work.
  • Produces path.

Use Cases

  • Route planning
  • Game navigation
  • Robotics motion planning

Inputs

  • Search graph or state space
  • Start state
  • Goal state or target set

Outputs

  • Path
  • Distance estimate
  • Search frontier state

Key Formulas (1)

Inflated priority

f(n) = g(n) + ε · h(n)
f(n) = g(n) + epsilon * h(n)

Uses epsilon above 1 to favor speed before refining the path.

Pseudocode

  1. 1.Prepare the inputs and state needed for Anytime Repairing A*.
  2. 2.Apply the anytime search step while the stopping condition has not been met.
  3. 3.Update intermediate state and discard invalid candidates.
  4. 4.Return path.

Canonical Example

Input
Anytime Repairing A* input with a small representative case
Output
Path
Explanation
Anytime Repairing A* applies anytime search to produce path.

Implementation Notes

  • Store predecessor information separately from distance or priority values.
  • Keep the anytime search step separate enough to test independently.

Common Pitfalls

  • Using a heuristic or preprocessed data that does not match the actual cost model breaks path quality.
  • Forgetting to check edge cases can make Anytime Repairing A* look correct on only ideal inputs.

Interactive Mechanism Walkthrough

2D Grid Wavefront & Trajectory

Show the frontier, settled nodes, and the final path over the search space.

S
#
#
#
#
#
#
#
G
Step 1 of 4: Prepare the inputs and state needed for Anytime Repairing A*.
pathfinding-mechanism

Notes

Anytime Repairing A* should be used with the assumptions and tradeoffs of anytime Heuristic Search in mind.

Sources (1)

What each reference supports for this entry.

Anytime Repairing A*

Paper

Reference for anytime heuristic search that repairs previous solutions as the inflation factor decreases.

Open source

Explore Next

Good next jumps from the relationship graph, ranked for useful discovery.

Open discoveryOpen map
Variant ofA* Search

Pathfinding · Core

Anytime Repairing A* refines a feasible path over time.

Compare with this
Conceptual neighborLifelong Planning A*

Pathfinding · Extended

Both reuse search information across improvements or changes.

Compare with this

Relationships

View full relationship page
Variant ofA* Search

Anytime Repairing A* refines a feasible path over time.

Conceptual neighborLifelong Planning A*

Both reuse search information across improvements or changes.

Related Algorithms

A* SearchLifelong Planning A*D* Lite

Tags

PathfindingHeuristic SearchPath ReplanningReal Time