Path Planning Methods in an Environment with Obstacles (A Review)

Planning the path is the most important task in the mobile robot navigation. This task involves basically three aspects. First, the planned path must run from a given starting point to a given endpoint. Secondly, it should ensure robot’s collision-free movement. Thirdly, among all the possible paths that meet the first two requirements it must be, in a certain sense, optimal.Methods of path planning can be classified according to different characteristics. In the context of using intelligent technologies, they can be divided into traditional methods and heuristic ones. By the nature of the environment, it is possible to divide planning methods into planning methods in a static environment and in a dynamic one (it should be noted, however, that a static environment is rare). Methods can also be divided according to the completeness of information about the environment, namely methods with complete information (in this case the issue is a global path planning) and methods with incomplete information (usually, this refers to the situational awareness in the immediate vicinity of the robot, in this case it is a local path planning). Note that incomplete information about the environment can be a consequence of the changing environment, i.e. in a dynamic environment, there is, usually, a local path planning.Literature offers a great deal of methods for path planning where various heuristic techniques are used, which, as a rule, result from the denotative meaning of the problem being solved. This review discusses the main approaches to the problem solution. Here we can distinguish five classes of basic methods: graph-based methods, methods based on cell decomposition, use of potential fields, optimization methods, фтв methods based on intelligent technologies.Many methods of path planning, as a result, give a chain of reference points (waypoints) connecting the beginning and end of the path. This should be seen as an intermediate result. The problem to route the reference points along the constructed chain arises. It is called the task of smoothing the path, and the review addresses this problem as well.