Energy-optimal trajectories for skid-steer rovers

Abstract

This paper presents the energy-optimal trajectories for skid-steer rovers on hard ground, without obstacles. We obtain 29 trajectory structures that are sufficient to describe minimum-energy motion, which are enumerated and described geometrically; 28 of these structures are composed of sequences of circular arcs and straight lines; there is also a special structure called whirls consisting of different circular arcs. Our analysis identifies that the turns in the trajectory structures (aside from whirls) are all circular arcs of a particular turning radius, R′, the turning radius at which the inner wheels of a skid-steer rover are not commanded to turn. This work demonstrates its paramount importance in energy-optimal path planning. There has been a lack of analytical energy-optimal trajectory generation for skid-steer rovers, and we address this problem by a novel approach. The equivalency theorem presented in this work shows that all minimum-energy solutions follow the same path irrespective of velocity constraints that may or may not be imposed. This non-intuitive result stems from the fact that with this model of the system the total energy is fully parameterized by the geometry of the path alone. With this equivalency in mind, one can choose velocity constraints to enforce constant power consumption, thus transforming the energy-optimal problem into an equivalent time-optimal problem. Pontryagin’s Minimum Principle can then be used to solve the problem. Accordingly, the extremal paths are obtained and enumerated to find the minimum-energy path. Furthermore, our experimental results by using Husky UGV provide the experimental support for the equivalency theorem.

Keywords

trajectory planning energy-efficiency equivalency theorem skid-steer rover optimal control

1. Introduction

Due to their mechanical simplicity, maneuverability, and robustness, skid-steer rovers are widely used for excavation and loading, planetary exploration (Kassel 1971; Reid et al. 2015), and other field robotics applications. Energy-optimal navigation is an important aspect of any of these applications, especially when autonomously planning paths in power-starved environments. However, the power consumption for skid-steer rovers can be high, and also highly variable, compared to other steering mechanisms such as explicit or Ackerman steering due to the lateral motion resistance while skidding in a turn. A key challenge of skid-steer mobility is thus the power and energy consumption of this steering configuration.

1.1. Sample-based and local planning methods

There are many applications where robots operate without obstacles, such as in open fields, but also many in which obstacles are present. Optimal path planning in the presence of obstacles is always challenging – for example, the Piano Mover’s Problem (LaValle 2006; Reif 1979), a special case of motion planning under differential constraints, is NP-hard. Generally, path planning with differential constraints are two-point boundary value problems (BVPs) (Heath 2018). However, the techniques to solve BVPs cannot efficiently or entirely solve the path planning problems while considering obstacles (LaValle 2006).

Hence, path planning for vehicles with differential constraints in complex environments motivates sampling-based approaches (e.g., Rapidly exploring Random Trees (RRT) introduced first by LaValle (1998)). However, there is also a need to generate feasible (in terms of the differential constraints) local paths between the nodes that sampling-based/global planning algorithms generate. Accordingly, local planning methods (LPM) provide useful motion primitives for global planning methods (LaValle 2006). In path planning in the presence of obstacles, each global path consists of several local paths that are generated in an obstacle-free environment, representing the space between nodes that are already chosen to avoid obstacles in a complex environment. When there are no obstacles, a single local path is sufficient. It may be possible to explicitly optimize these simpler local paths (in terms of either length, time duration, energy consumption, etc.). There are two probable advantages of considering such optimal local paths, as opposed to ad hoc candidates, to build global paths (LaValle 2006):

1. The global paths are closer to the global optimum answer

2. The process is more computationally efficient

1.2. Sample-based algorithms for global planning method

There are many different numerical sampling-based methods to globally search for efficient paths for different types of rovers in complex environments (such as in the presence of obstacles). These include several versions of rapidly exploring random tree algorithms as mentioned earlier, potential fields, heuristic and meta-heuristic approaches, deep reinforcement learning, and discretized/finite-horizon optimal control approaches. In all such methods, and others surveyed but omitted for brevity, the optimization problem is eventually solved numerically and the path types are not obtained analytically.

In related numerical work on energy efficient trajectories, Tokekar et al. (2014) work toward optimizing energy consumption for car-like robots; they first show how to find energy-optimal velocity profiles along a given path, and then build a discretized graph composed of individual circular arcs (or straight lines) connecting the vertices.

For global planning methods for skid-steer rovers specifically, there has been some work related to time-efficiency and energy-efficiency. Yamamoto et al. (1998) investigate time-optimal paths for skid-steer rovers in the presence of obstacles; they find quasi-optimal solutions by using a B-spline parametrization technique. Dunlap et al. (2011) find energy-efficient paths by using Sampling Based Model Predictive Optimization (SBMPO), which automatically satisfies differential constraints by sampling from the feasible space of control inputs. SBMPO generates nodes on a graph where a model predicts the position of the rover after that the sampled control inputs have been applied for some specified duration. The cost at each node is the sum of the cost of getting to that node (which can be predicted by the model used) plus an “optimistic” estimate (i.e., meant to guarantee to not over-estimate) of the remaining cost to get to the goal from that node. After a node is expanded with some fixed number of new nodes and each is assigned a cost, a priority queue is re-sorted to pick the next node to expand (the one with lowest cost). Reese (2015) proves that SBMPO gives the optimal path on the graph, but only once the priority queue is completely exhausted.

Recent attempts at global planning methods to determine energy-optimal paths for skid-steer rovers all use SBMPO (Gupta et al. 2017; Pentzer et al. 2016). Recent work by the authors identifies issues related to suboptimality and the “optimistic” estimates in these implementations (Effati et al. 2020, 2021, 2022; Effati 2020; Effati and Skonieczny 2023). Even a fully optimally implemented SBMPO provides only the optimal solution on the graph of sampled nodes. To approach a global optimum in continuous space, the sampling must thus be dense. However, it is mentioned by Gupta et al. (2017) that computation time is already a limiting consideration. These challenges in practice related to suboptimality and computational cost align exactly with the points raised by LaValle (2006) motivating optimal local paths (LPM).

1.2.1. LPM for different vehicles

There have not been any analytically obtained optimal LPM developed for skid-steer rovers that consider energy-efficiency. In related work, however, several analytical approaches to find shortest distance or time LPM paths for car-like, differential drive, omni-directional, and rigid body rovers moving in obstacle-free environments have been published. Dubins (1957) proposes a method to obtain the shortest path for a car-like rover that can only travel forward, subject to a constraint that the average curvature everywhere is less than or equal to a given constant value. Johnson (1974) obtains the Dubins paths using another method, namely, Pontryagin’s Minimum Principle. This principle, which is utilized in optimal control theory, helps to solve the constrained optimization problem of controlling a dynamical system to move from one state to another. Reeds and Shepp (1990) design the shortest path for car-like rovers that can go both forwards and backwards. In addition, Sussmann and Tang (1991), Soueres and Laumond (1996), as well as Boissonnat et al. (1994) use Pontryagin’s Minimum Principle to develop the shortest path for the Reeds-Shepp car. Qin et al. (2000) use Pontryagin’s Minimum Principle to obtain the energy-efficient trajectory for car-like rovers. The optimal control inputs are analytically obtained and Bang-bang theory is utilized to obtain the trajectory; however, the set of extremal paths is not provided. Balkcom and Mason (2000) (Balkcom 2000; Balkcom and Mason 2002) design time optimal trajectories for differential drive vehicles in an unobstructed plane by the use of Pontryagin’s Minimum Principle. In addition, Chitsaz et al. (2009) design the shortest path for differential drive mobile robots by using Pontryagin’s Minimum Principle. Also, Balkcom et al. (2006) (Balkcom and Kavathekar 2008; Wang and Balkcom 2012) use the Pontryagin’s Minimum Principle to obtain time-optimal paths for omni-directional vehicles. Furthermore, Balkcom et al. (2018) (Wang and Balkcom, 2020) obtain 3D time-optimal trajectories for rigid bodies. Firstly, they obtain the necessary conditions for optimality using Pontryagin’s Minimum Principle and a geometric method. Then, they design the optimal trajectories by sufficiently dense sampling. Furtuna et al. (2008) (Furtuna and Balkcom 2010; Furtuna et al. 2011; Furtuna 2011) investigate an algorithm for a general parameterized model of mobile robots. They use Pontryagin’s Minimum Principle and prove several other theorems to design the algorithm. In addition, some research on the structure of time-optimal trajectories for rigid bodies are performed by Furtuna et al. (2013). The challenge after obtaining the optimal control inputs from the Pontryagin’s Minimum Principle is to limit the number of switches between them. Accordingly, Lyu et al. (2014) (Lyu and Balkcom 2015, 2016; Lyu 2016) constrain the number of switches between the optimal controls to avoid the chattering phenomenon.

Table 1 presents a summary of the literature in this subsection. Indeed, it is indicated that there is no LPM for energy-optimal trajectory planning considering skid-steer rovers. A detailed explanation about the novelty of this paper is further presented in Contributions.

Table 1.

The summary of the literature presented in LPM for different vehicles.

Paper	Rover type	Optimized for	LPM (analytical approach)	Numerical approach
(Dubins 1957; Johnson 1974; Reeds and Shepp 1990)	Car-like	Min. Length	✓
(Balkcom and Mason 2002)	Differential drive	Min. Time	✓
(Chitsaz et al. 2009)	Differential drive	Min. Length	✓
(Tokekar et al. 2014)	Car-like	Min. Energy		✓
(Yamamoto et al. 1998)	Skid-steer	Min. Time		✓
(Gupta et al. 2017)	Skid-steer	Min. Energy		✓
This paper	Skid-steer	Min. Energy	✓

1.2.2. Hybrid approach

Hybrid algorithms can be used to take advantage of both sample-based (for global planning methods) and analytical approaches (for local planning methods). For example, Chaudhari et al. (2014) use analytically obtained Dubins path (Dubins 1957) to have differential drive rovers traverse between the waypoints of the global path, while avoiding obstacles, obtained by A*. Although Dubins paths are the shortest path (as a LPM) for car-like rovers, using these paths obtains smoother energy-efficient paths compared to paths obtained by A* alone or even smoothed A*-paths. This raises the question of what would happen if their utilized LPM was specifically designed for energy-efficiency of differential drive rovers? In this paper, the research is not on differential drive rovers. However, to deal with similar situations for skid-steer rovers, we develop an energy-optimal LPM and thus provide the opportunity for more investigations on other related energy-optimal global planning methods.

1.3. Energy and time optimization equivalency

Solving the energy-optimal path planning problem by using its equivalent time-optimal problem is one of the main contributions of this paper. Therefore, related literature on energy-time equivalency is identified and contrasted to our approach. Possible equivalencies between time optimization and energy optimization problems have been given preliminary consideration before. Ioslovich et al. (2015, 2017) and Gutman et al. (2015) state that by selection of special constraints for a rigid body with the dynamic equations of motion (Ioslovich et al. 2017), the minimum time problem and minimum energy problem are equivalent which means that they result in the same trajectory. In their approach the final time for the energy-efficient problem is fixed as the optimal time taken from the solution of the minimum time problem. In other words, they are searching for the most energy-efficient path from among already time-optimal paths. In the case of a unique time-optimal path (not unusual in practice), this reduces to a search within a set of cardinality 1. Such a restrictive search can miss lower energy solutions that take some extra time. In this work, we do not restrict the search space (for the minimum energy problem) by taking a fixed time based on the minimum time problem.

There are also some papers that have worked on time-energy minimization in terms of a trade-off between optimal time and optimal energy (Shiller 1996; Verscheure et al. 2008; Ji et al. 2019; Zhang and Cassandras 2019; Nshama and Uchiyama 2018; Lyu et al. 2017; Faraj and Basir 2016). However, none of them work on equivalency between time and energy in their research.

1.4. Contributions

As summarized above, there is a general lack of analytical work on skid-steer rovers to find paths minimizing the energy consumption. Before finding the general energy-optimal trajectory structures, preliminary work was performed by the authors to find the optimal path within a class of predefined (Circular arc - Line - Circular arc (CLC)) paths (Effati and Skonieczny 2018; Effati et al. 2020; Fiset et al. 2023). However, there had been no work on general non-predefined path types. Accordingly, this research explores optimally energy-optimal local paths (LPM) for skid-steer rovers by using an equivalency theorem that is developed in this paper.

The contributions of this work include the following:

• The equivalency theorem presented in this paper allows us to obtain the optimal path for the energy-optimal path planning problem considering any proper constraint (i.e., one that does not restrict the range of turning radii) on velocity. As a result, the constant power velocity constraint is utilized to convert the energy-optimal path planning problem for skid-steer rovers to an equivalent time-optimal problem.

• This work finds and describes energy-optimal local paths (29 trajectory structures) for skid-steer rovers under the practical assumptions elaborated in the next section.

• Another contribution is further exploration of the importance of R′ in energy-optimal local trajectories for skid-steer rovers. The overwhelming majority of energy-optimal trajectories include circular arcs of radius R′.

2. Problem statement

Firstly, the energy-optimal path planning problem is defined. The solution to this problem is sought for any and all proper velocity constraints (as will be defined later in Definition 3, and will be shown to not limit the solution search space in any way). Then, it is proved that there exist optimal trajectories for the optimal path planning problem. Afterwards, a well-known existing power model for skid-steer rovers is introduced and analyzed. This power model is utilized for all the analysis in this paper.

2.1. Problem

The problem is to find an energy-optimal trajectory (Figure 1) between a given starting (A) and end pose (C). Let the configuration of the rover at time t be $x (t) = {[x (t), y (t), θ (t)]}^{T}$ , the position and heading of the rover in the global coordinate system. The desired starting and end pose are given by x(t = 0) = x₀ and x(t = t_f) = x_f, where t_f is a free parameter. The control inputs are the left and right wheel velocities V_l and V_r.

Figure 1.

The general arc-based path (non-predefined class of paths) with the specified start and end pose.

The optimization problem is

\begin{array}{llll} \underset{V_{r}, V_{l}, t_{f}}{minimize} & \int_{0}^{t_{f}} P dt \\ subject to & \dot{x} = \frac{V_{r} + V_{l}}{2} c o s θ, \\ \dot{y} = \frac{V_{r} + V_{l}}{2} s i n θ, \\ \dot{θ} = \frac{V_{r} - V_{l}}{B_{s}}, \\ x (0) = x_{0}, y (0) = y_{0}, θ (0) = θ_{0}, \\ x (t_{f}) = x_{f}, y (t_{f}) = y_{f}, θ (t_{f}) = θ_{f} \end{array}

(1)

where P is the power which will be developed in equation (22). Also, B_s is slip track that will be explained in the next subsection (equation (12)).

Assumptions:

• The rover is skid-steer

• The rover can do point turns or go forward or backward with any turning radius

• The rover moves on hard flat ground

• There are no obstacles

• The rover center of mass is located at its centroid

• The trajectory is piecewise continuous

• Recall that no specific velocity constraints are required. Practical constraints to consider include motor saturation (|V_r| < v_max, |V_l| < v_max), constant v_c (see Figure 4), and velocities that maintain constant power.

