Comment by GregBuchholz

Celestial navigation plus accurate clocks. I'd think this would be especially good on a planet without clouds (as long as your planet rotates fast enough, so I guess Mercury is out). Anyone know if Mars has any polar stars?

https://en.wikipedia.org/wiki/Celestial_navigation