Chapter 17: Parallel Parking a Car

Our first example of Lie Theoretic Systems Theory will be how we parallel park a car. We shall use this to illustrate Theorem 13.4.

Overview

A car cannot drive out of a tight parallel park as the transformations that its engine and steering mechanism can impart do not include a side slide: we can drive forwards and backwards with or without a small curvature (steering) imparted to the car’s path. However, an analysis of the available manoeuvres shows that finite sequences of them can realise a side slide and get a car out of an arbitrarily tight parallel park, in the sense that if parking space’s length is $1+\epsilon$ times that of the car, for any $\epsilon>0$, then one can still drive the car out of the park without bumping those around it.

More generally, the set of all possible motions of a robotic system given a basic set of restricted transformations can be studied defining the basic motions by the corresponding Lie algebra members and then computing the smallest Lie algebra $\h$ containing these. A library of finite sequences of basic motions realising transformations of the form $U_j(\tau)=e^{\tau,\hat{X}_j}$ for the basis members $\hat{X}_j$ of the smallest Lie algebra members $\h$ can then be calculated using a constructive version of Theorem 13.4 even when the basis members cannot be realised by one basic motion of the robot. Such a library can then be used to guide the robot through space around things in its path using a higher dimensional analogue of the analysis in the parallel parking problem described below. Robotic system control theory has many examples of this kind of “reachable set” problem; see for example [Brockett] or [Selig].

Car Parking

Figure 17.1: Definitions for the configuration space and transformation group for parallel parking of an Ackermann-Steering car

We now look at a simplified car steering model as in Figure 17.1 following [Nelson] or [Burke]. There is a retelling of this problem in [Rossmann]. There is also at least one blog on this topic [Siegel]. A few background, non-mathematical comments are in order. Several of the references speculate the results of the analysis to follow is independent of the steering design details. This assertion is patently wrong: the model depends critically on the steering mechanism; to understand this, imagine a car with an exotic steering configuration where all four wheels were driven and could swivel independently like casters on a shopping trolley. To get out of an arbitrarily tight carpark, such a vehicle needs only to swivel its wheels to point at right angles to its current heading and drive sideways in a straight line; such configurations are indeed often used in industrial robotics. The design [Nelson], [Burke], [Rossmann] and [Siegel] talk about is Ackermann Steering or its equivalent. In such a steering system all wheels roll without slipping and with their planes parallel to the tangent vector to the path they follow. This means that a lines drawn normal to the planes of each wheel must all meet at a common point; the point $C$ in Figure 17.1. Thus the car body’s motion is a pure rotation about this common meeting point $C$. In the diagram in [Nelson] or [Rossmann] which I have reproduced below in Figure 17.2, this common meeting point $C$ arises owing to the forward wheels mounting on a rigid axle that can be rotated, through the steering angle $\theta$ to set the car’s heading. In Ackermann steering proper (Figure 17.1), there are two different steering angles $\theta_1,\, \theta_2$, one for each of the two forward wheels. A system of linkages ensures that the two wheels always point so that axes normal to their planes intersect the axis defined by the hinder axle at the common point $C$. The eponymous Rudolf Ackermann (1764–1834) was the man who filed the English patent (1818) on behalf of the inventor Georg Lankensperger (1779 – 1847). The Wikipedia page on Ackermann steering states that Erasmus Darwin probably came up with the idea independently in 1758, citing [King-Hele] (who reconstucts the history quite convincingly) in backing this assertion up. But all this is still very much an approximation; depending on the application, the steering of real vehicles is wilfully set to be non-Ackermann to some degree; the elastic warping of the rubber tyres in forcing a wheel’s rotation plane to deviate from its heading greatly increases the steering force. Indeed, there is always some slipping, and the design of steering is a tradeoff between the steering effectiveness and the lifetime of the tyres, which are swiftly worn by any slipping. Heavy vehicle steering is Ackermann at low steering angles to limit wear in normal steering, but highly non Ackermann for low speed nimbleness and manoeuvrability (the destruction wrought on any road where a laden concrete mixer has been working or at busy t-intersections where many semitrailers make sharp turns bears witness to this statement). Racing cars are “anti-Ackermann”, their wheels always in a state of very high slip to beget high tyre temperatures through the rubber’s ever cyclic bending state and thus extreme grip at the expense of very limited tyre lifetime. Even your own car’s wheels are always in some slip as you can experimentally prove to yourself by taking your car to one of those indoor carparks where the concrete is very smooth, ideally painted (as in many undercover shopping centre carparks). Open your driver’s window and drive as slowly as you can in a tight bend. You’ll find that you can hear a loud, squeaky sound from the forward end tyres no matter how slowly you go as the rubber is deformed (and undergoes little skids) whilst it passes through the region in contact with the ground. Now, if you’re reading this you’re likely to be a geeky type like me, so for the good of your social skills you need to be aware how truly outrightly weird this scene will seem to any onlooker, so take your children with you in the back seat and take due heed of the hilarious mixture of bewilderedness, embarassment, bewutheredness and “what the **** is Papa doing?!” on your childrens faces as they watch you with you with your head out of one window straining to be sure you can confirm the source of the noise, driving at the same time and with the vegetables and groceries sticking crazily out through the other open window. If you’re really thorough and insist on unambiguous confirmation, you will at this point be sitting on the window sill, one hand on the steering wheel, no feet on the pedals and with most of your body leaning out of the window.

