Search

Search Results

• STUDY OF PATH PLANNING METHODS IN TWO-DIMENSIONAL MAPPED ENVIRONMENTS

  М. Y. Medvedev, V.K. Pshikhopov, D.О. Brosalin, B.V. Gurenko, М.А. Vasileva, Hamdan Nizar

  2022-08-09

  Abstract ▼

  The article studies the problem of motion planning in two-dimensional mapped environments.
  The review and analysis of known planning algorithms based on Voronoi diagrams, probabilistic
  road maps, rapidly growing random trees, Dijkstra algorithms, A*, D* and their modifications, artificial
  potential fields and intelligent heuristics are carried out. Based on the analysis, it is concluded
  that classical methods in dynamic environments require significant costs in terms of calculation time
  and the amount of memory used. The conclusion is made about the relevance of the development of
  algorithms that increase the efficiency of known planning methods. In this regard, this article is devoted
  to the development of a modified algorithm of rapidly growing random trees and the study of its
  effectiveness in comparison with known methods. The article presents a modified algorithm for rapidly
  growing random trees, characterized in that when checking for a path to a new potential node of
  the tree, the path to some area near the specified node is checked. This reduces the number of nodes
  in the tree under construction. The developed algorithm is first compared with the traditional algorithm
  of fast-growing random trees. The comparison is made by the trajectory calculation time, the
  amount of memory required, the path length and the percentage of situations in which the trajectory
  to the target point was successfully found. Next, the developed algorithm is compared with the planning
  algorithms of other classes. The study uses representative samples of numerical experiments and
  various environments that differ in the density of obstacles and the presence of mazes. A study of
  planning algorithms using the results of experiments on a ground-based wheeled robot is also being
  conducted. Based on the results of numerical and real experiments, conclusions are drawn about the
  advantages and disadvantages of the developed algorithm of motion planning and the feasibility of its
  application in various environments.