Robot motion planning among moving obstacles

Abstract

This thesis presents a new approach for planning a robot's trajectory that avoids static and moving obstacles and minimizes motion time, subject to robot dynamics and actuator constraints. This approach consists of first computing a coarse trajectory that avoids the obstacles and satisfies an approximation of the actuator constraints. Then this trajectory is used as the initial guess of a dynamic optimization that satisfies obstacle avoidance, robot dynamics and the true actuator limits. The first step of the approach is based on the concept of Velocity Obstacle (VO) that defines, at every instant in time, the set of colliding velocities between the robot and the obstacles. The VO set is computed using the relative velocity between the robot and each obstacle, and is instrumental in determining the set of robot velocities avoiding all obstacles and satisfying approximate system dynamics and actuator limits. Within this set, the best avoidance maneuver is chosen heuristically so that the trajectory resulting from the sequence of maneuvers reaches the goal and minimizes motion time. The second step of the approach consists of refining the trajectory with a dynamic optimization that minimizes motion time, subject to the true robot's dynamics, actuator constraints, and time varying obstacle constraints. The dynamic optimization is based on Pontryagin's Minimum Principle and uses a gradient descent method. These two steps lead to the implementation of a powerful and flexible planner that combines the advantages of heuristics with those of dynamic optimization. Heuristics in fact, captures the non-analytic aspects of motion planning, such as sequence of obstacle avoidance, conservative or aggressive maneuvers, and so on, thus characterizing the global structure of the trajectory. Dynamic optimization on the other hand, ensures feasibility and optimality of the trajectory thus guaranteeing its local correctness. This approach is demonstrated for planning the motions of an automated vehicle in an Intelligent Vehicle Highway System (IVHS) scenario, and of an articulated robot moving in a dynamic environment. This motion planner is suitable to a wide range of applications. The Velocity Obstacle method is very fast and, although approximate, it can be used for real time planning. The Dynamic Optimization is computationally intensive, but yields optimal solutions, which can be used when off-line planning is acceptable.