Stack Overflow
Stack Overflow

Questions tagged [d-star]

D* is a search algorithm, capable of planning paths in unknown, partially known, and changing environments in an efficient, optimal, and complete manner. It is of particular interest in mobile robotics. (Do not use for questions related to digital voice and data protocol specification for amateur radio.)

Reference:

wikipedia

22 questions
39
votes
7 answers

Where can I find information on the D* or D* Lite pathfinding algorithm?

There are links to some papers on D* here, but they're a bit too mathematical for me. Is there any information on D*/D* Lite more geared towards beginners?
tehalynn
  • 399
  • 1
  • 3
  • 3
9
votes
2 answers

The D*-Lite algorithm

I'm trying to implement the D*-Lite pathfinding algorithm, as described in the 2002 article by Koenig and Likhachev, for Boost::Graph. I think I've gotten a decent grasp on the basic ideas and theory behind it, but I'm having a problem understanding…
carlpett
  • 12,203
  • 5
  • 48
  • 82
7
votes
2 answers

On Path Finding: a detailed description for a layman of the D* algorithm

The large network (of small world graph type) I wish to deal with is dynamic in nature, new nodes are added and subtracted frequently. Presumably using D* over A* would be a better way to detect paths in this dynamic environment? How solid is D*?…
Setori
  • 10,326
  • 11
  • 40
  • 46
5
votes
2 answers

Approaches to a Dynamic Pathfinding Algorithm

My A* implementation works well for my static environment. If I would now like to work with a dynamic environment, i.e. certain costs between my nodes change while we are traversing from the start to the finish. From my reading so far I have found…
AntonD
  • 51
  • 1
  • 2
4
votes
5 answers

Pathfinding algorithm creating loops

I've implemented the D*-Lite algorithm (here's a description, it's an algorithm for doing pathfinding when edge costs change over time), but I'm having problems with doing the edge cost updates. It works mostly, but sometimes it gets stuck in a…
carlpett
  • 12,203
  • 5
  • 48
  • 82
4
votes
3 answers

Pathfinding with Dynamic Obstacles

I am implementing a simulation that requires me to have some pathfinding. A* works fine for me when my environment does not change. LPA* and D* Lite work fine for me when I encounter a static obstacle that is not in my original map. However, how…
tezo
  • 41
  • 1
  • 1
  • 2
3
votes
1 answer

Why does D* Lite need to traverse the graph backwards?

If the reason is because the start node location is always changing, can't we just modify the g cost of each node in the OPEN set instead of the h cost? (e.g. subtract by the cost of the edge you just traversed)
Chara
  • 1,045
  • 10
  • 21
2
votes
2 answers

Best algorithm for path finding in a tower defense

A have read about A* as well as D* and similar, and i'm not able to choose between them. What is the best searching algorithm when it comes with many searches(50 searches every tick) and with many different possibilities?
Bartlomiej Lewandowski
  • 10,771
  • 14
  • 44
  • 75
2
votes
0 answers

D* Lite search algorithm for robot path planning gets stuck in infinite loop. Why does my fix work and is it any slower?

For a robotics project, I've been working with I want to use the D Lite (optimized version)* from paper Koenig, 2002 for dynamic path planning for a changing occupancy grid / cost map. The idea of the D* Lite search algorithm, as described in the…
Kristoffer Rakstad Solberg
  • 51
  • 6
2
votes
1 answer

D* Lite: Can you change the start node based off actual robot location?

I'm reading through this Koening and Likhachev paper on D* Lite and each iteration it updates the starting node by traversing to a connecting node on the graph. I'm wondering about the use in real world robotics where the robot might overshoot a…
mairead
  • 21
  • 1
2
votes
0 answers

Time and space complexities of D* and D* Lite

What are the time and space complexities of D* and D* Lite? How to derive those?
J.Dow
  • 65
  • 4
2
votes
1 answer

D* Lite and LPA* Algorithms: concept of predecessors and successors

I am trying to implement the D* Lite and LPA* algorithms (both proposed by Sven Koenig), and I am having difficulty in understanding the concept of the list of predecessors and successors contained by each node. I tried looking for answers at…
Arthur Ferreira
  • 311
  • 1
  • 6
  • 18
2
votes
1 answer

Implementing D* Lite for Path-Planning - How detect Edge Cost Change?

I currently try implementing the D* Lite Algorithm for path-planning (see also here) to get a grasp on it. I found two implementations on the web, both for C/C++, but somehow couldn't entirely follow the ideas since they seem to differ more than…
EliteTUM
  • 705
  • 2
  • 8
  • 21
1
vote
0 answers

Can it be true that D* Lite re-planning around an obstacles requires finding the g-values of lots of nodes adjacent to the original path?

I believe this is a half-theoretical, half-practical question as I'm working with a D* Lite planner in C++, but there'll be no code in this post, of course. Sorry in advance for perhaps not using the precisely correct technical terms ^^ D* Lite…
OverDemon
  • 103
  • 1
  • 3
  • 8
1
vote
1 answer

D* lite: how to compare and sort that paired keys?

I'm trying to implement the D*-Lite pathfinding algorithm, as described in the 2002 article by Koenig and Likhachev for grid based navgraph. At this algorithm double-keys are used. It has left and right part. How to correctly compare this keys for…
Robotex
  • 1,064
  • 6
  • 17
  • 41
1
2