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

Question

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?

Answer 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