Curves of Minimax Curvature

We are interested in finding a curve $z:[0,t_{f}]\longrightarrow{\rm{I\ \kern-5.39993ptR}}^{2}$ which minimises the almost everywhere (a.e.) pointwise maximum curvature of $z(t)$, i.e. the $L^{\infty}$-norm of the curvature, among all curves having fixed length; prescribed endpoints $z_{0}$ and $z_{f}$ at $0$ and $t_{f}$ respectively; and prescribed tangents $v_{0}$ and $v_{f}$ at the endpoints. Since the curvature is independent of parametrisation we will consider only curves which are parametrised with respect to arc length so that the curvature is $\|\ddot{z}(t)\|$, and the parameter $t_{f}$ is the length of the whole curve (and therefore $t_{f}$ is fixed). The problem can then be posed as

$$\mbox{(P)}\left\{\begin{array}[]{rl}\displaystyle\min_{z(\cdot)}&\ \displaystyle\max_{t\in[0,t_{f}]}\|\ddot{z}(t)\|\\[11.38109pt] \mbox{s.t.}&\ z(0)=z_{0}\,,\ z(t_{f})=z_{f}\,,\\[5.69054pt] &\ \dot{z}(0)=v_{0}\,,\ \dot{z}(t_{f})=v_{f}\,,\\[5.69054pt] &\ \|\dot{z}(t)\|=1\,,\mbox{ for a.e. }t\in[0,t_{f}]\,,\end{array}\right.$$

where $\dot{z}=dz/dt$, $\ddot{z}=d^{2}z/dt^{2}$, $\|\cdot\|$ is the Euclidean norm, and $v_{0}$ and $v_{f}$ are given such that $\|v_{0}\|=\|v_{f}\|=1$.

If the $L^{\infty}$-norm is replaced by the squared $L^{2}$-norm, of $\ddot{z}$, namely $\int_{0}^{t_{f}}\|\ddot{z}(t)\|^{2}\,dt$, then critical curves for Problem (P) become the celebrated (fixed-length) Euler’s elastica. The $L^{p}$-norm generalizations of the Euler elastica problem for $p\in[1,\infty)$, where $\int_{0}^{t_{f}}\|\ddot{z}(t)\|^{2}\,dt$ is replaced by $\int_{0}^{t_{f}}\|\ddot{z}(t)\|^{p}\,dt$, have been referred to as the $p$-elastica problem in the literature—see [9]. Similarly, potential minimisers of Problem (P) have been called the $\infty$-elastica in [20]. Here we refer to (P) as the problem of finding curves of minimum pointwise-maximum curvature, or simply curves of minimax curvature, because it is more descriptive and we are ultimately focused on finding global minimisers.

Another problem related to (P) is the Markov–Dubins problem, in which one is to minimize this time the (free) length $t_{f}$ of the curve of interest subject to a fixed bound $a$ imposed on the curvature, while the remaining constraints appearing in (P) are kept in place. This problem was first proposed and some instances studied by Andrey Markov in 1889 [17] (also see [16]) but fully solved by Lester Dubins only in 1957 [5]. Dubins’ result characterizes minimum-length solutions in terms of concatenations of straight lines and circular arcs: Let a straight line segment be denoted by an $S$ and a circular arc of the maximum allowed curvature $a$ (or, turning radius $1/a$) by a $C$, then the shortest curve is a concatenation of type $CCC$, or of type $CSC$, or a subset thereof. See [10] and the references therein for a literature survey of the Markov–Dubins problem.

The first published work on Problem (P) appears to be that of Moser [20] where it is studied for curves in $\mathbb{R}^{n}$, followed by the extension to Riemannian manifolds in [7]. In [20] $\infty$-elastica are defined as minimisers of the sum of maximum curvature and a penalty term which is a kind of $L^{2}$-distance between curves. In order to obtain differential equations which characterise $\infty$-elastica, Moser studies the Euler–Lagrange equations for the sum of $p$-elastic energy with the same penalty term, in the limit $p\to\infty$. From the differential equations Moser obtains a classification of $\infty$-elastica as concatenations of circular arcs and straight lines, similar to the solutions of the Markov-Dubins problem, except that $\infty$-elastica can contain more than three pieces, and closed loops are allowed. If we denote by $O$ a full circle with the maximum curvature, and $C,S$ as before, the conclusion is that $\infty$-elastica can be of type $CSOSOC$, perhaps with more or less loops and straight line segments, or of type $CC\ldots C$ with any number of $C$ segments and such that the interior segments have equal length and alternating orientation.

The present work takes a fundamentally different approach to that of Moser: we show that by using the same technique applied in [15], Problem (P) can be reformulated as an optimal control problem without any approximation by $p$-elastic energy. As usual, the maximum principle then provides us with necessary conditions for optimality in the form of differential equations for the state and costate variables, and constraints on the control. A careful analysis of these conditions – in particular of the phase portrait of the switching function, which is very similar to the analysis of the Markov–Dubins problem in [10, 11] – allows us to draw similar conclusions to Moser’s about which types of curves can be optimal.

The necessary conditions obtained from the maximum principle are then combined with a series of geometric arguments, such as Lemma 21 showing that a curve of type $CCCC$ cannot be optimal because it can be deformed into a feasible curve with the same maximum curvature, but which does not satisfy the necessary conditions. These observations lead to our main result, a refined classification in Theorem 22: any solution to Problem (P) is of type $CCC$, or $CSC$, or $COC$, or $SOS$, or a subset thereof, with all circular arcs having the same maximum possible radius (or minimum possible maximum curvature). So we have that, just like in the Markov–Dubins problem, solutions of problem (P) cannot consist of more than three segments. However, unlike in the Markov–Dubins problem, under specific conditions (Propositions 23 and 25), they can contain closed circular loops.

Since Problem (P) is related to the Markov–Dubins problem by interchange of constraint and cost, it is perhaps not surprising that the solutions are so similar. Indeed, a relationship between solutions of the two problems was established in [20, Proposition 5]: a solution of the Markov–Dubins problem is a solution to Problem (P). In Theorem 5 we give an alternative proof of this fact in terms of the optimal control formulation, and then demonstrate that the converse does not hold (Remark 6).

We devise a numerical method, which, using the classification of the solution curves stated in Theorem 22 and switching time optimization techniques, reduces the infinite-dimensional optimization problem (P) to a finite-dimensional optimization problem (Ps) with just six variables. We carry out extensive numerical experiments. We especially focus on solutions containing a loop to exemplify the specific results involving loops, as well as gain insights about those instances for which no specific results are available.

The paper is organized as follows. In Section 2, we reformulate Problem (P) as an optimal control problem. In Section 3, we write down the maximum principle for the optimal control problem. In Section 4, we classify the types of solutions for Problem (P) and provide the main theoretical result as Theorem 22. In Section 5, we develop a numerical method for solving Problem (P), and provide example applications and numerical solutions using off-the-shelf optimization software, so as to illustrate the theoretical results. Finally, in Section 6, concluding remarks and possible directions for future work are provided.

Obviously, if the distance separating $z_{0}$ and $z_{f}$ is more than the fixed length $t_{f}$ then Problem (P) has no solution. In fact, with $t_{f}=\|z_{0}-z_{f}\|$, a feasible solution may still not exist. Consider the points $z_{0}=(0,0)$ and $z_{f}=(1,0)$. With $t_{f}=1$, unless $v_{0}=v_{f}=(1,0)$, there exists no feasible curve between $z_{0}$ and $z_{f}$. Therefore we make the following assumption.

Before reformulating (P) as an optimal control problem and classifying the minimisers, we first address the existence of solutions.

Since the proof of Proposition 2 is somewhat long and does not contribute directly to our main result, we defer it until Section 4.1.

Problem (P) is nonsmooth because of the $\max$ operator appearing in its objective functional. On the other hand, Problem (P) can be transformed into a smooth variational problem by using a standard technique from nonlinear programming, in the same way it was also done in [15]:

$$\mbox{(P1)}\left\{\begin{array}[]{rl}\displaystyle\min_{a,z(\cdot)}&\ a\\[5.69054pt] \mbox{s.t.}&\ z(0)=z_{0}\,,\ z(t_{f})=z_{f}\,,\\[5.69054pt] &\ \dot{z}(0)=v_{0}\,,\ \dot{z}(t_{f})=v_{f}\,,\\[5.69054pt] &\ \|\ddot{z}(t)\|\leq a\,,\ \ \ \|\dot{z}(t)\|=1\,,\mbox{ for a.e. }t\in[0,t_{f}]\,,\end{array}\right.$$

where the bound $a\geq 0$ is a new optimization variable of the problem.

Problem (P) can equivalently be cast as an optimal control problem as follows. Let$z(t):=(x(t),y(t))\in{\rm{I\ \kern-5.39993ptR}}^{2}$, with $\dot{x}(t):=\cos\theta(t)$ and $\dot{y}(t):=\sin\theta(t)$, where $\theta(t)$ is the angle the velocity vector $\dot{z}(t)$ of the curve $z(t)$ makes with the horizontal. These definitions verify that $\|\dot{z}(t)\|=1$. Moreover,

$$\|\ddot{z}\|^{2}=\ddot{x}^{2}+\ddot{y}^{2}=\dot{\theta}^{2}\,.$$

Therefore, $|\dot{\theta}(t)|$ is nothing but the curvature. In fact, $\dot{\theta}(t)$ itself, which can be positive or negative, is referred to as the signed curvature. For example, consider a vehicle travelling along a circular path. If $\dot{\theta}(t)>0$ then the vehicle travels in the counter-clockwise direction, i.e., it turns left, and if $\dot{\theta}(t)<0$ then the vehicle travels in the clockwise direction, i.e., it turns right. If $\dot{\theta}(t)=0$ then the vehicle travels along a straight line.

Suppose that the directions at the points $z_{0}$ and $z_{f}$ are denoted by the angles $\theta_{0}$ and $\theta_{f}$, respectively. The curvature minimizing problem (P1), or equivalently Problem (P), can then be re-written as a (parametric) optimal control problem, where the objective functional is the maximum curvature $a$ (the parameter), and $x$, $y$ and $\theta$ are the state variables and $u$ is the control variable :

$$\mbox{(Pc)}\left\{\begin{array}[]{rll}\displaystyle\min_{a,u(\cdot)}&\ \displaystyle a&\\[5.69054pt] \mbox{s.t.}&\ \dot{x}(t)=\cos\theta(t)\,,&x(0)=x_{0}\,,\ x(t_{f})=x_{f}\,,\\[5.69054pt] &\ \dot{y}(t)=\sin\theta(t)\,,&y(0)=y_{0}\,,\ y(t_{f})=y_{f}\,,\\[5.69054pt] &\ \dot{\theta}(t)=u(t)\,,&\theta(0)=\theta_{0}\,,\ \theta(t_{f})=\theta_{f}\,,\\[5.69054pt] &&|u(t)|\leq a\,,\mbox{ for a.e. }t\in[0,t_{f}]\,.\end{array}\right.$$

Recall by Remark 3 that the solution to Problem (P), equivalently (Pc), with $a=0$ constitutes a special configuration of the given oriented endpoints: the angle $\theta(t)=\theta_{0}=\theta_{f}=\arctan((y_{f}-y_{0})/(x_{f}-x_{0}))$ for all $t\in[0,t_{f}]$, and so the curve $z(t)$ is a straight line from $(x_{0},y_{0})$ to $(x_{f},y_{f})$.

Note that with the unit speed constraint $\|\dot{z}(t)\|=1$ in Problem (P) the solution curve $z(t)$ is parametrized with respect to its length. Therefore the terminal time $t_{f}$ is nothing but the length of the curve $z(t)$. When the maximum allowed curvature $a$ is fixed, the length $t_{f}$ is allowed to vary, and the objective functional $a$ in Problem (Pc) is replaced by $t_{f}$, Problem (Pc) becomes the celebrated Markov–Dubins problem [5, 16, 17], where one looks for the shortest curve between the oriented points $(x_{0},y_{0},\theta_{0})$ and $(x_{f},y_{f},\theta_{f})$, with a prescribed bound $a$ on its curvature:

$$\mbox{(MD)}\left\{\begin{array}[]{rll}\displaystyle\min_{t_{f},u(\cdot)}&\ \displaystyle t_{f}&\\[5.69054pt] \mbox{s.t.}&\mbox{Constraints in Problem~{}(Pc) with $a$ fixed}.\end{array}\right.$$

Let a straight line segment be denoted by an $S$ and a circular arc segment of curvature $a$ (or, turning radius $1/a$) by a $C$. Dubins’ result is stated in terms of concatenations of type $S$ and type $C$ curve segments in the following theorem.

In the following theorem, we establish a relationship between Problems (MD) and (Pc). In fact, the proof of the theorem utilizes Theorem 4 as well as the following simple observation: Problem (MD) minimizes the length $t_{f}$ while the bound $a$ on the curvature is fixed, and Problem (Pc) minimizes $a$ while $t_{f}$ is kept fixed.

Proof. Suppose that, with $a=a^{*}$ fixed, the solution of Problem (MD) yields $t_{f}^{*}$. By Theorem 4, either $|\dot{\theta}^{*}(t)|=a^{*}$ or $\dot{\theta}^{*}(t)=0$, a.e. $t\in[0,t_{f}^{*}]$; in other words, with the optimal length $t_{f}^{*}$, the optimal angular velocity $\dot{\theta}^{*}$ has to satisfy

$$|\dot{\theta}^{*}(t)|\notin(0,a^{*})\,,\ \ \mbox{a.e.}\ \ t\in[0,t_{f}^{*}].$$

(1)

Now suppose that, with $t_{f}=t_{f}^{*}$ fixed, solution of Problem (Pc) yields $\widehat{a}$. Obviously, $0\leq\widehat{a}\leq a^{*}$. We can obtain a contradiction for the case when $\widehat{a}<a^{*}$ as follows.

1. (i)

   $\widehat{a}\neq 0$ : Since this solution of Problem (Pc) satisfies the constraints of Problem (MD) with $a=a^{*}$, and has the optimal length $t_{f}^{*}$ for Problem (MD), it must also be a solution of (MD). Then it must satisfy (1). However, since it is a solution of Problem (Pc) it also satisfies $0\leq|\dot{\theta}(t)|\leq\widehat{a}$ for a.e. $t\in[0,t_{f}^{*}]$, and so we cannot have $\widehat{a}<a^{*}$ unless $\widehat{a}=0$.

2. (ii)

   $\widehat{a}=0$ : In this case, we have the trivial case $\theta_{0}=\theta_{f}=\arctan((y_{f}-y_{0})/(x_{f}-x_{0}))$, which yields $\dot{\theta}(t)=0$, a.e. $t\in[0,t_{f}^{*}]$, as the solution of both Problems (Pc) and (MD), with $\widehat{a}=a^{*}=0$.

Therefore, with $t_{f}=t_{f}^{*}$ fixed, the solution of Problem (Pc) yields $\widehat{a}=a^{*}$. So, if the pair $(t_{f}^{*},a^{*})$ solves Problem (MD), then it also solves Problem (Pc). $\Box$

In this section, we study the optimality conditions for a re-formulation of Problem (Pc) in a classical form. Let us redefine the control variable $u$ such that $\alpha(t)\,v(t):=\dot{\theta}(t)$, where $\alpha(t):=a$ and so $\dot{\alpha}(t):=0$, for a.e. $t\in[0,t_{f}]$. Problem (Pc), or equivalently Problem (P), can then be re-written as the following optimal control problem:

$$\mbox{(OC)}\left\{\begin{array}[]{rll}\displaystyle\min_{v(\cdot)}&\ \displaystyle\int_{0}^{t_{f}}\alpha(t)\,dt&\\[11.38109pt] \mbox{s.t.}&\ \dot{x}(t)=\cos\theta(t)\,,&x(0)=x_{0}\,,\ x(t_{f})=x_{f}\,,\\[5.69054pt] &\ \dot{y}(t)=\sin\theta(t)\,,&y(0)=y_{0}\,,\ y(t_{f})=y_{f}\,,\\[5.69054pt] &\ \dot{\theta}(t)=\alpha(t)\,v(t)\,,&\theta(0)=\theta_{0}\,,\ \theta(t_{f})=\theta_{f}\,,\ |v(t)|\leq 1\,,\mbox{ for a.e. }t\in[0,t_{f}]\,,\\[5.69054pt] &\ \dot{\alpha}(t)=0\,,&\mbox{for a.e. }t\in[0,t_{f}]\,.\end{array}\right.$$

Define the Hamiltonian function for Problem (OC) as

$$H(x,y,\theta,\alpha,\lambda_{0},\lambda_{1},\lambda_{2},\lambda_{3},\lambda_{4},v):=\lambda_{0}\,\alpha+\lambda_{1}\,\cos\theta+\lambda_{2}\,\sin\theta+\lambda_{3}\,\alpha\,v+\lambda_{4}\cdot 0\,,$$

(2)

where $\lambda_{0}\geq 0$ is a scalar (multiplier) parameter and $\lambda_{i}:[0,t_{f}]\to{\rm{I\ \kern-5.39993ptR}}$, $i=1,2,3,4$, are the adjoint (or costate) variables. Let

$$H[t]:=H(x(t),y(t),\theta(t),\alpha(t),\lambda_{0},\lambda_{1}(t),\lambda_{2}(t),\lambda_{3}(t),\lambda_{4}(t),v(t))\,.$$

The adjoint variables are required to satisfy

	$\displaystyle\dot{\lambda}_{1}(t):=-H_{x}[t]=0\,,$		(3)
	$\displaystyle\dot{\lambda}_{2}(t):=-H_{y}[t]=0\,,$		(4)
	$\displaystyle\dot{\lambda}_{3}(t):=-H_{\theta}[t]=\lambda_{1}(t)\,\sin\theta(t)-\lambda_{2}(t)\,\cos\theta(t)\,,$		(5)
	$\displaystyle\dot{\lambda}_{4}(t):=-H_{\alpha}[t]=-\lambda_{0}-\lambda_{3}(t)\,v(t)\,,\ \ \lambda_{4}(0)=0\,,\ \lambda_{4}(t_{f})=0\,,$		(6)

where $H_{x}=\partial H/\partial x$, etc. By these definitions, the state and adjoint variables verify a Hamiltonian system in that, in addition to (3)–(6), one has $\dot{x}(t)=H_{\lambda_{1}}[t]$, $\dot{y}(t)=H_{\lambda_{2}}[t]$, $\dot{\theta}(t)=H_{\lambda_{3}}[t]$ and $\dot{\alpha}(t)=H_{\lambda_{4}}[t]$.

Note that (3)–(4) imply that $\lambda_{1}(t)=\overline{\lambda}_{1}$ and $\lambda_{2}(t)=\overline{\lambda}_{2}$ for all $t\in[0,t_{f}]$, where $\overline{\lambda}_{1}$ and $\overline{\lambda}_{2}$ are constants. Define new constants

$$\rho:=\sqrt{\overline{\lambda}_{1}^{2}+\overline{\lambda}_{2}^{2}}\,,\qquad\tan\phi:=\frac{\overline{\lambda}_{2}}{\overline{\lambda}_{1}}\,.$$

(7)

Then (2) and (5) can respectively be re-written as

$$H[t]=a\,\lambda_{0}+\rho\,\cos(\theta(t)-\phi)+a\,\lambda_{3}(t)\,v(t)\,,$$

(8)

where we have also used $\alpha(t)=a$, for all $t\in[0,t_{f}]$, and

$$\dot{\lambda}_{3}(t)=\rho\,\sin(\theta(t)-\phi)\,.$$

(9)

Since $H$ does not depend on $t$ explicitly,

$$H[t]=h\,,$$

(10)

where $h$ is some real constant.

The maximum principle [21, Theorem 1] for Problem (OC) can simply be stated as follows. Suppose that $x,y,\theta,\alpha\in W^{1,\infty}(0,t_{f};{\rm{I\ \kern-5.39993ptR}})$ and $v\in L^{\infty}(0,t_{f};{\rm{I\ \kern-5.39993ptR}})$ solve Problem (OC). Then there exist a number $\lambda_{0}\geq 0$ and functions $\lambda_{i}\in W^{1,\infty}(0,t_{f};{\rm{I\ \kern-5.39993ptR}})$, $i=1,2,3,4$, such that $\lambda(t):=(\lambda_{0},\lambda_{1}(t),\lambda_{2}(t),\lambda_{3}(t),\lambda_{4}(t))\neq\bf 0$, for every $t\in[0,t_{f}]$, and, in addition to the state differential equations and other constraints given in Problem (OC) and the adjoint differential equations (3)–(4), (6) and (9), the following condition holds:

$$u(t)\in\operatorname*{argmin}_{|w|\leq 1}H(x(t),y(t),\theta(t),\alpha(t),\lambda_{0},\lambda_{1}(t),\lambda_{2}(t),\lambda_{3}(t),\lambda_{4}(t),w)\,,$$

(11)

Using the definition in (2), (11) can be concisely written as

$$v(t)\in\operatorname*{argmin}_{|w|\leq 1}\ a\,\lambda_{3}(t)\,w\,,$$

(12)

which yields the optimal control as

$$v(t)=\left\{\begin{array}[]{ll}\ \ 1\,,&\mbox{if}\ a\,\lambda_{3}(t)<0\,,\\[8.53581pt] -1\,,&\mbox{if}\ a\,\lambda_{3}(t)>0\,,\\[8.53581pt] \mbox{undetermined}\,,&\mbox{if}\ a\,\lambda_{3}(t)=0\,.\end{array}\right.$$

(13)

Furthermore, (8) and (10) give

$$a\,\lambda_{3}(t)\,v(t)+\rho\,\cos(\theta(t)-\phi)+a\,\lambda_{0}=:h\,.$$

(14)

The control $v(t)$ to be chosen for the case when $a\,\lambda_{3}(t)=0$ for a.e. $t\in[\zeta_{1},\zeta_{2}]\subset[0,t_{f}]$ is referred to as singular control, because (12) does not yield any further information. On the other hand, when $a\,\lambda_{3}(t)\neq 0$ for a.e. $t\in[0,t_{f}]$ (which implies that $a>0$), i.e., it is possible to have $\lambda_{3}(t)=0$ only for isolated values of $t$, the control $v(t)$ is said to be nonsingular. It should be noted that, if $\lambda_{3}(\tau)=0$ only at an isolated point $\tau$, the optimal control at this isolated point can be chosen as $v(\tau)=-1$ or $v(\tau)=1$, conveniently. Therefore, if the control $v(t)$ is nonsingular, it will take on either the value $-1$ or $1$, the bounds on the control variable. In this case, the control $v(t)$ is referred to as bang–bang. Since the sign of $\lambda_{3}(t)$ determines the value of the optimal control $v(t)$, $\lambda_{3}$ is referred to as the switching function.

Proof. Suppose that the optimal control $v(t)$ is singular, i.e., $a\,\lambda_{3}(t)=0$, for a.e. $t\in[\zeta_{1},\zeta_{2}]\subset[0,t_{f}]$. If $a=0$, then $\dot{\theta}(t)=0$ and so $\theta(t)$ is constant. If $a>0$ then $\dot{\lambda}_{3}(t)=0$ for a.e. $t\in[\zeta_{1},\zeta_{2}]\subset[0,t_{f}]$. In other words, from (9), $\sin(\theta(t)-\phi)=0$, which implies that $\theta(t)$ is constant, i.e., $\dot{\theta}(t)=u(t)=0$, for all $t\in[\zeta_{1},\zeta_{2}]$. $\Box$

By Lemma 7, we have established that the only straight-line solution of Problem (OC) is a singular control solution. In the rest of this section we will assume that $a>0$, as there is nothing more to say for the simple case of $a=0$, as far as the maximum principle is concerned.

The problems that yield a solution with $\lambda_{0}=0$ are referred to as abnormal, so are their solutions, in the optimal control theory literature, for which the conditions obtained from the maximum principle are independent of the objective functional $\int_{0}^{t_{f}}\alpha(t)\,dt$ in Problem (OC) and therefore not sufficiently informative. The problems that yield $\lambda_{0}>0$, and their solutions, are referred to as normal. Lemma 10 below states that we can rule out abnormality for Problem (OC).

Proof. For contradiction purposes, suppose that $\lambda_{0}=0$ and recall the assumption that $a>0$. Then, from (6) and (15), $\dot{\lambda}_{4}(t)=|\lambda_{3}(t)|\geq 0$, for every $t\in[0,t_{f}]$, which, along with the boundary conditions $\lambda_{4}(0)=\lambda_{4}(t_{f})=0$, implies that $\lambda_{4}(t)=\lambda_{3}(t)=0$ for every $t\in[0,t_{f}]$, giving rise to a totally singular solution. This in turn implies that $v(t)=0$ and so $\dot{\theta}(t)=0$, for every $t\in[0,t_{f}]$, and thus $a=0$, which is a contradiction. Therefore $\lambda_{0}>0$. Then, without loss of generality, one can set $\lambda_{0}=1$. $\Box$

Proof. Suppose the optimal control $u(t)$ is singular over $[\zeta_{1},\zeta_{2}]\subset[0,t_{f}]$. Then $\lambda_{3}(t)=\dot{\lambda}_{3}(t)=0$ for a.e. $t\in[\zeta_{1},\zeta_{2}]$. From (9), $\sin(\theta(t)-\phi)=0$, which implies that $\cos(\theta(t)-\phi)=1$ or $-1$. Then, substituting $\lambda_{3}(t)=0$, $\cos(\theta(t)-\phi)=\pm 1$, and (from Lemma 10) $\lambda_{0}=1$, into (14), one gets $\rho=\mp(a-h)\geq 0$.

Next we show that $\rho\neq 0$. For contradiction purposes, suppose that $\rho=0$, i.e., $\lambda_{1}(t)=\lambda_{2}(t)=0$, for every $t\in[0,t_{f}]$, and recall the assumption that $a>0$. Then $\dot{\lambda}_{3}(t)=0$ and so $\lambda_{3}(t)=0$, for every $t\in[0,t_{f}]$. Now from (6), we get $\dot{\lambda}_{4}(t)=-1$, for every $t\in[0,t_{f}]$, which does not have a solution with $\lambda_{4}(0)=\lambda_{4}(t_{f})=0$. $\Box$

Proof. From (9),

$$\dot{\lambda}_{3}^{2}(t)=\rho^{2}\,\sin^{2}(\theta(t)-\phi)=\rho^{2}-\rho^{2}\,\cos^{2}(\theta(t)-\phi)\,.$$

(17)

Using $v(t)=-\operatorname*{sgn}(\lambda_{3}(t))$ and $\lambda_{0}=1$ in (14), one gets

$$\rho\,\cos(\theta(t)-\phi)=a\,|\lambda_{3}(t)|-a+h\,.$$

Substituting this into the right-hand side of (17) and rearranging give (16). $\Box$

In the rest of the paper, we will at times not show dependence of variables on $t$ for clarity of presentation.

Proof. Substitution of $v(t)=-\operatorname*{sgn}(\lambda_{3}(t))$ and $\lambda_{0}=1$ into (14) and re-arranging yield the required expression. $\Box$

Proof. (a) Suppose that $\rho=0$. Then, from Lemma 15, $|\lambda_{3}(t)|=(a-h)/a$, $\lambda_{3}(t)$ is a nonzero constant, i.e., $v(t)$ is either $1$ or $-1$, for all $t\in[0,t_{f}]$.
(b) Suppose that $0<\rho\neq|a-h|$. Then, the contrapositive of Lemma 12 states that the optimal control is not singular, i.e., bang–bang. $\Box$

Denote a straight line segment by $S$ and a circular arc by $C$, so that a trajectory satisfying the necessary conditions can be described as being of type $C,S,CSC,\ldots$ etc. In [10, Lemma 6] the analog of Figure 1 is used to conclude that an optimal path for (MD) contains a straight line segment $S$ then it must be of type $CSC,CS,SC,$ or $S$. Part of the argument is that a trajectory containing e.g. $SCS$ must traverse a full circle and is therefore not optimal because the objective in the Markov–Dubins problem is to minimize length.

For Problem (OC) we can also conclude from Figure 1 and (9) that $SCS$ must traverse a full circle, but it is no longer obvious that such a path cannot be optimal. In fact we will show that in some cases it is optimal ( Proposition 23, Proposition 25) while in others it is not (Corollary 20). It will be helpful to introduce the notation $O$ to represent a full circle once covered, and reserve $C$ for circular arcs which are not closed.

Proof. If the sub-path is a line then it is optimal. Assume it is not a line, and suppose it is not optimal. Then there exists a path satisfying the inherited constraints and having $0<a<a^{*}$, meaning it contains circular arcs with lower curvature than those in $\mathbf{x}^{*}$. We can insert it between $\mathbf{x}^{*}([0,t_{1}])$ and $\mathbf{x}^{*}([t_{2},t_{f}])$ to obtain a new path $\tilde{\mathbf{x}}(t)$. Now either $\mathbf{x}^{*}$ and $\tilde{\mathbf{x}}$ have the same maximum curvature, or the maximum curvature of $\tilde{\mathbf{x}}$ is smaller. The latter contradicts our assumption that $\mathbf{x}^{*}$ is optimal. If they have the same maximum curvature, then $\tilde{\mathbf{x}}$ contains at least one circular arc with curvature $a^{*}$ and at least one circular arc with curvature $a$, and so it does not satisfy the necessary conditions for optimality (specifically (13)). It then follows that $a^{*}$ cannot be a minimum, again contradicting our assumption on $\mathbf{x}$. $\Box$

Proof. Since at least one of $X$ and $Y$ is $S$ or $O$, in order for the path to be optimal it must have switching function on the (red) dashed ellipses in Figure 1. But since the middle $C$ in $XCY$ does not traverse a full loop it is impossible for the switching function to traverse a full ellipse and switch to $S$ or to $C$ or $O$ with the opposite orientation. (Note that we are assuming that, for example, in $CCS$ the two arcs have opposite orientation, otherwise this path would be written as $CS$ or $OCS$). In the case of $CCO$ (similarly $OCC$) this is perhaps not immediately obvious because the middle $C$ and the $O$ may have the same orientation, and then the switching function would not need to return to the origin of the phase portrait in Figure 1. However, we can reflect the loop about the endpoint with no change in maximum curvature, and the resulting path again is not compatible with the necessary conditions on the switching function. $\Box$