Mobile autonomous robots have finally emerged from the confined spaces of structured and controlled indoor environments. To fulfill the promises of ubiquitous robotics in unstructured outdoor environments, robust navigation is a key requirement. The research in the Simultaneous Localisation and Mapping (SLAM) community has largely focused on optical sensors to solve this problem, and the fact that the robot is a physical entity has largely been ignored. In this work a hierarchical SLAM framework is proposed that takes the interaction of the robot with the environment into account.  A sequential Monte Carlo filter is used to generate local map segments with a combination of visual and embodied data associations. Constraints between segments are used to generate globally consistent maps with a focus on suitability for navigation tasks. The proposed method is experimentally verified on two different outdoor robots. The results show that the approach is viable and that the rich modeling of the robot with its environment provides a new modality with the potential for improving existing visual methods and extending the availability of SLAM in domains where visual processing alone is not sufficient.