2
$\begingroup$

I'm trying to modify the original D* Lite algorithm adding a margin constraint wrt to any nearby obstacle to be satisfied for each selected cell in the path. This causes the edge cost function between nodes to be asymmetric: let x and y be 2 adjacent nodes, with x being distant to an obstacle less than the given margin, while y is far enough and is perfectly traversable. The cost from x to y is then 1, but the cost from y to x will be infinite due to the closeness of x to an obstacle. I noticed that sometimes the algorithm get stuck in calculating the shortest path and I'm wondering if the asymmetry of the edge costs can be the cause. As for the heuristic, I'm using the euclidean distance which is admissible.

$\endgroup$

1 Answer 1

2
$\begingroup$

Yes, D*-lite is a directed graph algorithm, so it works fine with asymmetric edge weights by definition.

However, note that the heuristic being admissible is not sufficient. According to the paper, it must be consistent. Based on what you described, I would guess Euclidean distance would be consistent for your graph, but we can't know for sure without seeing the graph.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.