Nelson's Car

Figure 17.2: Car Configuration Space Definition in [Nelson] (reproduced from that reference)

So, now back to our Lie theory and our highly, as should be clear now, idealised model. Our car’s state is defined by (i) the position of the midpoint on the hinder axle between the two hinder wheels and (ii) the car’s heading, which is the direction orthogonal to the hinder axle. Unlike the approach in [Nelson] and [Burke], I prefer not to think of the details of the steering and its angles and think of the two steering angles as being part of the “control force” below and not part of the car’s state. That is, I forget about the forward wheels and instead simply assert that any steering manoeuvre is summarised by one lone parameter $\kappa = r^{-1}$, the curvature of the car’s path. $r$ is the distance along the radius of curvature between the midpoint on the hinder axle between the two hinder wheels and the centre of curvature $C$ of the car’s motion. You can derive the steering angles from $\kappa$:

\begin{equation}\label{AckermannSteeringCondition}\begin{array}{lcl}\theta_1 &=& \arctan\left(\frac{\ell\,\kappa}{1-\frac{w\,\kappa}{2}}\right)\\\theta_2 &=& \arctan\left(\frac{\ell\,\kappa}{1+\frac{w\,\kappa}{2}}\right)\end{array}\end{equation}

where $\ell$ orthogonal distance between hinder axle and the line joining the two forward wheels (called the wheelbase) and $w$ is the width between the two hinder wheels (called the track). The Ackermann system of linkages simply enforces these equations. I shall also use complex co-ordinates on the Argand plane, to simplify the rotation geometry’s description. Thus two complex numbers define our car’s state: $z$, the car’s position on the Argand plane and $e^{i\,\phi}$ defines the car’s heading (see their descriptions in Figure 17.1). Our car’s general configuration can thus be written as the vector $\left(\begin{array}{c}z\\e^{i\,\phi}\end{array}\right)$. There are two manifolds at work here. The first is the car’s configuration space, which we have just seen is $\mathbb{C}\times \mathbb{T}^1 \cong \R^2\times \mathbb{T}^1$ (where $\mathbb{T}^1$ is the 1-torus or circle) whose members are $2\times 1$ complex column vectors. [Nelson]‘s, [Burke]‘s and [Rossmann]‘s configuration space is $\R^2\times \mathbb{T}^2$ for they have the heading and steering angles $\phi,\,\theta$ as part of their configuration space. The second manifold at work is the connected Lie group $\H$ of transformations acting on the configuration space $\mathbb{C}\times \mathbb{T}^1$, so let’s describe the latter manifold now.

With the steering set for path curvature $\kappa$, if we drive forward a distance $s$, the angular displacement on the circular path followed by $z$ is $\kappa\,s$ and the configuration space variables undergo (take heed that the centre of rotation $C$ has the position vector $z+i\,\kappa^{-1}\,e^{i\,\phi}$ where $z$ is the initial position) $z \mapsto e^{i\,\kappa\,s}\,\left(z – (z+i\,\kappa^{-1}\,e^{i\,\phi})\right)+z +i\,\kappa^{-1}\,e^{i\,\phi} = z + i\,\kappa^{-1}\,e^{i\,\phi}\,(1-e^{i\,\kappa\,s})$ and $e^{i\,\phi}\mapsto e^{i\,\kappa\,s}\,e^{i\,\phi}$, which we can summarise as a linear transformation:

\begin{equation}\label{AckermannSteeringTransformation}U_\kappa:\mathbb{C}\times \mathbb{T}^1\to\mathbb{C}\times \mathbb{T}^1;\quad\quad U_\kappa\,\left(\begin{array}{c}z\\e^{i\,\phi}\end{array}\right) = \left(\begin{array}{cc}1&\frac{i}{\kappa}\,(1-e^{i\,\kappa\,s})\\0&e^{i\,\kappa\,s}\,\end{array}\right)\,\left(\begin{array}{c}z\\e^{i\,\phi}\end{array}\right)\end{equation}

