Cad Cam Development



Differential constraints and self parking VW – part 2

In the previous post I’ve explained some of the maths of differential constraints and how to apply it to car dynamics. As a result a ESP system could be build. This post starts a series of posts to show how non-homological constraints can be used to program self-parking car system as Volkswagen has done recently.

Before reading watch the following two short movies to have idea how VW’s cars are automatically parking.

The self-parking system consists mainly of three parts:

  1. Scene generation with some computer vision algorithms
  2. Car’s parking path finding
  3. Car movement (steering)

In this post I’ll dwell into car’s parking path finding. I won’t discuss the other two points because it’s not relevant in CAD/CAM and does not relate to main topic: differential and non-homological constraints. The first point – scene generation with some CV’s algorithms is well-known problem, mainly from robotics and there are many solutions. You can also check how military cars are equipped and how do they work and this knowledge should allow you to proceed with first point. Car movement – this is only electronically steering, so this isn’t CAD/CAM, rather raw automatics, so I won’t spend time elaborating on those points, because they are out of scope.

Car’s parking path finding – geometry of motion

Suppose your car is parallel to the car parking place and you want it to move there. See the picture below.

Initial car parking situation

Then, suppose you know the distance you can travel forwards (eq. backwards) so that you wouldn’t hit any other object that is on your way. Using steering wheel you can adjust the radius of the circle the car will be moving tangentially on. The smaller the radius is, the faster you’ll set your car at place.

Distances and the way the car is traveling while parking

Consider the car movement same as it was presented in the previous post with ESP system: to be sequence of circle-based tangential moves with different curvature radius. This means, that either the car goes along a circle with a given radius (the car’s turn radius) or along a line with radius equal to 0.

The circle-based way to perform parking

There are two circles in each parking step ( curly brackets): the yellow one and the green one. Each of them can have different radius. Normally they should be symmetrical, this means, that the green and accordingly yellow radius should remain the same over single. The car is following two different circle in each cycle to imitate the perpendicular move (the arrow at the first picture). If the distance (see the pictures) is coming to zero, the limit of the distance between the car’s current position and the destination will increase to infinity. This means, that you won’t park your car perpendicularly to car’s motion direction if the distance is below some limit. That’s not astonishing, but is important while implementing mathematical algorithms to drive the car. The size of parking place and the setting of other neighbour cars will be the non-homological constraint that should be taken into account while programming.  So you know so far how to program the motion of car while parking. Suppose we know the distance, and is big enough.

Some basic theorems and remarks on geometric differential constraints on manifolds

How should the car turn the steering wheel so that it can follow path and as a result park? This is mathematical task and is similar to previous post ESP question, requires gaining some mathematical knowledge. In this post only part of the mathematical knowledge has been explained together with a rather primitive proposal of a formal solution to a problem. Keep visiting and reading my blog to read the next parts I’ll publish about differential constraints.

The foliation of the system would be the circles the car is going to move on. The constraints would be the curves (arcs of circles) that a car would be going on.

There is the theory I’ve taken out from lecture in italics that will allow to control steering wheel:

Let the foliation be defined as

(1) f_{i=1...(n-k)}(x)=0

T-differentiation of compositions

f_{i=1..(n-k)}=0

leads to (n-k) implicit differential identities:

\frac{df^i}{dx^a}\frac{dx^a}{dt}=\frac{df^i}{dx^a}x^a_{t}=0

Constraints (1) are locally expressed as implicit differential constraints:

(2) df_{ia}v^a=0,i=1..n-k of vanishing exterior derivatives df_i.

Replacing in (2) of exterior derivative df of a global constraint function f by arbitrary field \omega of 1-froms leads to more general differential constraint:

\omega_{a}v^a=0. We know that second exterior derivative d of arbitrary exterior p-form field \omega vanish.This means:

dd\omega=0.

In particular if a 1-form field $latex\omega$ is a differential then:

d_{b}\omega_{a}=d_{b}d_{a}f=0_{ba}.

If the exterior derivative of 1-form \omega vanish in a contractible region X of R^m, this means:

d\omega=0\ in\ X then field of 1-forms \omega is a differential of a scalar function f defined on this region X.

The theory in practice says that you should keep (2) vanishing and contract your space you’re moving on, compute the form and reverse contracting space and finally move your car. Note in contrary to ESP system where you handled only homological constraints, you’re using non-homological constraints in this example, so you should provide some system’s controllability feature. To provide this some further maths like Lie Algebra will be required. I’ll try to write a post about this later.

A system is locally controllable:

Let U be a subset of configuration space X. A configuration c\subset X is said to be U-accessible from configuration s\subset X iff there is trajectory x(t) from s to c such that:

  1. trajectory x(t) is in U
  2. all velocities x_{t}(t) are admissible
  3. map x_{t} is piecewise constant

Although this post is not finished yet, and some further math explanations are required to be published, I hope it helped you a bit in understanding what’s inside geometrical task of parking. Watchout next post in this series!

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s