The gait of a multi-segment inchworm robot is a series of actuator actions that will change the shape of the robot to generate a net motion. In this paper, we model the multi-segment inchworm robot as a finite state automaton. Gait generation is posed as a search problem on the graph described by the automaton with prescribed state transitions. The state transitions are defined based on the kinematics of robot locomotion. The auxiliary actuator concept is introduced. Single-stride and multi-stride gait generations are discussed. Single-stride gaits exhibit fault-tolerant and real-time computation features that are necessary in actual applications. Both computer simulation and experimental hardware platform are developed for various aspects of gait generation and planning.