2.2. Existence theorem

The existence of optimal trajectories was originally stated by Soueres and Boissonnat (1998) (Theorem 2 on page 99) and used by Furtuna (2011) (subsection 3.4 on page 16). The theorem is slightly restated to make notation consistent with this paper:

There exists an optimal trajectory for the control set of U from x₀ to x_f (two states in $S E$ (2)), if the following criteria are met:

1. There exists a function g(x) such that $\dot{x} = g (x) u$

2. g(x) is a locally Lipschitzian function of x

3. The control set U is a compact convex subset of $R^{m}$

4. There exists an admissible trajectory from x₀ to x_f

5. There exists a corresponding trajectory x(t) for any initial state of x₀ and control law of u(t), which is defined for the whole duration of the control law.

In the following, it is easily proved that the skid-steer rover verifies the conditions:

1. As it is indicated in (Equation (1)), for a skid-steer rover

(\begin{array}{l} \dot{x} \\ \dot{y} \\ \dot{θ} \end{array}) = (\begin{array}{lll} \cos θ & - \sin θ & 0 \\ s i n θ & c o s θ & 0 \\ 0 & 0 & 1 \end{array}) (\begin{array}{l} u_{x} \\ u_{y} \\ u_{θ} \end{array})

(2)

where u_x = (V_r + V_l)/2, u_y = 0, and u_θ = (V_r − V_l)/B_s. Therefore,

g (x) = (\begin{array}{ll} c o s θ & - s i n θ & 0 \\ s i n θ & c o s θ & 0 \\ 0 & 0 & 1 \end{array})

(3)

2. sin θ and cos θ are Lipschitz continuous.

Therefore, g(x) is locally Lipschitz continuous.

3. For the problem mentioned in (Equation (1)), the considered U is a closed convex control space.

4. A skid-steer rover can travel from any starting pose to any end pose by doing a Point turn - Line - Point turn (PLP) maneuver. Therefore, there always exists an admissible trajectory.

5. From equation (2) it is known that

x (t) = x_{0} + \int_{0}^{t} g (x) u (τ) d τ

(4)

The integral in equation (4) always exists because u(t) = (u_x, u_y, u_θ) is Lebesgue integrable. Hence, x(t) which is the corresponding trajectory to u(t) always exists.

2.3. Power modeling

The kinematics for skid-steer rovers are presented and then incorporated into a popular existing power model.

2.3.1. Skid-steer rovers kinematics

Rover kinematics can be defined based on the concept of Instantaneous Centers of Rotation (ICR) (Mandow et al. 2007). The parameters (x_ICRv, y_ICRv), (x_ICRr, y_ICRr), and (x_ICRl, y_ICRl) are the vehicle, right hand-side, and left hand-side ICR positions, respectively. These parameters are shown in Figure 2 and are as follows:

x_{ICRv} = - \frac{v_{y}}{ω_{z}}

(5)

x_{ICRl} = \frac{V_{l} - v_{y}}{ω_{z}}

(6)

x_{ICRr} = \frac{V_{r} - v_{y}}{ω_{z}}

(7)

y_{ICRv} = y_{ICRl} = y_{ICRr} = \frac{v_{x}}{ω_{z}}

(8)

v_{y} = \frac{V_{r} x_{ICRl} - V_{l} x_{ICRr}}{x_{ICRl} - x_{ICRr}}

(9)

v_{x} = \frac{(V_{l} - V_{r}) y_{ICRv}}{x_{ICRl} - x_{ICRr}}

(10)

ω_{z} = \frac{V_{l} - V_{r}}{x_{ICRl} - x_{ICRr}}

(11)

Figure 2.

A schematic figure of a skid-steer rover and its associated instantaneous centers of rotation (ICRs).

where v_x, v_y, and ω_z are the velocity in X, velocity in Y, and angular velocity around the Z axis of the rover’s body frame, respectively. Recall that V_r and V_l are the right and left wheel velocities (i.e., wheel angular velocities multiplied by wheel radius), respectively, and are control inputs. Martínez et al. (2005) show that the positions of ICRs can be assumed to be approximately constant for a particular terrain type; although these are in fact dynamics-dependent in general, they show them to be bounded for skid-steer rovers on hard flat ground traveling at “moderate speeds,”¹ which is an operating principle to keep in mind when weighing the validity of this kinematic approach for particular applications. ICRs can be estimated by taking experimental measurements or via dynamics simulations, for a particular soil type and narrow range of speeds.

W and L are the distance between the center of left and right wheels in the X direction and the distance between the center of front and rear wheels in the Y direction, respectively. Also, the slip track (B_s) is defined as follows:

B_{s} = x_{ICRr} - x_{ICRl}

(12)

and can also be seen in Figure 2. The value B_s is taken to be constant for a specific terrain type and skid-steer rover. For example, B_s for a Clearpath Husky on hard ground (concrete) is estimated to be 1.3 m (Effati et al. 2020).

Based on the assumptions listed in the problem statement, the rover center of mass is located at its centroid. Accordingly, the following equations are derived:

x_{ICRr} = - x_{ICRl}

(13)

y_{ICRv} = y_{ICRl} = y_{ICRr} = 0

(14)

From equation (9) through equation (14) we conclude that

v_{x} = 0

(15)

v = v_{y} = \frac{V_{r} + V_{l}}{2}

(16)

ω_{z} = \frac{V_{r} - V_{l}}{B_{s}}

(17)

x_{ICRr} = \frac{B_{s}}{2}

(18)

x_{ICRl} = - \frac{B_{s}}{2}

(19)

From the fact that |v| = R|ω_z| as well as equations (16) and (17), the turning radius can be expressed as

R = \frac{B_{s}}{2} | \frac{V_{r} + V_{l}}{V_{r} - V_{l}} |, V_{r} \neq V_{l}

(20)

Lemma 1

R = R′ is the boundary between the separate cases where V_r and V_l are either of equal or opposite sign.

Proof

R′ is the turning radius at which a skid-steer rover’s inner wheels are not commanded to turn. Without loss of generality consider the right wheel as the inner wheel. Therefore, at R′ the right velocity is zero (V_r = 0).

By using equation (20) the following relation for R′ is obtained:

