Hi Mike, Thank you very much for your valuable reply indeed! SBPL package is very interesting, I'm gonna do some research on that. Cheers, Simon On Wed, Dec 29, 2010 at 8:46 AM, Mike Phillips wrote: > Hi Simon, > The SBPL package has an implementation of AD* (anytime D*). If you > were to set the initial epsilon (initial weight on the heuristic) to > 1.0 the planner will run exactly like D* Lite. If you are interested > in the anytime functionality AD* works by running multiple iterations > weighted A*, and decrementing the weight until it gets to 1.0 (optimal > search). This allows the planner to find a suboptimal solution > quickly, improve it as time allows, and if there is enough time > produce the optimal solution. > > If you want to use SBPL with the navigation stack there is a package > called sbpl_lattice_planner which can be used as a global planner for > the navigation stack. The node is basically a wrapper around SBPL to > integrate it into the nav stack. The default parameters run ARA* (an > anytime A* planner) but you can change it to run AD* with an initial > epsilon of 1.0 to make it run D* Lite. This package runs the planners > on a 3D state space (x,y,theta) to produce smoother paths, handle > non-holonomic constraints, and deal with non-circular footprints. > This comes at a cost planning times. The package in its current form > doesn't support planning in a 2D state space, but SBPL does. Since > sbpl_lattice_planner is just a wrapper some relatively simple changes > can make the package use SBPL's 2D state space. > Specifically if you just change the type of field env_ from > EnvironmentNAVXYTHETALAT* to EnvironmentNAV2D*, change how it is > instantiated similarly, and then fix whatever doesn't compile (small > things like need a subset of the parameters for most function calls > due to one less dimension). > > The implementation of D* uses dynamic memory allocation for the states > in order to be general to planning in cases where the state space is > high-dimensional and you wouldn't want to construct all of the state a > priori. Therefore for the 2D case, this will cause some small slow > down since we already have the 2D costmap allocated and allocating the > whole state space in advance would probably be a little faster. > > Let me know if you have any questions about SBPL, or getting it to > work with the nav stack for your application. > > -Mike- > > > Hi Eitan, > > > > Here is the story. I have a need of Incremental heuristic search in Base > > Global Planner for long range navigation in an unknown area, so I tried > to > > modify your A* in move_base to D* Lite< > http://idm-lab.org/bib/abstracts/papers/aaai02b.pdf>. > > However, it is really difficult to arrange the order of the re-explored > > cells in the priority buffer because you are using the threshold curT to > > control the behavior of the priority queue. And also, some re-explored > cells > > have to be updated twice by the D* Lite during the re-planning. So I take > > use of your code to realize a new way: 1) Keep the potarr during one long > > range move; 2) Swap the start and goal cells before the propagation, make > > your A* as a backward version; 3)Do a limited re-propagation when > > re-planning is necessary. I also create a PointCloud2 message for the > > explored potential area, and add this patch > > to visualize the message. > > Here is a screencast of my > > experiment. > > > > At the moment, this method is not stable yet, some times the robot will > be > > stopped by the incomplete potential area. Do you think it is a good way > to > > do the Incremental replanning? Or it is still possible to realize the D* > > Lite based on your A*? > > > > Cheers, > > Simon > _______________________________________________ > ros-users mailing list > ros-users@code.ros.org > https://code.ros.org/mailman/listinfo/ros-users >