How do infants plan and guide locomotion under challenging conditions? This experiment investigated the real-time process of visual and haptic exploration in 14-month-old infants as they decided whether and how to walk over challenging terrain--a series of bridges varying in width. Infants' direction of gaze was recorded with a head-mounted eye tracker and their haptic exploration and locomotor actions were captured on video. Infants' exploration was an organized, efficient sequence of visual, haptic, and locomotor behaviors. They used visual exploration from a distance as an initial assessment on nearly every bridge. Visual information subsequently prompted gait modifications while approaching narrow bridges and haptic exploration at the edge of the bridge. Results confirm predictions about the sequential, ramping-up process of exploration and the distinct roles of vision and touch. Exploration, however, was not a guarantee of adaptive decisions. With walking experience, exploratory behaviors became increasingly efficient and infants were better able to interpret the resulting perceptual information in terms of whether it was safe to walk.