Real-Time Feasible Footstep Planning for Bipedal Robots in Three-Dimensional Environments Using Particle Swarm Optimization

Footstep planning in various three-dimensional environments is formulated as an optimization problem, which is solved using a particle swarm optimi-zation. The objective function for optimization is designed to achieve real-time footstep planning considering arrival at the goal with effective not only foot placements but also walking periods, kinematic constraints: obstacle avoidance and hardware limitations, and dynamic constraints for the bipedal dynamics: stability while walking and feasibility of footsteps in a walking pattern generator. Specifically, optimization objectives are to minimize remaining distance to the goal, lateral movement, rotational movement, and walking period variation. Three penalties are also consid-ered depending on the situations. The first penalty is for obstacle collision avoidance along with prevention of unstable walking due to excessive footstep height variation. The second penalty is for walking satisfying stable zero-moment point condition along with the foot collision avoidance. The third penalty is for feasible footstep planning in a walking pattern generator. Any approxi-mation or precomputation is not required for the proposed footstep planning method. The validity of the proposed method is verified through experiments in various 3-D environments with static and dynamic obstacles.