Analysis and possibility of modification of available algorithms for finding the optimal path on a square grid using parallel programming methods
М. I. Shakhov, O. H. Baybuz · Actual problems of automation and information technology · 2018
The task about unmanned aerial vehicle optimal path planning between two points on continuous terrain, which has obstacles, was set. Advantages and disadvantages of existing methods of continuous terrain discretization, application of which required for solution the task using computer, were considered. As the most optimal method of continuous terrain discretization the method of square grid was chosen. As selection criteria of the most optimal among existing path planning algorithms on square grid, the alteration angle was accepted. This criteria was suggested because of physical constraints of unmanned aerial vehicle during maneuvers on continuous terrain. According to the chosen criteria, review and analysis of the most widespread path planning algorithms on square grid, which are varieties of А* algorithm, was carrying out, including the short description of the principle of their work and data structures they use. As the most optimal path planning algorithm, which satisfies a given criteria, the LIAN algorithm was chosen. During testing the LIAN implementation in Delphi programming language were discovered disadvantages of this algorithm, and offered possible variants of their solution. Given that proposed and possible further modifications of LIAN will improve qualitative characteristics of founded path, and also will increase its execution time, LIAN algorithm was analyzed on the possibility of its modification using parallel programming methods. Was offer the scheme of work of parallel variant of LIAN algorithm, in which this algorithm will be divided into two parts: parallel part, which will perform integral subtask of the algorithm, and which can be implemented as an instance of one of the parallel threads, and synchronized part, which will be implemented as a main thread. In the context of reliability of software, which will be implement the parallel variant of LIAN algorithm, was determined, to which data structures, which use original LIAN algorithm, can access the synchronized part of new algorithm, and to which can access the parallel part. The specific variants of LIAN algorithm modifications, that use the parallel programming methods, which are planned in the future to implement and research on efficiency and reliability of execution, were offered.