ansaurus

Question

A* implementation always returns same value

Answer 1

+1 A:

Below is my code, it seems that no matter what values I enter it will always return 360.

My first guess is that you have a fixed heuristic cost for each node. So might that 360 come from?

final SearchNode START_NODE = new SearchNode(0,115,655);
final SearchNode END_NODE = new SearchNode(0,380,560);

Assuming you're using a Manhattan Distance heuristic, (380-115) + (655-560) = 265 + 95 = 360

The code is a little difficult to read because of its formatting. But my guess is you calculated the h-value for the start node and you are using that for every node thereafter. Remember that h(x) <= d(x,y) + h(y) and calculate it for each node expansion.

Shaggy Frog 2010-09-17 23:13:43

thats most likely where i am messing it up, thanks I will look into this and sorry about the formatting

Woot4Moo 2010-09-17 23:30:41

Answer 2

+1 A:

I am assuming the graph is a regular rectangular grid that has obstacle nodes in it through which none of the solutions should pass. Moreover I am assuming traveling from a node to a neighbour node is 1. Also I realized that Manhattan Distance is used as the heuristic.

Given these, I am afraid yours is a misimplementation.

First of all instead of a recursive one you should use an iterative approach. Given the size of your graph, you would definitely get Stackoverflows if it was a correct implementation.

Secondly, there seems to be a problem about the concepts of GValue, HValue, FValue and/or cost. I feel obliged to give an informal description of these terms.

The simple formula A* uses is F = G + H where

G is the currently calculated cost of travelling from the start node to the current node. So, for the start node the Gvalue should be 0, any node reachable from the startNode should have a G value of 1 (my assumption was so, traveling from a node to a neighbour node) I would like to stress the 'currently' term here, because the gValue of a node may change during the run of the algorithm.

H is the heuristic part of the cost, denoting the cost from the current node to the end node. Unlike the G part, H value of a node does not change at all (well I have a doubt here, may there be such a heuristic?, yours does not so let's continue), it should be computed only once. Your implementation seems to be using the Manhattan Distance as the heuristic which is definitely the best heuristic for such a graph. But beware my friend, there seems to be a small problem there as well: the absolute values of the differences should be taken seperately and then be summed.

And the F is the sum of these values denoting the possible cost of having a solution passing from the current node (Given your graph and heuristic any calculated F value should be equal or less than the actual cost, which is good).

With these at hand I would have used a SearchNode like this:

public class SearchNode {
    private int xCoordinate;
    private int yCoordinate;
    private double gScore;
    private double hScore;

    public double getfScore() {
        return gScore + hScore;
    }

    public double getgScore() {
        return gScore;
    }

    public void setgScore(int gScore) {
        this.gScore = gScore;
    }


    public SearchNode(int xCoordinate,int yCoordinate, double gScore, SearchNode endNode) {
        this.gScore=gScore;
        this.hScore = //Manhattan distance from this node to end node
        this.xCoordinate =xCoordinate;
        this.yCoordinate = yCoordinate;
    }

   public int getxCoordinate() {
       return xCoordinate;
   }

   public int getyCoordinate() {
       return yCoordinate;
   }
}

Then the algorithm may be implemented like :

private ArrayList<SearchNode> closedNodes = new ArrayList<SearchNode>();
private ArrayList<SearchNode> openNodes = new ArrayList<SearchNode>();
//create the start and end nodes
SearchNode end = new SearchNode(380, 560, -1, null);
SearchNode start = new SearchNode(115,655, 0, end);


// add start node to the openSet

openNodes.Add(start);

while(openNodes.Count > 0) // while there still is a node to test
{
    // I am afraid there is another severe problem here.
    // OpenSet should be PriorityQueue like collection, not a regular Collection.
    // I suggest you to take a look at a Minimum BinaryHeap implementation. It has a logN complexity
    // of insertion and deletion and Constant Complexity access.

   // take the Node with the smallest FValue from the openSet. (With BinHeap constant time!)
    SearchNode current = openNodes.GetSmallestFvaluedNode(); // this should both retrieve and remove the node fromt he openset.

    // if it is the endNode, then we are node. The FValue (or the Gvalue as well since h value is zero here) is equal to the cost.
    if (current.EqualTo(end)) // not reference equality, you should check the x,y values
{
    return current.getfScore();
}

   //check the neighbourNodes, they may have been created in a previous iteration and already present in the OpenNodes collection. If it is the case, their G values should be compared with the currently calculated ones.
 // dont forget to check the limit values, we probably do not need nodes with negative or greater than the grid size coordinate values, I am not writing it
 // also here is the right place to check for the blocking nodes with a simple for loop I am not writing it either

  double neighbourGValue = current.getgScore() + 1;
 if (openNodes.Contains(current.getXCoordinate(), current.getYCoordinate() + 1))
  {
     // then compare the gValue of it with the current calculated value.
     SearchNode neighbour = openNodess.getNode(current.getXCoordinate(), current.getYCoordinate() + 1);
     if(neighbour.getgScore() > neighbourGValue)
        neighbour.setgScore(neighbourGValue);
  }
  else if(!closedNodes.Contains(current.getXCoordinate(), current.getYCoordinate()))
  {
      // create and add a fresh Node
     SearchNode n = new SearchNode(current.getXCoordinate(), current.getYCoordinate() + 1, neighbourGValue, endNode);
     openNodes.Add(n);
  }
  // do the same for the other sides : [x+1,y - x-1,y - x, y-1]

  // lastly add the currentNode to the CloseNodes.
  closedNodes.Add(current);
}

// if the loop is terminated without finding a result, then there is no way from the given start node to the end node.
 return -1;

The only question pops to my mind about the above implementation is the line

if (openNodes.Contains(current.getXCoordinate(), current.getYCoordinate() + 1))

Even if the open set is implemented as Min Binary Heap there is no easy way to check the non-minimum f valued nodes. I cant remember the details now but I remember implementing this one with logN complexity. Moreover my implementation was accessing and changing the g value of that node (if it is necessary) in one call, so you dont spent time retrieving it again. No matter if g value is changed, if there is a node with the given coordinates, it was returning true so no new node is generated.

One last thing I realized when I finished writing all these. You said, with any input given your implementation was calculating the same result. Well if the input you are mentioning is the obstacle nodes, then it will most of the time be the case that it will find, no matter what implementation it is, the same distance since it is looking for the shortest possible distance. In the below image I tried to explain that.

alt text

tafa 2010-09-18 01:32:01

Quite the detailed answer my friend and I appreciate the time put into this. I will take these suggestions and apply them accordingly.

Woot4Moo 2010-09-18 02:16:19

ansaurus

tags:

views:

answers:

A* implementation always returns same value

related questions