A* search neighbors handling description

Question

I am learning how A* search algorithm works. I have found several descriptions of this algorithm and all of them seem to me a bit different. Namely they differ in how neighbor nodes are handled in for loop. I guess the are all equivalent but I can't understand why. Can anybody explain why are they equivalent if thy are?

From Wikipedia article:

 function A*(start,goal)
     closedset := the empty set    // The set of nodes already evaluated.
     openset := {start}    // The set of tentative nodes to be evaluated, initially containing the start node
     came_from := the empty map    // The map of navigated nodes.

     g_score[start] := 0    // Cost from start along best known path.
     // Estimated total cost from start to goal through y.
     f_score[start] := g_score[start] + heuristic_cost_estimate(start, goal)

     while openset is not empty
         current := the node in openset having the lowest f_score[] value
         if current = goal
             return reconstruct_path(came_from, goal)

         remove current from openset
         add current to closedset
         for each neighbor in neighbor_nodes(current)
             tentative_g_score := g_score[current] + dist_between(current,neighbor)
             if neighbor in closedset and tentative_g_score >= g_score[neighbor]
                     continue

             if neighbor not in closedset or tentative_g_score < g_score[neighbor] 
                 came_from[neighbor] := current
                 g_score[neighbor] := tentative_g_score
                 f_score[neighbor] := g_score[neighbor] + heuristic_cost_estimate(neighbor, goal)
                 if neighbor not in openset
                     add neighbor to openset

     return failure

 function reconstruct_path(came_from, current_node)
     if current_node in came_from
         p := reconstruct_path(came_from, came_from[current_node])
         return (p + current_node)
     else
         return current_node

From Amit’s A* Pages:

OPEN = priority queue containing START
CLOSED = empty set
while lowest rank in OPEN is not the GOAL:
  current = remove lowest rank item from OPEN
  add current to CLOSED
  for neighbors of current:
    cost = g(current) + movementcost(current, neighbor)
    if neighbor in OPEN and cost less than g(neighbor):
      remove neighbor from OPEN, because new path is better
    if neighbor in CLOSED and cost less than g(neighbor): **
      remove neighbor from CLOSED
    if neighbor not in OPEN and neighbor not in CLOSED:
      set g(neighbor) to cost
      add neighbor to OPEN
      set priority queue rank to g(neighbor) + h(neighbor)
      set neighbor's parent to current

reconstruct reverse path from goal to start
by following parent pointers

Another A* pseudocode:

1    Create a node containing the goal state node_goal
2    Create a node containing the start state node_start
3    Put node_start on the open list
4    while the OPEN list is not empty
5    {
6    Get the node off the open list with the lowest f and call it node_current
7    if node_current is the same state as node_goal we have found the solution; break from the while loop
8        Generate each state node_successor that can come after node_current
9        for each node_successor of node_current
10       {
11           Set the cost of node_successor to be the cost of node_current plus the cost to get to node_successor from node_current
12           find node_successor on the OPEN list
13           if node_successor is on the OPEN list but the existing one is as good or better then discard this successor and continue
14           if node_successor is on the CLOSED list but the existing one is as good or better then discard this successor and continue
15           Remove occurences of node_successor from OPEN and CLOSED
16           Set the parent of node_successor to node_current
17           Set h to be the estimated distance to node_goal (Using the heuristic function)
18            Add node_successor to the OPEN list
19       }
20       Add node_current to the CLOSED list
21   }

I know that in case of consistent (monotone) heuristic A* algorithm can be simplified but I am interested in general case when heuristic is not necessarily consistent.

Answer 1

I recommend first watching the following lecture by Pieter Abbeel. It is from UC Berkeley intro to AI course in Fall 2012.

Lecture 3: Informed Search (A*)

This should give you a good feel of how A* works, and he gives lots of good examples. To go more in depth, I recommend studying chapter 3 section 3.5 titled, "Informed (Heuristic) Search Strategies," of Artificial Intelligence: A Modern Approach. It's a pretty huge book, but it's very concise. In particular, it has the pseudo-codes that you need. Browsing it right now, I came across

" [A*] algorithm is identical to Uniform-Cost-Search except that A* uses g + h instead of g"

... where g is the cost to reach a node, and h is the cost to get from that node to the goal.

Here's the pseudo-code the book provides for UCS:

function UCS(problem) return a solution, or failure
    
    node ← a node with STATE = problem.INITIAL-STATE, PATH-COST=0
    frontier ← a priority queue ordered by PATH-COST, with node as the only element
    explored ← an empty set

    loop do
        if EMPTY?(frontier) then return failure
        node ← POP(frontier)
        if problem.GOAL-TEST(node.STATE) then return SOLUTION(node)
        add node.STATE to explored

        for each action in problem.ACTIONS(node.STATE) do
            child ← CHILD-NODE(problem, node, action)
            if child.STATE ins not in explored or frontier then 
                frontier ← INSERT(child, frontier)
            else if child.STATE is in frontier with higher PATH-COST then
                replace that frontier node with child

To change this to become A*, all you need to do is change the implementation of the frontier, so that the priority queue is ordered by PATH-COST + HEURISTIC-VALUE.

You may need to read the book to understand the pseudo-code better.