yaoqingyuan / dstarlite Goto Github PK
View Code? Open in Web Editor NEWAutomatically exported from code.google.com/p/dstarlite
Automatically exported from code.google.com/p/dstarlite
**************** * DSTAR Class * * README * **************** This software is an implementation of the D*-Lite algorithm as explained in [Koenig, 2002]. This is the non-optimized version as explained in Figure 5 of the paper. There are a few minor improvements that were made to this algorithm explained in section 3 below. This source is released under the GNU GENERAL PUBLIC LICENSE Version 3, 29 June 2007 available at: http://www.gnu.org/licenses/gpl.html. Please note this is an early release and the software still has small bugs. Contents: 1. Compiling and Running 2. Integration 3. Modifications 4. References 5. Author Info 1. Running the dstar test program: you will need to have the openGL/GLUT libraries installed for this to work. But you do not need them to use the Dstar class in your own program. $ tar -xzf dstar.tgz $ cd dstar $ make $ ./dstar Commands: [q/Q] - Quit [r/R] - Replan [a/A] - Toggle Auto Replan [c/C] - Clear (restart) left mouse click - make cell untraversable (cost -1) middle mouse click - move goal to cell right mouse click - move start to cell The cell colors are as follows: Red - untraversable Green - traversable but with changed cost Red/Green with small purple square - The cell is on the openList Yellow - start cell Purple - goal cell 2. Using in your own source: Here is a simple working test program that uses the Dstar class: #include "Dstar.h" int main() { Dstar *dstar = new Dstar(); list<state> mypath; dstar->init(0,0,10,5); // set start to (0,0) and goal to (10,5) dstar->updateCell(3,4,-1); // set cell (3,4) to be non traversable dstar->updateCell(2,2,42.432); // set set (2,2) to have cost 42.432 dstar->replan(); // plan a path mypath = dstar->getPath(); // retrieve path dstar->updateStart(10,2); // move start to (10,2) dstar->replan(); // plan a path mypath = dstar->getPath(); // retrieve path dstar->updateGoal(0,1); // move goal to (0,1) dstar->replan(); // plan a path mypath = dstar->getPath(); // retrieve path return 0; } 3. Implementational Details: Here is a list of the more interesting tweaks that we applied to improve the D* Lite algorithm explained in [Koenig, 2002]. 3.1 The Open Hash and Lazy Remove: In order to speed up the time it takes to add/remove/search on the open list we used both a stl::priority_queue and a "stl"::hash_map to store states. The queue keeps the states in sorted order so it is easy to find the next best state while the hash is used to quickly determine what states are in the queue. When a cell is inserted into the openlist it is pushed onto the queue and put into the hash table. In order to check if a cell is on the open list one can just check if it is in the hash table. The hash table also stores a hash of the cells key so cells that are outdated in the queue can still be removed. Any time a cell is popped off the queue we check if it is in the hash, if not it is discarded an a new one is chosen. 3.2 Euclidean Path Optimization Obtaining a path from the D* generated cost map is generally done by starting at the start node and doing a greedy search by expanding successor nodes with the lowest cost to goal. This approach can generate a path that starts heading out 45 degrees toward the goal instead of straight at it. This happens because the 8-way connected distance is an approximation and there is no difference between taking all of the angular moves first and taking all of the straight moves. In order to generate a path that is closer to the true shortest cost we added a simple modification to the greedy search. When we compare the costs to all of the successor cells we choose the one that minimizes: (cellA.g != cellB.g) return (cellA.g < cellB.g) return ((euclidean_dist(cellA,start) + euclidean_dist(cellA,goal)) < (euclidean_dist(cellB,start) + euclidean_dist(cellB,goal))) This means we break ties by choosing the cell that lies closest to the straight line between the start and goal states. 3.3 Goal Changes The D* Lite algorithm explained in [Koenig, 2002] doesn't include code to handle the goal changing locations. To do this we simply clear the map, change the location of the goal, re-add all the obstacles, and replan. There is probably a more efficient way of dealing with this but this modification worked great for our purposes. 3.4 Max Steps If there is no path to the goal D* can have a hard time detecting it and will likely loop forever. In order to partially deal with this issue the search will automatically return after a set number of node expansions (set to 'maxsteps'). After the search returns it can start again where it left off with another call to replan(). 4. References: Improved Fast Replanning for Robot Navigation in Unknown Terrain Sven Koenig, Maxim Likhachev Technical Report GIT-COGSCI-2002/3, Georgia Institute of Technology, 2002. 5. Author Info Please report any bugs or comments to: James Neufeld University of Alberta, Canada [email protected] thanks, and I hope this code is helpful.
The algorithm sometimes fails to find a valid path to goal.
Original issue reported on code.google.com by [email protected]
on 26 Nov 2007 at 6:44
Attachments:
In DSTAR.CPP:
if (close(val,cmin)) {
if (tmin > val2) {
tmin = val2;
cmin = val;
smin = *i;
}
} else if (val < cmin) {
tmin = val2;
cmin = val;
smin = *i;
}
should be replace by:
if (close(val,cmin)) {
if (cmin > val2) {
tmin = val2;
cmin = val;
smin = *i;
}
} else if (val < cmin) {
tmin = val2;
cmin = val;
smin = *i;
}
I'm not sure but it looks like more a good code: the test on tmin without
being initialized cause some random issues...
Original issue reported on code.google.com by [email protected]
on 16 Dec 2008 at 1:29
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.