A Velocity-Based Local Navigation Approach to Collision Avoidance of Elliptic Robots

Abstract

Collision-free motion planning has been hierarchically decomposed into two parts: global and local planners. While the former generates the shortest path to the goal from global environmental information, the latter modifies the path from the global one by considering unexpected dynamic obstacles and motion constraints of mobile robots. In the local navigation problem, robots and obstacles have been approximated by simple geometric objects in order to decrease the computation time. They have been generally enclosed by circles due to its simplicity in collision detection. However, this approximation becomes overly conservative if the objects are elongated, which leads the robots to travel longer paths than necessary to avoid collisions. This dissertation presents a velocity-based approach to address the local navigation problem of anisotropic mobile robots bounded by ellipses. Compared with the other geometries, Löwner ellipse, the minimum area bounding ellipse, provides more compact representation for robots and obstacles in a 2D plane, but the collision detection between them is more complicated. Hence, it is first investigated under what conditions a collision between two ellipses occurs. To this end, the configuration space framework and an algebraic approach are introduced. In the former method, it is found that an elliptic robot can be regarded as a circular robot with radius equal to its minor radius by adequately controlling its orientation. In the latter method, the interior-disjoint condition between two ellipses is characterized by four inequalities. Next, a velocity-based approach is suggested on the basis of the collision detection so that an elliptic robot moves to its goal without collisions with obstacles. The proposed algorithm is decomposed into two phases: linear and angular motion planning. In the first phase, the ellipse-based velocity obstacle (EBVO) is defined as the set of linear velocities of a robot that would cause a collision within a finite time horizon. Furthermore, strategies for determining a new linear velocity with the EBVO are explained. In the second phase, the angular velocity is selected with which the robot can circumvent the obstacle blocking the path to the goal with the minimum deviation. Finally, the obstacle avoidance method was extended for multi-robot collision avoidance on the basis on the concept of reciprocity. The concept of hybrid reciprocal velocity obstacles is adopted in the part of linear motion planning, and the collision-free reciprocal rotation angles are calculated in the part of angular motion planning on the assumption that if one robot rotates, then the other robot may rotate equally or equally opposite. The proposed algorithm was validated in simulations for various scenarios in terms of travel time and distance. It was shown that it outperformed the methods that enclosed robots and obstacles by circles, by ellipses without rotation, and by polygons with rotation. In addition, it was shown that the computation time of the proposed method was much smaller than the sampling time, which means that it is fast enough for real-time applications.