## 19100Bayesian conditional probability in sonar mapping

Expand Messages
• Aug 2, 2004
Bayes Rule has been in use in robotics for building sonar maps since the
mid-1980's or so. A link explaining the mathematics of the rule can be
found at http://www.ai.mit.edu/~murphyk/Bayes/bayesrule.html.

In essence, the use of Bayes Rule allows one to build up a high
resolution rasterized picture of the area around a robot within the
range of the sonar. Imagine a room with square tiles on the floor, with
a picture of a happy face made with black tiles surrounded by white
tiles -- that's a rasterized happy face. But we couldn't see that face
directly with sonar (assuming the black tiles are tall), due to the
width of the sonar beam. A sonar beam (on the typical Polaroid sonar)
is 22 or more degrees wide. Out at a distance of several feet, the
sonar might not be able to tell one black monolithic tile from another
if they were too close together. If one tile was widely separated from
the rest, and we detected it in a sonar beam, we would know there was
one there, and how far away it was, but we wouldn't know it's azimuth
other than it was within the beam arc at that distance.

Sonar strength and reliability varies with distance, and also within the
width of the beam at a give distance. The probability that something
will or will not be detected at various distances from the sonar
emitter, and azimuths from the beam centerline, given the variation in
reliability around those factors, is called the sonar model.

Bayes rule is a probabilistic framework that allows us to update our
knowledge of previous events, given a new event. The updating is based
on probability, and the value of the new event is probabilistic (the
sonar model in this case).

As a simple sonar example, lets say you have a sonar with a range of
(barely) 16 feet. The odds that you can detect a narrow object on the
beam centerline at 16 feet are not good, certainly not 100%. The
probability that you can detect an object at 16 feet that is at one
extreme of the beam width is practically zero. So if you got 3 hits
out of 18 indicating that there was an object at 16 feet, you would not
be too confident that there really was something there. However, if it
turns out that your poor probability was due to the object being at one
edge of the sonar beam at that distance, as you swung the sonar scan a
few degrees at a time into the direction of the object within the beam,
your odds of getting a return would improve, and your confidence would
also improve that there was something actually there. Using the
Bayesian approach is how we develop that probability over a grid space
(your tile floor), and it comes out in the form of what is called a
confidence grid. Using this method, we can see the happy face with sonar.

Extending this, if we can connect the dots in the evidence grid when
they represent straight lines, we can identify walls and other objects
that we can then compare to known features in a pre-existing map.
That's what I want the Hough transform information for. The robot
should think it knows where it is at all times using odometry. But
errors in odometry build up over time, and need to be corrected before
the robot gets hopelessly lost. There are various ways to do this,
like, perhaps, using bump sensors and deliberately running into known
objects so as to zero out errors in specific axes. Other ways include
using sonar, laser range finding, GPS (outdoors with room for position
error) and beacons.

Hope this helps. I have pointers to research papers on the subject, and
C code segments that do the actual work.

Best regards,

Gary Livick

raymond melton wrote:

>--- Gary Livick <glivick@...> wrote:
>
>
>>In the case of
>>localization using sonar, using the Bayesian
>>approach we are using
>>
>>
>
>be willing to elaborate a bit on that?
>
>Regards, Ray.
>
>P.S. Google on Hough transform brings up all kinds of
>bizarre blurbs.
>
>
>
>__________________________________
>Do you Yahoo!?
>Read only the mail you want - Yahoo! Mail SpamGuard.
>http://promotions.yahoo.com/new_mail
>
>
>Visit the SRS Website at http://www.seattlerobotics.org