Abstract: Footstep planning is a new idea of motion planning for humanoid robots.The model of humanoid footstep planning is presented in this paper,and it is implemented by A^* search algorithm based on the heuristic cost function.Specifically,for planning in complex multi-obstacle environments,a compound footstep transition model based on alterable potential footstep placements is proposed.Simulation experiments verify the validity and completeness of the model and the planning algorithm,and the planning results satisfy the requirements of online humanoid motion planning.Also,numerical experiments verify the good performance of the compound footstep tansition model implemented in planning in complex multi-obstacle environments.