High speed on-line motion planning in cluttered environments

Abstract

This paper presents an efficient algorithm for online obstacle avoidance that accounts for robot dynamics and actuator constraints. The robot trajectory (path and speed) is generated on-line by avoiding obstacles optimally one at a time. This reduces the original problem from one with m obstacles to m simpler problems with one obstacle each, thus resulting in a planner that is linear, instead of exponential, in the number of obstacles. While this approach is quite general and applicable to any cost function and to any robot dynamics, it is treated here for minimum time motions, a point mass robot, and planar circular obstacles.