WEBVTT
00:00:04.049 --> 00:00:14.465
So welcome back to the lecture on automotion today. Let
us continue with a chapter checking and introduce the last
00:00:14.465 --> 00:00:25.014
filter that we will discuss here, namely the particle
filter so. Last Monday, we had a look at, how can we
00:00:25.014 --> 00:00:32.381
represent probability density functions? if and how can we
calculate this probability density functions if they are
00:00:32.381 --> 00:00:40.182
complicated, if they are complex, and we cannot represent them
easily with a Gaussian distribution, for instance. And we
00:00:40.182 --> 00:00:50.639
found several ways to do that. The first way is shown here
on top of the slide. It is while we say," Okay, we create
00:00:50.639 --> 00:01:00.785
bins intervals we the state space or the values
that the random barrier can take into some intervals or bins
00:01:00.785 --> 00:01:11.393
and then we remember, or we, we store one probability
the probability how likely it is that the value of the
00:01:11.393 --> 00:01:19.696
random variable is within this interval, or within the
spin that yields a histogram. However, this method is
00:01:19.696 --> 00:01:28.880
inefficient, especially if we are faced with large spaces,
then we need very many bins, and things become easily very
00:01:28.880 --> 00:01:37.770
inefficient. The second way to represent a probability
distribution in a numerical way is to use a random sample. So we
00:01:37.770 --> 00:01:44.917
are using a random number generator that is using generating
random numbers from the respective distribution of
00:01:44.917 --> 00:01:53.578
interest, and then restore this random sample. So the random
sample can be understood as a numerical representation of
00:01:53.578 --> 00:02:01.566
the distribution. However, the disadvantage of this method is
that for complicated, complex distributions, usually it is
00:02:01.566 --> 00:02:10.547
quite difficult to find a random number generator for this
distribution. So another shortcoming or another problem, a
00:02:10.547 --> 00:02:22.303
third possibility is to extend this idea of of random samples
from a distribution to wait at random samples. And here we
00:02:22.303 --> 00:02:32.224
do not just store the random numbers, the random elements
that we have created. But for each random element that we
00:02:32.224 --> 00:02:43.082
created um, we memorize a non negative value that we can
interpret as the importance m of this random sample element and
00:02:43.082 --> 00:02:52.993
% um. Then we treat this @unoise@ as a waited random sample.
And with this weighted Sam random sample, we have more
00:02:52.993 --> 00:03:01.711
possibilities to find suitable random number generators than
for the random sample. So how should these weights be
00:03:01.711 --> 00:03:10.937
selected? Uh. Well, the idea is as follows. We have the blue
distribution, uh, which is our target distribution. So we
00:03:10.937 --> 00:03:19.275
want that this weight weighted random sample represents the
blue density function. However, we only have a random number
00:03:19.275 --> 00:03:30.470
generator for the green density function in cue. And what
we do is we see that in some areas, say here, the green
00:03:30.470 --> 00:03:39.687
distribution, or the random number generator for the green
distribution will generate to few random samples in this
00:03:39.687 --> 00:03:48.581
area. While in this area, the green probability distribution
will create too many random samples. And we compensate this
00:03:48.581 --> 00:03:57.485
effect by choosing appropriate weights. That means in those
areas in which the random number generator creates two few
00:03:57.485 --> 00:04:05.721
random sample elements. We ah we provide large weights
for those random samples to compensate this fact that we
00:04:05.721 --> 00:04:14.549
have two few elements here in this area @unoise@ while, in
those are areas in which the random number generates too many
00:04:14.549 --> 00:04:22.976
random samples elements @unoise@ we we use small weights
to indicate @unoise@ that ah we, have to @unoise@ ah to
00:04:22.976 --> 00:04:32.655
um @unoise@ consider. Those random aluminum sample elements,
not that much as others. So in general, we could argue that
00:04:32.655 --> 00:04:43.858
a good choice of these uh weights. Wi is to select them
proportional to the ratio of or a queue of X. I so X. I is
00:04:43.858 --> 00:04:53.347
a numbers that we have just created the random number that
we have just created. And P was a density function of the
00:04:53.347 --> 00:05:01.653
target distribution. Q is the distribution, the density function
of the distribution for which we have the random number
00:05:01.653 --> 00:05:10.067
generator. Furthermore, we need the constraint that the
sum of the weights of over all weights. Now of all random
00:05:10.067 --> 00:05:17.759
elements is equal to one where to get sarcastic consistency.
This method is called important sampling, and that is the
00:05:17.759 --> 00:05:25.299
basis for the particle filter, which will discuss now. The
question is, once we have sampled from such a distribution?
00:05:25.300 --> 00:05:34.488
how can be calculated with such a sample. So how can we
implement a prediction or an innovation step based not based on
00:05:34.488 --> 00:05:42.829
a probability density function, but based on a random sample.
Okay, let us have a look what we could do. The first thing
00:05:42.829 --> 00:05:51.953
we assume now on this light, we assume that the state space
from which we want to sample is just the projection plane
00:05:51.953 --> 00:06:00.797
here. So a two dimensional area in which we want to sample.
And each of the sample elements is illustrated by a circle
00:06:00.797 --> 00:06:11.426
here, by colored circle. So let us assume that we use this
an important sampling method to generate a random sample
00:06:11.426 --> 00:06:22.415
indicated by this blue the radius of each circle should
represent the weight of the sample element. That means the
00:06:22.415 --> 00:06:32.678
largest circles are. The is the weight that is assigned to
the sample elements. Okay, so let us start from that and ask
00:06:32.678 --> 00:06:42.576
how we can implement a prediction step for a filter like a
common like filter. Okay, what does the prediction step
00:06:42.576 --> 00:06:51.657
do well, the prediction step considers the state transition
from one point in time to the next point in time, and it
00:06:51.657 --> 00:07:00.252
should also cover the random noise that happens in this
transition process. Okay, let us assume that we know how the
00:07:00.252 --> 00:07:09.152
function that expresses how points from the current point
in time to the next point in time are changed. Yeah, a
00:07:09.152 --> 00:07:20.743
function, a state transition function F um that um that
describes how states change over time. Okay, each of these
00:07:20.743 --> 00:07:29.712
random sample elements, which we will call a particle
for now on @unoise@ can be described or actually represents
00:07:29.712 --> 00:07:38.979
one's value in state, in the state space. So that means we
can apply this function. F @unoise@ to each particle what.
00:07:38.990 --> 00:07:48.550
Happens while this will change the position of the particle
in space. And this is indicated here by the um solid arrows.
00:07:48.560 --> 00:07:57.147
That means each solid error indicates what this state
transition function. F, uh does Ah with each particle. Now it
00:07:57.147 --> 00:08:04.749
changes the value of each particle. And this is indicated
by the solid arrow, of course. Furthermore, we have the
00:08:04.749 --> 00:08:12.165
transition noise, the noise in the transition system, which
we have to consider. We assume that we know how this noise
00:08:12.165 --> 00:08:20.669
is distributed. And then, of course, what we could do is
we could add random noise to each particle. And this is
00:08:20.669 --> 00:08:29.023
indicated by the dotted arrows here. So for each of the
particles first the state transition function, and
00:08:29.023 --> 00:08:36.449
afterwards we randomly generate a value from the noise
distribution from this transition noise distribution. And the
00:08:36.449 --> 00:08:48.717
result is a new position for the particle, which is now shown
in green. So each of the particles in shown in blue is um
00:08:48.717 --> 00:08:59.490
um transformed to a particle in green by first applying the
state transition function, and afterwards adding some random
00:08:59.490 --> 00:09:09.706
noise, not just generating random numbers from the noise
distribution. So now we have a distribution, a particle set in
00:09:09.706 --> 00:09:19.778
green that represents the predicted state of the system. So
if blue represents the present state of the system, then the
00:09:19.778 --> 00:09:29.245
green politics that represents the state distribution
or the the state distribution for the next point in
00:09:29.245 --> 00:09:37.551
time @unoise@ um. Okay, what we did not change in this prediction
step are the weights of the particles. Yeah, the
00:09:37.551 --> 00:09:45.120
the radius of these Ah, these circles remained just the
same. Now, there is no reason at the moment to rew these
00:09:45.120 --> 00:09:52.403
particles now. So because the whole state transition is
already covered by what we did in we applying the state
00:09:52.403 --> 00:09:59.833
transition function and adding random transition noise to
it. Now, let us ask, what can? how can we implement the
00:09:59.833 --> 00:10:08.425
innovation step in the innovation staff, we get an observation.
And for simplicity, for this illustration, let us assume
00:10:08.425 --> 00:10:17.663
that what we sense is the state itself. So that means the
measurement equation would be while our measurement is equal
00:10:17.663 --> 00:10:27.239
to the state, plus some measurement noise here. For simplicity,
that means I can put a cross here, a Red Cross in this
00:10:27.239 --> 00:10:36.996
diagram to indicate which value is sensed by the censor.
Now, what we have is, well, we have a sense position. And we
00:10:36.996 --> 00:10:46.302
have report which represent the possible state and we
can compare both. We can ask, how well does the particle fit
00:10:46.302 --> 00:10:55.136
a particle fit to the measurement. And in this simple case,
where we directly measure the state, of course. Um, the
00:10:55.136 --> 00:11:03.664
better. The smaller the distance between a particle and the
sense measurement is, the better fits the particle to the
00:11:03.664 --> 00:11:12.643
measurement, or the measurement to the particle and
that means that more likely is it that this particle is a
00:11:12.643 --> 00:11:21.652
valid a representation of the two state of the system. Now
that means what happens now is that we reweigh the particles
00:11:21.652 --> 00:11:30.140
that we change, the weight of the particles. We do not change
the state values of the particles. We would only change
00:11:30.140 --> 00:11:38.494
the weights. And in this case, this would mean, and the
particles which are close to the measurement, which fit very
00:11:38.494 --> 00:11:46.303
well to the measurement. And for those, we increase the weights.
And for those measurements, which are far away from the
00:11:46.303 --> 00:11:54.306
measurement we do, which do not fit well. And for those, we
decrease it. Their weights are indicated now by the violet
00:11:54.306 --> 00:12:05.262
circles. Also the violet circles are, represents the particle
set after the innovation step. Now, @unoise@ okay what,
00:12:05.262 --> 00:12:15.430
happens next well? after having completed an innovation step.
Ah, we have to do execute the next prediction step again.
00:12:15.440 --> 00:12:25.758
What do we do while we apply the system dynamics, the
system transition function F onto each particle, and we
00:12:25.758 --> 00:12:35.160
shift those particles indicated by the solid arrows.
Afterwards, we randomly sample a random number from the noise
00:12:35.160 --> 00:12:45.369
distribution and transform each particle. According to this
random transformation indicated here by the dotted arrows.
00:12:45.379 --> 00:12:53.911
We do not change the weights of the particles and the
prediction steps of the Radi of those points here in this
00:12:53.911 --> 00:13:01.277
illustration remain the same afterwards. Er we execute an
innovation step again, that means we make a measurement, say
00:13:01.277 --> 00:13:10.227
we send a position here at the Red Cross. And now, again,
we have to increase the weights of all particles, which are
00:13:10.227 --> 00:13:18.786
which fit well to the measurement, or better to say where
the measurement fits well to the particle, and we have to
00:13:18.786 --> 00:13:27.038
decrease the weight for all those particles for which the
measurement does not fit well to the particle. Now that means,
00:13:27.038 --> 00:13:36.247
in this case, that here this um, this particle for this.
This one, we increase a weight for those two, the way it is
00:13:36.247 --> 00:13:46.048
become very, very small. Now, like that, we continue and
execute one of these prediction. And one of these innovation
00:13:46.048 --> 00:13:56.423
steps one after the other now, and that creates a filter
that is called a particle filter, or sometimes also called a
00:13:56.423 --> 00:14:06.609
condensation field @unoise@ okay. So, riding this down here
in a kind of stay of well transition diagrams of indicating
00:14:06.609 --> 00:14:17.179
the different steps so. We started the top um of this
diagram here. So we assume that we have given a random
00:14:17.179 --> 00:14:24.764
sample, a weighted random sample that describes the present
state distribution. So each particle is represented by state
00:14:24.764 --> 00:14:36.169
value X, I and a weight value W I. So now the prediction step.
What does it do? well, it keeps the weights as they are.
00:14:36.179 --> 00:14:46.848
So it doesn't change the weights and Ah, for the state
values X, I, it applies actually a ah conditional
00:14:46.848 --> 00:14:56.501
distribution um based on the present state value of the
particle that describes the um posterior distribution after no,
00:14:56.501 --> 00:15:05.645
sorry, not their posterior distribution that describes the
distribution of the state in the subsequent um. Subsequent um
00:15:05.645 --> 00:15:14.921
point in time, given the present state, just considering
the system dynamics. Yes of us. For simplicity, you might
00:15:14.921 --> 00:15:23.526
assume that this can be expressed by applying a deterministic
function onto X that describes how the state changes, plus
00:15:23.526 --> 00:15:32.101
an additional random noise that describes the uncertainty
in this transition process. But in general, we can write it
00:15:32.101 --> 00:15:42.208
down as a conditional distribution F that describes a
distribution of successful states. Given the present state, no
00:15:42.208 --> 00:15:53.463
@unoise@ okay. So that means, in this case, we sample. So
in this case, this should say we sample and you value X. I
00:15:53.463 --> 00:16:04.341
prime now for each particle based by taking a random sample
from this distribution @unoise@ so. That is a prediction
00:16:04.341 --> 00:16:13.755
step now we have a set of particles with the same number of
particles. The ways are the same, but the state values have
00:16:13.755 --> 00:16:23.744
changed. Now we execute the innovation step. Now we have
a measurement sad that we have observed, and we have a
00:16:23.744 --> 00:16:32.338
conditional distribution age that describes which the
distribution of measurements. Mhm, assuming that we know the true
00:16:32.338 --> 00:16:40.938
state of the system. So this describes the uncertainty
of the sensor. And in the simplest case, it can again be
00:16:40.938 --> 00:16:49.171
subdivided into a deterministic function that maps a state
on to a measurement plus a noise term, a random noise term
00:16:49.171 --> 00:16:57.390
that describes the error, the random error and of the sensor
and the uncertainty. Okay, what do we do in the innovation
00:16:57.390 --> 00:17:05.595
step? we keep the state rectors. As you can see, the Xi
primes here occur here again. So they are not changed at all,
00:17:05.595 --> 00:17:14.003
and but the weights are changed, though. Now we have these W
I prime weights, and those are taken from the previous W. I
00:17:14.003 --> 00:17:23.780
waits times the density function of this conditional measurement
density of the of the sense measurement said,"
00:17:23.780 --> 00:17:35.167
Given X, I prime the predicted state of the ice particle
@unoise@ okay um, this contains two things. Yeah, it is
00:17:35.167 --> 00:17:44.349
written here. It is proportional, too. So what do we do? first
of all, we multiply all the weights with the respective
00:17:44.349 --> 00:17:51.540
waiting factors. Age Ah of this given considering this
conditional distribution age, and afterwards we the
00:17:51.540 --> 00:18:00.272
weights. That means we sum up all the weights that we have
calculated and divide all these weights by this sum. So that
00:18:00.272 --> 00:18:10.346
finally um the the sum of all the new weights becomes
is one is equal to one. Okay, so now we have these um, the
00:18:10.346 --> 00:18:18.906
new particles that here. And this serves as starting point
for the next iteration. Now that means we so to say
00:18:18.906 --> 00:18:27.348
that we are done here and we can go to the next iteration,
starting from those wage weights, which and particles that we
00:18:27.348 --> 00:18:37.217
have just created. So that is the basic procedure of this kind
of particle filter. Well, @unoise@ so. Let us have a look
00:18:37.217 --> 00:18:45.109
at an example, a very simple example. So let us assume that I
want to represent the position of an object which moves in
00:18:45.109 --> 00:18:52.436
a two dimensional plain. Let us assume I know the velocity
and moving the movement direction of this object, namely, it
00:18:52.436 --> 00:19:01.685
is moving all the time to the right. And well, now let us
have a look. So now we start with a sample set that is
00:19:01.685 --> 00:19:10.436
uniformly distributed over the square that you can see
here. And now let us execute a first prediction step, then
00:19:10.436 --> 00:19:20.408
everything is moved to the right, and um spread a little
bit by random randomly afterwards. Ah, again, we get a
00:19:20.408 --> 00:19:28.602
measurement, which is now indicated with this green ah
asterisk @unoise@ and ah all the politics are they
00:19:28.602 --> 00:19:37.799
are given here by these ah, yellowish points. And again, we
see some of these points become became larger. That means
00:19:37.799 --> 00:19:46.264
they, their weights, become a larger and other points have
become smaller. Their weights have has decreased. Let us
00:19:46.264 --> 00:19:55.479
continue another predictions. Now we are here, the predicted
state distribution. Now we get a new measurement, and we
00:19:55.479 --> 00:20:02.959
all the particles. Now, things look like that. And let
us do another step. That is a predicted state distribution.
00:20:02.970 --> 00:20:11.499
Now we reweigh everything, and we end up like that. So over
these, in total three steps, we see that some particles
00:20:11.499 --> 00:20:19.549
became more and more important, and other particles become
became less important. And some of them, as you can see, are
00:20:19.549 --> 00:20:27.721
just very small points here. That means their weight is
really very, very small. If he would continue like that. We
00:20:27.721 --> 00:20:34.951
would observe um that more and more points become completely
unimportant, that for many, many points, the respective
00:20:34.951 --> 00:20:43.878
weights become zero or close to see him very close to zero,
where only a few points. Two, three, four points. And
00:20:43.878 --> 00:20:51.728
contribute with reasonably large weights to the whole
distribution. And that is a kind of degeneration of the particle
00:20:51.728 --> 00:21:00.364
cloud, because we could argue that those points which have
very small weights. They do not really contribute they
00:21:00.364 --> 00:21:07.880
create computational burden. We have to apply the innovation
and prediction step all the time for those points as well,
00:21:07.880 --> 00:21:14.873
but they do not help to represent this distribution. Now,
the distribution is only represented by those points with a
00:21:14.873 --> 00:21:22.583
reasonably large weight. And that would mean that we only
finally, after after many steps, only have two or three or
00:21:22.583 --> 00:21:28.809
four particles left, which really contribute to this representation.
That means we would have a poor representation that
00:21:28.809 --> 00:21:36.965
is a disadvantage of this method. And the question is, how can
we solve it? what do you? what aim to do as we would like
00:21:36.965 --> 00:21:43.280
to remove those particles with small weights, because they
do not help us to represent the distribution, and we would
00:21:43.280 --> 00:21:50.227
have to create new particles in the interesting area in that
area where we have a lot of large particles, how particles
00:21:50.227 --> 00:22:00.339
was a large weight? how can we do that in a sarcastically
sound way. Well, the idea is called woodstrapping or .
00:22:00.349 --> 00:22:07.850
And that is a technique that is has been introduced in in
statistics since the ninety in the nineteen eighties already.
00:22:07.859 --> 00:22:17.381
The idea is, we treat this random sample that we have as a
random sample, and we draw randomly from this random sample,
00:22:17.381 --> 00:22:24.932
where we interpret the weights as probabilities. Now that
means, if we have, say, three particles, the first particle
00:22:24.932 --> 00:22:34.706
has a weight of all point one. The second has a weight of all
point three say, and the third has a weight of six
00:22:34.706 --> 00:22:41.382
then we would randomly select the first particle with ten
percent probability, the second one with thirty percent
00:22:41.382 --> 00:22:51.081
probability, and the third one with sixty percent probability.
And we would repeat this process at all times, and to
00:22:51.081 --> 00:23:06.553
generate a new random sample from the same distribution now
@unoise@ so. What do we do in detail um? well, we take the
00:23:06.553 --> 00:23:19.085
weights, or the particles interpret that as probabilities,
then we randomly select particles. Now, using the weights as
00:23:19.085 --> 00:23:28.831
selection probabilities. We repeat this process as many
times as we have particles in the sample set and from the
00:23:28.831 --> 00:23:38.050
selected particles, we create a new sample set. And in this
new sample said each particle should have the same weight.
00:23:38.059 --> 00:23:49.530
Well, so how does it look like in this case? So this
is, say, the particle distribution with which we received up
00:23:49.530 --> 00:23:58.127
to now. We see there are really important particles that
contribute a lot that have large weights, and there are some
00:23:58.127 --> 00:24:06.712
particles which have very, very small weights, which do not
contribute very much, which you can see here just as very
00:24:06.712 --> 00:24:15.885
small points. Now we generate this process. So repeatedly,
we randomly select one of the particles. And that would mean
00:24:15.885 --> 00:24:23.557
in this case. After all, after doing this selection process,
we would select some of these particles several times, and
00:24:23.557 --> 00:24:31.997
some of the particles would never be selected. The numbers
for one experiment that I did are shown here with the red
00:24:31.997 --> 00:24:43.311
numbers. So for instance, this particles here on top. This
one here has not been selected at all. This one has elected
00:24:43.311 --> 00:24:53.790
once from this particle here we obtain it six times. And so
we have six copies of this particle and the new sample set,
00:24:53.790 --> 00:25:05.570
huh? so that means the new sample set is somehow the variant
of the old sample set And. Yeah that, means after
00:25:05.570 --> 00:25:13.531
all, the new sample set looks like that. However, some of
these points occur several times. And of course, plotting
00:25:13.531 --> 00:25:21.454
several points on top of each other, create something that
you cannot see here. Therefore, I just at some random noise
00:25:21.454 --> 00:25:29.825
yet, but just for visualization on it, so that you can see
where we get a lot of particles in which areas and where we
00:25:29.825 --> 00:25:37.102
don't get particles at all. What we can see is that in these
peripherical areas, um we lost particles because they do
00:25:37.102 --> 00:25:46.002
not contribute much. But in the central area, where the
probability is very large, we gained additional particles. That
00:25:46.002 --> 00:25:55.379
means in those areas, we have more particles available to
um model. The true probability distribution in more
00:25:55.379 --> 00:26:06.127
detailed way as before. While in these areas we
lost particles Uh we. We don't um. That is good because they
00:26:06.127 --> 00:26:15.735
are it. Is it is almost mhm very unlikely that
they represent the true position here, and therefore the true
00:26:15.735 --> 00:26:24.658
state value, and therefore we just remove it. We forget it.
We don't spend more computational time on these non
00:26:24.658 --> 00:26:32.526
promising areas of the state space @unoise@ so. Okay that,
is it so if we add this step, a bootstrapping or resembling
00:26:32.526 --> 00:26:40.720
step, we get a diagram like that. So the first step is the
same as we had before the prediction step. That is the same.
00:26:40.730 --> 00:26:49.085
The innovation step as well is the same as we had. But now,
instead of just using the resulting particles that directly
00:26:49.085 --> 00:26:58.312
for a starting point for the next iteration. We add this
resembling step here. That means we get take this partic
00:26:58.312 --> 00:27:08.290
assert, and then we randomly select particles from this
random set by sampling with replacement. And the the
00:27:08.290 --> 00:27:16.704
selection properties are chosen according to the weights of
the particles. The process that I just explain, and that
00:27:16.704 --> 00:27:27.354
creates a new M particle set that is used, then a starting
point for the next prediction star now. So that is a particle
00:27:27.354 --> 00:27:35.285
photo is resembling, and that is what typically is used in
practice so it is not necessary to do a resembling step
00:27:35.285 --> 00:27:43.794
in each cycle. So if you like to save time. You could
also say, okay, um, you execute, say, five cycles without
00:27:43.794 --> 00:27:51.753
resembling step. And after five cycles, you do a resembling
you at a resembling step, and then you again execute five
00:27:51.753 --> 00:28:00.241
cyclists without resembling step. And then again, due to
the resemblance that is also a very entered is possible
00:28:00.241 --> 00:28:10.403
@unoise@ okay. So, we will see a small example of that in
chapter number six, how this particle filtering works. It is
00:28:10.403 --> 00:28:18.185
often. It is used most often, actually, for robot localization
of a self localization. That is a topic in chapter six,
00:28:18.185 --> 00:28:27.973
and therefore we will see how it works in chapter six.
Okay, now let us have a look at the filters that we have
00:28:27.973 --> 00:28:37.964
introduced for the purpose of estimating the state
of a hid Markov model in a continuous state base um well,
00:28:37.964 --> 00:28:46.563
we started with a common filter that is the simplest technique.
The advantage is its quick, the complex the calculations
00:28:46.563 --> 00:28:55.316
are, can be done efficiently. However, it is limited to
linear Gulf models. However, if you are faced with the linear
00:28:55.316 --> 00:29:03.751
ghost models, a common fitter will always be more efficient,
more effective than all the other methods. Then we
00:29:03.751 --> 00:29:11.988
introduced the extended common filter and the unsented common
filter. Both are extensions of the common filter. They
00:29:11.988 --> 00:29:20.124
both, um assume, still assume Gauchian noise. That means
they are limited to caution distributions. They cannot
00:29:20.124 --> 00:29:29.252
represent other distributions and calculations, but with
those, it is possible to deal systems which have a nonlinear
00:29:29.252 --> 00:29:38.240
transition function or an nonlinear, a measurement function.
As long as those functions are derive, uh, differentiable.
00:29:38.250 --> 00:29:45.882
It is possible to use those filters. And of course, different
different trouble functions can be highly complicated. It
00:29:45.882 --> 00:29:54.350
can still be highly complicated their functions must be.
It must be possible to linearize them to approximate them
00:29:54.350 --> 00:30:02.977
by low. Is functions linear functions they are
still computationally cheap, so it is still not too too
00:30:02.977 --> 00:30:12.125
expensive. It doesn't require too much time in a computer
implementation to have them. And still they are accurate and
00:30:12.125 --> 00:30:19.229
highly accurate. Now, the most general thing is the particle
filter. It can represent arbitrary distribution. So it is
00:30:19.229 --> 00:30:26.129
not limited to caution distributions any more. You can also
represent other kind of distributions with it. You can even
00:30:26.129 --> 00:30:34.343
mix continuous and discreet random variables in the state
space, if you like. So for instance, if you want to model a
00:30:34.343 --> 00:30:42.834
car that drives along a road and arrives at an intersection,
you might have some, and you want to describe the position
00:30:42.834 --> 00:30:50.363
and driving direction of the vehicle. You might have some
continuous values that you want to estimate, like the position
00:30:50.363 --> 00:30:57.806
draw an et cetera. But maybe you also want to model some
discrete things, like, does the vehicle follow the straight,
00:30:57.806 --> 00:31:05.852
rode on at the intersection, or does it turn right, or does
it turn left @unoise@ that would be a discreet random, very
00:31:05.852 --> 00:31:13.022
apple that you might also consider @unoise@ that is possible
with a particle filter @unoise@ but. That is not possible
00:31:13.022 --> 00:31:19.621
for the Carman filter @unoise@ extended Carmen filter
Yeah the operations are sampling and resembling
00:31:19.621 --> 00:31:28.916
operations. So I'm not doing some algebraic calculations with
with mattresses. But now we are only faced with sampling
00:31:28.916 --> 00:31:37.332
and resembling operations, of course, doing that for a single
particle is computationally not very expensive. But since
00:31:37.332 --> 00:31:47.163
we need a lot of particles. The whole um approach requires a
lot of computation time. And the more particles you have,
00:31:47.163 --> 00:31:57.029
the higher will be the accuracy that you achieve. Well, that
means it is. You always have to balance somehow. How much
00:31:57.029 --> 00:32:05.246
time do you have computational time? do you have to execute
the parting filter @unoise@ and which accuracy do you need
00:32:05.246 --> 00:32:13.834
for your application. Now, the typical number of particles
that are used in partic filters range between, say, something
00:32:13.834 --> 00:32:23.598
like one hundred and maybe ten thousand, depending on the
accuracy that you want to have, but still ten thousand. Ah,
00:32:23.598 --> 00:32:32.496
would not not really that much. If you really want to approximate
a distribution accurately, a complicated distribution
00:32:32.496 --> 00:32:40.069
accurately @unoise@ okay. So, far the comparison of these
filters. And with this, we can complete the chapter on
00:32:40.069 --> 00:32:48.274
tracking @unoise@ and filtering methods so. We started with
tracking by regression @unoise@ and ah to say that although
00:32:48.274 --> 00:32:57.570
these Carmen filter and things @unoise@ sound really
nice and and and and ball. Many a very general purpose and
00:32:57.570 --> 00:33:06.633
generic. Don't forget that you can also use regression for
it. It is useful. It is often useful, and is often easier to
00:33:06.633 --> 00:33:16.825
use than a common filter approach, or an Ek, E, K, F, Uk, or
even a particle theatre. Then we ah discussed the Markovian
00:33:16.825 --> 00:33:25.917
transition systems. Ah, the hidden Markov model. And we
described them in a probabilistic way um. And those, of course,
00:33:25.917 --> 00:33:35.033
um are the basis for the Karlman filter and the extended
common filter party of filter then we derived the common
00:33:35.033 --> 00:33:43.734
filter we introduced what a linear gauge model is
derived, the common filter basin that and the extensions E, K,
00:33:43.734 --> 00:33:54.922
F, U, K, F @unoise@ and um we also um discuss how we can
use the U K to do an eagle motion estimation for an
00:33:54.922 --> 00:34:01.991
autonomous vehicle @unoise@ and. Finally today, we were talking
about the particulator important sampling and the basic
00:34:01.991 --> 00:34:11.484
particle filtering steps and the resembling step. Okay, so
far, this chapter number five of the lecture. So do you have
00:34:11.484 --> 00:34:23.003
questions at the moment about chapter number five, which
you want to ask," Mhm, oh, I don't see anyone." so we can
00:34:23.003 --> 00:34:31.859
immediately go to chapter number six. And there we will get
see again those techniques that we just introduced. So
00:34:31.859 --> 00:34:40.545
and and and particle filter so we can see chapter
number six are the chapter in which we apply those techniques
00:34:40.545 --> 00:34:49.582
which we have just introduced. What is chapter number six
about it is about self localization and mapping. So um in
00:34:49.582 --> 00:34:58.399
autonomous driving, knowing the position of the vehicle is
one of the most important things, and actually the current
00:34:58.399 --> 00:35:07.216
impressive development in automotive drive in autonomous driving
is heavily driven by the fact that people found that it
00:35:07.216 --> 00:35:17.889
is a good idea to use a map, a detailed map that contains a
lot of information about the environment that contains the
00:35:17.889 --> 00:35:26.706
rogioometry that contains the traffic regulations % uh
and and % um regulations at intersections
00:35:26.706 --> 00:35:38.408
et cetera um if we know where we are that simplifies a lot
driving, because then we can look up in the map. Where is the
00:35:38.408 --> 00:35:47.627
lane that we want to follow, which is the maximum speed that
is allowed here. Um, what is the radius of the curve in
00:35:47.627 --> 00:35:56.144
front of us. So which speed can we drive without without %
uh, risking an accident, etcetera, etcetera. So the only
00:35:56.144 --> 00:36:03.814
thing that remains that we have to perceive. So to say is
the things that change, that are dynamic, like other
00:36:03.814 --> 00:36:11.095
traffic participants, et cetera. But the Roger geometry usually
doesn't change. So we can rely on the map, Ok? but for
00:36:11.095 --> 00:36:18.638
that, we need techniques first to create a map, a detailed
map, and we need techniques also to local is to localize
00:36:18.638 --> 00:36:29.403
ourselves in the map. That means to know where we are and
the accuracy that we need is much higher than what is
00:36:29.403 --> 00:36:38.293
provided, for instance, by your smartphone that is using
satellite navigation, and maybe some, some other um wireless
00:36:38.293 --> 00:36:47.605
networks that it detects and based on which it determines
its position. Um no, this accuracy is not enough for our
00:36:47.605 --> 00:36:56.980
purpose. So what we want to have is an accuracy um that is has
an error that is below, say, ten centimeters, and that is
00:36:56.980 --> 00:37:05.390
not provided usually by those systems. So what could we do
instead? first of all, I had left. Let us have a look at
00:37:05.390 --> 00:37:12.349
literature. So what you could consider for for this chapter
is either the book of and Fox about probabilistic
00:37:12.349 --> 00:37:19.850
robotics. There are several chapters about the topic of self
localization and mapping @unoise@ you. Could also consider
00:37:19.850 --> 00:37:26.517
this two journal articles survey articles about simulated
simultaneous localization and napping from White and
00:37:26.517 --> 00:37:36.935
Bailey, or in the spring or hunt book of robotics as a chapter
on self localization, or if you like to have a book in
00:37:36.935 --> 00:37:45.686
German, you can consider the Book of Yarn hatsback
and about mobile robots they also are very active
00:37:45.686 --> 00:37:55.256
in this area, and also have two chapters about this topic
in their book. Yeah, the last um. The last reference is a
00:37:55.256 --> 00:38:02.552
reference that introduces the algorithm, the iterative
closest point algorithm. And so it is an original paper
00:38:02.552 --> 00:38:11.555
that you might consider if you are interested in reading that,
that okay, so now let us go. What do we want to do so let
00:38:11.555 --> 00:38:19.247
us first consider the problem of self organization. So we are
on a mobile robot or a mobile vehicle, and we want to know
00:38:19.247 --> 00:38:29.925
where we are. We assume that we have a map now, and we can
look up in the map, why we get information about @unoise@
00:38:29.925 --> 00:38:39.169
structures in the world @unoise@ we do not know the vehicle
position and the vehicle orientation and what we are able
00:38:39.169 --> 00:38:46.592
to. We have some senses on board of the vehicle with which we
can observe the environment, the local environment, around
00:38:46.592 --> 00:38:56.134
the vehicle. So how can we? so here is an example, not from
autonomous driving, but from autonomous soccer playing. So
00:38:56.134 --> 00:39:06.231
let us assume we have some soccer robots. They have cameras
on board, and they are playing on such a soccer field as
00:39:06.231 --> 00:39:16.333
shown here and at top you. So the camera view of the robot
might look like the picture on the right inside. What we see
00:39:16.333 --> 00:39:24.718
is a little bit the soccer field, the green areas as well.
We see some markings, some field markings on the soccer
00:39:24.718 --> 00:39:33.294
field. Then there are some other dynamic objects which which
we see, which are not part of the map, like the ball or
00:39:33.294 --> 00:39:40.647
other other robots that are participating in this soccer
game. And of course, what we want to. We want to take this
00:39:40.647 --> 00:39:48.461
camera image. And based on this camera image, find out where
we are in the soccer field. And if you are a face with such
00:39:48.461 --> 00:39:56.140
an image, you might say, okay, with a little bit of thinking,
you might say, Ok, the robot is here somewhere here and
00:39:56.140 --> 00:40:03.114
looks into this direction that is indicated by the arrow.
So unfortunately, in this case, it field is symmetric. That
00:40:03.114 --> 00:40:12.413
means there is not a unique position, but there is also a
position here which looks exactly the same. So we are either
00:40:12.413 --> 00:40:21.980
here or we are here. That is what we can conclude from this
image that we see, and that is actually the idea that we
00:40:21.980 --> 00:40:31.133
want to follow. So we observe the environment, we look at
things that we see in the environment that are part of the map
00:40:31.133 --> 00:40:40.432
that we can determine. And based on that, we want to calculate
where we are. So all these things that we observe in the
00:40:40.432 --> 00:40:48.744
environment, that we can find in the map, again, that we can
use for surf localization are called landmarks, though. The
00:40:48.744 --> 00:41:00.421
typical classical example of a landmark is a lighthouse. So
in in um, the um @unoise@ navigation on the sea. Of course,
00:41:00.421 --> 00:41:08.731
the people had the problem to find out where they are also in
centuries ago. And what they did is while they were either
00:41:08.731 --> 00:41:17.428
using the stars to look in the sky, look, see the stars. And
then they knew where the stars are in the season. And based
00:41:17.428 --> 00:41:25.241
on that, they were calculating where they are. And if they
were close to the shore, they build lighthouses or other um
00:41:25.241 --> 00:41:33.061
objects, high buildings that can be could be seen from from
ships on the sea. And then they were looking at that. They
00:41:33.061 --> 00:41:40.288
were, eh, finding out," Okay, this is the lighthouse from
that is um Ah, located at a certain position. The positions
00:41:40.288 --> 00:41:48.301
were written in maps, and based on that, they were calculating
where they are unseen. Ah, so a lighthouse would be a
00:41:48.301 --> 00:41:55.947
very classical idea of a landmark. But of course, it is not
the only landmark that exists. And for autonomous driving on
00:41:55.947 --> 00:42:04.208
the roads. Of course, there are no lighthouses. We have to
think about other landmarks, but of course, around in cities
00:42:04.208 --> 00:42:13.540
and on roads. There are, again, some other kind of landmarks
which could be useful. So for instance, on road we have
00:42:13.540 --> 00:42:20.889
lain markings, which we could use in cities. We have buildings
which we could detect. We have traffic signs, may be that
00:42:20.889 --> 00:42:28.065
we could detect and use it landmarks. So all these structures,
which are fixed at a certain position, which are not
00:42:28.065 --> 00:42:35.286
changing their position, which we could identify, which you
can find with senses sea with our sensors and identify which
00:42:35.286 --> 00:42:43.251
land my greasy. Okay, so what can we conclude from that? I
assume that we are in a two dimensional world. So we assume
00:42:43.251 --> 00:42:50.867
that the word is flat, and we only. We need to determine the
position and the orientation of the vehicle in this flat
00:42:50.867 --> 00:42:58.350
environment. So we don't want to deal at that point with the
three dimensional mapping of the word. Okay, what can we
00:42:58.350 --> 00:43:07.048
conclude from that? so assume we are given such a, we can
detect such a landmark, and we can measure the distance to the
00:43:07.048 --> 00:43:14.203
landmark. So what can we conclude? so obviously, if now, okay,
the landmark is a certain position, and the distance that
00:43:14.203 --> 00:43:21.771
we have from the landmark is whatever one hundred meters.
Then what we could do is we could draw a circle around the
00:43:21.771 --> 00:43:30.114
landmark in the map. And we would know that we are on that
circle. Ah, maybe we have some measurement noise. It means
00:43:30.114 --> 00:43:38.528
maybe we are not exactly on that circle, but somewhere um
around the circle. Ah, that is the most likely position
00:43:38.528 --> 00:43:47.340
@unoise@ that. Means um from. These point wisely appoint
landmarks. If you know distances, we can restrict our position
00:43:47.340 --> 00:43:55.754
to circles if we have two um landmarks. Now we can draw two
circles, and then we get some points of intersection. And
00:43:55.754 --> 00:44:03.409
based on these points of intersection. We know we are at one
of these points of intersection. Oh, @unoise@ of. Course
00:44:03.409 --> 00:44:12.369
if, we have three landmarks and we get a third circle, and
we could determine our position in a unique way @unoise@ um.
00:44:12.380 --> 00:44:22.640
Okay, so um. However, not all the senses provide distances,
and especially if landmarks are far away, the distance
00:44:22.640 --> 00:44:31.227
measurement becomes difficult. So however many senses provide
angles. So if we have a monocular camera, what we can
00:44:31.227 --> 00:44:40.671
determine is the angle at which we see an object object, a
landmark that is very accurate, but determine the distance
00:44:40.671 --> 00:44:50.161
arm is very difficult. So what can we conclude from angles?
so assume we have one landmark, and we now the angle at
00:44:50.161 --> 00:44:58.335
which we see it, then still we cannot determine a position,
but assume we would know the position, what we could
00:44:58.335 --> 00:45:06.540
determine would be the orientation of the Robert. Well, that
means we could argue if the robot would be located here.
00:45:06.550 --> 00:45:15.156
And the landmark is here, and we see the landmark under a
certain angle than we could determine the viewing direction of
00:45:15.156 --> 00:45:25.402
this mobile roboty. That means, still, we do not know where
it is. It still could be here and here as well. But we can
00:45:25.402 --> 00:45:35.279
at least restrict the orientation of the robot. If we have
at least two landmarks and we can observe the angle
00:45:35.279 --> 00:45:44.600
towards both of those landmarks. Then there is a theory from
a geometry that says that in such a case, we can restrict
00:45:44.600 --> 00:45:53.625
the position of the Robert to a circular arc, to a piece of
a circle. Now that is indicated here. So with this theorem
00:45:53.625 --> 00:46:01.464
that we don't discuss in detail here, but that exist. We
can draw a circle that connects the two landmarks that we
00:46:01.464 --> 00:46:10.479
observe. And we know that the robot must be located on one
point on this part piece of the circle that you can see. Now,
00:46:10.479 --> 00:46:20.054
that means even with angles, if you just see angles can measure
angles. We can determine positions of the Robert. If we
00:46:20.054 --> 00:46:27.729
have three landmarks and can observe three angles. Then we
can determine the position at which the robot is located.
00:46:27.739 --> 00:46:36.863
Well, that means angles are very powerful, although they don't
provide ah metric information. They are powerful, and we
00:46:36.863 --> 00:46:46.953
can determine the position of the robot based on angles. Mhm.
So these landmarks, which are just points are one possible
00:46:46.953 --> 00:46:57.168
kind of landmarks and of course in this robot soccer
example, as well as in autonomous driving, we might be faced
00:46:57.168 --> 00:47:06.455
very often also with landmarks, with objects that are not
points, but that are lines or line sections or elongated
00:47:06.455 --> 00:47:15.474
structures. And these, of course, are also very useful. So in
the soccer field, these would be the the field markings in
00:47:15.474 --> 00:47:23.470
the autonomous driving domain. This might be road markings
or curb stones. Yeah, that are also elongated objects or
00:47:23.470 --> 00:47:32.935
walls next to the road are walls of of houses. For instance,
the states of houses that are also kind of elongated
00:47:32.935 --> 00:47:42.107
structures which do not cannot be treated in the same way as
these point landmarks that we just disgust. However, still
00:47:42.107 --> 00:47:50.092
we can draw conclusions from those, especially if we can
measure distances, orthogonal distances of our vehicle with
00:47:50.092 --> 00:48:00.392
respect to these elongated structures. That means, if this is
the line, a linear structure in the map, the red one here,
00:48:00.392 --> 00:48:11.182
and we can send the orthogonal distance of offer of the
autonomous robot of a vehicle which is back to that line. What
00:48:11.182 --> 00:48:18.953
we can conclude is that the Robert is either on the blue
line here or on that blue line. So we create pearl lines,
00:48:18.953 --> 00:48:26.895
parole to the structure that we observe, and we can limit
our own position to them. These two lines. That means those
00:48:26.895 --> 00:48:35.299
odd, these linear structures, elongated structures, also
provide valuable information about the position of an object,
00:48:35.299 --> 00:48:43.428
of course. Ah, if we have several lines um two lines, for
instance, like that. We get such a situation, and then we get
00:48:43.428 --> 00:48:50.809
some points of intersection, and we can conclude that the
robot or the vehicle must be located at one of the points of
00:48:50.809 --> 00:49:00.144
intersection. Well, @unoise@ okay. That, means birth linear
structures as well as point structures can be used as
00:49:00.144 --> 00:49:08.482
landmarks, both provide valuable information about the
position of the ego vehicle. Now let us start with the first
00:49:08.482 --> 00:49:15.699
mathematical approach, the first algorithm to determine the
position of an object. We assume pointland marks. That means
00:49:15.699 --> 00:49:26.139
landmarks with just which just consists of out of single
point. Let us assume we are given a map, as shown here on the
00:49:26.139 --> 00:49:35.691
top right, a corner of this light. We have a world coordinate
system that is the coordinate system in which the map is
00:49:35.691 --> 00:49:42.529
described. That is this coordinate system with the coordinate
Exxis and Eta. And we assume in this case that we are
00:49:42.529 --> 00:49:48.659
faced with eight point land marks P, one, two, P, A. We know
the position of those landmarks with respect to the World
00:49:48.659 --> 00:49:56.453
Court in a system that is the information that is given by
the map. Now we assume that our vehicle that is shown here
00:49:56.453 --> 00:50:04.306
observes some of those pointland marks and the relative
position of those point land marks which are observed, we
00:50:04.306 --> 00:50:12.780
suspect to the vehicle coordinate system that is provided
here with the two coordinate axis accent. Why is given by
00:50:12.780 --> 00:50:21.726
these to three and Q five. So the vehicle, in
this case, observes the landmarks number two, three, four and
00:50:21.726 --> 00:50:29.986
five only, and we get the relative position of the landmarks
with respect to the Eagle League. So we might assume that
00:50:29.986 --> 00:50:38.224
we have Binoc, a camera system that is determining the
relative position. Now, the question is, well, how can we
00:50:38.224 --> 00:50:47.126
determine the position of the vehicle based on this information.
That means, how do we rotate and shift the world
00:50:47.126 --> 00:50:54.828
the vehicle coordinate system, respect to the world court in
that system @unoise@ such that the sensed positions and the
00:50:54.828 --> 00:51:03.664
positions in the map fit together as best as possible. Ah,
that is the task. How can we do that? what we will get at the
00:51:03.664 --> 00:51:10.684
end is a translation factor that describes the to the offset
of the vehicle coordinate system with respect to the word "
00:51:10.684 --> 00:51:20.521
court " in its system. That is the and a rotation matrix
that describes in which way we have to rotate the vehicle
00:51:20.521 --> 00:51:28.753
coordinate system, such that the landmarks, the observed
landmarks, fit as best as possible to the landmarks in the
00:51:28.753 --> 00:51:39.979
@unoise@ so. How do we do that @unoise@ ok so now
comes a little bit of mathematics. So the position of the
00:51:39.979 --> 00:51:50.381
landmarks in the world. Coordinate system is described by
these P I vectors. So P I is the position of the ice landmark
00:51:50.381 --> 00:52:01.677
in the map represented in the World Court in its system, then
we have a set of observed landmarks, and we represent the
00:52:01.677 --> 00:52:11.009
relative position of those landmarks with us, packed to the
vehicle coordinate system as so
00:52:11.009 --> 00:52:23.920
assume we assume we observe the first N landmarks. Well,
okay. So what do we want while we want to find a
00:52:23.920 --> 00:52:33.920
translation vector T, and the rotation metrics are such
that if we shift the vehicle coordinate system by the
00:52:33.920 --> 00:52:43.280
translation vector T and rotated by the rotation. Metrics are
@unoise@ after. Doing that the, observed landmarks and the
00:52:43.280 --> 00:52:52.935
land. My positions in the map should be as similar as
possible. That means what we want is we want to minimize the
00:52:52.935 --> 00:53:01.309
discrepancy between what we observe and what we have in the
map. And this discontancy is described here in this formula.
00:53:01.309 --> 00:53:11.563
So here this sum runs over all observed landmarks from one
to N. What does he do while it compares the of a
00:53:11.563 --> 00:53:20.377
landmark in the world with that position. What is it? well,
that is the observed position of the landmark relative to
00:53:20.377 --> 00:53:27.573
the vehicle coordinate system and multiplying it with the
rotation matrix and adding the translation vector is nothing
00:53:27.573 --> 00:53:34.370
else that transforming that position into the world coordinate
system, assume a certain translation vector and rotation
00:53:34.370 --> 00:53:46.297
metrics. Now, that means the term in brackets is nothing else
than the position of the observed landmark. Translated to
00:53:46.297 --> 00:53:55.564
the word coordinate system, assuming a certain position and
orientation of the autonomous vehicle. So we compare those
00:53:55.564 --> 00:54:06.448
two. And of course we wanted this. They are most similar.
That means we want to minimize the squared distance of those
00:54:06.448 --> 00:54:15.852
two positions. Now, of course, a priori, we do not know the
translation vector in the rotation matrix. So um, we have to
00:54:15.852 --> 00:54:25.373
search for it. That means we want to minimize this term here
with respect to these unknown parameters, T and R. How can
00:54:25.373 --> 00:54:36.051
we do that efficiently? so so that is what I already said
so now. Okay, so this is the arrow term that we want to
00:54:36.051 --> 00:54:48.664
minimize, depending on the unknown variables R and T. Now we
do a little bit of a transformation we introduce, we first
00:54:48.664 --> 00:54:59.737
calculate the average position of the landmarks. That is
yeah. That is just calculating the average of the
00:54:59.737 --> 00:55:10.703
landmark positions in the map well, and the other term
is nothing else than the average of the observed positions
00:55:10.703 --> 00:55:20.636
in vehicle coordinates. What you do is we introduce them new
variables prime by subtracting the average position
00:55:20.636 --> 00:55:31.083
from Pi, and as well for prime we introduce nuclear
prime by subtracting the average position of the observed
00:55:31.083 --> 00:55:39.771
landmarks from . This is a kind of simplification before,
because then afterwards, the whole calculations become
00:55:39.771 --> 00:55:49.655
simpler. Ah, but actually, yeah, it is. It is nothing
magical. What happens here? it is just to simplify the
00:55:49.655 --> 00:56:02.198
calculations in later stages @unoise@ okay. If, we do that
and replies Pi by P, I Prime Plus P Bar and Q I by
00:56:02.198 --> 00:56:14.570
then we get this term here at the bottom.
Yeah, so now let us simplify that. So we start here at the
00:56:14.570 --> 00:56:25.044
top in the top row. That is the function that we want to
minimize. So now we rearrange the different terms in this ear,
00:56:25.044 --> 00:56:35.706
in this formula. And by doing that, we get the second role,
and obviously what we see is, Ah, well, this goes here. This
00:56:35.706 --> 00:56:46.744
term here goes here. This term goes here. This product goes
here, and this term goes here. So it is just reordering the
00:56:46.744 --> 00:56:55.636
different terms. And in multiplying out the second party
on this part with the rotation matrix. So nothing strange
00:56:55.636 --> 00:57:09.372
happened here. The next step here is that we split up this
quiet distance term here at this point so we split it
00:57:09.372 --> 00:57:23.316
up and then we get while this is equal to actually the
first part, plus the second part, plus the make two times
00:57:23.316 --> 00:57:36.132
the next mixed product. Yeah, this is just a binomial equation
used for Ah video, Euclidean distance. So it is nothing
00:57:36.132 --> 00:57:44.443
magic. Again, it is just using the fact that we can represent
the squared in distance as the dot product of a term
00:57:44.443 --> 00:57:52.686
with itself. And then we use the linearity of the dock product
operation to split it up into different subterbs now, but
00:57:52.686 --> 00:58:03.908
nothing magic. Just simple. Executing this step, then we get
this term here @unoise@ now. We keep the first two terms as
00:58:03.908 --> 00:58:13.501
they are. And we factor out all germs here in the third term
that do not depend on eye on the running variable eye. So
00:58:13.501 --> 00:58:22.987
this is especially this first factor. It does not depend on
eye so we can factor it out and your and then are we? what
00:58:22.987 --> 00:58:32.556
remains is actually this term here. The second term in brackets,
and we split it up into two now. So we push this
00:58:32.556 --> 00:58:43.662
some symbol. So to say @unoise@ % um to hear
@unoise@ and um split it up into these two terms. But still,
00:58:43.662 --> 00:58:53.420
there is nothing magic going on. It is just simple calculations.
So then we observe that this term is equal to zero. Why
00:58:53.420 --> 00:59:04.387
is it equal to zero? because we define these Pi prime terms
by subtracting the ever rich position from the sent from
00:59:04.387 --> 00:59:13.068
from the map positions. That means, after doing that, the
ever average position of these Pi prime values must be equal
00:59:13.068 --> 00:59:22.827
to zero. And as well for this term. This is the average
position of the prime values. And since we subtracted the
00:59:22.827 --> 00:59:31.370
average already from it. For the prime terms the average
that means this term here in brackets is equal to
00:59:31.370 --> 00:59:39.659
Cyril, and that means the whole third part, the third piece
of this term here can be neglected. It is equal to Sierra.
00:59:39.670 --> 00:59:50.259
What remains is the first and the second part. Furthermore,
if we look at this term, we observe that T, the unknown
00:59:50.259 --> 00:59:59.679
translation vector only occurs in the second piece. In this
part, the first part is completely independent of tea. And
00:59:59.679 --> 01:00:09.353
furthermore, we can see that, well, we can doesn't matter
which value for are we choose for the rotation matrix, we can
01:00:09.353 --> 01:00:20.838
always find a value for tea that makes this term equal to
zero. Amy, if you choose tea equal to minus then
01:00:20.838 --> 01:00:30.902
this term here inside is always a Cyril vector. That means
we minimize this arrow term we suspect to tea. If we choose
01:00:30.902 --> 01:00:39.727
tea equal to peep our minus autumn's . Then if you choose
it like that, then this term becomes zero as well. What
01:00:39.727 --> 01:00:49.306
remains is only the first popular, which only depends on the
rotation matrix. And so we can, they resolve. We can solve
01:00:49.306 --> 01:01:01.400
this task if we minimize this first term @unoise@ ok
we can split this term into pieces again. It is again
01:01:01.400 --> 01:01:11.635
the square the square you cleaned lengths of a
factor, and we can split it up by using the calculation laws
01:01:11.635 --> 01:01:20.279
for the dot product into these pieces. So it is actually
just the square lanterns of Pierre Prime, plus the of
01:01:20.279 --> 01:01:29.143
mine is two times this mixed mixed term here. And we
see that the first and the second term, again, do not depend
01:01:29.143 --> 01:01:37.375
on our on the rotation matrix, though. They are just constant
offsets, which do not depend on our choice of R. So the
01:01:37.375 --> 01:01:46.702
whole term only depends on the third term. That means, if we
want to minimize this term here. What we have to do is we
01:01:46.702 --> 01:01:55.204
have to maximize this part here so maximized, because we
have the minus here in front. We have to maximize this term
01:01:55.204 --> 01:02:05.370
now. So that is what we have to do maximize this term.
Okay, so now, how can we do that? so there are different
01:02:05.370 --> 01:02:12.269
approaches. I just mentioned one of those here, the so called
singular, the method by the singular value decomposition.
01:02:12.280 --> 01:02:19.289
I don't know whether you ever heard about this technique,
singular value decomposition. However, it is a technique from
01:02:19.289 --> 01:02:26.272
linear algebra, which is quite powerful and quite useful
for many numerical calculations. What a single our value
01:02:26.272 --> 01:02:35.811
decomposition do is. Oh no, we go to that later, but first
we have to do another transformation. This term. If we
01:02:35.811 --> 01:02:46.608
look very carefully at it. And ah, then we will find out that
this term is exactly the same as this term. The trays of
01:02:46.608 --> 01:02:58.995
the matrix R times prime time transpose @unoise@
okay when i Look at that I also don't trust it. And then I
01:02:58.995 --> 01:03:07.045
take a a piece of sheet of paper. And I write down this term
and look what the result is. And then I look at the result
01:03:07.045 --> 01:03:14.117
of this term. And then I see, okay, it is really the same.
So I don't know how you event this equality. Yeah, how you
01:03:14.117 --> 01:03:22.639
find out that it exists, but you can check it is really true
though. It is a trace of this matrix, and this is actually
01:03:22.639 --> 01:03:32.669
equal to the trace of the rotation metrics times a matrix
age, which is composed like that, huh? so this sum here goes
01:03:32.669 --> 01:03:44.980
into inside of the trays function. And we can fact out on
the rotation matrix, and then we get that one. So still not
01:03:44.980 --> 01:03:54.078
magic. Now comes magic. So um, the support, the singular value
decomposition states that doesn't matter which matrix H
01:03:54.078 --> 01:04:04.596
we have. So that applies for all mattresses age. We can um
factorize such a matrix into three factors. Laughter also in
01:04:04.596 --> 01:04:14.988
all matrix, you an all signal matrix V and a diagonal matrix
D. No diagonal matrix means a square matrix, you know, and
01:04:14.988 --> 01:04:23.448
not necessarily a squaremat is erected by a matrix that has
the same dimension as H, and with zero elements everywhere,
01:04:23.448 --> 01:04:35.286
except on its diagonal. Yeah, @unoise@ so. That is a general
result from the . We can find such a factorization for
01:04:35.286 --> 01:04:47.649
every matrix H that can be calculated for for all mattresses,
age and um. It holds that H, then is equal to the product
01:04:47.649 --> 01:04:57.338
of U, D and V transpose. And there are algorithms that calculate
the um, this singular value decomposition on the basis
01:04:57.338 --> 01:05:06.640
of an iterative process. The details are too complicated
for here. But typically, if you search for A for a library
01:05:06.640 --> 01:05:14.208
about linear algebra. You will find some function that is
calculating the singular value of decomposition for you. Okay,
01:05:14.208 --> 01:05:23.601
let us assume we can do that. We can take this matrix H and
calculate the singular Valujet composition from it. @unoise@
01:05:23.601 --> 01:05:34.142
then there is a theory that states that the solution of this
optimization problem here, not to maximize this term is
01:05:34.142 --> 01:05:43.584
equal to either the matrix V times you transpose. If the
determinant of three times you transpose is plus one or three
01:05:43.584 --> 01:05:52.262
times while this matrix here, this diagonal matrix, which has
a minus one here, and it is in the third entry times you
01:05:52.262 --> 01:06:02.846
transpose. If the determinant of you transpose is
equal to minus one. Mhm. Oh, okay. I realize that this is a
01:06:02.846 --> 01:06:11.551
little bit might look a little bit strange at the moment to
you, because I was always talking about a flat world and the
01:06:11.551 --> 01:06:19.866
two dimensional coordinates. And here we have three dimensional
matrices @unoise@ okay. I, Was just shifting without
01:06:19.866 --> 01:06:27.012
telling it to three dimensional coordinates. Yeah, so this
is a method for three dimension accordance, as it is shown
01:06:27.012 --> 01:06:34.096
here. The same method can be used for two dimensional
accordance as well. If we assume a flat world, then this matrix
01:06:34.096 --> 01:06:43.252
here in the middle is a diagonal matrix at just as just the
entries one and minus one. Well, okay, but it can also be
01:06:43.252 --> 01:06:51.594
used in the sweet dimensional case. Then we have this matrix
here @unoise@ okay. So, the proof, if you are interested in
01:06:51.594 --> 01:07:02.121
the proof that this really maximizes this term. And look at
this paper here @unoise@ yeah. It, is described here
01:07:02.121 --> 01:07:09.876
it is yeah. You have to spend some time to understand it, but
it is possible. It is based on some basic mathematics that
01:07:09.876 --> 01:07:17.411
you might have heard in the basic classes on math. And but
it is a little bit technical. And therefore I think that I
01:07:17.411 --> 01:07:25.674
don't want to show you here in detail @unoise@ okay. So, the
good message is there is a mathematical way to calculate
01:07:25.674 --> 01:07:33.469
that, to calculate the solution of our optimization problem.
First, we do that. We calculate this matrix H, then we
01:07:33.469 --> 01:07:41.821
calculate the singular Valujet composition for it. And then
we calculate the times you transpose all the times. This Ah
01:07:41.821 --> 01:07:50.510
reflection matrix times as a result. And by doing that,
we get as result, the rotation matrix are that we need.
01:07:50.519 --> 01:08:02.557
And based on the rotation matrix are we can calculate the
translation vector T, mhm, okay, that is the nice thing. And
01:08:02.557 --> 01:08:13.577
based on that, we can take landmarks that we observe. And
based on that, and a map in which the two position of those
01:08:13.577 --> 01:08:23.946
landmarks are can be found. We can calculate the eager
position and the eagle. Yeah, it is the eagle position and
01:08:23.946 --> 01:08:33.600
the eagle orientation of our vehicle. However, in practice,
unfortunately, the world is often not that nice as it seemed
01:08:33.600 --> 01:08:41.543
to be, because in practice, often it happens that we cannot
identify the landmarks uniquely. That means we see there is
01:08:41.543 --> 01:08:48.759
a landmark of a certain type, but we are not able to say
whether it land in this landmark number one, two, three or
01:08:48.759 --> 01:08:57.918
four. And think about the case where you use, for instance,
say traffic signs as landmarks. Well, you see a traffic
01:08:57.918 --> 01:09:07.655
sign, and you have a lot of traffic signs in the map. But
of course, um traffic signs, several traffic signs look
01:09:07.655 --> 01:09:16.869
exactly the same. Well, some traffic signs can be distinguished.
Yeah, but for others, they look the same. And we do not
01:09:16.869 --> 01:09:24.764
know which of those different instances of the same kind of
traffic sign do we see? then we have. We are faced with the
01:09:24.764 --> 01:09:31.641
situation where we cannot uniquely identify which land mark
we observe. We know it is a landmark of that type. And we
01:09:31.641 --> 01:09:40.611
find several of possible landmarks in the map, which we could
see. But we do not know which one of those. And then we
01:09:40.611 --> 01:09:49.029
cannot say which Pi refers to, which and then the method
that we just introduce is not sufficient. However, still
01:09:49.029 --> 01:09:58.224
there is a possibility to solve this problem. What we could
do in general is a brute for search. We could check which
01:09:58.224 --> 01:10:06.890
combinations would be possible. And for each combination, we
would calculate this error term with the position and the
01:10:06.890 --> 01:10:14.256
resulting arrow, and then afterwards select the smallest
possible error that is possible, but this is computationally
01:10:14.256 --> 01:10:22.921
too expensive in practice. So we need another algorithm that
iteratively does this search for us. And the result is a so
01:10:22.921 --> 01:10:31.497
called I, C, P, iterative closest point algorithm. It is based
on two steps. Actually, the first step is that we need to
01:10:31.497 --> 01:10:39.554
assign the landmarks that we see to the landmarks in the map
somehow. And the second step is based on this assignment,
01:10:39.554 --> 01:10:47.119
recurculate the position of the vehicle. And then we
go through a psyche. Let us have a look at how this works.
01:10:47.130 --> 01:10:57.144
Okay, the first step is, let us assume we have first arm the
set of landmarks in the map capital P, and we have a set of
01:10:57.144 --> 01:11:09.245
observed landmarks, say the set cume. So the first step is
we assigned to each point in cue, the landmark in Pea, which
01:11:09.245 --> 01:11:19.919
is as close as possible, assuming some initial position of
the vehicle @unoise@ so. Then we determine the rotation
01:11:19.919 --> 01:11:30.075
matrix and the translation vector such that the era is
minimized that we just discuss for this assignment between
01:11:30.075 --> 01:11:38.200
observed landmarks and landmarks from the map. So based on
that, we apply this, this translation, this not translation,
01:11:38.200 --> 01:11:46.187
this transition and this rotation that we have just calculated
to all points in the observed set of landmarks. Q ah,
01:11:46.187 --> 01:11:54.303
maybe a little bit misleading. What is standing here on
the slide. So we assume, let us start again from from the
01:11:54.303 --> 01:12:03.367
beginning So. In the beginning we assume some position
and orientation of the vehicle. We know it from wherever we
01:12:03.367 --> 01:12:12.407
ask an oracle to tell us the position, or we know it from
previous calculations or whatever. Yeah, based on that, we
01:12:12.407 --> 01:12:20.592
calculate, we take the set of they are projected into
the World Court in its system based on this position. And
01:12:20.592 --> 01:12:28.242
then we compare, which is the closest landmark in the map for
each of the observed landmarks. By doing that, we pay so
01:12:28.242 --> 01:12:36.108
to say, each landmark that we observed with the landmarks
in the map. Based on that, we calculate the rotation and
01:12:36.108 --> 01:12:44.953
translation of the vehicle, the position of the video go,
which creates a new position, legal position, and based on
01:12:44.953 --> 01:12:59.415
this vehicle position that we just calculated. We restart the
process again. We project the % um. The @unoise@ observed
01:12:59.415 --> 01:13:09.947
landmarks into the map using the new position that we just
calculated. Again, check, which is the closest landmark in
01:13:09.947 --> 01:13:22.889
the map. And based on that, we take Led a new rotation matrix
and a new translation factor, Mhm. This provides a new
01:13:22.889 --> 01:13:32.371
vehicle position based on this new vehicle position. Again,
we map all the landmarks that we observed into the World
01:13:32.371 --> 01:13:40.808
Court unit system. And again, compare, which is the closest
landmark in the map. By doing that, we pair each landmark
01:13:40.808 --> 01:13:49.584
that we observe with a landmark from the map. And then again,
we calculate a new vector translation vector T, and a new
01:13:49.584 --> 01:13:59.596
rotation matrix are like that. We go on until the process
converges, and the process is guaranteed to converge with this
01:13:59.596 --> 01:14:10.061
algorithm, because actually in each of the step, the error
that we get this error term that we calculate. If we
01:14:10.061 --> 01:14:18.518
calculate it, we find that the error always decreases or
stays the same, but it never increases. And furthermore, the
01:14:18.518 --> 01:14:27.347
possible pairings between landmarks that we observed and
in the map is bounded. It is not. It is just a finite
01:14:27.347 --> 01:14:34.387
number of possibilities. And therefore it is guaranteed that
this process converges. That means that these landmarks
01:14:34.387 --> 01:14:44.329
that we pair with each other, despairing from a certain
point on remains the same @unoise@ okay. So, this is called
01:14:44.329 --> 01:14:53.631
iterative closest point algorithm. And here is an illustration,
a two dimensional case. We assume the red points are the
01:14:53.631 --> 01:15:05.611
landmark positions in the map, and the blue points are the
points that we observed with a sensor which are already um
01:15:05.611 --> 01:15:15.856
projected into the work coordinate system, assuming an initial
position and orientation of the vehicle. Now, what we do
01:15:15.856 --> 01:15:26.552
is we first check which landmarks in the map are the closest
landmarks for each of the observed landmarks. This is
01:15:26.552 --> 01:15:38.287
indicated here by these dash lines. Not so. Now we have paired
the landmarks, and you can see that the same landmark in
01:15:38.287 --> 01:15:47.326
the map could be assigned to several landmarks that we have
observed. Ah, that is possible. And there are also some
01:15:47.326 --> 01:15:56.390
landmarks in the map that are not assigned to anything, to
any observed landmarks that could happen. Now we have these
01:15:56.390 --> 01:16:04.449
assignments between the different landmarks. And now we
calculate a rotation matrix and a translation vector such that
01:16:04.449 --> 01:16:13.566
these landmarks which are paired here for those that the
distance between those landmarks becomes minimal. So to say you
01:16:13.566 --> 01:16:22.779
could assume so we are in mechanical engineering. So you
could assume that these dashed lines here are springs, yeah?
01:16:22.789 --> 01:16:32.438
and the springs put some force create some force
that pulls the landmarks together and then um at the end,
01:16:32.438 --> 01:16:41.559
somehow they have changed the setup. So afterwards, after doing
that and applying this movements, or to say that we have
01:16:41.559 --> 01:16:49.516
just calculated the translation at the transition and the
rotation, and to the legal position. The situation now looks
01:16:49.516 --> 01:16:57.601
like that. And so the position of the observed landmarks mapped
into the world has changed a little bit, because we were
01:16:57.601 --> 01:17:05.495
assuming a different vehicle position. Now we again do
this. Assign Minstopia. We assign each of the um observed
01:17:05.495 --> 01:17:15.819
landmark positions to the closest landmark position in the
map that would get create this them. This, this assignment,
01:17:15.819 --> 01:17:24.873
you know? and now again, we calculate a rotation matrix and
a translation vector, such that afterwards, after applying
01:17:24.873 --> 01:17:32.775
this rotation and translation to the vehicle position, the
distance between the observed and landmarks in the landmarks
01:17:32.775 --> 01:17:42.060
of the map is minimized afterwards. After doing that. And
applying this @unoise@ % uh rotation and relation
01:17:42.060 --> 01:17:51.901
to all points. The situation looks like that. Now we again
check whether we have to pay. Ah, the points in a different
01:17:51.901 --> 01:18:02.045
way. And we see now the pairing of points that we would get
now is the same as the pair of plies that he had before. And
01:18:02.045 --> 01:18:11.096
then we can stop the process and say the whole process is
converged. It will never change anything. And now the position
01:18:11.096 --> 01:18:21.999
of the vehicle now is the position that we it minimizes the
errand. Now, that is the iterative closest point algorithms.
01:18:22.010 --> 01:18:33.874
Here is another example Now. We have some blue okay.
Here. Unfortunately, I was not careful here. The landmark
01:18:33.874 --> 01:18:43.997
positions are in blue, and the observed positions are the red
crosses. Sorry for that. Some inconsistency. Yeah, so. And
01:18:43.997 --> 01:18:54.748
I want to find a rotation in translation that such that the
rat crosses are turned and shifted, such that they fit as
01:18:54.748 --> 01:19:04.024
best as possible to the blue circles. Now, the this example
was generated by assuming a forty five degree rotation of
01:19:04.024 --> 01:19:13.459
the points and a very small offset though. The true translation
vector is just a very small offset. And the two rotation
01:19:13.459 --> 01:19:22.370
matrix is a forty five degree rotation. Yeah, except of that,
there is no noise on the measurements. What happens? well,
01:19:22.370 --> 01:19:31.615
in the first step, all the points are shifted a little bit.
The red crosses them sense positions, and now they are
01:19:31.615 --> 01:19:41.043
rotated up to the point where they coincide with the landmark
positions in the map. So this works nicely. And what you
01:19:41.043 --> 01:19:50.961
can see is that at the end we really find the global optimum,
a perfect match in this case, here is another example
01:19:50.961 --> 01:19:59.609
where the main influence was a translation. So it is a forty
five degree rotation, plus a large offset that was added.
01:19:59.630 --> 01:20:11.253
So what happens here? the first step, the offset is compensated,
mainly compensated. And now what remains is is a little
01:20:11.253 --> 01:20:20.683
bit of rotation. And again, the whole process converges to a
global optimum. @unoise@ can hear another example where the
01:20:20.683 --> 01:20:28.112
where the rotation was ninety degrees. So the red point cloud
is rotated by ninety degree compared to the blue one. What
01:20:28.112 --> 01:20:35.767
happens here in the first step, there is a large shift,
and then a little bit of rotation, but now the process is
01:20:35.767 --> 01:20:45.416
converged. So what we can see is that this algorithm does not
find always a global optimum. It might be stuck in a local
01:20:45.416 --> 01:20:52.779
optimum as well, so that into it directly. Iterative, closest
point. Aoorism is a good algorithm. If the initial guests
01:20:52.779 --> 01:21:02.950
of the Robert position is good enough. But if the inner to
guess is not that good? well, the result that you get might
01:21:02.950 --> 01:21:16.138
not be the global optimum, but only a local optimum of this
error @unoise@ okay. So, far that the Icip algorithm. Okay,
01:21:16.138 --> 01:21:27.932
let us have an application. Um example, in this robot soccer
playing thing. Of course, knowing where the Robert is was
01:21:27.932 --> 01:21:35.486
one of the most important things. Otherwise, you cannot play
soccer. If you don't know where you are. So what did we do
01:21:35.486 --> 01:21:45.021
here to implement that. What we did is we were localizing
ourselves based on the field markings on the lines of the wide
01:21:45.021 --> 01:21:54.050
lines of the field, because that was very easy. We could easily
determine those lines with with the camera. Uh, that was
01:21:54.050 --> 01:22:02.496
very efficient. Well, it was very efficiently possible to do
that, and we always have. We have lots of lines. That means
01:22:02.496 --> 01:22:10.735
we always have lines somewhere around the Robert, which
help us to localize ourselves. So the robot was able to see
01:22:10.735 --> 01:22:20.169
lines up to three point five meters distance. So, but it had
a sensor with which it could see the whole environment. So
01:22:20.169 --> 01:22:28.777
it could also see in all three hundred and sixty degree
three hundred and sixty degree directions. Then the Aer
01:22:28.777 --> 01:22:38.179
term that we were using to determine the position of the
robot was we were like in the manner. We were
01:22:38.179 --> 01:22:46.573
matching lines that we observe two lines that existed in
the map, and we tried to minimize the distance between the
01:22:46.573 --> 01:22:55.489
observed lines and the line lines that existed in the map.
Okay, just to give you a little bit more details. The camera
01:22:55.489 --> 01:23:05.113
image looked like that. So just to tell you a little bit. So
in the center, this one is the camera itself. So the camera
01:23:05.113 --> 01:23:14.769
looks into a mirror above itself. And so it sees the which
that is reflected by the mirror. So of course, it sees the
01:23:14.769 --> 01:23:24.214
lens itself that in the centre. And then as we can see here
in front there is a soccer field. We see the lines with the
01:23:24.214 --> 01:23:32.672
the other robots, we see the ball, etc. So the first step
that we did is we were masking out some areas of the image,
01:23:32.672 --> 01:23:39.974
which are not interesting, because they were just showing the
lens of the camera, or some pieces of the mounting of the
01:23:39.974 --> 01:23:48.737
camera, et cetera. This is great out in this, this image. So
what remains are those areas um in which we were searching
01:23:48.737 --> 01:23:58.055
for line or points on the lines. We did that in a very efficient
way, but just, uh, to see searching along. Um, a long
01:23:58.055 --> 01:24:04.813
radial search directions. So the red lines indicate search
directions. We were walking through pixel by pixel along
01:24:04.813 --> 01:24:15.033
these lines. And once we found a very bright pixel, a white
pixel. Then we said," Okay, this might be a point on A on a
01:24:15.033 --> 01:24:23.185
white line so maybe in this case we got obtained
these points, which are shown in violet here. Um, these
01:24:23.185 --> 01:24:30.487
were the points in the camera image Ah, which were detected
as as ah field markets. Now we transformed the
01:24:30.487 --> 01:24:39.915
position of these field markings into a top view around the
robot. This is shown here on the right inside. So the blue
01:24:39.915 --> 01:24:48.991
axes are the coordinate. We, the robot, coordinate axis of
the Robert coordinate system. And these black points are the
01:24:48.991 --> 01:24:59.309
observed points on the lines projected into the robot
coordinate system. The next step is while we had the map of the
01:24:59.309 --> 01:25:09.016
environment, the map of the field. Now this is shown here
by by these green lines. And now we were trying to find to
01:25:09.016 --> 01:25:19.327
rotate and Ah shift the Ah robot coordinate system
in such a way that we get, ah, a large overlap between the
01:25:19.327 --> 01:25:28.860
observed field markings and the field markings that we expected
to find concerning the the map. And this is shown here.
01:25:28.869 --> 01:25:41.826
So here is a what also to say. And we somehow rotate and shift
until we find a best match. And that that was used as the
01:25:41.826 --> 01:25:49.622
position of the robot afterwards. We were using some
Carmen filter to smooth everything a little bit and to
01:25:49.622 --> 01:25:57.758
integrate the ego motion of the robot that we have since,
but mainly what we did was what you have seen here
01:25:57.758 --> 01:26:05.187
matching between the field markings that we observed in the
camera image and the markings that we expect to find based
01:26:05.187 --> 01:26:16.462
on the map of the environment. Okay, here are some examples
about from taken from a real, from real images, from a real
01:26:16.462 --> 01:26:27.562
scene. Here is a situation that shows the map background in
green and the lane markings in white as they were described
01:26:27.562 --> 01:26:37.466
in the map. And um, this blue circle is a position that
yielded the best fit. Now, the the best match between the
01:26:37.466 --> 01:26:45.083
observed lane markings and the true land markings and the
observed lane markings are projected into this, into this
01:26:45.083 --> 01:26:55.100
image as black spots, as black bullets. So we see that there
is a good fit between the black bullets and the wide lines.
01:26:55.109 --> 01:27:04.635
That means the position that we determined is is quite
accurate in this case. Now, um this plot here on the left hand
01:27:04.635 --> 01:27:14.665
side shows the arrow term indicated this gray level image.
That means the brighter pixel is here, the more likely or the
01:27:14.665 --> 01:27:23.558
smaller is the remaining error. The mismatch between the
observed field markings and the field markings that we expect
01:27:23.558 --> 01:27:32.153
to find. And we see that the maximum is really here in this
area. But we also see that there are a lot of local Optima
01:27:32.153 --> 01:27:40.675
here, a lot of local minima in this arrow term. That means
a good estimate can only be achieved if we the
01:27:40.675 --> 01:27:50.891
iterative closest point algorithm is a position that is very
close to the true position. No, yeah. @unoise@ okay. That,
01:27:50.891 --> 01:28:00.107
is another example and that also shows a little bit the
shortcomings of such an approach. And here the robot was located
01:28:00.107 --> 01:28:09.296
next to the sideline of the soccer field. And it was. It
only observed positions um field markings the site the
01:28:09.296 --> 01:28:17.696
sideline itself. Yeah, there was only one line that was
observed. The sideline of the soccer field as here. As we can
01:28:17.696 --> 01:28:28.162
see, the fit is very good. The arrow at this position is
very small. But what we also can see is that if we shift the
01:28:28.162 --> 01:28:38.690
position of the robot to the left or right, the error still
is very small. That means what we can determine is, well, we
01:28:38.690 --> 01:28:47.356
can determine very well the distance from the sideline. But
we are pretty bad in determining whether the two Robert
01:28:47.356 --> 01:28:58.565
position is a little bit more on the left or more on the right
now that means this is similar to what we get to know in
01:28:58.565 --> 01:29:06.453
optical flow calculation as the aperture problem, the
information that we get from our sensor is not sufficient to
01:29:06.453 --> 01:29:15.443
determine all elements of the Robert position. But we can
only determine the one coordinate accurately, but not the
01:29:15.443 --> 01:29:26.312
value of the other court in a direction that is
actually the problem. And we can see it here in the by
01:29:26.312 --> 01:29:35.744
having a look at the and seeing that the has kind
of valet with very small air values in between, so that we
01:29:35.744 --> 01:29:44.421
could shift the Robert position without getting a large
increase in the era term so to say that is a @unoise@ a
01:29:44.421 --> 01:29:52.343
little bit a difficult situation in which this kind of
algorithms would not be sufficient to get a reliable estimate of
01:29:52.343 --> 01:30:00.506
the Robert position @unoise@ okay. That, is it for the moment
for today, next time we will continue talking about
01:30:00.506 --> 01:30:02.289
rubble localization.