so we see straight away that the Lie group $\h$ in Theorem 13.4 is a Lie subgroup of $\G=GL(2,\,\mathbb{C})$, whose members’ determinants are all on the unit circle. Take heed that the sign of $\kappa$ automatically accounts for whether we steer to the left (positive $\kappa$) or right (negative $\kappa$). All possible transformations of the Ackermann steering car are finite products of transformations of the form in $\eqref{AckermannSteeringTransformation}$. We can pare away the detailed analysis of [Nelson] and [Burke] by simply taking heed that the $2\times2$ matrix in $\eqref{AckermannSteeringTransformation}$ is readily diagonalisable, so we can compute its logarithm:

\begin{equation}\label{AckermannSteeringTransformationLogarithm}\log U_\kappa = \left(\begin{array}{cc}0&1\\0&i\,\kappa\end{array}\right)\end{equation}

So, by Theorem 13.4, we must find the smallest Lie algebra $\h$ containing all matrices of the form in $\eqref{AckermannSteeringTransformationLogarithm}$ and then the theorem assures us that we can always find a finite sequence of transformations of the form in $\eqref{AckermannSteeringTransformation}$ that can realise any member of the connected Lie group generated by $\exp(\h)$ but no other transformations. Matrices of the form in $\eqref{AckermannSteeringTransformationLogarithm}$ are of the form $D + \kappa\,R$ where:

\begin{equation}\label{AckermannSteeringLieAlgebra}\begin{array}{c}D = \text{“drive”}=\left(\begin{array}{cc}0&1\\0&0\end{array}\right)\quad R = \text{“rotate”}=\left(\begin{array}{cc}0&0\\0&i\end{array}\right)\\S = \text{“sideslide”}=\left(\begin{array}{cc}0&i\\0&0\end{array}\right)\\\\\left[D,\,R\right]=\ad(D)\,R = S;\quad\left[R,\,S\right]=\ad(R)\,S = D;\quad\left[S,\,D\right]=\ad(S)\,D = 0\end{array}\end{equation}

The car cannot undergo a pure rotation $\exp(s\,R)$ directly, but by a linear combination of the directly realisable $D$ (drive straight ahead or backwards) and $D + R$ (drive forwards or backwards with unit steering force to the left) realises $R$, therefore, by the methods of Lemma 3.2 we know that $\exp(s\,(D+\kappa\,R))\,\exp(-s\,(D-\kappa\,R)$ is a $C^\omega$ function of $s$ whose tangent to the identity is $2\,\kappa\,R$. So $\h$ must be at least the whole vector space $\left<\{D,\,R\}\right>$ spanned by $D,\,R$. Therefore driving forward a small distance with the steering wheel at some setting $\kappa$ then driving backwards the same distance with the same magnitude but opposite sense steering setting approximates a pure rotation in the limit as the distance is small.

But this vector space is not closed under the Lie bracket, whereas, from the last line in $\eqref{AckermannSteeringLieAlgebra}$, the space $\left<\{D,\,R,\,S\}\right>$ is. Therefore, the connected Lie group of all transformations that can be reached with the car’s controls is $\H$ where:

\begin{equation}\label{AckermannSteeringLieGroup}\begin{array}{lcl}\h &=& \left\{x\,D + y\,S+\phi\,R\right|\quad x,\,y,\,\phi\in\R\}\\\H &=& \left\{\left.\prod\limits_{k=1}^n\,e^{X_k}\right|\quad X_k\in\h;\;n\in\mathbb{N}\right\}\end{array}\end{equation}

and one way to see the Lie group structure is with $\Nid = \{X|\,X\in\h;\,\left\|e^X-\id\right\|<1\}$ and $\lambda =\log$. In this simple case, we can further simplify the description of the Lie group by direct computation:

\begin{equation}\label{AckermannSteeringLieGroup_2}\H = \left\{\left.\left(\begin{array}{cc}1&-i\,(x-i\,y)\frac{e^{i\,\phi}-1}{\phi}\\0&e^{i\,\phi}\end{array}\right)\right|\quad x,\,y,\,\phi\in\R;\right\}\end{equation}

The set of such products is the whole affine group $\mathbb{E}(2)$ of translations and rotations of the Argand plane. This is a noncompact Lie group like $SL(2,\,R)$, however in this case, every member of $\mathbb{E}(2)$ can be represented by the exponential of a Lie algebra member as we can readily see from $\eqref{AckermannSteeringLieGroup_2}$. Define our rotations by $-\pi<\phi\leq\pi$, so we can choose a $\phi$ in this domain to realise any rotation operator $e^{i\,\phi}$. Furthermore, $(e^{i\,\phi}-1)/\phi$ is nonzero for all $-\pi<\phi\leq\pi$. Therefore, having chosen a $\phi$ to realise the wished for rotation, we can find $x\,y\,\in\R$ where $-i\,(x-i\,y)\,(e^{i\,\phi}-1)/\phi=z$ for any translation $z$ in the complex plane.

We note that a finite sideslide $e^{s\,S}$ is precisely what one needs to drive out of a parallel carpark. We have $\left[D-\kappa\,R,\,D+\kappa\,R\right] = 2\,\kappa\,S$. By looking at the lowest order terms in the Campbell-Baker-Hausdorff series, we know that:

\begin{equation}\label{SmallSideslide}\exp(s\,(D-\kappa)\,R))\,\exp(s\,(D+\kappa\,R))\,\exp(-s\,(D-\kappa)\,R))\,\exp(-s\,(D+\kappa\,R)) \approx \exp(2\,\kappa\,s^2\,S)\end{equation}

