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

Printable View

• October 18th, 2013, 10:41 AM
puneeth.meruva
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
• October 18th, 2013, 03:01 PM
GregBrannon
Re: Problems with A* Map Search - GC Overload Error and Null Error
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.