# 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.2 Dead-End Algorithm  
When the robot encounters a dead end while traveling to the destination, it is efficient to avoid it unless the destination is inside the dead end. When a robot encounters a dead end, if it is not on the way to its destination, it can avoid the dead end using the dead-end algorithm. Figure 10a shows the path planning results when \(\mathbf{e}_{t}\) is determined by _previous_\(\mathbf{e}_{b}\). This is the path where the robot trapped in the LM at point \(\mathbf{P}(\mathbf{t}_{0})\) moves to the destination along the obstacle ABCD section using the virtual hill technique. The ABCD section is a dead end and unnecessarily increases the robot's travel distance and time. In this case, the robot can also come back through the dead-end algorithm just as people come back after confirming that it is a dead-end path. Figure 8: The \(i\)-th and the \((i+1)\)-th vectors of the L sensor data. Figure 10: Dead-end algorithm: (**a**) driving path determined by a virtual hill with _previous_\(\mathbf{e}_{b}\). The path length is 32.87 [m]. (**b**) The moment the robot notices a dead end. (**c**) Driving path determined by the dead-end algorithm. The path length is 28.99 [m]. Figure 9: Driving path determined by _new_\(\mathbf{e}_{b}\) (in comparison to Figure 5). The path length is 13.82 [m]. The robot returns to the point \(\mathbf{P}(\mathbf{t}_{0})\) and then moves in the opposite direction. The robot travels along obstacles closer to the destination. If the dead-end algorithm is applied when encountering a dead end, the robot can avoid the dead end without completely entering it, as shown in Figure 10c. This algorithm is applied between the beginning and the end of the LM. The flowchart of the dead-end algorithm is shown in Figure 11. The criteria for determining that the robot is at a dead end are as follows. \[ifr(\theta)<maxRange,-\frac{\pi}{2}\leq\theta\leq\frac{\pi}{2}\textit{then the path is a dead end}. \tag{20}\]  
\(r(\theta)\) is the distance of the obstacle detected by the sensor, and \(maxRange\) is the sensor's maximum detection distance. If the obstacle detection distance of all sensor data in the \([-\pi/2,\pi/2]\) section corresponding to the front portion of the robot is shorter than \(maxRange\), it is determined that the robot has entered a dead end. If the robot is at a dead end, whether to enter or avoid further depends on the location of the destination. The following two conditions are examined to determine whether the destination is inside or outside the dead end. \[\left\{ \begin{aligned} \left|\mathbf{P}^{\mathbf{L}}_{goal} \right|<r_{k}\\ -\frac{\pi}{2}\leq\alpha\leq\frac{\pi}{2},\hskip 14.226378 pt \mathbf{P}^{\mathbf{L}}_{goal}=\left|\mathbf{P}^{\mathbf{L}}_{goal}\right| \angle\alpha\end{aligned} \right. \tag{21}\]  
\(\mathbf{P}^{\mathbf{L}}_{goal}\) represents the location vector of the destination for the local coordinate system with an origin at the center of the robot, as shown in Figure 6a. \(r_{k}\) is the measured distance of the \(k\)-th sensor data, which is at the angle closest to the vector \(\mathbf{P}^{\rightarrow}_{goal}-\mathbf{P}\) among all sensor data. \(\left|\mathbf{P}^{\mathbf{L}}_{goal}\right|<r_{k}\) means that there is no obstacle between the robot and the destination. \(\alpha\) is the angle of \(\mathbf{P}^{\mathbf{L}}_{goal}\) in the local coordinate system. \(-\pi/2\leq\alpha\leq\pi/2\) means that the goal is at the front portion of the robot. If both conditions are satisfied, it is determined that the  
Figure 11: Flowchart of the dead-end algorithm. destination is inside the dead end. If the destination is inside the dead end, the robot is controlled to the destination with \(\mathbf{F}_{total}=\mathbf{F}_{att}+\mathbf{F}_{rep}\). This \(\mathbf{F}_{att}\) is an attractive force heading to the initially set goal (destination). If the destination is outside the dead-end road, the robot returns to \(\mathbf{P}(\mathbf{t}_{0})\) and moves in the opposite direction.