If we concatenate two basic (i.e. those that can be done in one move) transformations, to wit, of the form $\exp(s_2\,(D + \kappa_2\,R))\,\exp(s_1\,(D + \kappa_1\,R))$ and choose $s_1\,\kappa_1 + s_2\,\kappa_2=0$, the outcome is a pure translation of $2\,(\kappa_1^{-1}-\kappa_2^{-2})\,\exp\left(i\,\frac{\kappa_1,\,s}{2}\right)\,\sin\left(\frac{\kappa_1,\,s}{2}\right)$ units, which is purely real for small $s_1$: we $s_1\,\kappa_1 = \pi$ need to make it purely imaginary (i.e. a pure sideslide), and a tight enough carpark does not let us drive forwards so much. Indeed, if we sketch the situation $s_1\,\kappa_1 = – s_2\,\kappa_2=\pi$ as in Figure 17.3 where we see the manoeuvre sequence is drive forwards through a half circle, set steering to opposite lock and then drive backwards through the mirror image half circle, it becomes clear that this twin manoeuvre is only workable if we have enough space in the parallel carpark to drive straight out of the latter in the first place!

 

Two Moves CarparkFigure 17.3: Pure Sideways Translation in Two Manoeuvres

So we cannot sideslide (purely imaginary translation) out of the park with two small manoeuvres. However, three such manoeuvres:

\begin{equation}\label{ThreeMoves}\exp(s_3\,(D + \kappa_3\,R))\,\exp(s_2\,(D + \kappa_2\,R))\,\exp(s_1\,(D + \kappa_1\,R))\end{equation}

with:

\begin{equation}\label{ThreeMovesCondition_1}s_1\,\kappa_1 + s_2\,\kappa_2 + s_3\,\kappa_3=0\end{equation}

gives a pure translation of:

\begin{equation}\label{ThreeMovesTranslation}\Delta z_3=i\,(\kappa_2^{-1}-\kappa_1^{-1})\,e^{i\,\kappa_1\,s_1} + i\,(\kappa_3^{-1}-\kappa_2^{-1})\,e^{-i\,\kappa_3\,s_3}+i\,(\kappa_1^{-1}-\kappa_3^{-1})\end{equation}

units, which can be purely imaginary for some arbitrarily small, but nonzero, $s_1,\,s_2,\,s_3$; for this to happen, we simply choose:

\begin{equation}\label{ThreeMovesCondition_2}(\kappa_1^{-1}-\kappa_2^{-1})\,\sin(s_1\,\kappa_1) + (\kappa_3^{-1}-\kappa_2^{-1})\,\sin(s_3\,\kappa_3)=0\end{equation}

Since $s_1,\,s_2,\,s_3$ can be arbitrarily small, we can do this in an arbitrarily tight park, a statement we shall now explore further.

Car Parking 2

Figure 17.4: Car Configuration Space Definition in [Nelson] (reproduced from that reference)

Given the definitions of Figure 17.4, the rotation whilst the car is in the carpark is limited: its profile projected onto the edge of the carpark has length $\ell^\prime\cos\phi + w^\prime\sin\phi$, therefore:

\begin{equation}\label{RotationLimit}\ell^\prime\,(\cos\phi – 1) + w^\prime\sin\phi < \delta\end{equation}

otherwise we shall bump the cars ahead of and behind us. Likewise, referring to the lower diagram in Figure 17.4, we can drive straight out of the park when the edge $E$ and $E^\prime$ both lie on a circle centred on the line parallel with the hinder axis a distance $r_{min} = \kappa_{max}^{-1}$ from the midpoint between the two hinder wheels, where $r_{min} = \kappa_{max}^{-1}$ is the minimum turning circle radius for the car. The radius of the circle through $E$ and $E^\prime$ is:

\begin{equation}\label{LimitingCircle}\begin{array}{llcl}&r^\prime &=& \sqrt{\left(\frac{\ell^\prime+\ell}{2}\right)^2+\left(r_{min} +\frac{w^\prime}{2}\right)^2}= \sqrt{\left(\frac{\ell^\prime+\ell}{2}+\delta\right)^2+\left(r_{min} -\frac{w^\prime}{2} + v\right)^2}\\\Rightarrow&v&=&\sqrt{\left(r_{min}+\frac{w}{2}\right)^2-\delta^2-\delta\, (\ell^\prime+\ell)}-r_{min}+\frac{w}{2}\end{array}\end{equation}

