## 2 Preliminaries
### Distance and Energy-Cost Calculations  
Let \(n\) be a general node in the terrain graph, and let \(x_{n},y_{n}\), and \(z_{n}\) denote its coordinates in space, respectively. The three-dimensional (3D) Euclidean distance between two nodes \(m\) and \(n\) can be calculated as follows  
\[d(m,n)=\sqrt{(x_{m}-x_{n})^{2}+(y_{m}-y_{n})^{2}+(z_{m}-z_{n})^{2}}. \tag{2}\]  
Considering the distances \(d(m,n)\) as link labels in a shortest path algorithm would result in the path with shortest physical distance from source to destination. However, our objective here is to also produce an energy-efficient route to comply with the UGV's power limitations. Thus, for energy-cost calculations, we employ the model from [27]. The angle of inclination for any two neighboring nodes on the terrain can be expressed as follows  
\[\phi(m,n)=tan^{-1}\Bigg{(}\frac{z_{n}-z_{m}}{\sqrt{(x_{m}-x_{n})^{2}+(y_{m}-y_ {n})^{2}}}\Bigg{)}. \tag{3}\]  
It is easy to see that a positive angle of \(\phi(m,n)\) reflects that the UGV is going up a hill, while a negative angle means that it is going down a hill. The inclusion of the energy cost into the physical model does not only serve the purpose of creating energy-efficient paths, but it also captures the case when it is unfeasible for the UGV to climb up a steep hill based on the angle of inclination and the available power. Our work assumes that the UGV is moving at a fixed velocity \(v\). Furthermore, we assume that the only two forces exerted on the UGV are gravity and the wheel-terrain friction. The combination of these two forces can be expressed as \(mg(\mu\cos\phi+\sin\theta)\), where \(m\) is the mass of the UGV, \(g\) is the acceleration of gravity, and \(\mu\) is the friction coefficient. It was reported experimentally in [28] that this methodology is limited to a small error margin of 1% for small slopes. It can be easily shown that the energy cost for a link between two nodes is \(mgd(m,n)(\mu\cos\phi(m,n)+\sin\phi(m,n))\). Now, we discuss the terrain untrafficability due to power limitations while climbing steep hills. We start with quantifying the power available in-hand for the UGV by defining the vehicle's output force as \(F_{UGV}=P_{max}/v\), where \(P_{max}\) is the maximum output power by the UGV. We conclude that, based on the used physical model, the maximum angle of inclination for a hill that the UGV is able to move forward up within its capabilities is  
\[\phi_{UGV}=\sin^{-1}\bigg{(}\frac{F_{UGV}}{mg\sqrt{\mu^{2}+1}}\bigg{)}-\tan^ {-1}(\mu). \tag{4}\]  
This concept can be expanded to any terrain with a slope. It should be stated that wheels' traction on soil can be lost, especially at great inclination angles. Thus, the static friction \(\mu_{st}\) for the UGV is considered. The traction-loss cases can occur when the angle of inclination is larger than \(\mu_{st}\)[27]. This angle can be obtained as  
\[\phi_{st}=\tan^{-1}(\mu_{st}-\mu). \tag{5}\]  
This further imposes restrictions on he UGV's capability of crossing steep inclined hills. Therefore, we can define \(\phi_{up}\) as the dead angle, above which the UGV is unable to pass, either due to power limitations or loss of traction. In particular,  
\[\phi_{up}=min(\phi_{UGV},\phi_{st}). \tag{6}\]  
In other cases, when the UGV is heading down a steep hill, the resultant external force exerted on the UGV is zero. This only occurs when the UGV's degree of inclination is smaller than \(\phi_{down}\), which is defined as the critical breaking angle. It can be shown that [22]  
\[\phi_{down}=-\tan^{-1}(\mu). \tag{7}\]Subsequently, if the UGV's angle of inclination is \(\phi_{UGV}<\phi_{down}\), the UGV is moving under its own weight because of the gravitational force vector alignment in the same direction of vehicle movement. Therefore, the energy cost is negative. It should be noted that the only type of energy required under such scenario is for braking to maintain a constant UGV velocity. Additionally, there is energy needed for turning the vehicle's wheels.