Ah, I figured it out. It is because he isn't using the distance to the landmark as the heuristic but the difference between the distance to the current location and the distance to the target. This means landmarks behind you will be negative (or useful in an undirected graph). This is also important for making the heuristic admissible as otherwise your heuristic would say zero when you are standing on top of the landmark.