# Path Planning Based on Artificial Potential Field with an Enhanced Virtual Hill Algorithm
## 3 Virtual Hill Concept and Open Path Indicator, _New e\({}_{b}\)_
### Open Path Indicator, New \(\mathbf{e}_{b}\)
#### 3.3.1 Two-Directional Obstacle Measurement and \(New\)\(e_{b}\)  
In the simulation environment, the range sensor is configured in a radial form with the center of the robot as the origin. The degree of openness in both directions is estimated using the rate of change in the detection distance according to the measurement angle of each sensor data. In order to calculate the rate of change in the obstacle detection distance, it is expressed as a polar coordinate system fixed to the center of the robot. Figure 6 shows the polar coordinate system with the origin at the center of the robot and the angle of each sensor data set in the simulation. The angle and detection distance for each sensor data are expressed as \(\theta_{i}\) and \(r_{i}\). At the moment when the robot is trapped in the LM, the rate of change in the outline of the obstacle is calculated for both the left and right directions based on the \(n\)-th sensor data that measured \(\mathbf{P}_{to}\). The one with the larger value is considered the open path and becomes the direction for the robot to move. When the contour of the two-directional obstacle is expressed as continuous functions \(\chi_{p}\) and \(\chi_{m}\), the moment of the LM is shown in Figure 7. The differential lengths \(d\chi_{p}\) and \(d\chi_{m}\) in the polar coordinate system can be written as follows. \[d\vec{\chi}_{p}=dr\ \mathbf{a}_{r}+r\ d\theta\ \mathbf{a}_{\theta}\qquad\qquad d \vec{\chi}_{m}=dr\ \mathbf{a}_{r}+r\ d\theta\ \mathbf{a}_{\theta} \tag{16}\]  
Figure 4: Direction determined by \(previous\)\(\mathbf{e}_{b}\): (**a**) the moment the robot is trapped in the local minimum; (**b**) \(\mathbf{e}_{t}\) determined by \(previous\)\(\mathbf{e}_{b}\). Figure 5: Driving path determined by \(previous\)\(\mathbf{e}_{b}\). The path length is 44.26 [m]. The rate of change in the obstacle contour for \(\theta\), \(d\chi_{p}/d\theta\) and \(d\chi_{m}/d\theta\), is as follows. \[\left|\frac{d\chi_{p}}{d\theta}\right|=\sqrt{\left(\frac{dr}{d\theta}\right)^{2} +r^{2}}\qquad\qquad\left|\frac{d\chi_{m}}{d\theta}\right|=\sqrt{\left(\frac{ dr}{d\theta}\right)^{2}+r^{2}} \tag{17}\]  
The obstacle contour is discretized as distance values received from the \(L\) sensor data, \(\{\mathbf{R}_{1}(r_{1},\theta_{1}),\ \mathbf{R}_{2}(r_{2},\theta_{2}),\ \ldots,\ \mathbf{R}_{i}(r_{i},\theta_{i}),\ \ldots \mathbf{R}_{L}(r_{L},\theta_{L})\}\). If \(dr/d\theta\) is replaced with \(\Delta r/\Delta\theta\), the sum of the power of the rate of change in each of the two directions based on the \(n\)-th sensor data may be written as follows. \[P_{sum}=\sum_{i=n}^{n+L/2}\left(\frac{r_{i+1}-r_{i}}{\Delta\theta}\right)^{2} +r_{i}^{2}\qquad\quad M_{sum}=\sum_{i=n-L/2}^{n}\left(\frac{r_{i+1}-r_{i}}{ \Delta\theta}\right)^{2}+r_{i}^{2} \tag{18}\]  
The angle and obstacle measurement distance of the \(i\)-th and \((i+1)\)-th sensor data are expressed in the polar coordinate system, as in Figure 8. The angle change \(\Delta\theta\) with the neighboring sensor data is determined according to the sensor resolution \(L\) and is calculated as \(2\pi/L\). \(P_{sum}\) is the sum of squares of the rate of change in the obstacle contour in the \((+)\) direction based on the \(n\)-th sensor data, and \(M_{sum}\) is the sum of squares of the rate of change in the \((-)\) direction. The direction with the further distance to the obstacle and the greater rate of change is regarded as an open path. That is, \(\mathbf{e}_{b}\) is set to \(+\mathbf{K}\) when \(P_{sum}>M_{sum}\) and to \(-\mathbf{K}\) when \(P_{sum}<M_{sum}\). In the map of Figure 4, _previous_\(\mathbf{e}_{b}\) is \(-\mathbf{K}\), and the robot rotates in the direction of \(-\theta\). _new_\(\mathbf{e}_{b}\), determined by the new algorithm, is \(+\mathbf{K}\), and the robot rotates in the direction of \(+\theta\), as shown in Figure 9. More efficient path planning is possible. If the degree of opening in both directions is similar by satisfying the following conditions, _previous_\(\mathbf{e}_{b}\) is maintained. _threshold_ is determined experimentally.