Astar algorithm, problem

Posted by Robbo on December 5, 2009, 6:11 pm

Hello,

I work on some program to move a robot
through a random maze. To count path
from place A to place B I use A* (Astart)
algorithm. But, sometimes (in rare cases)
A* is unnable to find path (but path do
exists -- just A* can not find it).
Is it normal that A* in some cases is
unnable to find path or there is probably
some error in my implementation of A*?

Thanks in advance for suggestions.

Posted by D Herring on December 6, 2009, 5:04 am

Robbo wrote:

> sometimes (in rare cases)
> A* is unnable to find path (but path do
> exists -- just A* can not find it).
> Is it normal that A* in some cases is
> unnable to find path or there is probably
> some error in my implementation of A*?

If one or more paths exist, A* should find the shortest one. I
suspect a bug in your implementation, in how the connectivity graph
was defined, or in a related detail.

You could compare your code to the wikipedia entry
http://en.wikipedia.org/wiki/A*_search_algorithm

- Daniel

Posted by Robbo on December 6, 2009, 8:17 am

> If one or more paths exist, A* should find the shortest one. I
> suspect a bug in your implementation, in how the connectivity graph
> was defined, or in a related detail.
> You could compare your code to the wikipedia entry
> http://en.wikipedia.org/wiki/A*_search_algorithm

Thanks for Your answer. I will compare my implementation
with others. Btw. I use this implementation:
http://sebastianpawlak.com/pl/Informatyka/Artykuly/Astar/index.html

Robbo

Posted by wheagy@gmail.com on December 6, 2009, 10:09 am

> > If one or more paths exist, A* should find the shortest one. =A0I
> > suspect a bug in your implementation, in how the connectivity graph
> > was defined, or in a related detail.
> > You could compare your code to the wikipedia entry
> >http://en.wikipedia.org/wiki/A*_search_algorithm

> Thanks for Your answer. I will compare my implementation
> with others. Btw. I use this implementation:http://sebastianpawlak.com/pl=

/Informatyka/Artykuly/Astar/index.html

> Robbo

Also, you can try setting the A* heuristic to 0...the algorithm should
then be comparable to Dijkstra and if a path exists, it should find
it. - -Win

Posted by Robbo on December 6, 2009, 10:30 am

> Also, you can try setting the A* heuristic to 0...the algorithm should
> then be comparable to Dijkstra and if a path exists, it should find
> it. - -Win

In my algorithm heuristic is set to 0 -- each edge, cell or how
you call it is equal.

It is my java implementation of A*. At the moment, unfortunately
I can not see any error... but it must be somewhere there because
in rare cases this algorithm falls in the sense that it can not find
path, even if some exists.

The representation of maze is just 2D array. Even cells of array
is for cells of maze. Odd cells of array is for walls or openings
between cells of maze.

