Transcript Probabilistic Robotics - School of Computer Science

Probabilistic Robotics
Introduction
Introduction
Robotics is the science of perceiving and
manipulating the physical world through
computer-controlled devices.
Desirability of “intelligent” manipulating
devices. Examples…
To be intelligent, robots have to
accommodate the enormous uncertainty
that exists in the physical world.
Introduction
Where does Uncertainty come from?
robot environments
are inherently unpredictable. Assembly line, high
way, private homes (highly dynamic and highly unpredictable)
Sensors
range and resolution,noise…
Robot actuation
motor, control noise,wear-and-tear, mechanical failure….
robot software,
internal models of robots are crude and approximate.
Model errors are a source of uncertainty that has often been ignored in robotics, despite the
fact that most robotic models used in state-of-the-art robotics systems are rather crude.
Algorithmic approximation
Introduction
As robotics is now moving into the open
world, the issue of uncertainty has
become a major stumbling block for the
design of capable robot systems.
Managing uncertainty is possibly the
most important step towards robust realworld robot systems.
Hence Probabilistic Robotics
Introduction- Probabilistic
Robotics
A relatively new approch robotics.
The key idea is to represent uncertainty
explicitly using the calculus of probability theory.
Maintaining a probability distribution instead of
a single best guess.
It outperforms alternative techniques in many
real-world applications.
Introduction- Probabilistic
Robotics
Examples using Probabilistic Robotics.
Mobile Robot Localization
The problem of estimating a robot‘s coordinates relative
to an external reference frame. Map of environment is
given, find out where I (the robot) am. Can consulte
sensor data and can move around.
See Figure 1.1
Introduction- Probabilistic
Robotics
Examples using Probabilistic Robotics.
Robotic Planning and Control
Coastal navigation
See Figure 1.2
Implication of Probabilistic Robotics
Probabilistic robotics seamlessly integrates models with
sensor data, overcoming the limitations of both at the same
time.
A bit of history of robotics research
Model-based paradigm
Behavior-based paradigm
Probabilistic robotics tends to be more robust in the face of
sensor limitations and model limitations. Scale much better to
complex real-world environments.
Probabilistc approachs are currently the only known
working solutions to hard robotic estimation problems, such
as localization and mapping
Implication of Probabilistic Robotics
Probabilistic robotics have weaker requirements on the
accuracy of the robot‘s models, and weaker requirements on
the accuracy of robotic sensors, compared with previous
approaches.
Probabilistic robotics is also criticized because of
Computational complexity, and
Need to approxiamte.
Probabilistic Robotics
Recursive State Estimation
Recursive State Estimation
Give me the sensor data, I will tell you something.
Estimate state from sensor data.
This is the core idea of probabilistic robotics.
Probabilistic state estimation algorithms comopute belief
distributions over possible world states. An example, already
shown, what is it?
The purpose of this part of lecture
Introduce notions and notions that will be used.
Background preparation
Introduce the algiorthm Bayes filters, the single most
important algorithm that is the basis of virtually every
techniques presented in the book.
Axioms of Probability Theory
Pr(A) denotes probability that proposition A is true.
•
0  Pr( A)  1
•
Pr(True)  1
•
Pr( A  B)  Pr( A)  Pr( B)  Pr( A  B)
Pr( False )  0
A Closer Look at Axiom 3
Pr( A  B)  Pr( A)  Pr( B)  Pr( A  B)
True
A
A B
B
B
Using the Axioms
Pr( A  A)
Pr(True)
1
Pr(A)
 Pr( A)  Pr(A)  Pr( A  A)
 Pr( A)  Pr(A)  Pr( False )

Pr( A)  Pr(A)  0

1  Pr( A)
Discrete Random Variables
• X denotes a random variable.
• 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.
• P( ) is called probability mass function.
• E.g.
P( Room)  0.7,0.2,0.08,0.02
Continuous Random Variables
• X takes on values in the continuum.
• p(X=x), or p(x), is a probability density function.
b
Pr( x  (a, b))   p( x)dx
a
• E.g.
p(x)
x
Joint and Conditional Probability
• P(X=x and Y=y) = P(x,y)
• If X and Y are independent then
P(x,y) = P(x) P(y)
• P(x | y) is the probability of x given y
P(x | y) = P(x,y) / P(y)
P(x,y) = P(x | y) P(y)
• If X and Y are independent then
P(x | y) = P(x)
Law of Total Probability, Marginals
Discrete case
Continuous case
 P( x)  1
 p( x) dx  1
x
P ( x )   P ( x, y )
y
P( x)   P( x | y ) P( y )
y
p ( x)   p( x, y ) dy
p ( x)   p ( x | y ) p ( y ) dy
Bayes Formula
P ( x, y )  P ( x | y ) P ( y )  P ( y | x ) P ( x )

P( y | x) P( x) likelihood  prior
P( x y ) 

P( y )
evidence
Normalization
P( y | x) P( x)
P( x y ) 
  P( y | x) P( x)
P( y )
1
1
  P( y ) 
 P( y | x)P( x)
x
Algorithm:
x : aux x| y  P( y | x) P( x)
1

 aux x| y
x
x : P( x | y )   aux x| y
Conditioning
• Law of total probability:
P ( x)   P( x, z )dz
P ( x)   P( x | z ) P ( z )dz
P( x y )   P( x | y, z ) P( z | y ) dz
Bayes Rule
with Background Knowledge
P ( y | x, z ) P ( x | z )
P( x | y, z ) 
P( y | z )
Conditional Independence
P( x, y z )  P( x | z ) P( y | z )
equivalent to
P( x z )  P( x | z , y )
and
P ( y z )  P( y | z , x )
Robot Environment Interaction
• See Figure 2.1
• The robot maintains an internal belief with
regards to the state of its environment.
• The robot also influence its environment
through its actuators.
• Uncertainty exists, as always….
Robot Environment Interaction
• Environment are characterized by state
variables.
• State can be conveniently considered as
the collection of all aspects of the robot and
its environment that can impact the future.
• Dynamic state variable and static state
variable?
• State is denoted x , the state at time t is
denoted xt
x
Robot Environment Interaction
•
Typical state variables:
– Robot pose,
– Configuration of the robot’s actuators,
x
– Robot velocity,
– Location and features of surrounding objects in the
environment
• Landmarks are distinct, stationary features of the
environment that can be recognized reliably.
– Location and velocities of moving objects and people…
– Whether sensor is broken.
– The list can go on and on…..
Robot Environment Interaction
•
Complete State
– Markov Chains
• You want to know if tomorrow is going to rain, you
only need to know…..
x
• Incomplete State
– A complete state is hard to obtain, we get by with a small subset of
complete state.
• In most robotics applications, the state is continuous,
meaning that is defined over
xt a continuum. For
example…
• Sometimes, the state can be discrete.
• Thus hybrid state space….
Robot Environment Interaction
• Two fundamental types of interactions between a robot and its
environment.
• 1. The robot can influence the state of its environment
through
x
its actuators.
– The control actions
• 2. The robot can gather information about the state through its
sensors.
– The environment sensor measurements
• How to probabilistically model these interactions?