Corresponding author: Aldoshkin Dmitry N., Postgraduate Student, Institute of Space and Information Technologies, Siberian Federal University, Krasnoyarsk, 660100, Russian Federation, e-mail: aldoshkind@gmail.com

Received on March 10, 2016
Accepted on March 24, 2016

Mobile robot motion is a complex field of research intensively studied during the recent decades. In this article the authors consider the problem of path planning for a mobile robot with two degrees of freedom (ground vehicle) in a priori undetermined environment. The authors formulate the path planning problem and propose a computationally effective algorithm for solving the problem of movement path construction in a priori unknown environment. The proposed algorithm decomposes the path planning problem in two main phases: construction of a graph-based presentation of a free space and graph search. The authors propose a dual graph of a free space polygon triangulation as a means of a free space presentation. This approach allows us to minimize the graph size without an uncontrollable loss of accuracy of environment representation. This approach uses Dijkstra algorithm for the conduct path search on a free space graph, but it is possible to replace this algorithm by another one with account of the particular constraints. The proposed algorithm envisages a continuous collection of the environment information by a robot using its sensors. A brief review of the existing approaches to the problem is presented, as well as a theoretical comparison of these approaches with the proposed one in terms of the computational complexity theory. The proposed algorithm's computational efficiency is demonstrated via a computational experiment, where the proposed and reference algorithms operate on a set of synthetic environment models of different geometric size, but with a similar structure. An experiment proved the algorithm's supremacy in speed.

Keywords: simultaneous localization and mapping, mobile robot, path finding, trajectory planning, path planning

For citation:
Aldoshkin D., Tsarev R. Mobile Robot Path Planning in the Presence of Obstacles and Lack of Information about the Environment, Mekhatronika, Avtomatizatsiya, Upravlenie, 2016, vol. 17, no. 7, pp. 465—470.
DOI: 10.17587/mau.17.465-470

To the contents