R^{'} = \frac{B_{s}}{2} | \frac{V_{l}}{- V_{l}} | = \frac{B_{s}}{2}

(21)

■

Definition 1

R′ is half of the slip track $(R^{'} = \frac{B_{s}}{2})$ .

Note: Based on Martínez et al. (2005), the positions of left and right ICRs are bounded and may be assumed constant for a specific terrain. Therefore, B_s (Equation (12)) and R′ are constant.

2.3.2. Power model

A popular power model, based on a frictional wheel-terrain contact assumption, developed by Morales et al. (2010, 2009) and used by Pentzer et al. (2016, 2014), is adapted here for usage according to the problem definition and assumptions given in the previous section. The power model is as follows:

P = μ | ω_{z} | \sum_{n = 1}^{N} (p_{n} ‖ \vec{a_{n}} - {\vec{C}}_{r, l} ‖) + G (| V_{r} | + | V_{l} |)

(22)

where P is power consumed, μ is the friction coefficient, ω_z is the angular velocity, p_n is the normal force on each wheel, V_r and V_l are right and left wheel velocities,

‖ {\vec{a}}_{n} - {\vec{C}}_{r, l} ‖

(Figure 3) is the distance from the right or left ICR to a wheel, G is the internal and rolling resistance coefficient, and N is the number of wheels. Also, V_r and V_l are the control inputs for the power model. This power model, using Figure 3, along with the center-of-mass at centroid assumption, is expanded as follows:

\begin{array}{l} P = μ | ω_{z} | p (\sqrt{{(\frac{L}{2} + y_{ICRr})}^{2} + {(\frac{W}{2} - x_{ICRr})}^{2}} \\ + \sqrt{{(\frac{L}{2} - y_{ICRr})}^{2} + {(\frac{W}{2} - x_{ICRr})}^{2}} \\ + \sqrt{{(\frac{L}{2} + y_{ICRl})}^{2} + {(\frac{W}{2} + x_{ICRl})}^{2}} \\ + \sqrt{{(\frac{L}{2} - y_{ICRl})}^{2} + {(\frac{W}{2} + x_{ICRl})}^{2}}) \\ + G (| V_{r} | + | V_{l} |) \end{array}

(23)

where p is the equal normal force applied to each wheel. The other parameters are as defined before. Using equations (14), (18), and (19), the power model can be simplified as follows:

P = 2 μ | ω_{z} | p \sqrt{L^{2} + {(W - B_{s})}^{2}} + G (| V_{r} | + | V_{l} |)

(24)

or,

P = k | ω_{z} | + G (| V_{r} | + | V_{l} |)

(25)

where k is

k = 2 μ p \sqrt{L^{2} + {(W - B_{s})}^{2}}

(26)

Figure 3.

Distance of a wheel from ICR for a skid-steer rover. To calculate $‖ {\vec{a}}_{n} - {\vec{C}}_{r, l} ‖$ for each wheel, the ICR on the same side as the wheel is always considered (i.e., for the wheels in the right hand side of the rover, ${\vec{C}}_{r}$ is considered.)

3. Equivalency theorem

The Equivalency theorem (Theorem 1) shows that all minimum-energy trajectories follow the same path irrespective of control constraints on the skid-steer rover, as long as these constraints do not prevent the rover from driving forward and backward along straight lines or with any turning radius (including a turning radius of 0, or point turn). This non-intuitive result stems from the fact that for the defined power model, the total energy is fully parameterized by the geometry of the path alone, as will be shown in Lemma 2. In this paper, the theorem is utilized to obtain an equivalent time-optimal problem. The equivalent problem will be solved to obtain the optimal path, which is the general answer to the energy-optimal path planning problem as well.

Definition 2

A general path is a sequential set of connected point turns, straight lines, and/or curves parameterized by R(s).

Energy (E) can be obtained by the following equation.

E = \int_{0}^{t_{f}} P dt

(27)

where t is time. In addition, along a general path (Figure 1), the related time can be obtained from the following relations:

t = \int_{θ_{0}}^{θ_{f}} | \frac{d θ}{ω_{z}} |

(28)

t = \int_{0}^{L_{P}} | \frac{ds}{v} |

(29)

where dθ and ds are the differential of angle and displacement of the rover, respectively. Also, L_P is the length of a path with R(s) > 0 for all s. Equation (28) is particularly useful for R = 0, while (29) is valid for all other R.

These relations are now used to show that the energy for a skid-steer rover following a general path can be written as a function of geometric path parameters of Δθ, Δs, and R(s).

Lemma 2

The energy for the skid-steer rover when following a general path (Figure 1) while using the power model of Equation (25) is equal to:

E = {\begin{cases} (k + G B_{s}) | Δ θ |, & if R = 0 \\ (k + 2 G R^{'}) \int_{0}^{L_{P}} \frac{1}{R (s)} ds, & if 0 < R (s) < R^{'} \\ \int_{0}^{L_{P}} (\frac{k}{R (s)} + 2 G) ds, & if R (s) \geq R^{'} \\ 2 G Δ s & if straight line \end{cases}

(30)

Proof

The energy for each interval of R is proved separately.

(I) R = 0:

Starting with the power model, equation (25), and the general equations (27) and (28), gives:

\begin{array}{l} E = \int_{θ_{0}}^{θ_{f}} (k | ω_{z} | + G (| V_{r} | + | V_{l} |)) | \frac{d θ}{ω_{z}} | \\ = \int_{θ_{0}}^{θ_{f}} (k + G \frac{| V_{r} | + | V_{l} |}{| ω_{z} |}) | d θ | \end{array}

(31)

Using (17), this becomes:

E = \int_{θ_{0}}^{θ_{f}} (k + G B_{s} \frac{| V_{r} | + | V_{l} |}{| V_{r} - V_{l} |}) | d θ |

(32)

The definition of R′ ensures that for R = 0, V_r and V_l are of opposite sign. Therefore, the following relation can be verified:

| V_{r} - V_{l} | = | V_{r} | + | V_{l} |

(33)

So,

\frac{| V_{r} | + | V_{l} |}{| V_{r} - V_{l} |} = 1

(34)

Hence, the energy is

\begin{array}{l} E = \int_{θ_{0}}^{θ_{f}} (k + G B_{s}) | d θ | \\ = (k + G B_{s}) \int_{θ_{0}}^{θ_{f}} | d θ | \\ = (k + G B_{s}) | Δ θ |, for R = 0 \end{array}

(35)

Therefore the energy for any turn with R = 0 is a constant times |Δθ|.

(II) 0 < R(s) < R′: Starting with the power model, (25), and the general equations (27) and (29), gives:

\begin{array}{l} E = \int_{0}^{L_{P}} (k | ω_{z} | + G (| V_{r} | + | V_{l} |)) | \frac{ds}{v} | \\ = \int_{0}^{L_{P}} (k | \frac{ω_{z}}{v} | + G \frac{| V_{r} | + | V_{l} |}{| v |}) ds \end{array}

(36)

Using equation (16), this becomes:

E = \int_{0}^{L_{P}} (k | \frac{ω_{z}}{v} | + 2 G \frac{| V_{r} | + | V_{l} |}{| V_{r} + V_{l} |}) ds

(37)

Since V_r and V_l have the opposite sign in 0 < R(s) < R′, the following relation can again be verified:

| V_{r} - V_{l} | = | V_{r} | + | V_{l} |

(38)

Therefore, using equation (20), the following relations are obtained:

R = R^{'} | \frac{V_{r} + V_{l}}{V_{r} - V_{l}} | = R^{'} \frac{| V_{r} + V_{l} |}{| V_{r} | + | V_{l} |}, V_{r} \neq V_{l}

(39)

So,

\frac{| V_{r} | + | V_{l} |}{| V_{r} + V_{l} |} = \frac{R^{'}}{R}

(40)

Also, |v| = R|ω_z|. Therefore,

E = \int_{0}^{L_{P}} (\frac{k}{R (s)} + 2 G \frac{R^{'}}{R (s)}) ds

(41)

Hence,

E = \int_{0}^{L_{P}} \frac{1}{R (s)} (k + 2 G R^{'}) ds

(42)

Since k + 2 GR′ is constant,

E = (k + 2 G R^{'}) \int_{0}^{L_{P}} \frac{1}{R (s)} ds

(43)

(III) R(s) ≥ R′:

Since V_r and V_l have the same sign, the following relation can be easily verified:

| V_{r} + V_{l} | = | V_{r} | + | V_{l} |

(44)

So, the following relation is true:

\frac{| V_{r} | + | V_{l} |}{| V_{r} + V_{l} |} = 1

(45)

Also, |v| = R|ω_z|. Therefore, using equation (37):

E = \int_{0}^{L_{P}} (\frac{k}{R (s)} + 2 G) ds

(46)

(IV) Straight line:

In the specific case of a straight line V_r = V_l, ω_z = 0 and thus $E = \int_{0}^{L_{P}} 2 Gds = 2 G Δ s$ with Δs = L_P.■

A key aspect of the power model that is fundamental to the above lemma is that power is proportional to speed (as represented by |ω_z| and (|V_r| + |V_l|) in equation (25)). In such a case, doubling speed, for example, halves the operation time but doubles the instantaneous power consumption, leaving the energy integral unchanged along any given path. Another key consideration is the assumption of co-location of centroid with center of mass; without this, equations (20) and (37) do not simplify cleanly, and the analyses in (II) and (III) above would become progressively less valid the larger the deviation from this assumption.

The lemma will be used to prove the equivalency theorem (see Theorem 1).

Definition 3

A proper constraint is one that does not place a limit on a skid-steer rover’s turning radii; that is one that allows point turns, straight lines, and 0 < R < ∞. Note that this includes the case of any arbitrary but finite velocities. A list of some examples of velocity constraints that will be shown to be proper includes:

• Constant v_c (|V_l| + |V_r| = 2v_c, where v_c is constant)

• |V_i| < |v_max|, i = {r, l} and v_max is constant

• Any arbitrary but finite velocities

• Constant power velocity constraint (see Figure 5)

These velocity constraints are kinematic by definition. They do not consider the possibility of motor torques saturating due to loading conditions, which could impose additional limitations for some rovers. However, given that skid-steer rovers tend to be designed with substantial maneuverability capabilities such a case would not be expected to be encountered during nominal (e.g., payload within rated limits) operations on hard flat ground.

Definition 4

Optimal controls are a solution ${V_{r}^{*}, V_{l}^{*}}$ to the energy optimization problem stated in Eq. (1).

Definition 5

An optimal path is the general path produced by applying optimal controls ${V_{r}^{*}, V_{l}^{*}}$ .

Theorem 1

Equivalency Theorem: An energy-optimal path found for energy optimization with a proper velocity constraint is also an optimal path for energy optimization with any other proper velocity constraint.

Proof

As can be seen in Lemma 2, the energy consumption along a general path while using the power model of equation (25) can be fully parameterized by geometric path parameters (Δθ, Δs, R(s)) and is not directly dependent on V_r, V_l. This is the crucial aspect of the structure of the power model that enables the Equivalency Theorem. In the case of considering any alternative power model, the Equivalency theorem would also hold if the model shares this feature of geometrically parameterized energy consumption (likely for models where power is proportional to speed).

Also, any general path can be achieved by a skid-steer rover with a proper velocity constraint. This follows directly from the definitions of a general path and a proper velocity constraint, respectively.

There are no general paths that can result in lower energy consumption than an optimal path. Furthermore, a proper velocity constraint ensures that controls generating any such hypothetically lower-energy general path would have been included in the search space.

An energy-optimal path is thus energy-optimal regardless of velocity constraints, as long as the velocity constraints are proper. Only the particular optimal controls used to follow such an optimal path vary between problems with different proper velocity constraints.■

In the following, more explanations are provided to clarify Theorem 1. Based on equation (20) the turning radius is a function of the control inputs. Therefore,

R (s) = R^{'} | \frac{V_{r} (s) + V_{l} (s)}{V_{r} (s) - V_{l} (s)} |, V_{r} (s) \neq V_{l} (s)

(47)

Also, from the equation for R(s), in the case of any arbitrary but finite velocities there are infinite {V_l(s); V_r(s)} that can produce a R(s), that is all the {aV_l(s); aV_r(s)} for the real number a ≠ 0 produce the same R(s).

The next step is showing that the velocity constraints do not limit the R(s) values and are thus proper. Each example constraint considered is evaluated separately in the following:

1. Constant v_c: Using the related figure (see Figure 4) and the equation for the turning radius (equation (20)) it is evident that for (V_l, V_r) ∈ {(−v_c, v_c), (v_c, − v_c)}, the turning radius is zero (R(s) = 0). In addition, when (V_l, V_r) is infinitesimally close to the middle of line segments in the first or third quadrant of the figure (i.e., (V_l, V_r) ≊ (v_c, v_c) or (−v_c, − v_c)), the turning radius approaches to infinity (R(s) → ∞) and is a straight line at the exact equality. For other values of V_l and V_r, the range of (0, + ∞) will be obtained for R(s).

2. |V_i| < |v_max|, i = r, l: Using equation (20), when V_l = −V_r, the turning radius is zero (R(s) = 0). Also, when V_r and V_l are almost equal, the turning radius approaches infinity (R(s) → ∞) and when they are exactly equal the rover follows a straight line.

3. Any arbitrary but finite velocities: The similar explanation in Part 2 is applicable for arbitrary but finite velocities.

4. Constant power: It is proven in the Appendix that to have constant power (P = P_c where P_c is a constant), V_r and V_l have the symmetric control space shown in Figure 5. By considering Figure 5 and equation (20), when (V_l, V_r) is the middle point of line segments in second or fourth quadrant of the figure², the turning radius becomes zero (R(s) = 0). In addition, when (V_l, V_r) is infinitesimally close to the middle of line segments in the first or third quadrant of the figure (i.e., $(V_{l}, V_{r}) ≊ (\frac{P_{c}}{2 G}, \frac{P_{c}}{2 G})$ or $(- \frac{P_{c}}{2 G}, - \frac{P_{c}}{2 G}))$ , the R(s) → ∞. The range of (0, + ∞) will be obtained for R(s) by taking other values of V_l and V_r along the curves between these points.

Figure 4.

The control space obtained from $| V_{r} | + | V_{l} | = 2 v_{c}$ (constant $v_{c}$ constraint).

Figure 5.

Control space for the constant power of $P_{c}$ .

This means the same path that is optimal for constant v_c, is optimal for |V_i| < |v_max| (i = r, l), is optimal for any arbitrary but finite velocities and is optimal for constant power velocity constraints.

By using equation (16) and equation (17), Figure 6 is obtained from a re-parameterization of Figure 5. The parameters in Figure 6 are as follows:

{\tilde{v}}_{\max} = \frac{P_{c}}{2 G}

(48)

{\tilde{ω}}_{\max} = \frac{P_{c}}{G B_{s} + k}

(49)

{\tilde{v}}_{R^{'}} = \frac{P_{c} B_{s}}{2 (G B_{s} + k)}

(50)

Figure 6.

Control space of a (constant power) skid-steer rover for the equivalent time-optimal problem.

Accordingly, to solve the energy-optimal path planning problem (see equation (1)) there are two approaches:

1. To directly apply Pontryagin’s Minimum Principle and then prove several theorems specified for skid-steer rovers to obtain all the extremal paths for the energy-optimal path planning problem: In this approach theorems and processes analogous to those performed by Furtuna (2011) should be regenerated and then be revised/adjusted for our problem (equation (1)). Furtuna (2011) proves several theorems for time-optimal path planning of a rigid body. These theorems are for obtaining the extremal control inputs, categorizing different type of paths, limiting the number of extremals, determining the switch points of the extremals, and defining length/periodicity of the correspondent extremal paths.

2. To use the “constant power” constraint and find an equivalent time-optimal problem for the energy-optimal problem (equation (1)): Based on the equivalency theorem, “constant power” is one of the several proper constraints that may be considered to obtain the optimal path for the energy-optimal path planning problem. Accordingly, the constraint can be used to convert the energy-efficiency to an equivalent time-efficiency problem. From equation (27) it is known that $E = \int_{0}^{t_{f}} P dt$ . For the “constant power” constraint, since P is constant, the relation can be written as E = Pt_f. Therefore, E is proportional to the total time (t_f) of the problem. Hence, if the total time (t_f) is minimized, the cost (E) will be minimized. The theorems proven by Furtuna (2011) can be used directly in this case and yet the energy-optimal paths will be obtained.

In this paper, the second approach, which is considering “constant power” and its related velocity constraints, is utilized to solve the energy-optimal path planning problem (see equation (1)). This is not the same as simply solving the time-optimal problem for skid-steer rovers in general. The energy-optimal solution is only found if the particular “constant power” velocity constraints (Figures 5 and 6), derived here, are considered; these constraints would not reasonably be applied if one were interested in finding the actual time-optimal paths.

Accordingly the following equivalent time-optimal problem is defined:

Equivalent time-optimal problem:

\begin{array}{l} \underset{{\tilde{V}}_{r}, {\tilde{V}}_{l}, {\tilde{t}}_{f}}{minimize} & \tilde{E} = \int_{0}^{{\tilde{t}}_{f}} P_{c} dt, P_{c} is a positive constant \\ subject to & \tilde{ω} (s) = f (\tilde{v} (s)) (see Figure 6) \\ \dot{\tilde{x}} = \tilde{v} (s) \cos \tilde{θ} \\ \dot{\tilde{y}} = \tilde{v} (s) \sin \tilde{θ} \\ \dot{\tilde{θ}} = \tilde{ω} (s) \\ \tilde{x} (0) = x_{0}, \tilde{y} (0) = y_{0}, \tilde{θ} (0) = θ_{0} \\ \tilde{x} ({\tilde{t}}_{f}) = x_{f}, y ({\tilde{t}}_{f}) = y_{f}, \tilde{θ} ({\tilde{t}}_{f}) = θ_{f} \end{array}

(51)

where

(\tilde{x}, \tilde{y}, \tilde{θ})

is the pose of the rover in the global coordinate system.

{\tilde{t}}_{f}

is the final time which is free. Also,

\tilde{v}

and

\tilde{ω}

are linear and angular velocity, respectively.

3. Extremal trajectories for the equivalent time-optimal problem

Firstly, Pontryagin’s Minimum Principle for time-optimal problems is presented. This theorem is required to obtain Hamiltonian level sets. Then, the optimal control inputs are calculated by the use of a theorem presented by Furtuna (2011). Hence, the Hamiltonian level sets are used to graphically analyze and categorize the extremal paths. Finally, explanations are given to restrict the number of periods and thus give the complete table of the extremal path structures. These finite number of extremal path structures will be enumerated and compared to find the optimal solution.

3.1. Pontryagin’s minimum principle for time-optimal problems

Pontryagin’s Minimum Principle for time-optimal problems (Theorem 2) is presented by Pontryagin et al. (1962). This theorem is required for this research to

• define the Hamiltonian

• use the concept of constant maximum of negative Hamiltonian (minimum of Hamiltonian), λ₀ in equation (76), to obtain the Hamiltonian level sets.

Theorem 2

Let x (t) = (x(t), …, x_m(t)) be a trajectory and u (t) mapping the time interval t₀ ≤ t ≤ t₁ to U:

u (t) = (u_{1} (t), \dots, u_{n} (t))

(52)

be the correspondent admissible (i.e., piecewise continuous) control input for transferring from x(t₀) = x₀ to x(t₁) = x₁. The necessary condition for u(t) and x(t) to be time-optimal is as follows:

A nontrivial continuous adjoint function of $λ (t) = (λ_{1} (t), λ_{2} (t), \dots, λ_{m} (t))$ which is in R^m exists that satisfies the adjoint equation:

{\dot{λ}}_{i} (t) = - \frac{\partial H}{\partial x_{i}}, i = 1 . . m

(53)

where H:R^m × SE² × U → R is the Hamiltonian:

H (x (t), u (t), λ (t)) = ⟨ λ (t), \dot{x} (x (t), u (t)) ⟩

(54)

\dot{x} = \frac{\partial H}{\partial λ}

(55)

Conditions for optimality:

(I) For all t, t₀ ≤ t ≤ t₁, the maximum of −H(x(t), u(t), λ (t)), which is the function of the variable u ∈ U, is at the point u = u(t):

\max (- H (x (t), u (t), λ (t))) = M (λ (t), x (t))

(56)

(II) M( λ (t), x(t)) = λ₀ is constant if λ (t), x(t), and u(t) satisfy equation (53), equation (55), and condition (I). Thus, λ₀ satisfies the following condition for t₀ ≤ t ≤ t₁:

λ_{0} \geq 0

(57)

Proof

The proof of the theorem is presented by Pontryagin et al. (1962).■

The following relations for the first derivatives of the states are known:

\dot{x} (t) = v (t) \cos (θ (t))

(58)

\dot{θ} (t) = ω_{z} (t)

(59)

\dot{y} (t) = v (t) \sin (θ (t))

(60)

Note: For notational simplicity, the time variable is omitted in the following relations and variables.

Using Equation (54) and Equation (58) through equation (60) gives the following relation for the Hamiltonian:

H = λ_{1} v \cos (θ) + λ_{2} v \sin (θ) + λ_{3} ω_{z}

(61)

Also, using equation (53) gives:

\dot{λ} = (0,0, λ_{1} \dot{y} - λ_{2} \dot{x})

(62)

After integrating to solve for λ:

λ = (c_{1}, c_{2}, η (x, y))

(63)

where c_i (i = 1, 2, 3) are the constants obtained by integration and they are not zero simultaneously. Also, η is as follows:

η (x, y) = c_{1} y - c_{2} x + c_{3}

(64)

Substituting equation (63) into the Hamiltonian results in the following relation:

H = v (c_{1} \cos θ + c_{2} \sin θ) + ω_{z} (c_{1} y - c_{2} x + c_{3})

(65)

Pontryagin’s Minimum Principle indicates that the adjoint equation (equation (53)) cannot be identically zero. In other words, c₁, c₂, and c₃ are not all zero. Hence, the following two cases are considered:

1. c₁ = c₂ = 0

2. One of c₁ or c₂ is not zero. For simplicity and without loss of generality it is assumed that $c_{1}^{2} + c_{2}^{2} = 1$ . This assumption is considered by Furtuna (2011) as well. For Pontryagin’s Minimum Principle the conditions of the principle are invariant to the scaling of the adjoint with a positive number (Furtuna 2011).

The paths that are obtained for the case when c₁ and c₂ are both zero, are called whirls by Furtuna (2011), and the rest of paths are non-whirls. Whirls for a skid-steer rover have a maximum value of angular velocity almost everywhere (|ω_z| = 2v_c/B_s) while their speed (|v|) is in [0, v_c]. This is equivalent to paths with maximum |ω_z| when R ∈ [0, R′]. The structure of whirls consists of rolls and a catch (Furtuna 2011). The rolls are circular arcs with R = R′. The catch part is a circular arc of $R \in [0, R')$ that puts the rover in the final pose.

In the following the second case is investigated when the following condition is held:

c_{1}^{2} + c_{2}^{2} = 1

(66)

Lemma 3

For a line in the plane given by the equation ax + by + c = 0, where a, b, and c are real constants with a and b not both zero, the perpendicular distance of a point (x₀, y₀) from the line is as follows (Spain 2007):

distance = \frac{| a x_{0} + b y_{0} + c |}{\sqrt{a^{2} + b^{2}}}

(67)

Considering equation (64) for η(x, y), assuming equation (66), and using Lemma 3, it is concluded that η(x, y) is the signed distance of the robot’s centroid from a line which is named the η-line, following a convention from Balkcom and Mason (2002). Also, the η-line is named control line by Furtuna (2011). For simplicity it is assumed that the center of mass and centroid of the robot are the same. The η-line (see Figure 7) is a hypothetical control line in 2D and distance to it determines the path type.

Lemma 4

If β (see Figure 7) is defined as Equation (68), the Hamiltonian (Equation (65)) will be converted to Equation (69), while Equation (64) and Equation (66) are considered.

β = {\begin{cases} θ - \arctan 2 (- c_{2}, - c_{1}) & if c_{1} \neq 0 \\ θ - \arctan 2 (- c_{2}, - c_{1}) & if c_{1} = 0 and c_{2} < 0 \\ θ - \arctan 2 (c_{2}, c_{1}) & if c_{1} = 0 and c_{2} > 0 \end{cases}

(68)

- H = {\begin{cases} v \cos β - ω_{z} η & if c_{1} \neq 0 \\ v \cos β - ω_{z} η & if c_{1} = 0 and c_{2} < 0 \\ - v \cos β - ω_{z} η & if c_{1} = 0 and c_{2} > 0 \end{cases}

(69)

Figure 7.

Schematic figure to show the η-line and the related parameters. β is the orientation of rover with respect to the η-line.

Proof

The proof for c₁ ≠ 0 as well as c₁ = 0 & c₂ < 0 is presented by Balkcom and Mason (2002). There is a typo in equation (79) of the paper published by Balkcom and Mason (2002). It should be written in the format of β = θ − arctan2(−c₂ , − c₁). Then, the results presented in the paper for the mentioned conditions of c₁ and c₂ are valid. The only remaining part is c₁ = 0 & c₂ > 0 which is elaborated hereunder:

For two variables of x and y the definition of arctan2(y, x) (Betz 2015; Lenarcic et al. 2012) is

\arctan 2 (y, x) = {\begin{cases} \arctan (\frac{y}{x}) & if x > 0 \\ \arctan (\frac{y}{x}) + π & if x < 0 and y \geq 0 \\ \arctan (\frac{y}{x}) - π & if x < 0 and y < 0 \\ + π / 2 & if x = 0 and y > 0 \\ - π / 2 & if x = 0 and y < 0 \\ undefined & if x = 0 and y = 0 \end{cases}

(70)

Therefore, the following relation is concluded for the condition of c₁ = 0 & c₂ > 0:

\arctan 2 (c_{2}, c_{1}) = + \frac{π}{2}

(71)

Eq . (68) \Rightarrow \cos β = \cos (θ - \frac{π}{2}) = \sin (θ)

(72)

Eq . (69) \Rightarrow - H = - v \sin θ - ω_{z} η

(73)

Also, for c₁ = 0 & c₂ > 0 and considering $c_{1}^{2} + c_{2}^{2} = 1$ (equation (66)), it is obtained that c₂ = 1. As a result, equation (65) is converted to:

H = v \sin θ + ω_{z} η

(74)

As it is seen, equation (73) and equation (74) are the same.■

Equation (69) and the optimal control inputs that will be obtained in the next subsection will be used to graph the Hamiltonian level sets.

3.2. Time-optimal control inputs

The following theorem is Theorem 2 (page 29) of Andrei Furtuna’s thesis (Furtuna 2011). This theorem is utilized to obtain the optimal control inputs $({\tilde{v}}^{*}, {\tilde{ω}}^{*})$ for the equivalent time-optimal problem.

Theorem 3

The problem is time-optimal control of an autonomous rigid body and the assumptions are as follows:

• moving in the Euclidean plane without obstacles;

• the state vector of x = (x, y, θ) gives the configuration of the rigid body in the plane.

• the model is fully kinematic, assuming that acceleration happens so fast that its time can be neglected. This is a common assumption for rovers of low speeds;

• it is assumed that the control set U is a convex polyhedron in $R^{3}$ ;

• U fully specifies the vehicle’s capabilities.

For the control set U, there is canonical finite subset U_c that includes the vertices of U and at most one point on each face or edge of U that intersects the $\dot{θ} = 0$ plane, such that any mentioned optimal control problem has a solution that is a control policy which

1. is piecewise continuous

2. only takes values in U_c

The control space in Figure 6 can be convexified (converted into a convex polyhedron in $R^{3}$ by including its interior), and then Theorem 3 is applicable for the equivalent time-optimal problem. Therefore, by using Figure 6 and Theorem 3 the canonical finite subset for the equivalent time-optimal problem is

\begin{array}{l} U_{c} = {({\tilde{v}}_{\max}, 0), (- {\tilde{v}}_{\max}, 0), \\ ({\tilde{v}}_{R^{'}}, {\tilde{ω}}_{\max}), (- {\tilde{v}}_{R^{'}}, {\tilde{ω}}_{\max}), \\ ({\tilde{v}}_{R^{'}}, - {\tilde{ω}}_{\max}), (- {\tilde{v}}_{R^{'}}, - {\tilde{ω}}_{\max})} \end{array}

(75)

Because U_c are all vertices of Figure 6, it is clear that convexification has not ultimately violated the original constraint. Given that U_c already includes the $\dot{θ} = 0$ plane crossing points, no further additions to U_c are needed to avoid chattering. In the following subsection, U_c (equation (75)) will be used to obtain the Hamiltonian level sets for the equivalent time-optimal problem.

3.3. Hamiltonian level sets

Firstly, the Hamiltonian level sets for the following conditions

• c₁ ≠ 0

• c₁ = 0 & c₂ < 0

are calculated. Then, the Hamiltonian level sets for c₁ = 0 & c₂ > 0 are explained. Hence, the Hamiltonian level sets for the equivalent time-optimal problem (equation (51) of Theorem 1) are obtained. These level sets will be used in obtaining the extremal paths.

Hamiltonian Level Sets for c₁ ≠ 0 or c₁ = 0 & c₂ < 0:

λ₀ is defined as the maximum of equation (69). Therefore,

λ_{0} = \max (- H (t))

(76)

It is mentioned in Theorem 2 that λ₀ is constant. Also, equation (76) is the dot product of the following vectors:

V_{u} = ({\tilde{v}}^{*}, {\tilde{ω}}^{*})

(77)

and,

V_{η} = (\cos β, - η)

(78)

where

{\tilde{v}}^{*}

and

{\tilde{ω}}^{*}

are the time-optimal control inputs. Also, V_u is the control vector, and V_η is called characteristic vector (the naming convention is taken from the paper published by Balkcom and Mason (2002)).

\begin{array}{l} λ_{0} = ⟨ V_{u}, V_{η} ⟩ \\ = {\tilde{v}}^{*} \cos β - {\tilde{ω}}^{*} η \end{array}

(79)

As mentioned before, λ₀ is constant for the equivalent time-optimal problem. Also, $({\tilde{v}}^{*}, {\tilde{ω}}^{*})$ are the time-optimal control inputs to be chosen from U_c (equation (75)). The optimal control inputs are the vertices of the control space shown in Figure 6. For example, if $({\tilde{v}}^{*}, {\tilde{ω}}^{*})$ = $({\tilde{v}}_{\max}, 0)$ is considered, the λ₀ becomes:

λ_{0} = {\tilde{v}}_{\max} \cos β

(80)

Since λ₀ is constant, cos β becomes constant; which means constant angle with respect to the η-line. So

λ_{0} \leq {\tilde{v}}_{\max}

corresponds to straight forward motion. In both Figure 10 and Figure 11, which will be further explained below, the level set related to straight forward maneuver ⇑ aligns with the

({\tilde{v}}_{\max}, 0)

point of control space. By using the same process all the Hamiltonian level sets can be obtained utilizing equation (79), which is explained in the following. Firstly, single maneuvers taken from U_c (equation (75)) and their related symbols are introduced in Table 2.

Table 2.

Symbols and the related maneuvers. CCW and CW stand for counter clockwise and clockwise, respectively.

Index	Symbol	Maneuver
1	⇑	Straight forward with $({\tilde{v}}^{}, {\tilde{ω}}^{}) = ({\tilde{v}}_{\max}, 0)$
2	⇓	Straight backward with $({\tilde{v}}^{}, {\tilde{ω}}^{}) = (- {\tilde{v}}_{\max}, 0)$
3	↶	CCW forward turn with $({\tilde{v}}^{}, {\tilde{ω}}^{}) = ({\tilde{v}}_{R^{'}}, {\tilde{ω}}_{\max})$
4	↷	CW forward turn with $({\tilde{v}}^{}, {\tilde{ω}}^{}) = ({\tilde{v}}_{R^{'}}, - {\tilde{ω}}_{\max})$
5	$\overset{b}{↶}$	CCW backward turn with $({\tilde{v}}^{}, {\tilde{ω}}^{}) = (- {\tilde{v}}_{R^{'}}, {\tilde{ω}}_{\max})$
6	$\overset{b}{↷}$	CW backward turn with $({\tilde{v}}^{}, {\tilde{ω}}^{}) = (- {\tilde{v}}_{R^{'}}, - {\tilde{ω}}_{\max})$

Notice that all the turns (Index three through 6) in Table 2 have the turning radius of R′ (in R′ just one of ${\tilde{V}}_{r}$ or ${\tilde{V}}_{l}$ is zero). Then, using equation (75) and equation (79) the following results are obtained for the level sets.

1. $({\tilde{v}}^{*}, {\tilde{ω}}^{*}) = ({\tilde{v}}_{\max}, 0)$

λ_{0} = {\tilde{v}}_{\max} \cos β \Rightarrow \cos β = \frac{λ_{0}}{{\tilde{v}}_{\max}}

(81)

2. $({\tilde{v}}^{*}, {\tilde{ω}}^{*}) = (- {\tilde{v}}_{\max}, 0)$

λ_{0} = - {\tilde{v}}_{\max} \cos β \Rightarrow \cos β = \frac{- λ_{0}}{{\tilde{v}}_{\max}}

(82)

3. $({\tilde{v}}^{*}, {\tilde{ω}}^{*}) = ({\tilde{v}}_{R^{'}}, {\tilde{ω}}_{\max})$

λ_{0} = {\tilde{v}}_{R^{'}} \cos β - {\tilde{ω}}_{\max} η \Rightarrow - η = \frac{λ_{0} - {\tilde{v}}_{R^{'}} \cos β}{{\tilde{ω}}_{\max}}

(83)

4. $({\tilde{v}}^{*}, {\tilde{ω}}^{*}) = ({\tilde{v}}_{R^{'}}, - {\tilde{ω}}_{\max})$

λ_{0} = {\tilde{v}}_{R^{'}} \cos β + {\tilde{ω}}_{\max} η \Rightarrow - η = \frac{{\tilde{v}}_{R^{'}} \cos β - λ_{0}}{{\tilde{ω}}_{\max}}

(84)

5. $({\tilde{v}}^{*}, {\tilde{ω}}^{*}) = (- {\tilde{v}}_{R^{'}}, {\tilde{ω}}_{\max})$

λ_{0} = - {\tilde{v}}_{R^{'}} \cos β - {\tilde{ω}}_{\max} η \Rightarrow - η = \frac{λ_{0} + {\tilde{v}}_{R^{'}} \cos β}{{\tilde{ω}}_{\max}}

(85)

6. $({\tilde{v}}^{*}, {\tilde{ω}}^{*}) = (- {\tilde{v}}_{R^{'}}, - {\tilde{ω}}_{\max})$

λ_{0} = - {\tilde{v}}_{R^{'}} \cos β + {\tilde{ω}}_{\max} η \Rightarrow - η = \frac{- {\tilde{v}}_{R^{'}} \cos β - λ_{0}}{{\tilde{ω}}_{\max}}

(86)

In general cos β ∈ [−1, 1]. Therefore, from equation (81) and Equation (82) it is concluded that if $λ_{0} > {\tilde{v}}_{\max}$ , there are no ⇑ and ⇓ maneuvers. However, for $λ_{0} \leq {\tilde{v}}_{\max}$ all the reported maneuvers in Table 2 are possible. In addition, λ₀ > 0 (Theorem 2). If λ₀ = 0, the Hamiltonian level set becomes a point at the origin (see Figure 11). Therefore, no path will be produced. This point is discussed in Lemma 6 which will be proved in the next subsection. Therefore, the following are the possible categories for λ₀:

(i) $λ_{0} > {\tilde{v}}_{\max}$

Feasible Maneuvers: ↶, ↷, $\overset{b}{↶}$ , and $\overset{b}{↷}$

(ii) $λ_{0} = {\tilde{v}}_{\max}$

Feasible Maneuvers: ⇑, ⇓, ↶, ↷, $\overset{b}{↶}$ , and $\overset{b}{↷}$

(iii) $0 < λ_{0} < {\tilde{v}}_{\max}$

Feasible Maneuvers: ⇑, ⇓, ↶, ↷, $\overset{b}{↶}$ , and $\overset{b}{↷}$

The feasible equations, considering the above categories for λ₀, from amongst equation (81) through equation (86) are considered. Hence, the following conclusions are obtained for Hamiltonian level sets:

• The Hamiltonian level set for $λ_{0} > {\tilde{v}}_{\max}$ is shown in Figure 9

• The Hamiltonian level set for $λ_{0} = {\tilde{v}}_{\max}$ is shown in Figure 10

• The Hamiltonian level set for $0 < λ_{0} < {\tilde{v}}_{\max}$ is shown in Figure 11

For the figures (Figure 9 through 11), the line segments of Hamiltonian level set closest to the origin are kept. Because λ₀ = max(−H(t)) (see equation (76)), for the farther part of a level set’s line, there is always another line with higher λ₀. For example, consider the dashed line which extends from P₁P₂ (level set’s line) in Figure 8. There are other level set’s lines, which are parallel to P₂P₃, with higher λ₀, that is, the line segment that crosses the dashed line at P_Cross. Therefore, the dashed line segment does not satisfy Pontryagin’s Minimum Principle and should not be sketched/considered. Hence, by the similar explanation, the other line segments for the Hamiltonian level sets in Figure 9 through Figure 11 are obtained.

Figure 8.

An example to show why the level set’s lines should not be extended in Figure 9.

Figure 9.

The level set (black lines) for $λ_{0} > {\tilde{v}}_{\max}$ . The blue hexagon is the control space shown in Figure 6.

P_i, i = 1..6 (Table 3) are the vertices of the Hamiltonian level sets (see Figure 10 through Figure 11). The location of these points depends on the value of λ₀.

Table 3.

The vertices of Hamiltonian level set in Figure 9 through Figure 11.

Point	(cos β, − η) for Figures 9 and 10	(cos β, − η) for Figure 11
P₁	$(1, \frac{λ_{0} - {\tilde{v}}_{R^{'}}}{{\tilde{ω}}_{\max}})$	$(\frac{λ_{0}}{{\tilde{v}}_{\max}}, \frac{λ_{0} - {\tilde{v}}_{R^{'}} \cos β}{{\tilde{ω}}_{\max}})$
P₂	$(0, \frac{λ_{0}}{{\tilde{ω}}_{\max}})$	$(0, \frac{λ_{0}}{{\tilde{ω}}_{\max}})$
P₃	$(- 1, \frac{λ_{0} - {\tilde{v}}_{R^{'}}}{{\tilde{ω}}_{\max}})$	$(- \frac{λ_{0}}{{\tilde{v}}_{\max}}, \frac{λ_{0} - {\tilde{v}}_{R^{'}} \cos β}{{\tilde{ω}}_{\max}})$
P₄	$(1, \frac{{\tilde{v}}_{R^{'}} - λ_{0}}{{\tilde{ω}}_{\max}})$	$(\frac{λ_{0}}{{\tilde{v}}_{\max}}, \frac{{\tilde{v}}_{R^{'}} \cos β - λ_{0}}{{\tilde{ω}}_{\max}})$
P₅	$(0, \frac{- λ_{0}}{{\tilde{ω}}_{\max}})$	$(0, \frac{- λ_{0}}{{\tilde{ω}}_{\max}})$
P₆	$(- 1, \frac{{\tilde{v}}_{R^{'}} - λ_{0}}{{\tilde{ω}}_{\max}})$	$(- \frac{λ_{0}}{{\tilde{v}}_{\max}}, \frac{{\tilde{v}}_{R^{'}} \cos β - λ_{0}}{{\tilde{ω}}_{\max}})$

Figure 10.

The level set (black hexagon) for $λ_{0} = {\tilde{v}}_{\max}$ . The blue hexagon is the control space shown in Figure 6.

Figure 11.

The level set (black hexagon) for $0 < λ_{0} < {\tilde{v}}_{\max}$ . The blue hexagon is the control space shown in Figure 6.

3.3.1. Hamiltonian level sets for c₁ = 0 & c₂ > 0

If the same process that was explained in the previous subsection is followed for the Hamiltonian level sets, Figure 9 to Figure 11 will be mirrored with respect to the line of cos β = 0. The reason for being mirrored is the negative sign by which cos β is multiplied (see −H equation for the condition of c₁ = 0 & c₂ > 0 in equation (69)). For example, in Figure 9, the hexagonal shape level set is mirrored with respect to the vertical orange line. Therefore, Figure 12 is obtained.

Figure 12.

The level set (black hexagon) for $0 < λ_{0} < {\tilde{v}}_{\max}$ and the condition of c₁ = 0 & c₂ > 0. The blue hexagon is the control space shown in Figure 6.

The Hamiltonian level sets will be used to obtain the shape of the extremal paths in upcoming subsections. First, some constraints on the period of the paths must be considered which are explained in the following subsection.

3.4. Restricting the number of periods for the obtained paths

Using the obtained Hamiltonian level sets and the geometrical interpretation presented by Balkcom and Mason (2002), the extremal paths can be obtained. Actually, the distance of the rover’s centroid to the η-line determines the control policy (Balkcom and Mason 2002). Therefore, different paths that are shown in Figure 13 are obtained from the level sets that were shown in Figure 9, Figure 10, and Figure 11. As it is shown in Figure 13, there are three types of paths:

• Generic Turns which consist of only turns

• Singular paths

• Generic TST which stands for generic paths with sequences of Turns, Straight lines, and Turns

Figure 13.

Different path types based on the λ₀ categories.

The naming convention of Generic and Singular paths are adopted from the references (Balkcom and Mason 2002; Furtuna 2011).

Also, the difference between the above-mentioned paths is explained in the following:

For Generics (Generic Turns and Generic TST) the position of the η − line uniquely determines the optimal control inputs. Therefore, the paths will be unique.

However, Singulars are the paths that may include singularities. As it can be seen in Figure 13, since in the singular points the angle of the robot with respect to the η − line is 0 or 180^o, the robot can maintain its straight line motions or can switch to turns at any particular point in time. Specifically, Singulars are the paths that their straight line motions (⇑, ⇓) are parallel to the η − line.

Now, by using Figure 13 all the paths will be obtained using methods analogous to those used by Furtuna et al. (2011) and Dolinskaya and Maggiar (2012). However, the period of paths can be restricted. Accordingly, the following theorems are proved/presented.

Theorem 4

The generic (non-singular) paths contain no more than one period if the following conditions are held:

1. The image of θ(t) is not S¹

2. $\dot{θ} (0) \neq 0$

Proof

It is proved in page 46 (Lemma 16) of Furtuna’s thesis (Furtuna 2011).■

All the generic TST paths which will be reported in Table 4, except those extremal trajectories that start with a straight line motions (i.e.,

⇑ ↷_{\frac{π}{2}} {\overset{b}{↷}}_{\frac{π}{2}} ⇓ {\overset{b}{↷}}_{\frac{π}{2}} ↷_{\frac{π}{2}}

), are satisfying the conditions in Theorem 4. Based on Theorem 5 of (Furtuna and Balkcom 2010), it is concluded that the generic TST paths starting with a straight line motion are less than one period, as well. It can be easily verified that if the path is extended to

⇑ ↷_{\frac{π}{2}} {\overset{b}{↷}}_{\frac{π}{2}} ⇓ {\overset{b}{↷}}_{\frac{π}{2}} ↷_{\frac{π}{2}} ⇑

, it can be replaced by

⇑ ↷_{\frac{π}{2}} {\overset{b}{↷}}_{\frac{π}{2}} ⇓ {\overset{b}{↷}}_{\frac{π}{2}} ↷_{\frac{π}{2}}

Table 4.

Extremal Path Structures for the equivalent Time-Optimal Problem.

Path type		Paths
Generic turns	$↶ {\overset{b}{↶}}_{π} ↶_{π} \overset{b}{↶}$	$\overset{b}{↶} ↶_{π} {\overset{b}{↶}}_{π} ↶$	$↷ {\overset{b}{↷}}_{π} ↷_{π} \overset{b}{↷}$
Generic turns	$\overset{b}{↷} ↷_{π} {\overset{b}{↷}}_{π} ↷$
Singular	$⇓ {\overset{b}{↶}}_{\frac{π}{2}} ↶_{\frac{π}{2}} ⇑ ↶_{\frac{π}{2}} \overset{b}{↶}$	$⇑ ↶_{\frac{π}{2}} {\overset{b}{↶}}_{\frac{π}{2}} ⇓ {\overset{b}{↶}}_{\frac{π}{2}} ↶$	$⇓ {\overset{b}{↷}}_{\frac{π}{2}} ↷_{\frac{π}{2}} ⇑ ↷_{\frac{π}{2}} \overset{b}{↷}$
	$⇑ ↷_{\frac{π}{2}} {\overset{b}{↷}}_{\frac{π}{2}} ⇓ {\overset{b}{↷}}_{\frac{π}{2}} ↷$	$\overset{b}{↶} ⇓ {\overset{b}{↶}}_{\frac{π}{2}} ↶_{\frac{π}{2}} ⇑ ↶_{\frac{π}{2}} \overset{b}{↶}$	$↶ ⇑ ↶_{\frac{π}{2}} {\overset{b}{↶}}_{\frac{π}{2}} ⇓ {\overset{b}{↶}}_{\frac{π}{2}} ↶$
	$\overset{b}{↷} ⇓ {\overset{b}{↷}}_{\frac{π}{2}} ↷_{\frac{π}{2}} ⇑ ↷_{\frac{π}{2}} \overset{b}{↷}$	$↷ ⇑ ↷_{\frac{π}{2}} {\overset{b}{↷}}_{\frac{π}{2}} ⇓ {\overset{b}{↷}}_{\frac{π}{2}} ↷$	$\overset{b}{↶} ↶_{\frac{π}{2}} ⇑ ↶_{\frac{π}{2}} {\overset{b}{↶}}_{\frac{π}{2}} ⇓ {\overset{b}{↶}}_{\frac{π}{2}} ↶$
	$↶ {\overset{b}{↶}}_{\frac{π}{2}} ⇓ {\overset{b}{↶}}_{\frac{π}{2}} ↶_{\frac{π}{2}} ⇑ ↶_{\frac{π}{2}} \overset{b}{↶}$	$\overset{b}{↷} ↷_{\frac{π}{2}} ⇑ ↷_{\frac{π}{2}} {\overset{b}{↷}}_{\frac{π}{2}} ⇓ {\overset{b}{↷}}_{\frac{π}{2}} ↷$	$↷ {\overset{b}{↷}}_{\frac{π}{2}} ⇓ {\overset{b}{↷}}_{\frac{π}{2}} ↷_{\frac{π}{2}} ⇑ ↷_{\frac{π}{2}} \overset{b}{↷}$
Generic TST	$⇑ ↶ \overset{b}{↶} ⇓ \overset{b}{↷} ↷$	$↶ \overset{b}{↶} ⇓ \overset{b}{↷} ↷ ⇑ ↶$	$\overset{b}{↶} ⇓ \overset{b}{↷} ↷ ⇑ ↶ \overset{b}{↶}$
	$⇓ \overset{b}{↷} ↷ ⇑ ↶ \overset{b}{↶}$	$\overset{b}{↷} ↷ ⇑ ↶ \overset{b}{↶} ⇓ \overset{b}{↷}$	$↷ ⇑ ↶ \overset{b}{↶} ⇓ \overset{b}{↷} ↷$
	$↷ \overset{b}{↷} ⇓ \overset{b}{↶} ↶ ⇑ ↷$	$⇑ ↷ \overset{b}{↷} ⇓ \overset{b}{↶} ↶$	$↶ ⇑ ↷ \overset{b}{↷} ⇓ \overset{b}{↶} ↶$
	$\overset{b}{↶} ↶ ⇑ ↷ \overset{b}{↷} ⇓ \overset{b}{↶}$	$⇓ \overset{b}{↶} ↶ ⇑ ↷ \overset{b}{↷}$	$\overset{b}{↷} ⇓ \overset{b}{↶} ↶ ⇑ ↷ \overset{b}{↷}$

Theorem 5

the total turning angle of singular paths is less than 3π.

Proof

As it is shown in Figure 13 there are three types of singular paths, based on the starting maneuver:

(I) CCLCCLCC…, that is, $↶ {\overset{b}{↶}}_{\frac{π}{2}} ⇓ {\overset{b}{↶}}_{\frac{π}{2}} ↶_{\frac{π}{2}} ⇑ ↶_{\frac{π}{2}} \overset{b}{↶}$

(II) CLCCLCCL…, that is, $\overset{b}{↶} ⇓ {\overset{b}{↶}}_{\frac{π}{2}} ↶_{\frac{π}{2}} ⇑ ↶_{\frac{π}{2}} \overset{b}{↶}$

(III) LCCLCCLC…, that is, $⇑ ↶_{\frac{π}{2}} {\overset{b}{↶}}_{\frac{π}{2}} ⇓ {\overset{b}{↶}}_{\frac{π}{2}} ↶_{\frac{π}{2}}$

where “C” stands for R′-Circular arcs and “L” stands for Lines In the following each type is elaborated separately.

(I) CCLCCLCC…

• If the rotation during the initial “C” is less than $\frac{π}{2}$ , the maximum length optimal Type(I) path is CCLCCLCC with the last “C” also less than $\frac{π}{2}$ : Without loss of generality consider $↶ {\overset{b}{↶}}_{\frac{π}{2}} ⇓ {\overset{b}{↶}}_{\frac{π}{2}} ↶_{\frac{π}{2}} ⇑ ↶_{\frac{π}{2}} \overset{b}{↶}$ where the turning of each ↶ and $\overset{b}{↶}$ is less than $\frac{π}{2}$ . If the path is extended to $↶ {\overset{b}{↶}}_{\frac{π}{2}} ⇓ {\overset{b}{↶}}_{\frac{π}{2}} ↶_{\frac{π}{2}} ⇑ ↶_{\frac{π}{2}} {\overset{b}{↶}}_{\frac{π}{2}}$ , it can be replaced by $↶ {\overset{b}{↶}}_{\frac{π}{2}} ⇓$ . As straight lines are commanded at ${\tilde{v}}_{\max}$ and are by definition the shortest path between two points, a ⇑ is always more time optimal than a path that includes turns. In singular paths the length of straight line motions (⇑, ⇓) is in $[0, + \infty)$ . Any further hypothetical extension of the pattern will always include the subset $↶ {\overset{b}{↶}}_{\frac{π}{2}} ⇓ {\overset{b}{↶}}_{\frac{π}{2}} ↶_{\frac{π}{2}} ⇑ ↶_{\frac{π}{2}} \overset{b}{↶}$ once or more times, and in each case this subset is more optimally replaced with a straight line.

• If the rotation of the initial “C” is equal to $\frac{π}{2}$ , the maximum length optimal Type(I) path is CCLCC with the last “C” less than $\frac{π}{2}$ : Without loss of generality consider $↶_{\frac{π}{2}} {\overset{b}{↶}}_{\frac{π}{2}} ⇓ {\overset{b}{↶}}_{\frac{π}{2}} ↶$ . If the path is extended to $↶_{\frac{π}{2}} {\overset{b}{↶}}_{\frac{π}{2}} ⇓ {\overset{b}{↶}}_{\frac{π}{2}} ↶_{\frac{π}{2}}$ . The extended path easily can be replaced by ⇑. As before, any extension can be replaced with a shortest path.

(II) CLCCLCCL…

The maximum length optimal Type(II) path is CLCCLCC with the rotation of the final “C” less than $\frac{π}{2}$ . The initial “C” may be less than or equal to $\frac{π}{2}$ : Without loss of generality consider $\overset{b}{↶} ⇓ {\overset{b}{↶}}_{\frac{π}{2}} ↶_{\frac{π}{2}} ⇑ ↶_{\frac{π}{2}} \overset{b}{↶}$ . The extended path is $\overset{b}{↶} ⇓ {\overset{b}{↶}}_{\frac{π}{2}} ↶_{\frac{π}{2}} ⇑ ↶_{\frac{π}{2}} {\overset{b}{↶}}_{\frac{π}{2}}$ which can be replaced by $\overset{b}{↶} ⇓$ . Any extension can be replaced by a subset of the path.

(III) LCCLCCLC…

The maximum length optimal Type(III) path is LCCLCC with the rotation of last “C” less than $\frac{π}{2}$ : Without loss of generality consider $⇑ ↶_{\frac{π}{2}} {\overset{b}{↶}}_{\frac{π}{2}} ⇓ {\overset{b}{↶}}_{\frac{π}{2}} ↶$ . If the path is extended to $⇑ ↶_{\frac{π}{2}} {\overset{b}{↶}}_{\frac{π}{2}} ⇓ {\overset{b}{↶}}_{\frac{π}{2}} ↶_{\frac{π}{2}}$ , it can be replaced by ⇑. In any extension can be replaced by a subset of the path.■

Theorem 6

the total turning of Generic Turns are less than 3π.

Proof

Considering Figure 13, it could be concluded that Generic Turns are analogous to Singularities but without straight line motions (⇑, ⇓). The sections that can be replaced by just straight lines always include a π/2 rotation in one direction (forward or backward) followed by a π rotation in the other direction and finally another π/2 rotation in the first direction, always in the same sense (CW or CCW), a 2π rotation in total (see Theorem 5). The maximum Generic Turn that avoids containing this particular pattern as a subset is just under 3π. Accordingly, the total turning of Generic Turns must be less than 3π. ■

3.5. Extremal path structures

From Theorem 3, the set of the optimal control inputs (U_c) is obtained. The control inputs are utilized to obtain and draw Hamiltonian level sets (Figure 9 through Figure 11). A sample for the related path to each level set is shown in Figure 13. Then, Theorem 4 through Theorem 6 are utilized to constrain the number of periods for the Generics and Singulars. Hence, Table 4 for the extremal path structures is obtained, covering all possible candidates for optimal path according to the Hamiltonian level sets. The finite number of path structures, 28, shown in Table 4 and their sub-paths are enumerated to obtain the optimal path for a given start and end pose. In the following section, a numerical scenario is solved for the above-mentioned table. In addition, some of the paths in the table are visualized.

4. Numerical scenario

The goal of this section is solving a numerical example to show how Table 4 is to be used for a particular scenario. Firstly, two lemmas are presented which will be used to calculate the length of straight lines for generic TST paths. Then, the scenario for the numerical example is explained. Afterwards, the algorithms to obtain the feasibility region for the extremal paths are explained. These regions show the feasible starting points of the extremal path structures for the considered scenario. Finally, a map (see Figure 19) is drawn for the particular scenario (Table 5) that shows which extremal path structure is optimal at each starting point in the 2D plane. The costs of the finite number of extremal path structures are enumerated and compared to draw the map.

Table 5.

The Start (S) and end (E) pose of the considered scenario. This type of particular scenario is useful for illustrating the kind of paths that are optimal depending on where the rover starts relative to a desired goal.

Point	Coordination
(x_S, y_S, θ_S)	$(x, y, \frac{π}{4})$
(x_E, y_E, θ_E)	$(0,0,0)$

4.1. Length of straight lines in generic TST paths

Firstly, a complete maneuver is explained in Definition 6. Then, the length of complete ⇑ or ⇓ for generic TST paths (see Figure 13) is mathematically obtained in Lemma 5.

Definition 6

For the maneuvers shown in Table 2, a complete maneuver for a particular λ₀ includes all the possible η and cos β for its related line segment of the level set (i.e., from one switching point to the other).

For example, ⇑ in Figure 14 is a complete maneuver if its related level set’s line segment includes all the points between A and B inclusive. Point A is the switching point between ↷ and ⇑. Also, B is the switching point between ⇑ and ↶.

Lemma 5

The length of a complete ⇑ or ⇓ maneuver for Generic TST paths is

L_{D} = \frac{2 η_{c}}{\sin β_{c}}, β_{c} \neq 0

(87)

where η_c is the maximum distance of the maneuver from the η − line. Also, β_c is the acute angle between the maneuver and η − line. For generic TST paths, cos β < 1 (See Figures 11 and Figure 13). The parameters are shown in Figure 15 and are obtained from the following relations:

β_{c} = \cos^{- 1} (\frac{λ_{0}}{{\tilde{v}}_{\max}})

(88)

η_{c} = \frac{λ_{0}}{{\tilde{ω}}_{\max}} (1 - \frac{{\tilde{v}}_{R^{'}}}{{\tilde{v}}_{\max}})

(89)

Figure 14.

The level set for explaining a complete maneuver.

Figure 15.

Complete ⇑ maneuver for a generic TST path in Figure 13.

${\tilde{v}}_{\max}$ , ${\tilde{v}}_{R^{'}}$ , and ${\tilde{ω}}_{\max}$ were indicated in Figure 6.

Proof

In the following, the analysis is done for complete ⇑ maneuver that the similar evaluation can be performed for complete ⇓ maneuver.

From the symmetry of the level sets (Figure 13) the η − line crosses the middle of a complete ⇑. Hence, by considering Figure 14 the following relation is obtained:

\sin β_{c} = \frac{2 η_{c}}{L_{D}}

(90)

Therefore,

L_{D} = \frac{2 η_{c}}{\sin β_{c}}, β_{c} \neq 0

(91)

Since ⇑ is a complete maneuver, η_c occurs at the switching point of ↷ ⇑ or ⇑ ↶ path. In the following each one is analyzed separately:

• Switching point of ↷ ⇑

Equation (81) and equation (84) give the following relations at the switching point:

λ_{0} = {\tilde{v}}_{\max} \cos β_{s_{1}}

(92)

λ_{0} = {\tilde{v}}_{R^{'}} \cos β_{s_{1}} + {\tilde{ω}}_{\max} η_{s_{1}}

(93)

where

η_{s_{1}}

and

β_{s_{1}}

are the η and β at the switching point of ↷ ⇑, respectively. By solving the above two equations, the following results are obtained for

η_{s_{1}}

and

β_{s_{1}}

η_{s_{1}} = \frac{λ_{0}}{{\tilde{ω}}_{\max}} (1 - \frac{{\tilde{v}}_{R^{'}}}{{\tilde{v}}_{\max}})

(94)

β_{s_{1}} = \cos^{- 1} (\frac{λ_{0}}{{\tilde{v}}_{\max}})

(95)

Therefore, η_c is the absolute value of

η_{s_{1}}

. Also,

{\tilde{v}}_{R^{'}} < {\tilde{v}}_{\max}

(see Figure 6). Hence,

η_{c} = | η_{s_{1}} | = \frac{λ_{0}}{{\tilde{ω}}_{\max}} (1 - \frac{{\tilde{v}}_{R^{'}}}{{\tilde{v}}_{\max}})

(96)

For generic TST paths,

0 < λ_{0} < {\tilde{v}}_{\max}

(see Figure 11). Thus,

0 < β_{s_{1}} < \frac{π}{2}

(

β_{s_{1}}

is acute). So,

β_{c} = | β_{s_{1}} | = \cos^{- 1} (\frac{λ_{0}}{{\tilde{v}}_{\max}})

(97)

• Switching point of ⇑ ↶

Equation (81) and equation (83) give the following relations at the switching point:

λ_{0} = {\tilde{v}}_{\max} \cos β_{s_{2}}

(98)

λ_{0} = {\tilde{v}}_{R^{'}} \cos β_{s_{2}} - {\tilde{ω}}_{\max} η_{s_{2}}

(99)

where

η_{s_{2}}

and

β_{s_{2}}

are the η and β at the switching point of ⇑ ↶, respectively. By solving the above two equations, the following results are obtained for

η_{s_{2}}

and

β_{s_{2}}

η_{s_{2}} = \frac{λ_{0}}{{\tilde{ω}}_{\max}} (\frac{{\tilde{v}}_{R^{'}}}{{\tilde{v}}_{\max}} - 1)

(100)

β_{s_{2}} = \cos^{- 1} (\frac{λ_{0}}{{\tilde{v}}_{\max}})

(101)

Hence, η_c is the absolute value of

η_{s_{2}}

. Accordingly,

η_{c} = | η_{s_{2}} | = \frac{λ_{0}}{{\tilde{ω}}_{\max}} (1 - \frac{{\tilde{v}}_{R^{'}}}{{\tilde{v}}_{\max}})

(102)

Also,

β_{s_{1}} = β_{s_{2}} = β_{c}

(103)

■

Lemma 6

For generic TST paths:

λ_{0} \neq 0

(104)

Proof

Consider equation (87) through equation (89). If λ₀ = 0, it will result in β_c = $\frac{π}{2}$ and η_c = 0. Hence, L_D = 0. Therefore, the Hamiltonian level set becomes a point at the origin of Figure 11 (or see Figure 13 for generic TST paths). As a result, no Generic TST path will be produced. Therefore, λ₀ cannot be zero.■

The proved lemmas will be used in Algorithm 1 to create a table that includes β_c and L_D. Before that step, the scenario will be defined in the following subsection.

4.2. Particular scenario and steps to find the optimal paths

Scenario: To go from start poses anywhere in the x − y plane (at a starting orientation of π/4) to the origin (see Table 5) in minimum time while constrained to the control space in Figure 15. Also, the considered B_s is 1.32 m which is the measured B_s for Husky UGV on hard ground. Therefore,

R^{'} = \frac{B_{s}}{2} = 0.66 m

(105)

Inspecting Figures 6 and 16 reveals that:

\begin{array}{l} {\tilde{v}}_{\max} = 1 \\ {\tilde{v}}_{R^{'}} = \frac{2}{3} \\ {\tilde{ω}}_{\max} = 1 \end{array}

(106)

Figure 16.

The example control space considered for the numerical scenario.

There are three main steps for producing the optimal map shown in Figure 19:

I Generating all the extremal path structures reported in Table 4 and their subpaths by using turtle library in Python.

II Finding the feasibility region for each of the paths for the considered scenario. Also, calculating the cost of the paths.

III Comparing the cost of the paths and drawing the optimal map.

Step I and step II are explained in the following subsection. Step III is performed in subsection Map of the Optimal Paths.

4.3. Generating extremals and finding the feasibility regions

An example for a generic TST path is plotted in Figure 17. The path is generated by using turtle library in Python.

Figure 17.

$⇑ ↷ \overset{b}{↷} ⇓ \overset{b}{↶} ↶$ path. It is going from (x, y, θ) to (0,0,0), which is denoted by •.

Feasibility Regions: A feasibility region for a path type indicates the (x_S, y_S) values from which the origin can be reached by following that path type. To obtain the feasibility region the end pose of the paths are forced to be at (x_E, y_E, θ_E)=(0,0,0). Then, the turns and straight line maneuvers are allowed to vary in their acceptable range for the considered path. Afterwards, θ_S is checked. If θ_S is π/4 within a small error (ϵ_th = 0.1° which is ϵ_th = 0.0006π radian), (x_S, y_S) is saved. Therefore, the feasibility regions/lines for each of the generic Turns, singular, and generic TST paths or their subpaths are obtained.

As an example the algorithm utilized to obtain the feasibility region/line for the path (and its subpaths) shown in Figure 17 is explained. The algorithms of all remaining paths and their subpaths are obtained with similar methodology.

Algorithm 1 uses Lemma 5 to generate a table including L_D and the related β_c. The table produced by this algorithm is used in Algorithm 2 which calculates the feasibility regions for subpaths of Figure 17 (an example of generic TST paths). In all these cases, subpaths are defined such that the first and last maneuvers need not be complete (by Definition 6).

Algorithm 1: Algorithm to create the L_D table

Algorithm 2: Algorithm to obtain the feasibility region shown in Figure 18

Figure 18.

Resulting feasibility region for all subpaths of $⇑ ↷ \overset{b}{↷} ⇓ \overset{b}{↶} ↶$ . The plot is trimmed for y values.

As explained previously, whirls have the structure of “roll-and-catch.” Rolls are R′-circular arcs that finally will be followed by a catch which is a circular arc of $R \in [0, R^{'})$ . Therefore, the feasibility region for the whirls is produced by varying the angles for each part (for rolls and catch) while considering their proper turning radii.

Considering the scenario, the feasibility regions for the starting points of the extremals are sketched and the related costs are calculated. In the following subsection, the costs are compared to determine the path with the minimum cost when starting in different parts of the x − y plane in 2D.

4.4. Map of the optimal paths

The subsequent process for the considered scenario is followed to compare the costs and draw the map (Figure 19) of the optimal paths:

• The parameters reported in Table 6 are considered for the scenario (that was introduced in subsection of Particular Scenario and Steps to Find the Optimal Paths).

• Algorithm 3 is applied to all the obtained feasibility regions. To compare the costs of extremal path structures, they should have the same (x, y) for the samples/grids. Thus, Algorithm 3 is required to create those samples/grids by using the data of the existing samples in the feasibility region of each path.

• Algorithm 4 is applied to the data produced in the previous step. Therefore, the minimum-cost path for each (x, y) is chosen and plotted in Figure 19.

Figure 19.

Map indicating the optimal paths to the origin when starting at different $(x, y, \frac{π}{4})$ on the x − y plane.

Table 6.

The Parameters Considered for the Algorithms to Obtain the Map (Figure 19).

Parameter	Value
x _step	0.1 m
y _step	0.1 m
{x_min, y_min}	{−5 m, 5 m}
{x_max, y_max}	{−5 m, 5 m}
n_NN	5-10

Algorithm 3: Grid producing algorithm for an extremal path structure.

Algorithm 4: Comparing the costs and drawing the optimal map.

The legends for the optimal paths shown in Figure 19 are indicated in Table 7 by using the maneuver symbols defined in Table 2. As it can be seen from the map, there are three types of paths that cover the largest areas of the figure and extend to its boundaries. They are as follows: CLC, CCLC, and CLCC. To interpret the map, consider as an example the coordinate of (4,1). Based on the map, the optimal path to go from (4, 1, π/4) to (0,0,0) is a CLC path. Each of the categories for the paths that were mentioned includes several path types. For example, the CLC (true blue region) path in the map includes all the path types that are reported in Table 7 and shown in Figure 20.

Table 7.

The Correspondent Maneuver Symbols for the Paths Shown in Figure 19.

Path		Arrows
CLC	$\overset{b}{↷} ⇓ \overset{b}{↶}$	↶⇑↷
	$\overset{b}{↶} ⇓ \overset{b}{↷}$	↷⇑↶
	$\overset{b}{↷} ⇓ \overset{b}{↷}$	↷⇑↷
CCL	$\overset{b}{↷} ↷ ⇑$	$↷ \overset{b}{↷} ⇓$
LCCL	$⇓ \overset{b}{↷} ↷ ⇑$	$⇑ ↷ \overset{b}{↷} ⇓$
CLCC	$\overset{b}{↶} ⇓ \overset{b}{↷} ↷$	$↶ ⇑ ↷ \overset{b}{↷}$
CCLC	$↷ \overset{b}{↷} ⇓ \overset{b}{↶}$	$\overset{b}{↷} ↷ ⇑ ↶$
CCLCC	$\overset{b}{↷} ↷ ⇑ ↶ \overset{b}{↶}$	$↷ \overset{b}{↷} ⇓ \overset{b}{↶} ↶$
LCCLCC	$⇓ \overset{b}{↷} ↷ ⇑ ↶ \overset{b}{↶}$	$⇑ ↷ \overset{b}{↷} ⇓ \overset{b}{↶} ↶$
LCCLC	$⇓ \overset{b}{↷} ↷ ⇑ ↶$	$⇑ ↷ \overset{b}{↷} ⇓ \overset{b}{↶}$
CLCCL	$\overset{b}{↶} ⇓ \overset{b}{↷} ↷ ⇑$	$↶ ⇑ ↷ \overset{b}{↷} ⇓$

Figure 20.

The paths related to the true blue region (CLC) in Figure 19.

Whirls have the structure of “roll-and-catch”: R′-circular arcs, starting from the initial pose, eventually followed by a turn with $R \in [0, R^{'})$ which puts the rover to the final pose. The Cyan color in the map (see Figure 19) includes two types of whirls:

• Whirls that are closest to the origin just consist of a catch part.

• The other whirls which are far enough from the origin include a roll (a circular arc with R′) and a catch part.

4.4.1. More discussion on the map

Since there are some similarities between the dynamics of differential drive rovers and skid-steer rovers, and also Balkcom and Mason (2002) analyzed a scenario for differential drive rovers similar to ours listed in Table 5 for skid-steer rovers, we discuss similarities and differences between the results in our map (Figure 19) and in Figure 12 presented by Balkcom and Mason (2002). In both figures, there is a type of path which is dominant (covers the most region): PLP for differential drive and CLC for skid-steer rovers. Also, the comparison reveals that instead of R′-circular arcs (“C”), differential drive rovers do point turns (“P”). The analogy extends to either single or pairs of “C”s standing in for “P”s. For example, from similar starting regions, instead of Line-Point turn-Line (LPL) for differential drive, the skid-steer rovers perform LCCL. Also, instead of PLPL for differential drive rovers, skid-steer rovers do CLCCL.

4.4.2. Expectation/Prediction about other scenarios

We expect that for other scenarios beyond the one that was thoroughly analyzed above, the CLC paths will be dominant in the correspondent optimal map. The reason is that avoiding extra turns and instead doing straight lines will normally result in more efficient paths. Therefore, for those regions where CLC paths are feasible, they are the most efficient path. Such CLC paths are generally feasible when the starting pose is far enough from the goal pose, and the goal pose is roughly ahead or behind the start pose. When the goal pose is predominantly to the rover’s left or right, an additional turn (for a CLCC or CCLC) is required. All other path types are only optimal when start and end points are close together, within a few multiples of R′.

The procedure of finding the optimal map involves conducting the grid-producing process, constructing an extremal path structure, and subsequently comparing the costs to derive the optimal map for any starting angle starting (x,y) with the specific angle directed towards the origin. Following this, the look-up table approach can be employed to determine the appropriate path for the specific starting pose. In cases where the entire map creation is unnecessary, applying algorithms 1–4 solely for the selected (x, y, θ) will suffice. In conclusion, two approaches are presented. The first approach entails creating a comprehensive map for various starting angles and employing the look-up table or regression for intermediate specifications. On the other hand, the second approach does not utilize the optimal map or regression and instead follows the explained method of using algorithms 1–4 to obtain the path for a specific pose.

In addition, to illustrate various instances of the predominant paths within the optimal map, Figure 21 is included.

Figure 21.

Dominant paths on the optimal map. Whirls consist of a roll, that is circular arc with R = R′, and a catch, a circular arc with a tighter R ∈ [0, R′] that puts the rover in the final pose. Green arrow indicates starting pose and red arrow indicates final pose.

5. Experimental tests

The objective of the work in this section is to provide experimental support for Theorem 1. Specifically, we demonstrate that the following problems have the same optimal answer:

(a) Constant v_c Energy-Optimal Problem: the energy-efficient problem (see equation (1)) subject to the proper constraint of Constant v_c (Case 1 on page 8) and the control space defined by |V_r|+|V_l| = 2v_c, with v_c = 0.3 m/s.

(b) Equivalent Time-Optimal Problem: the energy-efficient problem (see equation (1)) subject to the proper constraint of constant-power (Case 4 on page 8) and the corresponding control space shown in Figure 22,

Figure 22.

The hexagonal control space considered for the Equivalent Time-Optimal experiments.

Two separate scenarios which are reported in Table 8 are performed for both of the Constant v_c energy-efficient problem and equivalent time-optimal problem to investigate which turning radii are optimal, in terms of energy and time respectively. A Husky UGV (see Figure 23) is used for the tests. The CLC path is selected for testing, which is the most common and dominant path on map 19; it is compared in terms of energy and time against the PLP, which is the most prevalent path to traverse between two poses for skid-steer rovers. The following relations are used for the comparisons:

Δ E % = \frac{E_{CLC} - E_{PLP}}{E_{PLP}} \times 100

(107)

Δ t % = \frac{t_{CLC} - t_{PLP}}{t_{PLP}} \times 100

(108)

Table 8.

Husky rover test plan on hard ground. It is noted that plp is the abbreviation for point turn-line-point turn.

Terrain	Maneuver	$(θ_{A}^{P}, θ_{C}^{P})$	Commanded $‖ \vec{AC} ‖$ for Husky
Concrete	CLC	(45°, 45°)	10 m
Concrete	CLC	(60°, 30°)	8 m
Concrete	PLP	(45°, 45°)	Measured Dis., CLC (45°, 45°)
Concrete	PLP	(60°, 30°)	Measured Dis., CLC (60°, 15°)

Figure 23.

Husky UGV and the laser total station for tracking the rover motion.

The power measurement process encompassed both the left and right motors, employing a Texas Instruments INA226 bidirectional current and power sensor. The power consumption over a specific duration was collected, and then numerically integrated over the time period to determine energy consumption.

As it can been seen from Figures 24 and 25, the minimum-energy for CLC paths subject to the Constant v_c constraint happens at R′ (Effati et al. 2020). Moreover, Figures 26 and 27 show that the minimum time for the equivalent time-optimal problem also occurs at R′. It is noted that the tests are repeated at least 3 times for each turning radius.

Figure 24.

Energy comparison between CLC and PLP paths for the Constant vc experiments for the distance of 10 m and $(θ_{A}^{P}, θ_{C}^{P})$ = (45^o, 45^o). Note: measured R′ is 0.65 m for Husky UGV on hard ground.

Figure 25.

Energy comparison between CLC and PLP paths for the Constant vc experiments for the distance of 8 m and $(θ_{A}^{P}, θ_{C}^{P})$ = (60^o, 30^o). Note: measured R′ is 0.65 m for Husky UGV on hard ground.

Figure 26.

Time comparison between CLC and PLP paths for the Equivalent Time-Optimal experiments for the distance of 10 m and $(θ_{A}^{P}, θ_{C}^{P})$ = (45^o, 45^o). Note: measured R′ is 0.65 m for Husky UGV on hard ground.

Figure 27.

Time comparison between CLC and PLP paths for the Equivalent Time-Optimal experiments for the distance of 8 m and $(θ_{A}^{P}, θ_{C}^{P})$ = (60^o, 30^o). Note: measured R′ is 0.65 m for Husky UGV on hard ground.

These results provide strong experimental support for Theorem 1, which states that the minimum time optimization problem subject to the hexagonal shape control space (i.e., the constant-power constraint, Figure 14) has the same solution as the minimum energy optimization problem subject to any proper constraint, including the Constant v_c constraint.

Table 9 compares the average actual measured energy with the predicted values, for the scenario with a distance of 10 m and starting and ending angles of 45°, at various turning radii, all subject to the constant v_c constraint. All errors are less than 10%.

Table 9.

Measured Energy (ME), Predicted Energy (PE), and the % Error, for Different Turning Radii, for the Distance of 10 m and $(θ_{A}^{P}, θ_{C}^{P})$ = (45^o, 45^o).

R (m)	ME (J)	PE (J)	Error (%)
0.5 R′	982	925	6
R′	925	907	2
1.5 R′	945	917	3
2R′	1002	928	8

Figure 28 shows a visualization of the paths generated at different R′ values.

Figure 28.

CLC paths for different turning radii of 0.5 R′, 1R′, 1.5 R′, and 2R′. (a) CLC paths for different turning radii, the distance of 10 meters, and $(θ_{A}^{P}, θ_{C}^{P})$ = (45^o, 45^o) (b) CLC paths for different turning radii, the distance of 10 m, and $(θ_{A}^{P}, θ_{C}^{P})$ = (60^o, 30^o).

Representative samples comparing the commanded and measured paths from experimental tests are shown in Figure 29.

Figure 29.

Comparison of commanded and measured CLC paths, with turning radii of 0.5 R′ in this sample. The slight difference between the measured and commanded paths in (b) is due to some excess skidding that occurred toward the end of the path. (a) Commanded and measured CLC paths for the distance of 10 meters and $(θ_{A}^{P}, θ_{C}^{P})$ = (45^o, 45^o) (b) Commanded and measured paths for the distance of 8 m and $(θ_{A}^{P}, θ_{C}^{P})$ = (30^o, 60^o).

As depicted in Table 8, two distinct scenarios are presented: one involving an angle of (45, 45) degrees and a distance of 10 m, and the other featuring an angle of (60, 30) degrees and a distance of 8 m. Each of these scenarios was evaluated across four varying turning radii (0.5R′, R′, 1.5R′, and 2R′). The energy consumption was calculated for each combination, and subsequently, the average energy consumption was computed. For the first scenario, the average energy consumption attributed to the angular velocity (ω_z) term and the linear velocity (v) are determined to be 31% and 69%, respectively. For the second scenario, the corresponding percentages are 37% and 63%, respectively.

6. Conclusions and future work

The contributions and results of this paper are discussed and summarized here, and then proposed/planned future work is reported.

6.1. Conclusions

Skid-steer rovers consume a lot more power in point turns compared to straight-line motions. As energy is the integral of power over time, lower instantaneous power consumption for wider arcs must be traded off against shorter traversal distance for tighter arcs. A thorough review of the published literature reveals a lack of analytical energy-optimal path planning approaches for skid-steer rovers. This paper has addressed this problem for such rovers moving on obstacle-free hard ground. From the evaluations and investigations of the problem, the following findings are concluded:

• Equivalency Theorem: This theorem which is a key contribution of this paper indicates that, for a popular power model for skid-steer rovers on hard ground, all minimum-energy solutions follow the same path irrespective of velocity constraints that may or may not be imposed. This non-intuitive result stems from the fact that for the relevant power model, the total energy is fully parameterized by the geometry of the path alone. The velocity constraint must not limit the range of the turning radius. According to our research, the constraint may be “constant v_c,” “constant-power velocity constraint,” or “bounded velocity,” among others. Our approach to solve the energy-optimal path planning problem is considering “constant-power velocity constraint,” and thus converting the problem to an equivalent time-optimal problem. Hence, the equivalency theorem avoids the regeneration/revising/adjusting of theory for being applied to our energy-optimal problem. Instead, the equivalent time-optimal problem is solved using the existing theory and process from the literature (references (Balkcom and Mason 2002; Furtuna 2011))–built upon the basis of Pontryagin’s Minimum Principle to find the extremals for time-optimal path planning for a rigid body.

• Experimental support for the Equivalency Theorem: Using a Husky UGV skid-steer rover, several experimental tests are done for the equivalent time-optimal problem and Constant v_c energy-optimal problem. To perform these tests, CLC (the dominant path on the optimal map for the energy efficiency) and PLP (the most prevalent path for navigating between two poses) paths are chosen. The results demonstrate that the answers for both of the above motioned problems is the same and happens at R′. Therefore, the answer for the energy-optimal problem by considering the proper constraints of the constant power and constant forward velocity is the same. Accordingly, the power of the equivalency theorem is demonstrated experimentally.

• Extremal Path Structures: Using the existing theory and proving some additional theorems specifically for skid-steer rovers, the answer to the equivalent time-optimal path planning problem is found. Hence, all the possible extremal path structures for the energy-optimal path planning problem are obtained, which is another key contribution of this paper. As there is a finite number of extremals, 28 plus whirls, they can be enumerated to find the one with minimum cost. An example scenario, going from a starting point in 2D x-y space with the orientation of π/4 to the origin with orientation of 0, is provided to demonstrate the method by which the extremal path structures are be utilized to obtain the optimal path. The results indicate that there are three types of path that cover the most area of the optimal map: CLC, CCLC, and CLCC. For those regions where CLC paths are feasible (when the goal pose is sufficiently ahead or behind the rover) they are the most efficient path. When the goal pose is predominantly to the rover’s left or right, an additional turn (for a CLCC or CCLC) is required. All other path types are only optimal when start and end points are close together, within a few multiples of R′. We expect similar results for other scenarios besides the analyzed example.

• R′: Another key contribution is more investigation on the importance of R′, a particular turning radius equal to half of a skid-steer rover’s slip track. In other words, R′ is the turning radius at which the inner wheels of a skid-steer rover are not commanded to turn. The analysis identifies that all the turns for the non-whirl paths (the vast majority of the obtained extremals paths) have a turning radius of R′.

6.2. Future work

Since the power model (equation (22)) is designed for hard ground, all the theoretical analysis in this paper are performed by the assumption of moving on hard ground. However, for applications such as space robotics the rover should be able to follow the optimal trajectory on loose soil. Accordingly, the power model (equation (22)) should be revised for loose soil. Some preliminary research has been performed to identify the power model for loose soil around R′ by Fiset (2019); Fiset et al. (2019). However, it still requires more investigation to obtain a proper power model on loose soil. After the mentioned step, the energy-optimal path planning problem should be solved for this type of terrain.

As both energy and time can be considered in optimal trajectory planning, an interesting direction of future work is optimal path planning by minimizing a hybrid time-energy cost for skid-steer rovers. This may even be directly interesting to energy minimization as, beyond the large share of power used for locomotion, rovers typically also have some component of energy consumption that is approximately constant in time such as electrical power draw for computing and sensing.

Another interesting direction for future work is considering obstacles. As mentioned in the introduction, the scope of this work has been local planning methods (LPM) for the space between nodes that are already chosen to avoid obstacles in a complex environment. However, direct extensions to environments with obstacles might prove fruitful, especially if the obstacles are sparse. In that case, initial LPM solutions could be checked for obstacle intersection, with interim nodes iteratively added in case of intersections; adaptive processes for such tasks would need to be developed.

Finally, results from this work could immediately be integrated into ongoing work with skid-steer rovers that use Sampling Based Model Predictive Optimization (SBMPO). Instead of “sampling” from among the space of admissible controls, one could simply use the same six optimal candidate controls (forward, backward, and the 4 R′ turns) at each branching point in the SBMPO framework and obtain results closer to the global optimum at lower computational cost.

Footnotes

Acknowledgements

The authors acknowledge funding and technical collaboration from Mission Control Space Services Inc. as well as financial support from the Natural Sciences and Engineering Research Council of Canada (NSERC). Additionally, the authors acknowledge Tim Freiman’s collaboration in conducting the experiments to generate the two figures related to the time-optimal experiments.

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported by the Canadian Network for Research and Innovation in Machining Technology and Natural Sciences and Engineering Research Council of Canada (NSERC CRD 520713-2017).

ORCID iDs

Meysam Effati

Krzysztof Skonieczny

Notes

Appendix

References

Balkcom

(2000) Time optimal trajectories for bounded velocity differential drive robots. In: Proceedings 2000 Icra. Millennium Conference. Ieee International Conference on Robotics and Automation. San Francisco, CA, USA: IEEE, volume 3, pp. 2499–2504.

Balkcom

Kavathekar

(2008) The minimum-time trajectories for an omni-directional vehicle. In: Algorithmic Foundation of Robotics VII. Berlin, Germany: Springer, pp. 343–358.

Balkcom

Mason

(2000) Extremal Trajectories for Bounded Velocity Differential Drive Robots. In: Proceedings 2000 ICRA. Millennium Conference. IEEE International Conference on Robotics and Automation. Symposia Proceedings (cat. No. 00CH37065). San Francisco, CA, USA: IEEE, volume 3, pp. 2479–2484.

Balkcom

Mason

(2002) Time optimal trajectories for bounded velocity differential drive vehicles. The International Journal of Robotics Research 21(3): 199–217.

Balkcom

Kavathekar

Mason

(2006) Time-optimal trajectories for an omni-directional vehicle. The International Journal of Robotics Research 25(10): 985–999.

Balkcom

Furtuna

Wang

(2018) The Dubins car and other arm-like mobile robots. In: 2018 IEEE International Conference on Robotics and Automation (ICRA). Brisbane, QLD, Australia: IEEE, pp. 380–386.

Betz

(2015) Engineering Satellite-Based Navigation and Timing: Global Navigation Satellite Systems, Signals, and Receivers. Hoboken, NY, USA: John Wiley & Sons.

Boissonnat

Crzo

Leblond

(1994) Shortest paths of bounded curvature in the plane. Journal of Intelligent and Robotic Systems 11(1-2): 5–20.

Chaudhari

Vachhani

Banerjee

(2014) Towards optimal computation of energy optimal trajectory for mobile robots. IFAC Proceedings Volumes 47(1): 82–87.

10.

Chitsaz

LaValle

Balkcom

, et al. (2009) Minimum wheel-rotation paths for differential-drive mobile robots. The International Journal of Robotics Research 28(1): 66–80.

11.

Dolinskaya

Maggiar

(2012) Time-optimal trajectories with bounded curvature in anisotropic media. The International Journal of Robotics Research 31(14): 1761–1793.

12.

Dubins

(1957) On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents. American Journal of mathematics 79(3): 497–516.

13.

Dunlap

Caldwell

Collins

, et al. (2011) Motion planning for mobile robots via sampling-based model predictive optimization. In: Recent Advances in Mobile Robotics 1. Norderstedt, Germany: Books on Demand.

14.

Effati

(2020) Energy-Efficient Trajectory Planning for Skid-Steer Rovers. PhD Thesis. Montreal, Canada: Concordia University.

15.

Effati

Skonieczny

(2018) Circular arc-based optimal path planning for skid-steer rovers. In: 2018 IEEE Canadian Conference on Electrical & Computer Engineering (CCECE). Quebec, QC, Canada: IEEE, pp. 1–4.

16.

Effati

Skonieczny

(2023) Systematic solution for optimally energy-efficient turning radius for wheeled skid-steer rovers. Robotics and Autonomous Systems 159: 104306.

17.

Effati

Fiset

Skonieczny

(2020) Considering slip-track for energy-efficient paths of skid-steer rovers. Journal of Intelligent and Robotic Systems 100: 335–348.

18.

Effati

Fiset

Skonieczny

(2021) Experimental validation of energy-optimal turning radii for skid-steer rovers. In: Experimental Robotics: The 17th International Symposium. Berlin, Germany: Springer, pp. 402–410.

19.

Effati

Skonieczny

Freiman

, et al. (2022) An equivalent time-optimal problem to find energy-optimal paths for skid-steer rovers. In: 2022 IEEE/RSJ international conference on intelligent robots and systems (IROS). Piscataway, NJ, USA: IEEE, pp. 13341–13346.

20.

Faraj

Basir

(2016) Optimal energy/time routing in battery-powered vehicles. In: 2016 IEEE transportation electrification conference and expo (ITEC). Dearborn, MI, USA: IEEE, pp. 1–6.

21.

Fiset

(2019) Effects of turning radius on skid-steered wheeled robot power consumption on loose soil. Master’s Thesis. Montreal, Canada: Concordia University.

22.

Fiset

Effati

Skonieczny

(2019) Effects of turning radius on skid-steered wheeled robot power consumption on loose soil. In: 12th Conference on Field and Service Robotics. Tokyo, Japan: FSR, pp. 1–14.

23.

Fiset

Effati

Skonieczny

(2023) Power and energy consumption of skid-steer rovers turning on loose soil. Journal of Field Robotics 40(2): 193–214.

24.

Furtuna

(2011) Minimum time kinematic trajectories for self-propelled rigid bodies in the unobstructed plane. PhD Thesis. Hanover, NH, USA: Dartmouth College. https://rlab.cs.dartmouth.edu/publications/FurtunaPhD.pdf

25.

Furtuna

Balkcom

(2010) Generalizing Dubins curves: minimum-time sequences of body-fixed rotations and translations in the plane. The International Journal of Robotics Research 29(6): 703–726.

26.

Furtuna

Balkcom

Chitsaz

, et al. (2008) Generalizing the Dubins and reeds-shepp cars: fastest paths for bounded-velocity mobile robots. In: 2008 IEEE international conference on robotics and automation. Pasadena, CA, USA: IEEE, pp. 2533–2539.

27.

Furtuna

Wang

, et al. (2011) Minimum-time trajectories for kinematic mobile robots and other planar rigid bodies with finite control sets. In: 2011 IEEE/RSJ International Conference on Intelligent Robots and Systems. San Francisco, CA, USA: IEEE, pp. 4321–4328.

28.

Furtuna

Wang

Lyu

, et al. (2013) Structure and geometry of minimum-time trajectories for planar rigid bodies. In: 2013 51st Annual Allerton Conference on Communication, Control, and Computing (Allerton). Monticello, IL, USA: IEEE, pp. 1584–1591.

29.

Gupta

Ordonez

Collins

(2017) Dynamically feasible, energy efficient motion planning for skid-steered vehicles. Autonomous Robots 41(2): 453–471.

30.

Gutman

Ioslovich

Moshenberg

(2015) On the optimal control of the rigid body precise movement: is energy optimality the same as time optimality? In: 2015 Proceedings of the Conference on Control and its Applications. Sydney, NSW, Australia: SIAM, pp. 32–38.

31.

Heath

(2018) Scientific Computing: An Introductory Survey. Sydney, NSW, Australia: SIAM, Volume 80.

32.

Ioslovich

Moshenberg

Gutman

(2015) On the energy-optimal precise wafer stage positioning: equivalence with minimal time optimality. In: 2015 IEEE 24th International Symposium on Industrial Electronics (ISIE). Buzios, Brazil: IEEE, pp. 95–99.

33.

Ioslovich

Gutman

Berger

, et al. (2017) On energy-optimal and time-optimal precise displacement of rigid body with friction. Journal of Optimization Theory and Applications 172(2): 466–480.

34.

Kong

(2019) Time-energy optimal trajectory planning for variable stiffness actuated robot. IEEE Access 7: 14366–14377.

35.

Johnson

(1974) An application of the maximum principle to the geometry of plane curves. Proceedings of the American Mathematical Society 44(2): 432–435.

36.

Kassel

(1971) Lunokhod-1 Soviet Lunar Surface Vehicle. Santa Monica, CA, USA: Technical Report, Rand Corp Santa Monica.

37.

LaValle

(1998) Rapidly-exploring random trees: a new tool for path planning. Department of Computer Science, Iowa State University, Research Report 9811.

38.

LaValle

(2006) Planning Algorithms. Cambridge: Cambridge University Press.

39.

Lenarcic

Bajd

Stanišić

(2012) Robot Mechanisms. Berlin, Germany: Springer Science and Business Media, volume 60

40.

Lyu

(2016) Implications of motion planning: optimality and k-survivability. Hanover, NH, USA: Dartmouth College.

41.

Lyu

Balkcom

(2015) Optimal trajectories for planar rigid bodies with switching costs. In: Algorithmic Foundations of Robotics XI. Berlin, Germany: Springer, pp. 371–387.

42.

Lyu

Balkcom

(2016) Optimal trajectories for kinematic planar rigid bodies with switching costs. The International Journal of Robotics Research 35(5): 454–475.

43.

Lyu

Furtuna

Wang

, et al. (2014) The bench mover’s problem: minimum-time trajectories, with cost for switching between controls. In: 2014 IEEE international conference on robotics and automation (ICRA). Hong Kong, China: IEEE, pp. 106–112.

44.

Lyu

Song

Dai

, et al. (2017) Time-optimal and energy-efficient trajectory generation for robot manipulator with kinematic constraints. In: 2017 13th IEEE Conference on Automation Science and Engineering (CASE). Xi’an, China. IEEE, pp. 503–508.

45.

Mandow

Martinez

Morales

, et al. (2007) Experimental kinematics for wheeled skid-steer mobile robots. In: 2007 IEEE/RSJ International Conference on Intelligent Robots and Systems. San Diego, CA, USA: IEEE, pp. 1222–1227.

46.

Martínez

Mandow

Morales

, et al. (2005) Approximating kinematics for tracked mobile robots. The International Journal of Robotics Research 24(10): 867–878.

47.

Morales

Martinez

Mandow

, et al. (2009) Power consumption modeling of skid-steer tracked mobile robots on rigid terrain. IEEE Transactions on Robotics 25(5): 1098–1108.

48.

Morales

Martínez

Mandow

, et al. (2010) Simplified power consumption modeling and identification for wheeled skid-steer robotic vehicles on hard horizontal ground. In: 2010 IEEE/RSJ International Conference on Intelligent Robots and Systems. Taipei, Taiwan: IEEE, pp. 4769–4774.

49.

Nshama

Uchiyama

(2018) Time and energy optimal trajectory generation in feed drive systems using kinematic corner smoothing with interrupted acceleration. In: 2018 26th Mediterranean Conference on Control and Automation (MED). Zadar, Croatia: IEEE, pp. 102–107.

50.

Pentzer

Brennan

Reichard

(2014) Model-based prediction of skid-steer robot kinematics using online estimation of track instantaneous centers of rotation. Journal of Field Robotics 31(3): 455–476.

51.

Pentzer

Reichard

Brennan

(2016) Energy-based path planning for skid-steer vehicles operating in areas with mixed surface types. In: 2016 American Control Conference (ACC). Boston, MA, USA: IEEE, pp. 2110–2115.

52.

Pontryagin

Boltyanskii

Gamkrelidze

, et al. (1962) The Mathematical Theory of Optimal Processes. Hoboken, NJ, USA: John Wiley.

53.

Qin

Soh

Xie

, et al. (2000) Optimal trajectory generation for wheeled mobile robot. In: Proc. 5th Int. Conf. Comput. Integr. Manuf. Princeton, NJ, USA: Citeseer, volume 1: 434–444.

54.

Reeds

Shepp

(1990) Optimal paths for a car that goes both forwards and backwards. Pacific Journal of Mathematics 145(2): 367–393.

55.

Reese

(2015) A graph based approach to nonlinear model predictive control with application to combustion control and flow control. Tallahassee, FL, USA: Technical report. Florida A. M University.

56.

Reid

Iles

Muise

, et al. (2015) The Artemis Jr. rover: mobility platform for lunar ISRU mission simulation. Advances in Space Research 55(10): 2472–2483.

57.

Reif

(1979) Complexity of the mover’s problem and generalizations. In: 20th Annual Symposium on Foundations of Computer Science (Sfcs 1979). San Juan, PR, USA: IEEE, pp. 421–427.

58.

Shiller

(1996) Time-energy optimal control of articulated systems with geometric path constraints. Journal of Dynamic Systems, Measurement, and Control 118(1): 139–143.

59.

Soueres

Boissonnat

(1998) Optimal trajectories for nonholonomic mobile robots. In: Robot Motion Planning and Control. Berlin, Germany: Springer, pp. 93–170.

60.

Soueres

Laumond

(1996) Shortest paths synthesis for a car-like robot. IEEE Transactions on Automatic Control 41(5): 672–688.

61.

Spain

(2007) Analytical Conics. Chelmsford, MA, USA: Courier Corporation.

62.

Sussmann

Tang

(1991) Shortest paths for the reeds-shepp car: a worked out example of the use of geometric techniques in nonlinear optimal control. Rutgers Center for Systems and Control Technical Report 10: 1–71.

63.

Tokekar

Karnad

Isler

(2014) Energy-optimal trajectory planning for car-like robots. Autonomous Robots 37(3): 279–300.

64.

Verscheure

Demeulenaere

Swevers

, et al. (2008) Time-energy optimal path tracking for robots: a numerically efficient optimization approach. In: 2008 10th IEEE International Workshop on Advanced Motion Control. Trento, Italy: IEEE, pp. 727–732.

65.

Wang

Balkcom

(2012) Analytical time-optimal trajectories for an omni-directional vehicle. In: 2012 IEEE International Conference on Robotics and Automation. Saint Paul, MN, USA: IEEE, pp. 4519–4524.

66.

Wang

Balkcom

(2020) Time-optimal motion of spatial Dubins systems. Algorithmic Foundations of Robotics XIII: Proceedings of the 13th Workshop on the Algorithmic Foundations of Robotics, 529–544.

67.

Yamamoto

Iwamura

Mohri

(1998) Time-optimal motion planning of skid-steer mobile robots in the presence of obstacles. In: Proceedings. 1998 IEEE/RSJ international conference on intelligent robots and systems. Innovations in theory, practice and applications (cat. No. 98CH36190). Victoria, BC, Canada: IEEE, volume 1, pp. 32–37.

68.

Zhang

Cassandras

(2019) Joint time and energy-optimal control of connected automated vehicles at signal-free intersections with speed-dependent safety guarantees. arXiv preprint arXiv:1903.05692.

Energy-optimal trajectories for skid-steer rovers

Abstract

Keywords

1. Introduction

1.1. Sample-based and local planning methods

1.2. Sample-based algorithms for global planning method

1.2.1. LPM for different vehicles

1.2.2. Hybrid approach

1.3. Energy and time optimization equivalency

1.4. Contributions

2. Problem statement

2.1. Problem

2.2. Existence theorem

2.3. Power modeling

2.3.1. Skid-steer rovers kinematics

2.3.2. Power model

3. Equivalency theorem

3. Extremal trajectories for the equivalent time-optimal problem

3.1. Pontryagin’s minimum principle for time-optimal problems

3.2. Time-optimal control inputs

3.3. Hamiltonian level sets

3.3.1. Hamiltonian level sets for c 1 = 0 & c 2 > 0

3.4. Restricting the number of periods for the obtained paths

3.5. Extremal path structures

4. Numerical scenario

4.1. Length of straight lines in generic TST paths

4.2. Particular scenario and steps to find the optimal paths

4.3. Generating extremals and finding the feasibility regions

4.4. Map of the optimal paths

4.4.1. More discussion on the map

4.4.2. Expectation/Prediction about other scenarios

5. Experimental tests

6. Conclusions and future work

6.1. Conclusions

6.2. Future work

Footnotes

Acknowledgements

Declaration of conflicting interests

Funding

ORCID iDs

Notes

Appendix

References

3.3.1. Hamiltonian level sets for c₁ = 0 & c₂ > 0