Open main menu

In computer science, anytime A* , also known as anytime repairing A* (ARA*), is a variant of the A* search algorithm. Like other anytime algorithms, it has a flexible time cost, can return a valid solution to a pathfinding or graph traversal problem even if it is interrupted before it ends, by generating a fast, non-optimal solution before progressively optimizing it.[1].

BackgroundEdit

Running the optimal A* algorithm to completion is too expensive for many purposes. A*'s optimality can be sacrificed in order to gain a quicker execution time by inflating the heuristic. Iteratively reducing the degree the heuristic is "inflated" provides a naive anytime algorithm, but this repeats previous work. ARA* provides a mechanism for an efficient anytime heuristic search that reuses search efforts from previous executions.[1]

Anytime A* is an extension to the A* algorithm, mostly developed in past few years. The only difference between A* and Anytime A* is that Anytime A* adds a time limit to the algorithm. When the A* Algorithm hits this limit, it is stopped though it can be restarted with a new limit if desired.

UseEdit

Anytime A* is almost an extension on Anytime algorithms that basically focuses on solving problems fast rather than optimal. This means that the Anytime A* will be trying to solve problems in sub-set of the solutions. The main drive behind this is to find the fastest solution (not necessarily the optimal) and if more time is allowed keep working on the project. This ability to spit out quick solutions has made it attractive to Search-base sites and AI designs.

Difference between A* Algorithm and Anytime A* AlgorithmEdit

A* algorithm can be presented by the function of f(n) = g(n) + h(n), where n is the last node on the path, g(n) is the cost of the path from the start node to n, and h(n) is a heuristic that estimates the cost of the cheapest path from n to the goal. Different than the A* algorithm, the most important function of Anytime A* algorithm is that, they can be stopped and then can be restarted at anytime. The approach uses a control manager class which takes care of the time limit and the stopping and restarting of the A* algorithm to find an initial, possibly suboptimal solution, and then continues to search for improved solutions until meeting to a provably optimal solution.

PseudocodeEdit

To avoid changes in implemented A* Algorithm, the pseudocode implements a sub-module class called as control manager class (ctr_manager), which takes care of the time limit and the stopping and restarting of the A* algorithm.

public class ctr_manager
{
  bool is_First = true;
  Node new_Solution = null;
  public void run_A*( )
  {
    thread.sleep( sleep_Time );
    goalSucc = true;
  }
  public void thread_AA*(int sleep_Time, Node rN, Node gN)
  {
    thread_a = new thread( );
    if(is_First)
    {
       new_Solution = rN;
       thread.Start(run_A*);
       A*( rN, gN);
    } elseif( rN == new_Solution)
    {
       // keep all the states intact because algorithm needs more time
       // to find a better solution
       thread.Start(run_A*);
       A*( rN, gN);
    } elseif( rN != new_Solution)
    {
       // algorithm finds an improve solution, clears all the previous states
       // to allow algorithm a fresh start
       closeList.RemoveAll( );
       openList.RemoveAll( );
       thread.Start(run_A*);
       A*( new_Solution, gN);
    }
  }
}

LimitationEdit

The Anytime A* algorithm proves to be useful as it usually finds a first, possibly highly sub-optimal, solution very quickly and then continually works on improving the solution until the allocated time expires. Unfortunately, it can rarely provide bounds on the sub-optimality of its solutions unless the cost of an optimal solution is already known.[2]

ReferencesEdit

  1. ^ a b Likhachebv, Maxim; Gordon, Geoff; Thrun, Sebastian. "ARA*: formal analysis" (PDF). School of Computer Science, Carnegie Mellon University. Retrieved 24 July 2018. Cite journal requires |journal= (help)
  2. ^ Likhachebv, Maxim; Gordon, Geoff; Thrun, Sebastian. "ARA*: Anytime A* with Provable Bounds on Sub-Optimality" (PDF). School of Computer Science, Carnegie Mellon University. Retrieved 24 April 2018. Cite journal requires |journal= (help)