## 1 Introduction  
Unmanned ground vehicles (UGVs) have been under the scope of research for a long period of time [1]. With the current advancements, it is now possible to integrate UGVs in a broad range of applications, such as autonomous road vehicles [2], information collection and delivery for wireless sensor networks [3], and object detection and face recognition [4]. We are interested in looking at UGV guidance systems for surveillance and exploration purposes on natural uneven rough terrains. Typically, guidance systems take into consideration the problem of path planning on traversable terrain based on predetermined constraints and limitations. Thus, the goal of this work is to propose new methods for planning energy-efficient shortest paths for UGVs crossing over natural terrains. Vehicle path planning can be categorized based on whether offline data are calculated beforehand prior to navigation or real-time sensory input data are being recorded while navigating [5]. We are interested here in the former form of navigation that considers calculating the path offline. As the power supply for UGVs is limited by the capacity of the carried batteries, it becomes important to consider planning paths with minimum energy consumption, for the purpose of extending the hours of operation [6, 7]. As will become evident in the energy cost model discussed in Section II, the vehicle energy consumption along a path depends on the distance of the path, its angle of inclination (i.e., the steepness of the hills being crossed), and the soil trafficability. The soil trafficability is the UGV's capability to cross over the surface of the terrain without getting stuck due to the wheel sinkage effect related to soil deformation. The wheel sinkage severity is characterized by the contact pressure between the vehicle's wheels and the terrain surface [8], also known as Terramechanics (vehicle/terrain mechanics). In particular, Terramechanics takes into consideration multiple factors related to the vehicle and the soil sides, known as the main Terramechanics variables [9]. For the vehicle, the main Terramechanics variables are vehicle weight, contact pressure factor, wheels grouser, slippage and friction factors, vehicle ground clearance, bogie factor, engine and transmission factors, and track/tire factor, all of which are used to calculate what is known as the _Mobility Index (MI)_. For the soil, the main Terramechanics variables are the soil cohesion, compactness, homogeneity, sheer stress generated from the vehicle on top of the soil, and humidity percentage. All of the aforementioned factors and variables are used to calculate the _Rated Cone Index (RCI)_ and the _Vehicle Cone Index (VCI)_ factors. These factors are being considered at the core of soil trafficability calculation in this paper, as will be explained later in Section 2.1. The literature concerned with UGV path planning algorithms is rich and broad; it can be mainly split into two categories. The first is concerned with constructing optimal paths using graph-based path search algorithms such as Dijkstra, Bellman-Ford and/or \(A^{*}\) methods, and the second focuses on the use of general-purpose optimization algorithms and heuristics. Examples of studies focusing on graph-based search algorithms can be found in [10; 11; 12]. The work of [10] explores the Dijkstra algorithm for dynamically solving the problem of energy-efficient path planning for UGVs dropping loads at predefined nodes. However, the study does not take the surface inclination or the soil Terramechanics into consideration. The study in [11] develops a hybrid (offline and online) energy-efficient path planning method for off-road terrain based on a Gaussian Process and an \(A^{*}\)-like algorithm. A limitation of this work is that only noninclined planer off-road terrains are considered. The work of [12] proposes an energy-efficient path planning and obstacle avoidance algorithm based on an \(A^{*}\) algorithm for UGVs on off-road rough terrains.