In this blog post, I explain graph-search based motion planning algorithms, which overlay a grid on configuration space and assume that each configuration is corresponding to a grid node. Then, the robot is allowed to traverse to adjacent grid points as long as the edge between the nodes is collision-free. The graph-based algorithms need setting a grid resolution. Search is faster with lower resolution, but the algorithm can fail to find the solution more. These algorithms are resolution optimal as well as resolution complete. A* does this efficiently by using a heuristic to estimate the total cost of a solution. D* is able to plan paths in unknown dynamic environments in an optimal and complete manner.
Although naive application of A* is typically unreasonable for high-dimensional planning problems since number of nodes on the grid grows exponentially, various algorithms has been proposed so far in applying forward search to many DoFs robots. ARA* starts by finding a suboptimal solution quickly using a loose path quality bound, then tightens the bound progressively as time allows. Given enough time, it finds a provably optimal solution. In addtion, ARA* reuses previous search efforts so that it is significantly more efficient than other anytime search algorithms. Curretnly, we are modifing ARA* to choose the cheap edge explicitly. Lazy Shortest Path (LazySP) is recently proposed that minimizes the number of edge evaluation during planning, which dramatically decreases the running time of problems with expensive edge validation. We also formulate our proposed planning algorithms in a lazy edge validation way inspired by LazySP.
If you are interested in how these algorithms work in practice, you can easily implement them thanks to OMPL, the Open Motion Planning Library.