Occupancy grids
Special case of fixed decomposition
The environment is represented by a discrete grid, where each cell
is either filled (part of an obstacle) or empty (part of free space)
according to range values
The range values of each sensor, combined with the absolute
position of the robot, can be used directly to update the filled or
empty value of each cell
Each cell has a counter, where 0 indicates likely free space
As the number of ranging strikes increases, the cell’s value is
incremented and, above a certain threshold, the cell is deemed to
be an obstacle
The values of cells are commonly discounted when a ranging
strike travels through the cell, striking a further cell
THE MAP ...
WHILE BUILDING
BIM
180 LIDAR
MY OBSTACLE ALL CELLS In WHICH
THERE'S THE
↓ ROBOT BECOME
… …
州
DARKER
…
进
\
for each
cell
e
&
I
counter
threshold
:
wait sometimes
putse
cell dak
before turning
a
>
- the into is not
just where is the
obstacle but from Robot *
If
>
- somerere pon
VERSO TUTTA LA DISTANZA *
is not detect
through
DAL ROBOT
·
È Una MATRICE con O/1/Undefined Values
there
maybe are
RESULTS
of combination of robot building
my
map glassen das
" so I con see
Incemental MAP
↓ ↓ zurough
built
incrementally
-
first I have acquisition
O
FADES AWAY
Blck sobstacle
GREY e
indefined dea
matimum distance
detectable
The size of the map in robot memory grows with the size of the environment.
BUILT BY A 2D LIDAR
Visiont detection Map decomposition
nodes/brachen/graph
TOPOLOGICAL GRAPH
We represent the MAP by just a
>the
- robot is able to detect
doors /I've placed ArUUK
each
MARKERS of the top of
Door With a ID)
O O O
0 0 0
3D environment models
·
GEO-REFERENCED >
- made thanks
DRONE
Struction
·
example of
Obtained by Motion
Point cloud
3D environment models
3D mesh
3D environment models
hest value in view
hig
a Top
>
-
of the environment
DRAWBACK
Digital Elevation Model
↓
OF EACH PIXEL
3D environment models
Top VIEW -So I LOOSE THE UNDERNEAT LEVELS
I have a
Digital Surface Model vs Digital Terrain Model
3D environment models
wat
useful if
you
to have
info just
abeut obstacles
Octomap
3D environment models
From:
OctoMap: An Efficient Probabilistic 3D Mapping Framework Based on Octrees, Hornung et al. (2013)
Ind cotegay
Belief representation
Robot’s internal representation of its own state with
respect to the map
– Single-hypothesis belief: a single unique pose in the
map
– Multiple-hypothesis belief: a set of poses in the map
Single-hypothesis belief representation
The principal advantage of the single-hypothesis
representation of position stems from the fact that,
given a unique belief, there is no position ambiguity
Of MY CURRENT STATE
The unambiguous nature of this representation
"
facilitates decision-making at the robot’s cognitive
level (e.g., path planning)
The robot can simply assume that its belief is correct
and can then select its future actions based on its
V
unique position.
Multiple-hypothesis belief
In the case of multiple-hypothesis beliefs regarding position,
the robot tracks not just a single possible position but a set of
positions
ORDER OF POSITIONS
Typically, some ordering on the possible robot positions is
incorporated, capturing the fact that some robot positions are
likelier than others
> SOME
- ARE MORE PROBABLE
dovuto al che parliamo di Gorgia distribution
fatto
· Multiple-hypothesis belief: examples related
just probability to the highest al
UNIMODA ~ I
segment
<
1D Scenario = MAP is a in XAXIS
DISTRIBUTION ε
(a) Continuous map with single Gaussian
centered at a single continuous value.
>
- DISTRIBUTION WITH SOME
GAUSSIAN
meanvolve UNCERTAIN
MULTIMODAL DISTRIBUTION
(b) Continuous map with multiple
I
All set
Gaussians centered at multiple
continuous values.
of different
velue neue Goussions
mere of the oe with
higher diffent probabiate
(c) Discretized (decomposed) grid map
with probability values for all possible
robot positions HISTO GRAM
>
-
(d) Discretized topological map with
probability values for all possible nodes
(topological robot positions)
mu
PROBABILITY TO BE IN A
centein node
い "
Probabilistic Map-based Localization
Thanks to the multiple-hypothesis belief representation the
robot can explicitly maintain uncertainty regarding its position.
Two main sources of uncertainty:
robot moves in
my
– in the actuation Iluction vibration slipping effects)
, ,
a
different may as I
– in the sensing and measured systems expected
The key idea is to represent the robot belief as a probability
distribution over the robot poses
Prediction vs. Correction update
The general process for the robot position update comprises two steps:
1) prediction update USING
– the robot uses its proprioceptive sensors to estimate its configuration
– the uncertainty about the robot configuration increases
2) correction update but then when I combine date from prope and data exter
)
– the robot uses the information from its exteroceptive sensors to correct the
position estimated during the prediction phase
– the uncertainty of the robot configuration decreases
{
In PROBABILIST CASE
Prediction vs. Correction update: 1D example
50 +1 ,
xz =
different time steps
,
Xo - I'm Sure ABOUT MY POSITION
a soon as it moves >
- Gaussian
EFFECT is FLATNEss of GAUSSIAN
moving
on
-
>
- going ON - we
get a Uniform distribution
い "
the well of distance d
IMPORTANTE liketyhoed peceiving
a no
Trovare
I solo
l'ostacolo
Prediction vs. Correction update: 1D example
mode
ล
using
by the
given
sensal
THIS IS
MADE BY
KALMANN
flter
A
that gives d distance
then I turn on me =
sensor
my
}
THINNER under
-IS
- one
integral
must be 1
IT MEANS I TRUST THE MOST
THE FIRST ONE
THE REAL ONE
↑
OBSERVED POSITION
↓
from
~
exteroop IS THE COMBINATION Of
WALL
THE
that is a distance measurement GAUSSIANS
Prediction vs. Correction update: 2D example
DARKER ARED = mult
, ple hypother is
probability
↓
more
〜
NOT cloud more
t an ACCORDING TO
spead start to
perception
I
the
us
exteroceptive
just on hollveys
fom s to 2 dland - the
> other al
We don't have I stat
>
- track
na distinguishble
features - so all the -only portion of my map
scettend and hallways
In which I have a clesome
distributed BREA
REAL
d
↓
DIFFERENT LIKELYHOOD
=
verosimilmente
Probabilistic Map-based Localization
We will deal with two classes of probabilistic map-based
localization:
it needs other semplifications
– Markov localization -
» robot’s belief state can be represented with any arbitrary
probability density function
» prediction and correction phases update the probability of
every possible robot pose application : seisa FUSION
>
- main
distribution
– Kalman filter localization making emption of lea cornier
Using a
» robot’s belief state is represented as a single Gaussian
UNIMODAL probability density function (µ and σ parameterization)
DISTRIBUTION
that is required
↓
» updating the parameters of the Gaussian distribution is all
FOR THIS ISsaid PARAMETRIC APPROAC
↓
Remark: the Kalman filter localization results from the Markov
localization if the robot’s position uncertainty is assumed to have a
Gaussian form
well-known distributions
Markov vs. Kalman filter localization
1) Markov localization
Allows for localization starting from any unknown position
and can thus recover from ambiguous situations because the
robot can track multiple, completely diverse possible
positions
To update the probability of all positions within the whole
state space at any time requires a discrete representation
disovertages :
I MUST PERFORM DISCRETIZATION /Space a state-spece
Markov vs. Kalman filter localization
2) Kalman filter localization DRAWBACK : Unimodel
Tracks the robot from an initially known position
It can be used in continuous world representations
If the uncertainty of the robot becomes too large (e.g., due to
a robot collision with an object), the Kalman filter can
become irrevocably lost
something that make loosing
the unimodality
A taxonomy of localization problems
Position tracking
The robot current location is updated based on the knowledge of its
previous position. The initial robot pose is assumed to be known.
Global localization problem
The robot initial location is unknown. This means that the robot can be
placed anywhere in the environment and is able to localize globally
within it. even if at the begginning it abesn't know his position the map
in
Kidnapped robot problem ESTRICTLY RENTED
The kidnapped robot problem is a more difficult variant of the global
localization problem. During operation, the robot can get kidnapped and
moved to some other locations. The robot might believe it knows where
it is while it does not. The ability to recover from catastrophic
localization failures is essential for truly autonomous robots
Probability Theory Recall
Key idea of probabilistic robotics:
Explicit representation of uncertainty using the calculus of
probability theory veloce
Axioms of Probability Theory: Pr(A) denotes probability
_ that
proposition A is true
combination
True
A A B B
Probability Theory Recall
Random variable: volai cambiaro in moniere casuale
-
a variable whose value is subject to variations due to chance
Discrete Random Variable X:
– X can take on a countable number of values in {x1, x2, …, xn}
– P(X=xi), or P(xi), is the probability that the random variable X
takes on value xi - > HISTO GRAM
GENERAL DEF
.
Continuous Random Variable X:
– X takes on values in the continuum
– p(X=x), or p(x), is a probability density function
Both discrete and continuous probabilities integrate to one:
r∞ sum of
PROBABILITIES
Some but with the
catinvous volue
Probability Theory Recall
∞ Joint probability:
P(X=x and Y=y) = P(x,y)
If X and Y are independent:
P(x,y) = P(x) P(y) PRODUCTOf the Two
Conditional probability: the probability of x given y
P(x | y) = P(x,y) / P(y)
If X and Y are independent:
P(x | y) = P(x)
foex
P(y | x) = P(y)
given y
Probability Theory Recall
Law of total probability:
λ
Adopted notation
Visual interpretation of the rule (discrete case):
interectio
genera EVENT
A
probability of
Observing Bn
Probability Theory Recall to delive
"
λ
Bayes Rule "Joint probability of X
given y
some
info
giver probabilities
and
eikelihood
>
- to esse some
postend
estimation
If x is a quantity that we would like to infer from y, the probability p(x)
will be referred to as prior probability distribution, and y is called the
data (e.g., a sensor measurement).
The probability p(x | y) is called the posterior probability distribution
over X.
The denominator of Bayes rule, p(y), does not depend on x. Thus, the
factor p(y)−1 will be the same for any value x in the posterior p(x | y)
=> p(y)−1 is often written as a normalization factor η: