Browse Groups

• I generally get over my head about once a week. Perhaps someone has some information that will get my project going forward. The basic project: Between Kent
Message 1 of 12 , Aug 1, 2004
View Source
I generally get over my head about once a week. Perhaps someone has
some information that will get my project going forward.

The basic project: Between Kent Farnsworth and myself, we have an
RF-linked Hero 2000 setup that allows controlling the robot via a remote
host computer, using the robot itself running in its native BASIC from
the command line as a slave. We use C as the programming language on
the host. All the library programs have been written for mechanical
control of the robot's functions, such as motion, sonar scanning, etc.

The expanded project, phase 1: We have ported the "Grid Nav 1.0"
grid-based planner, written by Tucker Balch, in its totality. This
planner allows the Hero to navigate from point A to point B, self
planning its route around obstacles. We utilize the robot's own PID
system and odometry capabilities. It operates very effectively.

The expanded project, phase 2: Using work by Hans Moravec, as explained
very effectively by Prof. Crabbe at the US Naval Acadamy
(http://www.cs.usna.edu/~crabbe/2004-01/SI475/classes/mapping/mapping.pdf),
we have implemented an certainty grid, utilizing a Baysian conditional
probablily approach, built up from sonar date. We display the results
on the host screen, and see that we get an excellent representation of
the local areas around the robot.

The expanded project, phase 3: This is the over-the-head part. In order
to make use of the certainty grid for simultaneous localization and
mapping, we think it will be most expedient to utilize a Hough transform
approach to both create the global map of the robot's world, and for use
in later self-localization of the robot within it. That's where I'm
stuck.

What is needed is a Schaum's Outline-like straight explanation of the
Hough transform for generating straight and simple curved lines from an
occupancy grid (actually converted to an occupancy grid for this
purpose, which will then represent a coarse bitmap of the environment),
along with simple example applications written in C, or at least pseudo
code.

The work I'm seeing which uses the above approach tends to use MAT-LAB.
We want to do it all self-contained in our own code.

Anyone have any pointers to something like this. Anyone doing similar work?

Thanks,

Gary Livick

[Non-text portions of this message have been removed]
• Gary, You reminded me of graphics programs and why I buy them... so I don t have to do the math myself. And of course, looking at this site reminded me again
Message 1 of 12 , Aug 1, 2004
View Source
Gary,

You reminded me of graphics programs and why I buy them... so I don't
have to do the math myself.

And of course, looking at this site reminded me again why I don't do
the math... but gee whiz, ya gotta like the little Java applet they
put together to illustrate their point (or curve, as it were).

http://www.cs.nps.navy.mil/people/faculty/capps/iap/class2/splines/

-Todd

--- In SeattleRobotics@yahoogroups.com, Gary Livick <glivick@s...> wrote:
>
>
> I generally get over my head about once a week. Perhaps someone has
> some information that will get my project going forward.
>
> The basic project: Between Kent Farnsworth and myself, we have an
> RF-linked Hero 2000 setup that allows controlling the robot via a
remote
> host computer, using the robot itself running in its native BASIC from
> the command line as a slave. We use C as the programming language on
> the host. All the library programs have been written for mechanical
> control of the robot's functions, such as motion, sonar scanning, etc.
>
> The expanded project, phase 1: We have ported the "Grid Nav 1.0"
> grid-based planner, written by Tucker Balch, in its totality. This
> planner allows the Hero to navigate from point A to point B, self
> planning its route around obstacles. We utilize the robot's own PID
> system and odometry capabilities. It operates very effectively.
>
> The expanded project, phase 2: Using work by Hans Moravec, as explained
> very effectively by Prof. Crabbe at the US Naval Acadamy
>
(http://www.cs.usna.edu/~crabbe/2004-01/SI475/classes/mapping/mapping.pdf),

> we have implemented an certainty grid, utilizing a Baysian conditional
> probablily approach, built up from sonar date. We display the results
> on the host screen, and see that we get an excellent representation of
> the local areas around the robot.
>
> The expanded project, phase 3: This is the over-the-head part. In
order
> to make use of the certainty grid for simultaneous localization and
> mapping, we think it will be most expedient to utilize a Hough
transform
> approach to both create the global map of the robot's world, and for
use
> in later self-localization of the robot within it. That's where I'm
> stuck.
>
> What is needed is a Schaum's Outline-like straight explanation of the
> Hough transform for generating straight and simple curved lines from an
> occupancy grid (actually converted to an occupancy grid for this
> purpose, which will then represent a coarse bitmap of the environment),
> along with simple example applications written in C, or at least pseudo
> code.
>
> The work I'm seeing which uses the above approach tends to use
MAT-LAB.
> We want to do it all self-contained in our own code.
>
> Anyone have any pointers to something like this. Anyone doing
similar work?
>
> Thanks,
>
> Gary Livick
>
>
>
>
> [Non-text portions of this message have been removed]
• ... Okay, suppose that I am undaunted by mathematics. What is a Hough transform? Regards. __________________________________ Do you Yahoo!? New and Improved
Message 1 of 12 , Aug 1, 2004
View Source
--- toddpierce1968 <todd_pierce@...> wrote:

Okay, suppose that I am undaunted by mathematics.
What is a Hough transform?

Regards.

__________________________________
Do you Yahoo!?
New and Improved Yahoo! Mail - Send 10MB messages!
http://promotions.yahoo.com/new_mail
• Were you looking for information in respect of something specific or just in general? I know its early and the coffee probably hasn t done its job yet, but
Message 1 of 12 , Aug 2, 2004
View Source
Were you looking for information in respect of
something specific or just in general?

I know its early and the coffee probably hasn't done
its job yet, but google shows 21000 pages that talk
examples and tutorials.

--- raymond melton <rtmelton@...> wrote:

> --- toddpierce1968 <todd_pierce@...> wrote:
>
> Okay, suppose that I am undaunted by mathematics.
> What is a Hough transform?
>
> Regards.
>
>
>
> __________________________________
> Do you Yahoo!?
> New and Improved Yahoo! Mail - Send 10MB messages!
> http://promotions.yahoo.com/new_mail
>
>
> Visit the SRS Website at
> http://www.seattlerobotics.org
>
>
> SeattleRobotics-unsubscribe@yahoogroups.com
>
>
>
>

__________________________________
Do you Yahoo!?
Yahoo! Mail is new and improved - Check it out!
http://promotions.yahoo.com/new_mail
• The Hough transform is an algorithm that is used to generate lines, curves, etc., from, for example, pixels in a video image. It can be used to detect shapes,
Message 1 of 12 , Aug 2, 2004
View Source
The Hough transform is an algorithm that is used to generate lines,
curves, etc., from, for example, pixels in a video image. It can be
used to detect shapes, edges, that sort of thing. In the case of
localization using sonar, using the Bayesian approach we are using
produces a pixelated image of the space around the robot. Converting
those pixels into lines greatly facilitates matching the sonar map to an
a priori line map.

Gary

raymond melton wrote:

>--- toddpierce1968 <todd_pierce@...> wrote:
>
>Okay, suppose that I am undaunted by mathematics.
>What is a Hough transform?
>
>Regards.
>
>
>
>__________________________________
>Do you Yahoo!?
>New and Improved Yahoo! Mail - Send 10MB messages!
>http://promotions.yahoo.com/new_mail
>
>
>Visit the SRS Website at http://www.seattlerobotics.org
>
>
>
>
>
>
>
>
• Yes, there are many links, just need a practical approach to detecting straight lines in a pixel space, not the theory. I ve been looking for awhile, and
Message 1 of 12 , Aug 2, 2004
View Source
Yes, there are many links, just need a practical approach to detecting
straight lines in a pixel space, not the theory. I've been looking for
awhile, and can't locate anything basic. If necessary, we'll need to
dig into the theory and work out the application, but was hoping someone

Thanks for responding,

Gary Livick

Mr S wrote:

>Were you looking for information in respect of
>something specific or just in general?
>
>I know its early and the coffee probably hasn't done
>its job yet, but google shows 21000 pages that talk
>examples and tutorials.
>
>--- raymond melton <rtmelton@...> wrote:
>
>
>
>>--- toddpierce1968 <todd_pierce@...> wrote:
>>
>>Okay, suppose that I am undaunted by mathematics.
>>What is a Hough transform?
>>
>>Regards.
>>
>>
>>
>>__________________________________
>>Do you Yahoo!?
>>New and Improved Yahoo! Mail - Send 10MB messages!
>>http://promotions.yahoo.com/new_mail
>>
>>
>>Visit the SRS Website at
>>http://www.seattlerobotics.org
>>
>>
>> SeattleRobotics-unsubscribe@yahoogroups.com
>>
>>
>>
>>
>>
>>
>
>
>
>
>__________________________________
>Do you Yahoo!?
>Yahoo! Mail is new and improved - Check it out!
>http://promotions.yahoo.com/new_mail
>
>
>Visit the SRS Website at http://www.seattlerobotics.org
>
>
>
>
>
>
>
>

[Non-text portions of this message have been removed]
• ... I m curious about your Bayesian approach. Would you be willing to elaborate a bit on that? Regards, Ray. P.S. Google on Hough transform brings up all
Message 1 of 12 , Aug 2, 2004
View Source
--- 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
• Anybody willing to use Skype to join a multiperson audio chat? It works really well and it is claims to be free. I will do my best to answer if you call me in
Message 1 of 12 , Aug 2, 2004
View Source
Anybody willing to use Skype to join a multiperson audio chat? It works
really well and it is claims to be free.
I will do my best to answer if you call me in the next 4 hours, it can do up
to 5 persons at once.

Giuseppe Marullo

P.S: my username is name dot surname
• 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
Message 1 of 12 , Aug 2, 2004
View Source
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
>
>
>
>
>
>
>
>

[Non-text portions of this message have been removed]
• ... Tantalizing... I (and I suspect others) would be very interested in both the references and the source if you re willing to share it. Very informative -
Message 1 of 12 , Aug 2, 2004
View Source
> Hope this helps. I have pointers to research papers on the
> subject, and C code segments that do the actual work.

Tantalizing... I (and I suspect others) would be very interested in
both the references and the source if you're willing to share it.

Very informative - Thanks
--Martin

-----Original Message-----
From: Gary Livick [mailto:glivick@...]
Sent: Monday, August 02, 2004 6:37 PM
To: SeattleRobotics@yahoogroups.com
Subject: [SeattleRobotics] Bayesian conditional probability in sonar
mapping

[...]
• Martin, This ambitious work has produced some excellent results using many of the same tools I am developing. Unfortunately, his source, which is free for the
Message 1 of 12 , Aug 2, 2004
View Source
Martin,

This ambitious work has produced some excellent results using many of
the same tools I am developing. Unfortunately, his source, which is
idea of what can be done with a single sonar module mounted on a servo.

http://rossum.sourceforge.net/papers/Localization/PosPosterv4.pdf

I'll post some code of mine that will actually display a certainty grid
on a screen, given some assumed sonar data. It's written to run under
DOS. Just need to put it together from various routines. I'll post
for free from Borland) and also the .exe file. With a little fiddling,
and a sonar of your own on a servo, you can make it your own.

Best regards,

Gary

Martin R. Calsyn wrote:

>>Hope this helps. I have pointers to research papers on the
>>subject, and C code segments that do the actual work.
>>
>>
>
>Tantalizing... I (and I suspect others) would be very interested in
>both the references and the source if you're willing to share it.
>
>Very informative - Thanks
>--Martin
>
>-----Original Message-----
>From: Gary Livick [mailto:glivick@...]
>Sent: Monday, August 02, 2004 6:37 PM
>To: SeattleRobotics@yahoogroups.com
>Subject: [SeattleRobotics] Bayesian conditional probability in sonar
>mapping
>
>[...]
>
>
>
>Visit the SRS Website at http://www.seattlerobotics.org
>
>
>
>
>
>
>
>

[Non-text portions of this message have been removed]
• Hi guys, I ve been converting a 1/6 scale rc car to robotic control, complete with an IMU and GPS. More on that later when I have time to put together a web
Message 1 of 12 , Aug 11, 2004
View Source
Hi guys,

I've been converting a 1/6 scale rc car to robotic control, complete with
an IMU and GPS. More on that later when I have time to put together a web
page.

Here's my problem: yesterday the steering servo burned out for no
apparent reason. I built custom servo-driving electronics (a mux from the
rx and the uc). The servos run off of a 5-cell NiMH pack. We have used
the current circuitry many times before. So yesterday while the car was
sitting on the test bench, the servo started
smoking and the motor heat sink got pretty warm before I could turn off
the power. No commands were being sent (except perhaps a little radio
noise, but the servos weren't twitching). The servo was not jammed (as
far as I can tell) and the front wheels were in the center of their
motion.

I opened up the servo. The metal gears were fine, and it had full range
of motion. It looks like som surface mount resistors next to a transistor
got really hot and melted the case (smoke).

The only think I can find wrong with MY circuitry is a loose power
connection. The ground pin from the servo batteries was loose. The
driving signal (which was inactive?) comes from another battery. Could
spotty power cause a nice digital RC servo to get confused and
self-destruct? Oh yeah, the throttle servo, a smaller digital, was
connected to the same power, and it's fine. I've got to replace the dang
thing, but I'm afraid. Anyone ever see anything like this before?

Thanks!

-Lyle Chamberlain
Your message has been successfully submitted and would be delivered to recipients shortly.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.