Based on input steering commands, a legged robot may select a target gait. Based on the target gait, the legged robot may obtain a list of gait controllers. Each gait controller may define a gait of the legged robot, and include validity tests and steering commands. The legged robot may apply a cost function to the gait controllers, where the cost for a gait controller is based on a difference between the steering commands of the gait controller and the input steering commands, and a proximity of the legged robot to obstacles should the legged robot operate according the gait controller. The legged robot may reorder the list in increasing magnitude of the cost function, and traverse the list until a validity test associated with a particular gait controller passes. The legged robot may actuate its legs according to the steering commands of the particular gait controller.