Misplaced Pages

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "SMA*" – news · newspapers · books · scholar · JSTOR (March 2015) (Learn how and when to remove this message)

This article may be too technical for most readers to understand. Please help improve it to make it understandable to non-experts, without removing the technical details. (November 2009) (Learn how and when to remove this message)

SMA* or Simplified Memory Bounded A* is a shortest path algorithm based on the A* algorithm. The main advantage of SMA* is that it uses a bounded memory, while the A* algorithm might need exponential memory. All other characteristics of SMA* are inherited from A*.

Process

Properties

SMA* has the following properties

• It works with a heuristic, just as A*
• It is complete if the allowed memory is high enough to store the shallowest solution
• It is optimal if the allowed memory is high enough to store the shallowest optimal solution, otherwise it will return the best solution that fits in the allowed memory
• It avoids repeated states as long as the memory bound allows it
• It will use all memory available
• Enlarging the memory bound of the algorithm will only speed up the calculation
• When enough memory is available to contain the entire search tree, then calculation has an optimal speed

Implementation

The implementation of Simple memory bounded A* is very similar to that of A*; the only difference is that nodes with the highest f-cost are pruned from the queue when there isn't any space left. Because those nodes are deleted, simple memory bounded A* has to remember the f-cost of the best forgotten child of the parent node. When it seems that all explored paths are worse than such a forgotten path, the path is regenerated.

Pseudo code:

function simple memory bounded A*-star(problem): path
  queue: set of nodes, ordered by f-cost;
begin
  queue.insert(problem.root-node);
  while True do begin
    if queue.empty() then return failure; //there is no solution that fits in the given memory
    node := queue.begin(); // min-f-cost-node
    if problem.is-goal(node) then return success;
    s := next-successor(node)
    if !problem.is-goal(s) && depth(s) == max_depth then
        f(s) := inf; 
        // there is no memory left to go past s, so the entire path is useless
    else
        f(s) := max(f(node), g(s) + h(s));
        // f-value of the successor is the maximum of
        //      f-value of the parent and 
        //      heuristic of the successor + path length to the successor
    end if
    if no more successors then
       update f-cost of node and those of its ancestors if needed
    if node.successors ⊆ queue then queue.remove(node); 
    // all children have already been added to the queue via a shorter way
    if memory is full then begin
      bad Node := shallowest node with highest f-cost;
      for parent in bad Node.parents do begin
        parent.successors.remove(bad Node);
        if needed then queue.insert(parent); 
      end for
    end if
    queue.insert(s);
  end while
end

External links

• Simplified Memory Bounded A Star Search Algorithm | SMA* Search | Solved Example in by Mahesh Huddar

References

1. Russell, S. (1992). "Efficient memory-bounded search methods". In Neumann, B. (ed.). Proceedings of the 10th European Conference on Artificial intelligence. Vienna, Austria: John Wiley & Sons, New York, NY. pp. 1–5. CiteSeerX 10.1.1.105.7839.

• Graph algorithms
• Routing algorithms
• Search algorithms
• Game artificial intelligence