Two-stage Shortest Path Algorithm for Solving Optimal Obstacle Avoidance Problem

摘要

AbstractIn most of the path-planning applications, the controlled object (mobile robot) is expected to reach its predetermined target by following the shortest path and avoiding the obstacles. This navigation problem is also called optimal obstacle avoidance. In this work, obstacles are assumed to be motionless circles in different sizes. The object is supposed to be a point robot. The two-stage algorithm is proposed to And a numerical solution to the problem. At first stage, the method, which is optimal for one step, is applied iteratively. In every step of the method the first obstacle on the straight line between the current position and the target is assumed to be a single obstacle. The proposed method is realized using geometric representations. Some evaluations are made to prove that the method is convergent. The path obtained at the first stage might not be optimum. However, its length can be used to limit the feasible region through an ellipse, which contains the shortest path. Thus, the reduced s...