# Path Planning Based on Artificial Potential Field with an Enhanced Virtual Hill Algorithm
## 3 Virtual Hill Concept and Open Path Indicator, _New e\({}_{b}\)_
### Virtual Hill Concept  
APF can be expressed as the sum of the attractive potential corresponding to the goal and the repulsive potential generated by the obstacle [10]. The artificial forces that determine the control output of the robot, that is, the linear velocity and angular velocity, are the negative gradients of the potentials [10; 12]. The attractive potential \(U_{att}\), force \(\mathbf{F}_{att}\), and the repulsive potential \(U_{rep}\), force \(\mathbf{F}_{rep}\), are obtained as follows. \[U_{att}=\left\{ \begin{array}{cc}k_{a}d^{2},&d\leq d_{0}\\ k_{a}\big{(}2d_{0}d-d_{0}^{2}\big{)},&d>d_{0}\end{array} \right. \tag{1}\]  
\[\mathbf{F}_{att}=-\
abla U_{att}=\left\{ \begin{array}{cc}-2k_{a}\Big{(} \mathbf{P}-\mathbf{P}_{goal}\Big{)},&d\leq d_{0}\\ -2k_{a}d_{0}\frac{\mathbf{P}-\mathbf{P}_{goal}}{d},&d>d_{0}\end{array} \right. \tag{2}\]  
\[U_{rep}=\left\{ \begin{array}{cc}\frac{1}{2}k_{r}\Big{(}\frac{1}{\rho}-\frac {1}{\rho_{0}}\Big{)}^{2},&\rho\leq\rho_{0}\\ 0\,,&\rho>\rho_{0}\end{array} \right. \tag{3}\]  
\[\mathbf{F}_{rep}=-\
abla U_{rep}=\left\{ \begin{array}{cc}k_{r}\Big{(}\frac {1}{\rho}-\frac{1}{\rho_{0}}\Big{)}\frac{\mathbf{P}-\mathbf{P}_{eq}}{\rho^{3} },&\rho\leq\rho_{0}\\ 0\,,&\rho>\rho_{0}\end{array} \right. \tag{4}\]  
\(d_{0}\) is the radius of the quadratic range, \(k_{a}\) is the proportional gain of the function, and \(d=\left\|\mathbf{P}-\mathbf{P}_{goal}\right\|\). In the quadratic area, the attractive force is proportional to distance between the goal and the robot. If \(d_{0}\) is large, a robot smoothly and slowly stops at the goal. \(\mathbf{P}\) and \(\mathbf{P}_{goal}\) are the position vectors of the robot and the goal. \(\rho_{0}\) is a potential field's distance limit of repulsive potential influence, and \(\rho\) is the shortest distance between the robot and its closest obstacle, where \(\rho=\left\|\mathbf{P}-\mathbf{P}_{co}\right\|\). \(\mathbf{P}_{co}\) is the position vector of the closest obstacle to the robot. The entire artificial force \(\mathbf{F}_{total}\) is \(\mathbf{F}_{att}+\mathbf{F}_{rep}\). The robot is controlled by this force, which is converted to speed and angular velocity according to the force-to-velocity conversion method [32]. However, before arriving at the goal, the robot is trapped in local minima and stops driving when the attractive force and the repulsive force are the same or very similar. In [32], the virtual hill allows the robot to escape from the LM (local minimum) by generating an extra force instead of an attractive force when in the LM area. The artificial force, \(\mathbf{F}_{total}\), applied to the robot from the moment of being trapped in the LM to the moment of escape, is \(\mathbf{F}_{rep}+\mathbf{F}_{ext}\). After the robot is out of the LM, \(\mathbf{F}_{total}\) = \(\mathbf{F}_{att}\)+\(\mathbf{F}_{rep}\) is applied to move to the goal. Extra force can be applied even in complex environments and does not create a new local minimum. Extra potential is applied from the moment the robot is trapped in the LM until the escape is completed and is defined as follows. \[U_{ext}=-k_{c1}\Psi+k_{c2}\rho^{2} \tag{5}\]  
\(k_{c1}\) and \(k_{c2}\) are proportional constants. \(\rho\) is the distance between the robot and the closest obstacle. \(\Psi\) is the path integral, which is the line integral for \(\gamma\) and expressed as \[\Psi=\int_{\gamma}d\Psi,\qquad\gamma(t)\ :\ \{\mathbf{Q}(t^{*}):t_{0}\leq t^{*} \leq t\ \ \ \text{and}\ \ \ t_{0}\leq t\leq t_{k}\ \} \tag{6}\]  
\[\mathbf{Q}(t_{i})=\mathbf{P}_{co}(t_{i})\qquad\qquad\qquad\qquad\qquad\qquad \qquad\qquad\qquad\qquad\qquad\text{where}\ i=0,1,\ \cdots,\ K \tag{7}\]  
\(\gamma\) is defined as the path of the closest obstacles, indicating the trajectory of the closest obstacle while the robot is moving within the LM. The concept of \(\gamma\) is shown in Figure 2a [34]. \(t_{0}\) is the time when the robot is trapped in the LM, and \(t_{k}\) is the time when it escapes from the LM. \(\mathbf{Q}\) is the position vector of the closest obstacle on the continuous trajectory.