Avoiding Dynamic Obstacles with Real-time Motion Planning using Quadratic Programming for Varied Locomotion Modes

Abstract

We present a real-time motion planner that avoids multiple moving obstacles without knowing their dynamics or intentions. This method uses convex optimization to generate trajectories for linear plant models over a planning horizon (i.e. model-predictive control). While convex optimizations allow for fast planning, obstacle avoidance can be challenging to incorporate because Euclidean distance calculations tend to break convexity. By using a half-space convex relaxation, our planner reasons about an approximated distance-to-obstacle measure that is linear in its decision variables and preserves convexity. Further, by iteratively updating the relaxation over the planning horizon, the half-space approximation is improved, enabling nimble avoidance maneuvers. We further augment avoidance performance with a soft penalty slack-variable for-mulation that introduces a piecewise quadratic cost. As a proof of concept, we demonstrate the planner on double-integrator models in both single-agent and multi-agent tasks-avoiding multiple obstacles and other agents in 2D and 3D environments. We show extensions to legged locomotion by bipedally walking around obstacles in simulation using the Linear Inverted Pendulum Model (LIPM). We then present two sets of hardware experiments showing real-time obstacle avoid-ance with quadcopter drones: (1) avoiding a 10m/s swinging pendulum and (2) dodging a chasing drone.