# Target Recognition and Navigation Path Optimization Based on NAO Robot
## 4 Optimal Navigation Path for Mobile Robot
### Improved ABC Algorithm for Finding the Optimal Path  
After the map is built, the optimal path can be searched with an improved artificial bee colony algorithm in the map. However, the traditional ABC algorithm adopts a roulette strategy. The strategy has the disadvantage of slow convergence speed and local optimum. To find a better path, a bi-directional parallel search strategy and simulated annealing algorithm are introduced to improve the traditional artificial bee colony algorithm. In the process of searching the optimal path, every time a bee walks a grid, the direction is random. The bee may move in the grid of obstacles, so the method of weight is introduced to decide the path length in Equation (16):  
\[L=\mu_{n}l+\mu_{o}l \tag{16}\]  
where \(L\) is the path length, \(l\) is the path length at each step, \(\mu_{n}\) is the weight factor without obstacles, \(\mu_{o}\) is the weight factor with obstacles. The basic theory of the bi-directional parallel search strategy is that the searcher \(X_{s}\) at the beginning and the searcher \(X_{e}\) at the end search the optimal path at the same time. If the two search paths overlap, the search path of two searchers is deemed as the best path. The bi-directional parallel strategy contains three situations:  
1. The two search paths do not overlap as Figure 6. The search path is the shortest path. 2. The two searchers meet at a point as Figure 7. The search path is the common search path. 3. The two search paths overlap as Figure 8. The search path is the overlap path and another search path. Figure 5: Obstacle map for path planning. Figure 6: Two paths do not overlap. The simulation annealing algorithm is from the solid annealing principle. The algorithm is used in the combinatorial optimization field and adopts an iterative solution strategy. The simulation annealing algorithm makes temperature decrease from a large value at certain parameters based on the principle of temperature drop. The procedure of updating food source with the simulation annealing algorithm is as follows:  
1. Initialize starting temperature value. 2. The food source is updated at each generation, the fitness of the new food source is \(fitness_{new}\), and the fitness of the original food source is \(fitness_{old}\), If \(fitness_{new}-fitness_{old}\leq 0\), nothing is done. Otherwise, calculate \(\Delta fitness=fitness_{new}-fitness_{old}\). 3. Determine whether to replace the original food source with \(P=e^{-\frac{\Delta fitness}{kT}}\), where \(k\) is a parameter between 0 and 1. \(T\) is the temperature value at every moment and satisfies \(T(t)=kT(t-1)\), namely, the current temperature value is the temperature after the decay of the last time. The simulation annealing algorithm will be finished if the optimization process is over. Otherwise, go to (2) to continue. When bees search the new food source around the original food source, a bi-directional parallel search strategy is adopted. Figure 9 shows that searchers at the beginning and the end find a random position in the original path and continue searching a new path from this position. Suppose the fitness of the new food source is better than the original. In that case, a simulated annealing algorithm is introduced to decide whether the new food source will replace the original food source. Figure 8: Two paths overlap. Figure 7: Two searchers meet at a point. **Remark 2**. : _The most important feature of the simulated annealing algorithm is that it can obtain more possible solutions than other algorithms when selecting the initial solution. This ensures that it does not fall into local optimality prematurely at the initial stage of the algorithm due to the tendency of the solutions. As the algorithm enters the later stage, the control parameter \(t\) decreases, and the possibility of accepting inferior solutions gradually decreases, and when \(t\) reaches the limit, the possibility of accepting inferior solutions disappears, and the probability approaches zero.