One of the difficult problems to solve has always been and still remains the problem of finding a path either in a graphic chart or a graphic maze of large size. The main problem is that traditional algorithms require a lot of time due to combinatorial complexity. At the same time, both classical algorithms based on the search of variants (such as Dijkstra's algorithm, A*, ARA*, D* lite), and stochastic algorithms (ant algorithm, genetic), alongside with algorithms based on morphology (wave) are not always able to achieve the goal. The article proposes a new modification of the path-finding algorithm, which is a hybrid of the following: the morphological operations on graphic chart approach and genetic algorithm having a useful property of elasticity in time. The experiments (both synthetic and real data) have shown the feasibility of the proposed idea and its comparison with the most commonly used algorithms of contemporaneity.
Finding a path in the maze has been and remained rather a
complex computational task [
In this paper, we consider the problem of finding the optimal route of movement on the map, given graphically. Let there be given a map as a matrix:
11 ⋯ 1 = ( ⋮ ⋱ ⋮ ) , (1)
1 ⋯ where aij = {wall, free, start, finish}; n – image width; m – image height.
It is required to find a path P of length l such that:
= { 1, 2 , … , }, → , where ki = {left, right, up, down}; n – number of turns; l – geometric path length.
Graphical representation, complex topology, and large map size result in the following problems, in the context of autonomous robot path-finding algorithms:
As a rule, autonomous robots are used to work in conditions that are dangerous for human life and health, which often implies danger also for the robot itself. When the values of environmental parameters are beyond the permissible values for the operation of the robot, it is necessary to plan an evacuation route as quickly as possible. Accordingly, the algorithm must have the property of elasticity in time that is the ability to vary the location time, even if it decreases the quality of the discovered path.
Graphical representation means a checkered field having marks and implying the possibility of movement through the checker squares. The problem is that each free square is a decision point concerning the direction of further movement, which greatly increases combinatorial complexity in the case of large free spaces.
The non-formalized representation imposes restrictions on both: the use of graph-based algorithms and the reuse of the previous algorithm runs results: since the map is an image and you can just use methods based on morphology, but on large maps in case of reruns, they are much slower than graph-based algorithms.
A large number of nodes of the graph is a classical problem of algorithms based on the search of variants, since combinatorial, and as a consequence, computational complexity increases, at best, in proportion to the number of nodes. The use of heuristics based algorithms improve, in general, the efficiency of algorithms based on the enumeration of possibilities, however, in case of unfavorable for heuristics topology of the maze, these algorithms work extremely inefficiently.
To solve these problems, this paper proposes a hybrid algorithm based on morphological operations in image maps for pre-optimization, formalization of the map to the graph-based one as a transition table of a finite-state automation with a preliminary estimate of the nodes and calculation of arcs weights, and the application of a modified genetic algorithm to search the paths in the graph. 3. Use of morphological operations for preliminary optimization of the map
For preliminary optimization of the map it has been decided to use
morphological transformations [
Suppose A is the map image (1), W is the convolution kernel, in such case:
( −1, −1) ( −1, ) = ( ( , −1) ( , ) −1, +1) ( , +1) ) , ( +1, −1) ( +1, ) ( +1, +1) where w = {wall, free, no matter}; i, j are coordinates relative to the center point.
Suppose ( , ) is a convolution operator, so: ( , ) = { , where
∈ , ∈ .
In this case, standard operations such as erosion, dilation, make-and-break are ill-adapted for solving the problem.
Therefore, to optimize the maze, we’ve developed our own kernel packages, which are created to fill with “inefficient path” labels. Their main task is to reduce the number of paths and branches that can
be discarded in advance and thereby downscale the dimension of the problem. The main kernels were chosen as follows: elimination of nonconvex areas, going across which is not advantageous for geometric reasons (Fig. 1). This allows us to eliminate from consideration those paths that will be obviously longer (for example, diagonally).
There is an optimization of both: rectangular areas with multiple inputs and cubes of 2x2 square (bottom row in Fig. 1-3).
In all figures, the black color is the indicator of the presence of obstacles, light gray presents free spaces, dark gray indicates that the state of the square does not matter in this convolution operation.
Mathematically, the kernel is expressed by the following convolution matrix (for example, for the kernel in ) .
Fig2. Convolution kernels to remove the 2x2 cubes Fig3. "Greedy" convolution kernels to fill large empty areas After these convolution kernels’ run over all maps dead-end branches would shrink and turn to be completely full, wide paths and large spaces are compressed either to the optimal paths or road forks of single width and that results in the map image being formalized into the graph. In this case, the paths are treated as arcs because of the single width, while the forks are regarded as nodes of the graph. In addition, the nodes are estimated by the farness distance from the target point, transition table is constructed, weights are counted and sequences of commands to move along arcs are recorded. In other words, after this step the problem is put into a formalized finite state bot.
An example of the original map and the results of the morphology are shown in Fig. 4 and 5. For illustrative purpose a map of the Bezhitsky district of Bryansk was taken, the image of which was obtained from the Yandex Map Service (people’s map). In the original map, white indicates areas, which are good for moving, while black is the indicator of unfitted areas. Fig1. Convolution kernels to fill non-convex regions
Fig 5. Marked paths and road forks
The image of the result has been inverted in brightness for better readability, where white presents not available for traffic areas, light grey indicates available ones, dark grey specifies the ways of single width and black is the indicator of single width road forks.
In its original state, the map contained 61951 locations with possible movements in more than one direction (road forks). The use of morphological operations described above reduced the dimension of the problem to 647 road forks.
Even after reducing the dimension of the problem, the use
of algorithms based on the search is impractical for reasons of
graphical representation and a large number of the transition
graph nodes. Morphological algorithms are suitable only for
initial optimization and are not good for being the only means
in solving the problem of finding paths. The proposed solution
is connected with stochastic algorithms. However, the ant
algorithm tends to hit local maxima and according to studies [
The first and the most serious disadvantage is the” fragility” of the genotype. From the point of view of the current task the way can be estimated either by attaining the goals or in case of covering the distance. The consistent nature of the pathway, shifted to the chromosomes with which standard genetic operators work, leads to the fact that random changes in the genotype violate the integrity and correctness of the paths resulting in the impossibility to evaluate their optimality in the context of the active task.
In terms of implementation it is easier to use approaches that involve a fixed chromosome length. In this case, it is convenient to represent the genotype in the form of chromosomes, in which genes are forks and loci are respectively directions of movement at the forks. This raises the following problem: with a large number of forks very long chromosomes are obtained, that increases the combinatorial complexity and “fragility " of the genotype significantly.
These problems make the use of the classical genetic algorithm almost impossible in the context of the abovementioned task. However, the work has developed a modification of the algorithm which is permissive for the successful purposes of the problem. The basic principles of modification are as follows.
Using a greedy algorithm to correct an individual's genotype is a way to counter destructive mutations. The use of this mechanism is designed to reduce the search space by creating obviously integral parts of the path, to align the population.
The use of stigmergy mechanism, which is aimed at indirect interaction of individuals in order to share knowledge about the world. Stigmergy is the basic principle of the ant colony optimization algorithm, however, in respect to genetics, it is advantageous to use this approach not in the framework of the population, but through many generations of one and the same individual, i.e. learning cycles.
When using automatic adjustment of the genotype on the basis of the greedy algorithm and stigmergy, the classical mutation and cross are useless, since their effect is offset by the described above algorithms. To avoid this, allele fixation and elitism mechanisms have been introduced. Elitism gives the possibility to disable the actions of all modified genetic operators, in order not to lose good genotypes for retraining under the action of stigmergy. Fixation of alleles allows blocking within a certain number of generations the effect of greedy algorithm on genes having been under mutation and cross operations. The result of the algorithm is shown in Fig. 6. The obtained path is shown in red.
Fig 6. The result of the algorithm
For the combined algorithm testing the images of mazes generated in Daedalus were used, as well as images of maps in the areas with selected roads.
At first there were some tests, which were carried out to compare the full-time operation of the genetic algorithm and then in the mode with disabled operators of crossing and mutation. The main idea of the test is to illustrate that using greedy algorithm with stigmergy solely is less optimal than applying a combination of genetics. The result is an acceleration of convergence by using crossing and mutation operators.
Then a series of comparisons of the developed algorithm with the algorithm D * lite took place, taking into account the fact that D* lite is the most popular in the control devices of autonomous robots. These comparisons were made by using large mazes with the best algorithms based on the variety of being tried topologies, average cases, unfavorable topology (multiple nested horseshoe-shaped obstacles –fig. 7), as well as by using the terrain map small image.
The main interest lies in the card with bad topology. The image of the maze is generated by Daedalus, then it is manually amended: horseshoe-shaped walls have been added and besides it, some passages have to be also made because of the walls, which create unattainable areas in some places making impossible to find the way to the goal.
In the case of an advantageous topology D* lite made a quick work of it, for the average case and on the terrain map it dispatched the developed hybrid algorithm, but if it were disadvantageous topology D* lite would fail because of 2 GB memory. The exact time of the algorithms is given in table 1. Table 1 D* lite Developed algorithm
Time taken by an algorithm Complex Average Advantageous topology case topology
OOM 225 129
In the course of investigation we've succeeded in the development of a hybrid algorithm for finding a path in the maze, surpassing the analogues used in practice in complex topologies on large maps.
Further research is required by policies of step-by-step map corrections with rebalance of the graph, the use of concurrent and adaptive crossover and mutation operators.