1

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 sorting in priority queue? Should I compare left parts firstly and compare right only if it is equal? Or should I choose some other way?

Robotex
  • 1,064
  • 6
  • 17
  • 41
  • It's been years since I've read the paper, but it definitely tells you exactly what to do with both halves. Perhaps it would be helpful to read their paper(s) on LPA\*, the algorithm D\*-lite is built on top of. They have multiple that go into a _lot_ of detail. – BlueRaja - Danny Pflughoeft Oct 30 '19 at 16:46

1 Answers1

1

You should compare the left parts 1st (f-values). Only if they are equal you should compare the second part which is basically the g-values. It is a lexicographic comparison. This and other concepts used in D* lite are explained in the video lecture from mit opencourseware on youtube: https://youtu.be/_4u9W1xOuts

yasht
  • 195
  • 1
  • 15