TY - JOUR

T1 - Two-stage shortest path algorithm for solving optimal obstacle avoidance problem

AU - Gasilov, Nizami

AU - Doǧan, Mustafa

AU - Arici, Volkan

PY - 2011/5

Y1 - 2011/5

N2 - In 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 find 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 search space makes the next stage more efficient and endurable for real-time applications. In the second stage of the algorithm, the elliptic region is meshed with squares, the side length of which is set in agreement with the minimum distance between obstacles. It is prohibited to pass through the squares that intersect obstacles. Thus, by discretization the problem becomes the shortest path problem in a graph, and is solved by applying the Dijkstra's algorithm. The proposed two-stage algorithm is verified with numerical simulations. Obstacles are chosen randomly. A target position is selected and fixed. For different starting points, the algorithm is tested repeatedly. The results show that the proposed algorithm can be applied to find an optimal solution for the obstacle avoidance problem.

AB - In 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 find 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 search space makes the next stage more efficient and endurable for real-time applications. In the second stage of the algorithm, the elliptic region is meshed with squares, the side length of which is set in agreement with the minimum distance between obstacles. It is prohibited to pass through the squares that intersect obstacles. Thus, by discretization the problem becomes the shortest path problem in a graph, and is solved by applying the Dijkstra's algorithm. The proposed two-stage algorithm is verified with numerical simulations. Obstacles are chosen randomly. A target position is selected and fixed. For different starting points, the algorithm is tested repeatedly. The results show that the proposed algorithm can be applied to find an optimal solution for the obstacle avoidance problem.

KW - Dijkstra's algorithm

KW - Graph theory

KW - Obstacle avoidance

KW - Path planning

UR - http://www.scopus.com/inward/record.url?scp=80052807427&partnerID=8YFLogxK

U2 - 10.4103/0377-2063.83650

DO - 10.4103/0377-2063.83650

M3 - Article

AN - SCOPUS:80052807427

SN - 0377-2063

VL - 57

SP - 278

EP - 285

JO - IETE Journal of Research

JF - IETE Journal of Research

IS - 3

ER -