The DLR Space Administration started the Initiative "VaMEx - Valles Marineris Explorer" with the aim to explore craters on Mars up to 7 km deep fully autonomous by a heterogeneous swarm of robots. This environment appears due to the earlier volcanic activity as well as the references to water resources extremely promising for a variety of scientific issues. To have a comprehensive picture of Valles Marineris and thus potential niches for extraterrestrial life, areas which are difficult to access have to be included in the exploration in particular. Utilizing a hominid robot platform and novel approaches for fully autonomous positioning, mapping and navigation will help to meet and to deal with the environmental conditions.