and if $v<0$ one can drive straight out of the park. Otherwise, we need to undergo a sequence of triple moves defined by $\eqref{ThreeMovesCondition_1}$, $\eqref{ThreeMovesTranslation}$ and $\eqref{ThreeMovesCondition_2}$. The obvious sequence is with $\kappa_1 = -\kappa_2=\kappa$, $s_1=s_2$ and $\kappa_3=0$ so $\eqref{ThreeMovesCondition_2}$ becomes $2 \sin(s_1\,\kappa) / \kappa + s_3=0$. When the manoeuvre takes up the whole park, we have $s_3 = \Delta$, thus $\eqref{ThreeMovesTranslation}$ becomes $\delta z_3= 2\,i\,(1-\sqrt{1-\frac{\kappa^2 \delta^2}{4}})/\kappa$. After the first transformation $\exp(s_1\,(D + \kappa_1\,R))$, we find that the car’s forward translation is $\delta/2$ and its angle of rotation $s_1 /r_{min}$ where $\delta / r_{min} = 2 \sin(s_1 /r_{min})$. Therefore, $\eqref{RotationLimit}$ (less $\delta/2$ to account for the forward translation) which ensures the rotated car doesn’t bump its neighbours becomes:

\begin{equation}\label{RotationLimit_2}\ell^\prime\left(\sqrt{1-\frac{\delta^2}{4\,r_{min}^2}}-1\right)+w^\prime\,\frac{\delta}{2\,r_{min}}<\frac{\delta}{2}\end{equation}

