The goal of this project is to develop non-intruding and reliable navigation systems giving the robot the ability to select natural landmarks, and to navigate with respect to them, extending in this way the autonomy range of autonomous robots operating in unknown and unstructured environments. Reliability is achieved by continuously controlling the uncertainty associated with knowledge of the environment and of the robot’s position and orientation. In the context of the project, non-intrusiveness means that the robot must be able to operate without special purpose landmarks being added to its environment. Non-intrusive operation in unstructured environments precludes navigation with respect to a set of handcrafted landmarks, and requires the robot’s ability to infer its position from learned natural landmarks of the environment using its perception system. Instead of passive reconstruction of the working space, perception is faced as a process of selectively extracting from the world the information needed to accomplish a given task, trading generality for specificity and gaining in simplicity and robustness. It is no longer a separate off-line module, but an integral part of the closed loop control system. This coupling will be explicitly addressed at the control level by assessing the compatibility of the current state of the robot’s knowledge of its environment, its mission and safety requirements. Availability of such systems has a considerable impact in many economic, social and industrial activities such as control of marine pollution, surveillance of restricted areas, surveillance of equipment, agriculture, underwater cartography and marine biology studies, to mention but a few.