The D* Algorithm
Hello. I'm trying to implement Anthony Stentz' D* algorithm for our thesis. The algorithm I'm trying to implement can be found in this paper, http://www.frc.ri.cmu.edu/~axs/doc/icra94.pdf
So far, so good. The implementation works. I have tried hard to follow the algorithm described in the paper. However, the implementation has some problems:
1.) On some maps, the implementation creates a circular path, causing the simulated robot to go around in circles and into an infinite loop.
2.) On certain occassions when the robot recomputes a path after having discovered discrepancies in the map, it just stops, returning NO-PATH after having expanded a few cells.
I have linked Number 2's cause to an empty OPEN list, but I could not figure out the cause of Number 1. I looked around the internet for other implementations of D*. I found one in this site, http://palantir.swarthmore.edu/maxwell/classes/e28/S00/reports/addo-kim-silk-lab2/ .It appears we have the same problem. I couldn't get their code to work. It required some sort of interface to a NOMAD client or robot .
If anyone has encountered the same problems when implementing the D* algorithm, I appreciate it if you could tell us the cause. For now, we just recompute from scratch just like the other implementation.
