Generalized intelligent Water Drops algorithm by fuzzy local search and intersection operators on partitioning graph for path planning problem

3.1 Representation of environment

The authors used grid based for solving the path planning. The graph G(N, E) is defined as a distributed memory for IWD algorithm. Using this method makes it easier to display obstacles. Also, in this paper, due to simplicity, ease of implementation and ability to create complex models, (x, y) coordinates plane is used. In this model, the nodes locate in the corners of grid cells and are addressable with Cartesian coordinates (x, y). Thus, there are 8 possible choices to moving the robot from each node in eight directions. Traveled distance is measured by using Euclidean distance between consecutive nodes and global path length is equal to sum of Euclidean distances between all consecutive nodes on the path [24].

3.2 Initialization parameters

In this subsection, different static parameters values of algorithm will be set. The quality of best solution is set to the worst value: q(P^B) =∞. Number of iterations (iter_max) and number of intelligent water drops (N_IWD) is determined by a positive number. Also, global update parameter (ρ _IWD) is set with a positive number between zero and one. In addition, the initial soil on each edge of graph is denoted by the constant InitSoil. Moreover, each IWD will have soil value equal to zero initially. Also, each IWD holds a list of visited nodes which is initially empty: VC(IWD) = {} [24].

3.3 Spread IWDs on the nodes of graph

Each IWD is placed at the start node that represents the current location of mobile robot. Start node is the first meeting node by all IWDs [24].

3.4 Update list of visited nodes

For each node i, adjacent node j will be chosen if node j is not an obstacle and not already in the list of visited nodes. Then the selected node j will be added in the list of visited nodes. Selection probability of each node is determined according to Equation 1. P i IWD ( j ) = ( f ( soil ( i , j ) ) ) α Huristic β Σ k ∉ VC ( IWD ) ( f ( soil ( i , k ) ) ) α Huristic β(1) f ( soil ( i , j ) ) = 1 / ɛ s + g ( soil ( i , j ) )(2)

