Thread: Problems with A* Map Search - GC Overload Error and Null Error

Dear Users,

I am trying to implement an A* map search algorithm in java, both the tree search and the graph search versions.

Tree Search Code:

SearchNode startState = new SearchNode(null, startID, 0, EuclideanHeuristic.eval(startStateSN,goalStateSN)) ;

pq.add(startState); // make sure start node is in current somehow
SearchNode current = null;
StateNode currentSN = null;

long enqueued = 1;
long dequeued = 0;
boolean solutionFound=false;

while(pq.size() > 0)
{

current = pq.poll();
//System.out.println(current.endstate);
dequeued ++;
currentSN = rnw.getNode(current.endstate);
if (current.endstate == goalID)
{
solutionFound=true;
break;

}
Set<StateGraphEdge> Edges = rnw.getOutgoingEdges(current.endstate);
for(StateGraphEdge s:Edges) // don't create multiple neighbor objects
{
long neighborID= s.id2;
double distance = s.distance;
double g_score = current.g_value + distance;
SearchNode neighbor = new SearchNode(current, neighborID, g_score, EuclideanHeuristic.eval(currentSN, goalStateSN)); // convert current to state node
pq.add(neighbor);
enqueued ++;
}
}


long numSteps = 0;
double solutionDistance = current.g_value;
Stack<Long> path = new Stack<Long>();
while(current.parent != null)
{

path.push(current.endstate);
current=current.parent;
numSteps++;

}
// print results to .osm file



System.out.println("number of nodes enqueued:" + enqueued + "\n");
System.out.println("number of nodes dequeued:" + dequeued + "\n");

if (solutionFound == true)
{
System.out.println("Was solution found? <yes>\n");
System.out.println("Solution distance:" + solutionDistance + "\n");
System.out.println("Number of steps in solution:" + numSteps + "\n");

System.out.println("<" + startID + ">\n");
while(path.empty() == false)
{
System.out.println("<" + path.pop() + ">\n");
}
}
else
{
System.out.println("Was solution found? <no>\n");
}



}

However, when I run the code, I get the following error:

Exception in thread "main" java.lang.OutOfMemoryError: GC overhead limit exceeded
at scraps.Searcher.main(Searcher.java:108)

-----------------------------------------------------------------------------------------------------------------------------------

Graph Search Code:

SearchNode startState = new SearchNode(null, startID, 0, EuclideanHeuristic.eval(startStateSN,goalStateSN)) ;

pq.add(startState);

SearchNode current = null;
StateNode currentSN = null;

long enqueued = 0;
long dequeued = 0;
boolean solutionFound=false;

while (pq.size() > 0)
{

current = pq.peek();
dequeued++;
currentSN = rnw.getNode(current.endstate);

if (closedset.contains(current.endstate))
{
while (closedset.contains(current.endstate))
{
pq.poll();
current = pq.peek();
//dequeued++;
currentSN = rnw.getNode(current.endstate);
}
dequeued++;
}
System.out.println(current.endstate);
if (current.endstate == goalID)
{
solutionFound = true;
break;
}
SearchNode remove = pq.poll();
closedset.add(remove.endstate);
Set<StateGraphEdge> Edges = rnw.getOutgoingEdges(current.endstate);
SearchNode neighbor = null;
for(StateGraphEdge s:Edges)
{
long neighborID= s.id2;
double distance = s.distance;
double g_score = current.g_value+ distance;
neighbor = new SearchNode(current, neighborID, g_score, EuclideanHeuristic.eval(currentSN, goalStateSN)); // convert current to state node
pq.add(neighbor);
enqueued++;
}
}

double solutionDistance = current.g_value;
long numSteps = 0;
Stack<Long> path = new Stack<Long>();
while(current.parent != null)
{

path.push(current.endstate);
current=current.parent;
numSteps++;

}

System.out.println("number of nodes enqueued:" + enqueued + "\n");
System.out.println("number of nodes dequeued:" + dequeued + "\n");

if (solutionFound == true)
{
System.out.println("Was solution found? <yes>\n");
System.out.println("Solution distance:" + solutionDistance + "\n");
System.out.println("Number of steps in solution:" + numSteps + "\n");

System.out.println("<" + startID + ">\n");
while(path.empty() == false)
{
System.out.println("<" + path.pop() + ">\n");
}
}
else
{
System.out.println("Was solution found? <no>\n");
}

However, when I try to implement this code, I get the following error:

Exception in thread "main" java.lang.NullPointerException
at mapsearch.EuclideanHeuristic.eval(EuclideanHeurist ic.java:11)
at scraps.Searcher.main(Searcher.java:201)


Could someone please help me? I am relatively new to Java so I am not entirely sure about how to fix the errors. Also, I am sorry if my post does not follow the accepted protocol for the forum, I am new to the forum as well.

Thanks in advance,
Puneeth

Eeeee gads! Please learn to post code in code tags, properly formatted. Read the Announcement topic at the top of the sub-forum. Most will pass on reading so much code that is improperly formatted and posted. It 'hurts' to read it.