If robotic agents are to act autonomously they must have the ability to construct and reason about models of their physical environment. For example, planning to achieve goals requires knowledge of how the robot’s actions affect the state of the world over time. The traditional approach of hand-coding this knowledge is often quite difficult, especially for robotic agents with rich sensing abilities that exist in dynamic and uncertain environments. Ideally, robots would acquire knowledge of their environment and then use this knowledge to act. We present an unsupervised learning method that allows a robotic agent to identify and represent qualitatively different outcomes of actions. Experiments with a Pioneer-1 mobile robot demonstrate the utility of the approach with respect to capturing the structure and dynamics of a complex, real-world environment, and show that the models acquired by the robot correlate surprisingly well with human models of the environment.