Abstract: In order to imitate biological gait accurately and develop the movement potential of hexapod robots comprehensively, a discrete gait model is built based on the discretization of foot trajectories and the fusion of CPG (central pattern generator) model and reflect model.Firstly, the stable position state space is constructed based on stability analysis, and the complex gait planning is transformed into the sequencing problem of position states in the stable position state space.Then, a free gait generation algorithm is proposed, and the optimized free gait planning algorithm for specific terrain is investigated by taking the average stability margin as performance index based on Markov decision process, which is good at dealing with sequential decision problem.The gait experiment results of the prototype show that both the free gait generation algorithm and the optimized algorithm can generate stable gait which accords with motion characteristics of creatures to some extent, and the optimized free gait planning algorithm can plan the optimized gait for specific terrain based on average stability margin quickly.