The unmanned exploration of planets such as Mars requires a high level of autonomy because of the communication delays between robots in space and their Earth-based stations. This affects all the components of the system: planning, sensing, and mechanism. In particular, such a level of autonomy can be achieved only if each robot has a perception system that can reliably build and maintain models of the environment. The perception system is a major part of the development of a complete system that includes planning and mechanism design. The target vehicle is the Spider-bot, a four-legged walking robot shown in Figure DP8.2 (a), being developed at NASA Jet Propulsion Laboratory [18]. The control system of one leg is shown in Figure DP8.2 (b).