Abstract: In this paper we present the work done at the Canadian Space Agency on the problem of planetary exploration. One of the main goals is the over-the-horizon navigation of a mobile robot on a Mars like environment. A key component is the ability to plan a path using maps of different resolutions and also to refine/replan when more data becomes available. Our algorithms on path planning and path segmentation are presented together with results from two years of experiments in realistic conditions.