# Target Recognition and Navigation Path Optimization Based on NAO Robot
## 3 Navigation Theory and Navigation Map
### Navigation Map Building  
The main purpose of the robot navigation path study is to update the value of \(Q\) at different states and different behaviors in real-time. There are four movement directions of the robot from the current state to the next state: forward, backward, left, and right. The selection of next state depends on the value of \(Q\). The movement probability \(P\) is introduced to decide next direction. The movement probability is written as Equation (14).  
\[P(a_{i}|s)=\frac{Q(s,a_{i})}{\frac{4}{\sum\limits_{j}\left|Q(s,a_{j})\right|}} \tag{14}\]  
where \(P(a_{i}|s)\) represents the probability of direction \(a_{i}\) in the current state \(s\). \(Q(s,a_{i})\) represents the \(Q\) value of direction \(a_{i}\) in the current state \(s\). The direction of maximum probability is the direction of the robot to move to a new state.  
Before the robot begins to execute the navigation task, the initial value of \(Q\) is 0 in any behaviors in any state, the robot updates the value of \(Q\) in real-time during walking according to the surrounding environment. When the robot meets obstacles, a penalty factor is added. When the robot meets the final landmark, an incentive factor is added. The scope of the obstacle is \(R_{1}\), when the distance between the obstacle and the robot is less than \(d_{1}\); the penalty factor \(R(s,a)\) is \(-100\), namely, \(R(s,a)=-100\). The scope of the end landmark is \(R_{2}\), when the distance between the final landmark and the robot is less than \(d_{2}\); the incentive factor \(R(s,a)\) is \(100\), namely, \(R(s,a)=100\). Figure 4 shows this process.  
The value of the penalty factor and incentive factor is written as Equation (15).  
\[R(s,a)=\left\{\begin{array}{cc}100&r<d_{1}\\ 0&(r>d_{1})\&\&(r>d_{2})\\ -100&r<d_{2}\end{array}\right. \tag{15}\]  
where \(r\) represents the distance between the robot and obstacles or between the robot and the final landmark in the current state.  
In many cases, the traditional K-means algorithm can only classify specified groups which limit the popularization of the K-means algorithm. Therefore, the traditional K-means algorithm is improved in this experiment. The procedure of classifying data with the improved K-means algorithm is as follows:  
1. Randomly choose \(k\) elements from n elements as the center of \(k\) clusters.
2. According to average, each object is assigned to similar clusters.
3. Recalculate the distance between each cluster and the shortest cluster.
4. If the distance of any two clusters is less than \(d_{0}\), the two clusters are merged. The average distance of two original cluster centers is taken as the center of a new cluster. Otherwise, go to step (2) to continue.
5. If the result no longer changes, the algorithm is over. Otherwise, go to step (4) to continue.  
The procedure of Simultaneous Localization and Mapping is as follows under the premise of avoiding obstacles:  
1. Collect the surrounding environment with two sonar sensors.
2. Classify these data with the K-means clustering algorithm to detect the number of obstacles and the distance between robot and obstacle.
3. Make sure the value of penalty and incentive factor according to the detecting results.
4. The robot updates \(Q\) value according to Equation (12).
5. The robot selects the next state according to Equation (14).
6. If the robot meets the end landmark, the experiment is over. Otherwise, go to (1) to continue.