private static boolean computeShortestPath(int destX, int destY, boolean
displayRoute) {

//ratX, ratY is beginning position of the robot
//destX, destY is desired end position of the robot

int pointsTmp = points;

// copy maze
int mazePathNumbers[][] = new int[N][N]; // LenMapa
for (int x = 0; x < N; x++)
for (int y = 0; y < N; y++)
mazePathNumbers[x][y] = 0xffff;

class Pair { int x, y; Pair(int x, int y)};

Pair positionOfNodes[] = new Pair[500]; // WezlyPoz
positionOfNodes[0] = new Pair(ratX, ratY);

int lengths[] = new int[500];
lengths[0] = ((ratX - destX) * (ratX - destX) +
(ratY - destY) * (ratY - destY));

mazePathNumbers[ratX][ratY] = 0;

int nodeNumber = 1;

int shortestPath = 0;
Pair pos = null;
do {
for (int i = 0; i < nodeNumber; i++)
if (lengths[i] < lengths[shortestPath])
shortestPath = i;

pos = positionOfNodes[shortestPath];
positionOfNodes[shortestPath] = positionOfNodes[nodeNumber - 1];
lengths[shortestPath] = lengths[nodeNumber - 1];
nodeNumber--;

int x, y;

// createNode(0, -2);
x = 0;
y = -1;
if ((mazePathNumbers[pos.x + x + x][pos.y + y + y] == 0xffff) &&
(maze[pos.x + x][pos.y + y] == DISCOVERED_OPENING) &&
(maze[pos.x + x + x][pos.y + y + y] == DISCOVERED_SQUARE)) {

mazePathNumbers[pos.x + x + x][pos.y + y + y] =
mazePathNumbers[pos.x][pos.y] + 1;
positionOfNodes[nodeNumber] = new Pair(pos.x + x + x, pos.y
+ y + y);
lengths[nodeNumber] =
(((pos.x+x+x)-destX)*((pos.x+x+x)-destX)+

((pos.y+y+y)-destY)*((pos.y+y+y)-destY));
nodeNumber++;
}

//createNode(0, 2);
x = 0;
y = 1;
if ((mazePathNumbers[pos.x + x + x][pos.y + y + y] == 0xffff) &&
(maze[pos.x + x][pos.y + y] == DISCOVERED_OPENING) &&
(maze[pos.x + x + x][pos.y + y + y] == DISCOVERED_SQUARE)) {

mazePathNumbers[pos.x + x + x][pos.y + y + y] =
mazePathNumbers[pos.x][pos.y] + 1;
positionOfNodes[nodeNumber] = new Pair(pos.x + x + x, pos.y
+ y + y);
lengths[nodeNumber] =
(((pos.x+x+x)-destX)*((pos.x+x+x)-destX)+

((pos.y+y+y)-destY)*((pos.y+y+y)-destY));
nodeNumber++;
}

//createNode(-2, 0);
x = -1;
y = 0;
if ((mazePathNumbers[pos.x + x + x][pos.y + y + y] == 0xffff) &&
(maze[pos.x + x][pos.y + y] == DISCOVERED_OPENING) &&
(maze[pos.x + x + x][pos.y + y + y] == DISCOVERED_SQUARE)) {

mazePathNumbers[pos.x + x + x][pos.y + y + y] =
mazePathNumbers[pos.x][pos.y] + 1;
positionOfNodes[nodeNumber] = new Pair(pos.x + x + x, pos.y
+ y + y);
lengths[nodeNumber] =
(((pos.x+x+x)-destX)*((pos.x+x+x)-destX)+

((pos.y+y+y)-destY)*((pos.y+y+y)-destY));
nodeNumber++;
}

//createNode(2, 0);
x = 1;
y = 0;
if ((mazePathNumbers[pos.x + x + x][pos.y + y + y] == 0xffff) &&
(maze[pos.x + x][pos.y + y] == DISCOVERED_OPENING) &&
(maze[pos.x + x + x][pos.y + y + y] == DISCOVERED_SQUARE)) {

mazePathNumbers[pos.x + x + x][pos.y + y + y] =
mazePathNumbers[pos.x][pos.y] + 1;
positionOfNodes[nodeNumber] = new Pair(pos.x + x + x, pos.y
+ y + y);
lengths[nodeNumber] =
(((pos.x+x+x)-destX)*((pos.x+x+x)-destX)+

((pos.y+y+y)-destY)*((pos.y+y+y)-destY));
nodeNumber++;
}

} while (((pos.x != destX) || (pos.y != destY)) && (nodeNumber !=
0));

String directionString = "";
int step = 0;
Pair path[] = new Pair[500];
int pathIndex = 0;

if (nodeNumber != 0) {
pos = new Pair(destX, destY);
int shortestStep = 0xffff;
Pair shortestPos = null;
int x = 0, y = 0;
boolean isFirstStep = true;
while ((pos.x != ratX) || (pos.y != ratY)) {
step++;

shortestStep = 0xffff;

//Sprawdz (0,-1);
x = 0; y = -1;
if ((mazePathNumbers[pos.x + x + x][pos.y + y + y] <
shortestStep) &&
(maze[pos.x+x][pos.y+y] == DISCOVERED_OPENING)){
shortestStep = mazePathNumbers[pos.x+x+x][pos.y+y+y];
shortestPos = new Pair(pos.x+x+x,pos.y+y+y);
}

//Sprawdz (1,0);
x = 1; y = 0;
if ((mazePathNumbers[pos.x + x + x][pos.y + y + y] <
shortestStep) &&
(maze[pos.x+x][pos.y+y] == DISCOVERED_OPENING)){
shortestStep = mazePathNumbers[pos.x+x+x][pos.y+y+y];
shortestPos = new Pair(pos.x+x+x,pos.y+y+y);
}

//Sprawdz (0,1);
x = 0; y = 1;
if ((mazePathNumbers[pos.x + x + x][pos.y + y + y] <
shortestStep) &&
(maze[pos.x+x][pos.y+y] == DISCOVERED_OPENING)){
shortestStep = mazePathNumbers[pos.x+x+x][pos.y+y+y];
shortestPos = new Pair(pos.x+x+x,pos.y+y+y);
}

//Sprawdz (-1,0);
x = -1; y = 0;
if ((mazePathNumbers[pos.x + x + x][pos.y + y + y] <
shortestStep) &&
(maze[pos.x+x][pos.y+y] == DISCOVERED_OPENING)){
shortestStep = mazePathNumbers[pos.x+x+x][pos.y+y+y];
shortestPos = new Pair(pos.x+x+x,pos.y+y+y);
}

pos = shortestPos;

path[pathIndex++] = new Pair(shortestPos.x, shortestPos.y);
}

myRatX = ratX;
myRatY = ratY;
myRatDirection = ratDirection;

for (int i = pathIndex - 2; i >= 0; i--)

directionString =
directionString.concat(addMoveCommand(path[i].x, path[i].y));

directionString = directionString.concat(addMoveCommand(destX,
destY));
pointsTmp -= directionString.length();

howManyStepsFromHereToDestination = directionString.length();
} else {

//!!! System.err.println("No path!");
return false;
}
}

Page 1 of 2 1 2 > last >>

Similar Threads	Posted
PID algorithm?	March 3, 2010, 9:52 pm
PIC usart problem	June 26, 2006, 10:52 am
video cam problem	December 8, 2006, 5:54 am
Lee's algorithm - Described?	February 5, 2007, 12:09 pm
pic16f876a problem	June 6, 2008, 9:23 pm
Re: Motor Speed Problem	July 22, 2005, 3:12 am
Re: Motor Speed Problem	July 23, 2005, 12:03 pm
stepper driving problem!	February 23, 2006, 11:33 pm
fanuc robot problem	March 8, 2006, 2:44 am
Inverse kinematics problem for CRS F3	July 24, 2007, 4:51 pm