In Equation 2, the constant parameter ɛ _s is a small positive number to prevent division by zero in the function f (soil). Foe satisfying the constraint of problem the authors used VC (IWD) set. The set VC (IWD) denotes the nodes that the IWD should not visi. In Equation 3, g (soil (i, j)) is used to keep the soil (i, j) positive. g ( soil ( i , j ) ) = { soil ( i , j ) if min ( soil ( i , l ) ) ≥ 0 l ∉ v c ( IWD ) soil ( i , j ) - min ( soil ( i , l ) ) l ∉ v c ( IWD ) else(3)

According to Equation 1, the choice of the next node has inverse relation with the amount of available soil in the path and it has direct relation with desired heuristic function. Amount of specified heuristic functions guarantee that the closest node to the destination will be selected with more probability. Denominator sum considered all possible choices (neighbouring nodes) that are not in the list of VC (IWD). Values of α and β defines weight of soil and heuristic function. These values have an equal amount [24].

The amount of soil of each edge represents past IWD’s experience in previous generations. Each IWD moves in the environment and decreases soil of edges of the traveled path. The amount of decreased soil from each edge depends on speed of IWDs and heuristic functions according to Equation 4. Δ soil ( i , j ) = vel IWD ( t + 1 ) / b s + c s . HUD ( j )(4)

For each IWD that moves from node i to j; the soil values of edges that connected i to j are reduced and the amount of soil of IWDs will be added by using Equations 5 and 6 [24]. soil ( i , j ) = ( 1 - ρ n ) . soil ( i , j ) - ρ n . Δ soil ( i , j )(5) soil IWD = soil IWD + Δ soil ( i , j )(6)

Global smooth operator search over the obtained path and check sequential moves and replace them with better moves if exists. Figure 2 shows states that will be replaced with a better one.

Figure 3 shows how this operator works. Figure 3(b) is obtained from running of this operator on the path of Fig. 3(a). This operator makes a shorter and smoother path from original path and decrease next processes runtime.

3.7 Memory for best solutions

In each generation of IWD algorithm, feasible solution removes some soil of graph and therefore guides next generation drops. But the exact behaviour of these solutions will be forgotten. Also heuristic operations on all paths in all generations increase runtime of algorithm. These operations on weak solutions usually have not a good result. So to overcome these problems the authors consider a memory for best solutions of algorithm to perform heuristic operations on them.

In IWD_PG algorithm, if there is no progress in algorithm in successive generations then more heuristic operations will be performed on solutions in memory. So, IWD_PG algorithm need less operations to improve best solutions. If there is a better solution in current generation compare with worst solution of memory, IWD_PG algorithm updates the memory and replaces them.

3.8 First intersection operator

First intersection operator works on best drops that are saved in memory. This operator considers two solutions of memory, if there is an intersection point between them. Intersection point divides paths into two sub path. First part of a path connects with second part of another path and vice versa. So, two new paths will be obtained. If fitness of new solutions is better than old one, new Solutions will be replaced. After a new solution is selected, IWD_PG algorithm uses local search on it for more improvement. Pseudo-code 1 shows details of first intersection operator. Figure 4 shows an example of this operator.

3.9 Second intersection operator

There may be no intersection between two solutions, but may exist a small distance between them. So the authors introduce second intersection operator. Second intersection operator is applied on best solutions on memory. This operator considers two solutions and selects one point from each of them with shortest distance. Then this operator applies local search operator between these two selected points.

In this case, local search operator is another run of IWD algorithm between two points of solutions with some differences. In local search run, number of initial population and number of algorithm iteration is less than main algorithm, and there is no memory. IWD algorithm in small space is able to find optimal solutions with high speed. So, if the number of iterations and the population size are relatively small, optimal response will be obtained with high speed. Figure 5 shows an example for second intersection operator. Operator finds two points that have lowest distance between two solutions, and then runs a local search between two points and connects these solutions. After this connection, second intersection operator behaves like first intersection operator. If there is an improvement new solutions take place of older one. Pseudo-code 2 explains details of second intersection operator.

3.10 Local search on sub paths based on fuzzy score

Applying the local search improves solutions fitness but this operation increases runtime. To control increasing runtime, the algorithm must find proper locations for applying local search operator. After finding these locations the algorithm needs very few local searches to obtain desired optimal solution.

The authors divide the input graph into equal subsections. This partitioning will be done in axis X or Y randomly. For example in Fig. 6, input graph divide to 4 equal sections in X axis. All sub paths that located in created subsections compare with each other by a fuzzy inference system, and then each sub path get a fuzzy score between 0 and 1. Higher score assign to a sub path that behave better than other sub paths in same subsection. Behaviour of sub paths will be determined by a fuzzy inference system. This fuzzy inference system has two inputs for each solution: 1. Traveled distance along a subsection 2. Traveled distance in other subsections.

Output of fuzzy inference system is a score for each sub path between 0 and 1. The triangular and trapezoidal membership functions are used in this fuzzy inference system, because they often provide adequate representation of the expert knowledge and simplify the process of computation.

Characteristics of inputs and output of fuzzy system is described in Table 1. Figure 7 shows fuzzy sets for input and output variables that are used in fuzzy inference system. In Fig. 7, SPL is used as an abbreviation for section path length and OSPL for other section path length. In Fig. 7, MinSPL and MaxSPL show lowest and highest length of solutions that belong to a section

respectively. For example in section three of Fig. 6, maximum length belongs to path 1 and minimum length belongs to path 2. MaxOSPL and MinOSPL show highest and lowest length of other sections for a solution respectively. For example in Section 1 of Fig. 6, SPL for path 1 equals to Sa length and OSPL equals to sum of ab and bE lengths. Table 2 shows Fuzzy rules that are used in fuzzy inference system. This system uses center of gravity method for defuzzification. Output of fuzzy inference system is a number between 0 and 1 that determines the probability of sub path selection. After a sub path is selected, IWD_PG algorithm uses local search on it for more improvement.

3.11 Fuzzy score comparison

In this stage, fuzzy scores of all sections for each solution compare with others then a sub path that is located in the section with worst performance (lowest fuzzy score) get more probability for using local search operator. Therefore, in each solution, algorithm pays more attention to sections that have lower performance than others. IWD_PG algorithm applies local search operator for selected sub path. Pseudo-code 3 shows details of this operator.

4.1 Effects of each operator

In first experiment, the authors study global smooth operator. Figure 8(b) show the model in this test. Figure 8(a) shows the comparison between Performance of IWD algorithm with and without global smooth operator. This test is an average of 5 times running of algorithms.

In Table 3, the results of the first experiment implementation for 50 runs of algorithm are given. Global smooth operator usually reduces length of solutions noticeably. According to Table 3, in some run of algorithm, if the algorithm don’t use global smooth operator, it falls in local optimum.

In second experiment, the authors consider the first intersection operator. Figure 9(b) shows a comparison between result of IWD algorithm with and without first intersection operator. This figure uses 10 runs of algorithm. It is shown in Fig. 9, optimal solution can find in early iterations by using first intersection operator. According to result of our test, best solution founded in 36th iteration of algorithm by using first intersection operator, but without it, best result is not obtained in 50th iteration. In addition, with using this operator average length of best solutions in first generation is shorter.

Figure 9(b) shows first global intersection operator does not increase speed of the algorithm significantly but saves it from falling into local optimum.

Without using first local operator that works on memory, algorithm falls in local optimum in a complex environment because algorithm finds a local optimum solution after some generation, for example path 1 in Fig. 10 is a local optimum solution. IWD algorithm without using memory just keeps behaviour of best solution and forgot other good solutions. Other solutions just affect the environment. For example in Fig. 10, after finding path1, path 2 will be founded. Path 2 has a longer length than path1 and will be forgotten without using memory but it can improve significantly with using heuristic operators like the local search.

Proposed memory in the algorithm keeps the behaviour of solutions that are near the best solution. In addition, algorithm could combine best solutions of memory and prevent from falling in local optimum.

In third Experiment, the authors want to show the effectiveness of second intersection operator. Figure 11(b) compares IWD algorithm performance with and without second intersection operator. This experiment result is obtained from average of 10 times running of algorithm. It is shown in Fig. 11(a), best result can be obtained even if second intersection operator don’t use. However, algorithm can obtains best solution in lower runtime by using this operator.

In fourth experiment the authors show how proposed fuzzy inference system works. In Fig. 12, algorithm found three paths. Fuzzy inference system divides the environment to 4 sections. Then it checks the behaviour of all solutions in each section and gives a fuzzy score to each part of solution. For example in section 1, sub path 1 has best performance; because the length of this sub path in Section 1 is lower than other sub paths, in addition sum of the length of sub path 1 in other sections is better than other solutions.

Output variable Values for all sub paths in all sections list in Table 4. Values in this table show which solution better than others in each section. In this table higher score shows better performance.

Fifth experiment shows the effect of fuzzy inference system in IWD algorithm. IWD algorithm can find optimal solution by using local search, but use of local search operation increase fitness function call. Our fuzzy inference system cause the local search operator focus on locations that solutions haven’t good performance, so number of fitness function call will be decreased. Figure 13 shows average of 10 runs of algorithm.

This figure shows that our algorithm obtains better result in lower fitness function call by using fuzzy score system. In Table 5, the results of the fifth experiment implementation are given. proposed fuzzy score system, with the same number of fitness function calls, reduced access time to optimal solution significantly and obtained better results in the mean and worst fitness value.

4.2 Comparison with previous work

In sixth test, the authors compare performance of IWD_PG algorithm with previous work. IWD_PG algorithm Have global smooth, first intersection, second intersection operators, Fuzzy Score System and a memory that hold best solutions. The authors use SPset07 to compare IWD_PG algorithm performance. SPset07 is one of the complex scenarios in SPset that used in earlier path planning study [23–25].

In this test like other pervious work, the authors run IWD_PG algorithm 15 times then compare its result with other IWD algorithm in [24] and GA algorithm in [25]. Table 6 shows the variables values in these three algorithms and their results. The results show that IWD_PG algorithm is able to find optimal solutions in all runs and access 100 percent success rate, while the number of fitness function calls is rather low.

Figure 14 shows a comparison between IWD_PG algorithm and IWD algorithm in [24]. IWD_PG algorithm obtains optimal solution faster. In [24] the algorithm obtains better solutions in early iteration by using a repair mechanism for infeasible solutions. But IWD_PG algorithm after finding feasible solutions, improves the solution faster, and obtains optimal solution. Figure 14 shows that the best path can found in 2600th fitness function calls that is less than previous IWD algorithm.