Splitting the path into difficult and easy terrain speeds up path planning for robots that use “hands” to maintain balance on uneven ground.