I am working on a non-holonomic motion planning problem of a mobile robot in a completely unknown environment. After going through some research papers, I found that D-star algorithm is widely used in such conditions. But there are many D-star variants like Focused D*, D*-Lite, Field D* etc... So which of these variants is suitable in this case? Also please suggest any other better approach for this problem?
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
A brief overview of some of these variants:
- A* A variant Dijkstra's algorithm that maintains a heuristic distance to the goal to first explore parts of the graph that are more likely closer to the goal (same result as Dijkstra's algorithm, but faster).
- Theta* An "any-angle" variant of A*. In other words, movements between nodes are not restricted to the immediate neighbourhood. So you get paths that appear more natural and are often the shortest possible distance between two points (e.g., in a grid environment, A* might plan a non-straight line between two points because of the constraint requiring the path to "stay in the grid", Theta* relaxes this).
- D* A variant of A* that is fast to update changing edge costs in the graph. For example, let's say the robots path is suddenly blocked by a new obstacle. D* doesn't need to replay the whole path from scratch; rather, it amends the previous path.
- Focused D* A variant of D* that uses heuristics to more efficiently choose which parts of the graph are updated when a change in the graph (e.g., an obstacle) is detected.
- D* Lite Essentially the same as Focused D* but is more intuitive and easier to program. Is pretty much used in place of Focused D* in virtually all applications.
- Field D* An "any-angle" version of D* Lite. You get natural paths that update rather quickly to changing obstacles. This algorithm has been used on Mars rovers. Downside is it is much trickier to implement and understand then Theta*, for example.