which, when $\delta \ll r_{min}$, becomes $w^\prime / r_{min} <1$ and is therefore fulfilled for all reasonable car measurements. Our $\delta z_3= 2\,i\,r_{min}\,(1-\sqrt{1-\frac{\delta^2}{4\,r_{min}^2}}$ is pure sideways translation. For a car with a 2m minimum turning radius in a carpark one metre longer than the car (i.e. $\delta = 1$), $|\delta z_3| = 8{\rm cm}$. $\eqref{LimitingCircle}$ yields $v=24{\rm cm}$ if the car is $5{\rm m}$ long and $2{\rm m}$ wide, so we need about three triple manoeuvres to get a sideslide of $v=24{\rm cm}$, whence we can drive straight out of the park. If the park is half a metre longer than the car, $\eqref{LimitingCircle}$ yields $v=1.28{\rm m}$ and $\delta z_3 = 2{\rm cm}$. Now we shall need 64 triple manoeuvres to get a sideslide of $v=1.28{\rm m}$, whence we can drive straight out of the park. In theory, we can get out of any park that is longer than the car, i.e. for any $\delta>0$, but the task becomes swiftly harder as $\delta\to 0$. The number of cycles needed for this car (an integer, hence the quantisation in the graph below), plotted as a function of the “clearance” $\delta$ (i.e. difference between the length of the carpark and the car) is plotted in Figure 17.5, where we see this swift increase in task difficulty as $\delta\to 0$.

Parking Calcs

Figure 17.5: Number of Cycles Needed to Get Out of Carpark as a Function of Clearance in metres for a 5m Long, 2m Wide Car with 3m Minimum Turning Circle Radius

One can experiment with these constraints in the Mathematica simulation below, where the car can be set to do both pure sideslide (parallel parking) manoeuvres (“action” = “Park” on the pulldown menu) and pure rotation manoeuvres (“action” = “Rotate” on the pulldown menu). The clearance can be adjusted with the “Clearance” slider to any value up to the car’s width. The tightest turning circle radius the car can steer is adjusted with the “Turn Circle” slider: greatest turning circle (lowest path curvature) is at the bottom and represents a turning circle radius of ten times the car’s width. With the “Turn Circle” slider set to the top, the turning circle radius equals the car’s width. The paths of the four corners of the car’s footprint can be tracked by clicking the appropriate checkboxes, as can be the path of the point on the hinder axle halfway between the hinder wheels. To start the car in its manoeuvre, click the “+” box to the right of the $t$-slider, and then press the play symbol. You can begin the manoeuvre again by pressing reset.



Vector Fields of Automomorphisms of the Parallel Parking Car’s Configuration Space

The above analysis is only successful because we could find a linear configuration space acted on by a Lie group of analytic automorphisms of the car’s configuration space. However, we have seen in Chapter 9 that the notion of a Lie group’s action on a manifold is rather more general that the special case where the Lie group acts on a linear vector space. So let’s look at the problem from a standpoint more like that of [Nelson]‘s, [Burke]‘s or [Rossmann]‘s.

In this standpoint the configuration space is the manifold $\mathcal{M}=\R^2\times \mathbb{T}^1\times \R$ where the typical point in the configuration space is $(x,\,y,\,\phi,\,\kappa)$, where $x$ and $y$ define the position of “datum”, i.e. of the midpoint on the hinder axle between the car’s hinder wheels, $\theta$ defines the car’s heading angle and $\kappa$ the curvature of the datum’s path when the car drives with a constant steering setting. We simply assume Ackermann steering, so that $\kappa$ replaces the steering angle in [Nelson], [Burke] and [Rossmann]. When the car drives forward at a speed $v = \d_\tau s$ when its configuration is the point $p=(x,\,y,\,\theta,\,\kappa)$, the tangent $X\in T _p\,(\mathcal{M})$ to $p\in\mathcal{M}$ is defined by:

\begin{equation}\label{CarConfigurationTangent}\begin{array}{lclclcl}\d_\tau\,x &=& \cos\phi\,\d_\tau s&&\d_\tau\,y &=& \sin\theta\,\d_\tau s\\\d_\tau\,\phi&=& \kappa\,\d_\tau s&&\d_\tau\,\kappa &=&0\end{array}\end{equation}

and the directional derivative associated with this tangent is therefore:

\begin{equation}\label{CarConfigurationTangent_2}\mathscr{D} = \cos\phi\,\partial_x +\sin\phi\,\partial_y + \kappa\,\partial_\phi\end{equation}

When the car steers without driving, the steering setting $\kappa$ changes. With the configuration given by $p=(x,\,y,\,\theta,\,\kappa)$, the tangent $X\in T _p\,(\mathcal{M})$ to $p\in\mathcal{M}$ defined by such a steering action is:

\begin{equation}\label{CarConfigurationTangent_3}\mathscr{S} = \partial_\kappa\end{equation}

By elementary calculation, we get:

\begin{equation}\label{CarConfigurationTangent_4}\mathscr{R}=\left[\mathscr{S},\,\mathscr{D}\right] = \partial_\phi;\;\left[\mathscr{R},\,\mathscr{S}\right] = 0\end{equation}

where $\mathscr{R}$ clearly exponentiates to a pure rotation of the car about the datum point, hence the notation $\mathscr{R}$. We then have:

\begin{equation}\label{CarConfigurationTangent_5}\mathscr{Y}=\left[\mathscr{R},\,\mathscr{D}\right] = -\sin\phi\,\partial_x+\cos\phi\,\partial_y;\quad\mathscr{X} = \left[\mathscr{Y},\,\mathscr{R}\right]= \cos\phi\,\partial_x+\sin\phi\,\partial_y\end{equation}

and $\mathscr{X}$ and $\mathscr{Y}$ clearly exponentiate to pure forwards and sideways translations of the car, respectively.

However, we now have the vector field $\mathscr{T} = \mathscr{D}-\mathscr{X} = \kappa\,\partial_\phi$.

\begin{equation}\label{CarConfigurationTangent_6}\left[\mathscr{T},\,\mathscr{R}\right] =0;\quad \left[\mathscr{T},\,\mathscr{S}\right]= -\mathscr{R};\left[\mathscr{T},\,\mathscr{D}\right] = \kappa\,X\quad\end{equation}

and also the pathological sequence:

\begin{equation}\label{CarConfigurationTangent_7}\left[\mathscr{T},\,\mathscr{X}\right] = \kappa\,\mathscr{Y};\quad\left[\mathscr{T},\,\left[\mathscr{T},\,\mathscr{X}\right]\right] = -\kappa^2\,\mathscr{X};\quad\left[\mathscr{T},\,\left[\mathscr{T},\,\left[\mathscr{T},\,\mathscr{X}\right]\right]\right] = -\kappa^3\,\mathscr{Y}\,\cdots\end{equation}

so with this configuration space we do not get a closed, finite dimensional Lie algebra of vector fields generated by $\mathscr{D}$ and $\mathscr{S}$ but rather a countably infinite dimensional one. Recall that in this approach, $\kappa$ belonged to the configuration space and did not simply characterise the family of steering transformations as in $\eqref{AckermannSteeringTransformation}$.

The same problem arises in the problem description in [Nelson], [Burke] and [Rossmann]. The configuration space is $\mathcal{M}=\R^2\times \mathbb{T}^2$ where $p=(x,\,y,\,\phi,\,\theta)$ where now $\phi$ represents the heading of the centre of the forward axle relative to the car’s long axis of reflexional symmetry, i.e. the line joining the central points of forward and hinder axles and $\theta$ represents the “steering angle”, i.e. the angle between the car’s long axis and the line joining this central forward axle point and the centre $C$ of rotation in Figure 17.1 then the radius of curvature of the path of the central forward axle point is $\ell/\sin\phi$ (see Nelson’s drawing in Figure 17.2 where he defines these symbols thus). The relationship between the “steering angle” $\theta$, the individual steering angles of the two forward wheels defined by $\eqref{AckermannSteeringCondition}$ and the car’s steering wheel setting is complicated and nonlinear, but it is one-to-one and is thus quite acceptable as a co-ordinate for the configuration space. From this standpoint, the tangent $X\in T _p\,(\mathcal{M})$ to $p\in\mathcal{M}$ when one holds a constant steering angle $\theta$ is defined by:

\begin{equation}\label{CarConfigurationTangent_8}\begin{array}{lclclcl}\d_\tau\,x &=& \cos(\theta+\phi)\,\d_\tau s&&\d_\tau\,y &=& \sin(\theta+\phi)a\,\d_\tau s\\\d_\tau\,\phi&=& \ell^{-1}\,\sin\theta\,\d_\tau s&&\d_\tau\,\theta&=&0\end{array}\end{equation}

and the tangent when the car is standing still and changing its steering angle is defined by $\d_\tau\,x =\d_\tau\,y = \d_\tau\,\phi= 0;\;\d_\tau\,\theta= 1$ so our differential operators (directional derivatives associated with these tangents) are now:

\begin{equation}\label{CarConfigurationTangent_9}\mathscr{D} = \cos(\theta+\phi)\,\partial_x +\sin(\theta+\phi)\,\partial_y + \ell^{-1}\,\sin\theta\,\partial_\phi;\quad\mathscr{S} = \partial_\theta\end{equation}

whence:

\begin{equation}\label{CarConfigurationTangent_10}\begin{array}{lcl}\mathscr{W}\stackrel{def}{=}\left[\mathscr{S},\,\mathscr{D}\right] &=& -\sin(\theta+\phi)\,\partial_x +\cos(\theta+\phi)\,\partial_y + \ell^{-1}\,\cos\theta\,\partial_\phi\\\mathscr{T}\stackrel{def}{=}\ell\,\left[\mathscr{W},\,\mathscr{D}\right]&=&-\sin\phi\,\partial_x+\cos\phi\,\partial_y\\\mathscr{U}\stackrel{def}{=}-\ell^{-1}\left[\mathscr{D},\,\mathscr{T}\right]&=&\sin\theta\left(\cos\phi\,\partial_x+\sin\phi\,\partial_y\right)\end{array}\end{equation}

$\mathscr{W}$ is the operator [Nelson] and [Rossmann] call “wriggle” and $\mathscr{T}$ is slide. However here is where we strike the same countably infinite Lie algebra problem; for instance:

\begin{equation}\label{CarConfigurationTangent_11}\ad(\mathscr{D})^{2\,k}\,\mathscr{T} = (-1)^k\,\ell^{2\,k}\,(\sin\theta)^{2\,k}\,\mathscr{T};\quad\ad(\mathscr{D})^{2\,k+1}\,\mathscr{T} = (-1)^k\,\ell^{2\,k+1}\,(\sin\theta)^{2\,k+1}\,\mathscr{U}\end{equation}

So now we go back to $\eqref{CarConfigurationTangent_2}$ and now think of the configuration space as $\R^2\times\mathbb{T}^1$ comprising the $x$ and $y$ co-ordinates and the heading $\phi$ of the car. We think of the path curvature $\kappa$ as parameterising a family of “drive” operators, analogously with the successful, linear space approach of the last section. This makes sense: from any point in $(x,\,y,\,\phi)\in\R^2\times\mathbb{T}^1$ we can clearly get to any point $(x,\,y,\,\phi,\,\theta)\in\R^2\times\mathbb{T}^2$ in [Nelson]‘s and [Rossmann]‘s configuration space by leaving the car standing still and imparting the steer angle to the forward wheels. So there is little lost from dropping $\kappa$ or [Nelson]‘s and [Rossmann]‘s $\theta$ from the configuration space. From this standpoint, we can see that $\eqref{CarConfigurationTangent_2}$ can be written as $\mathscr{X} + \kappa\,\mathscr{R}$ with $\mathscr{X},\,\mathscr{R}$ defined in $\eqref{CarConfigurationTangent_5}$. So our Lie algebra contains all linear combinations of $\mathscr{X}$ and $\mathscr{R}$ and this does generate a finite dimensional Lie algebra for we now have:

\begin{equation}\label{CarConfigurationTangent_12}\begin{array}{l}\begin{array}{\lcl}\mathscr{X}&=&\cos\phi\,\partial_x+\sin\phi\,\partial_y\\\mathscr{Y}&=&-\sin\phi\,\partial_x+\cos\phi\,\partial_y\\\mathscr{R} &=& \partial_\phi\end{array}\\\begin{array}{lcl}\left[\mathscr{R},\,\mathscr{X}\right] &=& \mathscr{Y}\\\left[\mathscr{R},\,\mathscr{Y}\right] &=& -\mathscr{X}\\\left[\mathscr{X},\,\mathscr{Y}\right] &=& 0\end{array}\end{array}\end{equation}

Clearly, $\exp(s\,\mathscr{X})$ is an automorphism of $\mathcal{M}$ for all $s\in\R$; the exponential is simply a translation forwards in the direction of the car’s heading through distance $s$. Likewise $\exp(s\,\mathscr{Y})$ is a sideways translation through distance $s$ and is thus an automorphism $\mathcal{M}\to\mathcal{M}$ for all $s\in\R$. Likewise for $\exp(\phi\,\mathscr{R})$: this is a pure rotation about the central point of the car’s hinder axis through an angle $\theta$. Therefore, condition 2 of Theorem 11.14 holds, and condition 1 of the same theorem holds by $\eqref{CarConfigurationTangent_12}$. Theorem 11.14 therefore holds, so that there is a connected finite dimensional Lie group $\G=\left\{\left.\prod\limits_{k=1}^M\,\exp\left(\tau_k\,\hat{\mathscr{X}}_k\right)\right|\;\tau_k\in\R;\;M\in\mathbb{N}\right\}$ of automorphisms of the manifold $\R^2\times\mathbb{T}^2$ whose three dimensional Lie algebra is defined by the basis vectors $\hat{\mathscr{X}}_1 = \mathscr{X},\,\hat{\mathscr{X}}_2 = \mathscr{Y},\,\hat{\mathscr{X}}_3 = \mathscr{R}$ of $\eqref{CarConfigurationTangent_12}$. By Theorem 14.21, we know therefore that this Lie group of automorphisms is either the Euclidean group $\mathbb{E}(2)$ (since it has the same Lie algebra, on comparing $\eqref{CarConfigurationTangent_12}$ and $\eqref{AckermannSteeringLieAlgebra}$) or, by Theorem 14.21, a cover or projective group of $\mathbb{E}(2)$. It cannot be the latter, because $\mathbb{E}(2)$ has trivial centre $\mathscr{\mathbb{E}(2)}=\{\id\}$. Further investigation is needed to find out whether we are dealing with $\G=\mathbb{E}(2)$ or a cover, because $\mathbb{E}(2)$ is not simply connected.

The above is really a different take on the way that [Nelson], [Burke] or [Rossmann] deal with the “pathological behaviours” shown in $\eqref{CarConfigurationTangent_7}$ and $\eqref{CarConfigurationTangent_11}$, when they choose vector fields over constant $\theta$ sections of the whole manifold and note that any point in the configuration space (manifold $\mathcal{M}$) $(x_0,\,y_0,\,\phi_0,\,\theta_0)$ can be reached from any point of the form $(x_0,\,y_0,\,\phi_0,\,\theta_1)$ simply by imparting the with some value $\theta_0$ of $\theta$ can be reached by simply steering (imparting the operator $\exp(s\,\mathscr{S})$ for some $s\in\R$) whilst the car is still.

The idea of a homogeneous space seems very powerful, and it is from a theoretical standpoint. However, the above two methods show how fiddly it can be and how it can take considerable ingenuity (and slogging) to find an atlas for a manifold in question that proves the existence of the finite dimensional symmetry Lie group for a manifold by exhibiting a finite set of vector fields $\hat{\mathscr{X}}_k$ whose exponentiations $\exp\left(\tau \hat{\mathscr{X}}_k\right)$ define genuine continuous one-parameter groups and which are closed under the Lie bracket.

References:

  1. Roger Brockett, “Robotic manipulators and the product of exponential formula“, in P. Fuhrman ed. Proc. Mathematical Theory of Networks and Systems pp. 120–129, 1984
  2. J.M. Selig, “Lie Groups and Lie Algebras in Robotics“, NATO Advanced Study Institute on Computation Noncommutative Algebra and Applications held at Il Ciocco Resort Hotel, in Tuscany, Italy, July 6 through 19, 2003
  3. William L. Burke, “Applied Differential Geometry“, Cambridge University Press, Cambridge England, Part III, §19, “Holonomy”
  4. Wulf Rossmann, “Lie Groups: An Introduction through Linear Groups (Oxford Graduate Texts in Mathematics)”, Oxford University Press, 2003, p161
  5. Edward Nelson, “Tensor Analysis“, Princeton University Press, New Jersey, 1967, §2, Part 4 “Vector Fields and Flows”, p34
  6. Charles Siegel, Parallel Parking page 1st of October 2007 on his blog “Rigorous Trivialities”
  7. Desmond King-Hele, “Erasmus Darwin’s Improved Design for Steering Carriages – And Cars“, Notes Rec. R. Soc. London, 56, #1,2002 pp. 41-62