Society of Robots - Robot Forum

Software => Software => Topic started by: sparty on January 09, 2012, 08:59:06 AM

Title: Wavefront algorithm and sharp ir sensors
Post by: sparty on January 09, 2012, 08:59:06 AM
I am planning to implement the wavefront path finding algorithm (with adaptive mapping) on a small mobile robot using the arduino uno as a final year engineering project. I am a beginner(I have done some very basic programming using the arduino). It would be really helpful if the following questions are answered.

1. Is is feasible?, that is, is the arduino capable enough to handle the algorithm?(I am assuming that it is possible if the world has small dimensions).
2. Has anyone tried it before? Your suggestions would be really helpful.
3.Should I be using servo motors to drive the robot?(For the localisation part)
4.Is it worthy of a final year engineering project? Should I try something more easier/harder ?

Thank you.
Title: Wavefront algorithm and sharp ir sensors
Post by: sparty on February 05, 2012, 09:29:52 AM
hello,
I am trying to implement the admin's wavefront algorithm using an arduino mega. I can see that the admin is using the sharp ir rangefinders to implement the algorithm but the problem is in the place where I am from all the electronic stores are unaware of the fact that such a sensor exists. I managed to get a few standard ir sensors with ambient light protection like this one

[urlhttp://probots.co.in/index.php?main_page=product_info&cPath=9&products_id=360][/url]

Do I really need the sharp ir sensors to implement the wavefront algorithm?

Can I use the above sensors as a replacement for the sharp sensors?

Can I use an ultrasonic sensors to achieve the same?

I am posting this because the sharp ir sensors are pretty expensive if I have them shipped to my place and the sipping may take some time. I cant afford both of them as my project deadline is fast approaching. Hence, I would also like to know if some alternative sensors are available. A reply will be very much helpful. Thank you :) 
Title: Re: Wavefront algorithm and sharp ir sensors
Post by: Pierre on February 05, 2012, 12:31:51 PM
Hi sparty

     Not that I am an expert but I played with an IR Range sensor 20cm to 15cm ( up to five feet).  I had to use algorithm to figure the appropriate distance for an object.

     The sensor you showed is great with adjust pot. but the output is digital and will gave you a "1" or "0" if it sees an object or not.  If you use an IR Range sensor then you can use an algorithm and use an Arduino using an analog input.  With 8 bit you can receive 0V to 5V or 0 to 1024.  I understand the time limit for your project.  If I may suggest to get your IR Sensor as it will get to you quick and make a demonstration with what that sensor can do.

     I am in the same boat making a sumo robot with white line sensor(QRB1114) and a few IR Range Sensor.  It's like Biomedical Eng. VS Electronic/Robotic Eng.

     Make the best of what you can do and good luck for your project 
Title: Re: Wavefront algorithm and sharp ir sensors
Post by: sparty on February 06, 2012, 03:02:57 AM
Hi pierre,
thanks for the reply :) I am aware that the sensor I posted gives a digital output. I am under the impression that the robot only needs to know if an obstacle is present in a grid or not. Please correct me if I am wrong.

Reply from users or the admin who have already implemented the slgorithm will be very helpful. Thank you.
Title: Re: Wavefront algorithm and sharp ir sensors
Post by: rbtying on February 07, 2012, 11:19:31 AM
Since the sensor only gives a digital output for a small distance, you will not be able to reliably fill the obstacle map (and thus the costmap) for wavefront calculation. The analog output allows you to look at obstacles which are farther away, thereby letting you actually map the area out.
Title: Re: Wavefront algorithm and sharp ir sensors
Post by: Admin on February 10, 2012, 03:59:26 AM
admin note: I merged your other related topic to this one.

The Arduino uses the *exact* same microcontroller as the $50 Robot and my iRobot Wavefront demo. So yes, the Arduino can handle it. But it's memory is puny, limiting yourself to a tiny crude map for real-life locations.

Quote
the problem is in the place where I am from all the electronic stores are unaware of the fact that such a sensor exists.
No electronics stores has anything useful that is affordable other than your very basic most common parts . . . as long as you live in the US, online is the way to go.


As mentioned above by others, a digital output doesn't give you any range information. Plus, that sensor you linked to has a total range of only 10 inches - and it's very imprecise at that.

Quote
sharp ir sensors are pretty expensive
Sharp IR's give you precise analog range measured in feet and/or meters. You get what you pay for, and ~$15 isn't that bad really. :P

Quote
Can I use an ultrasonic sensors to achieve the same?
Yes, but sonar is even more expensive than a Sharp IR, and it's precision is a wide beam. Sonar is best for other stuff, not mapping.

Quote
Is it worthy of a final year engineering project?
You mean college level senior? It's worthy doing for fun in your freetime, great for the educational value, but for science it's been done a thousand times before :P
Title: Re: Wavefront algorithm and sharp ir sensors
Post by: sparty on February 12, 2012, 09:24:48 PM
hey admin,
thanks for the reply :) I was wondering if I could use methods like himm to incorporate sonar sensors. Could you please give me your opinions on that?

Quote
You mean college level senior?


yep..college senior level it is (cs undergrad final year) :P I am finding the whole process pretty difficult as I am very new to robotics. The time I have to complete this robot is nearly a month and a half and I have completed the 'basic setup'. I am using the arduino mega ( I assumed that the memory available is sufficient for a decent sized map, am I wrong?) and it was such a pain to make the robot move in a straight line :| (since  rotary encoders aren't available here and the one I made is crappy) . I will soon implement the adaptive mapping technique and I think adding the sonar sensors and implementing himm would make the project a little more 'complicated' . Could you please suggest some other additions that would make the project a little more worthy, like taking obstacles with non zero velocities into account, maybe? I am feeling guilty after reading your post as I have made my guide into thinking that I am doing a very complicated project :P Thanks for your help again :)

ps. The reason that I am using a sonar sensor is that's the one I have in hand right now and I don't want to waste it and I am sorry about the double post, I am well versed with the rules of the forum now :)
 
Title: Re: Wavefront algorithm and sharp ir sensors
Post by: Admin on February 12, 2012, 10:04:27 PM
The Arduino (ATmega328) has 2kb of ram. So if you make an array of ints, then you're map grid will be a maximize size of 44x44. Depending on your required precision, that's just barely enough to map out one room (with no clutter on the floor). By comparison, my Axon has 8kb of ram. If you want to get fancy and overcomplicated, you can also put to use the EEPROM (1kb for Arduino, 4kb for Axon).

The thing with sonar is that it has a wide beam, while Sharp IR has a pencil tip beam, so you're accuracy won't be so great with the sonar. You can of course do some fancy algorithms with sonar to interpolate, but I'm too lazy to describe how to do it . . .

The wave front algorithm was first developed, if I remember right, in the early 1960's. :P

You can perhaps have your robot try to identify items that it scans - this is extremely complicated, especially in 3D.
Title: Re: Wavefront algorithm and sharp ir sensors
Post by: sparty on February 14, 2012, 09:01:29 AM
hey admin,
The atmega2560(the one on arduino mega) has 256 Kb of memory...I would love to use the axon too as the programming language is C which looks better to me than the one used in arduino ide (it looks kiddish :P) but again the problem is axon isn't available here.

I am going to try things out with the sonar sensor that I have and then order the sharp ir if sonar turns out to be impossible or very hard.

lol...I didn't realize that the algorithm was that old..it's still great though :D I will try to implement the identification algorithm after this one is complete :) Thank you very much for mentioning it.

 
Title: Re: Wavefront algorithm and sharp ir sensors
Post by: rbtying on February 14, 2012, 10:19:03 AM
The Arduino uses an ATMega328P; it's not like the programming language used isn't just a few libraries on top of avr-gcc and avr-g++.

Since AVR devices are Harvard-architecture processors, though, it's important to distinguish between PROGMEM (flash memory) and SRAM (program memory). While the ATMega2560 does have 256kb of flash, it only has 8kb (and the Arduino only 2kb) of SRAM, which is the more important value, seeing as you can't change PROGMEM while running the program.
Title: Re: Wavefront algorithm and sharp ir sensors
Post by: Admin on February 15, 2012, 10:15:49 AM
The ATmega2560 on the Arduino Mega and the ATmega640 on the Axon are *exactly* the same microcontrollers. The only difference is the 640 has 64kb of flash and the 2560 has 256kb of flash. You won't need anywhere near that much flash. Even my ERP only uses about ~40kb and it's not even optimized for memory.

As rbtying points out, for mapping, you need RAM and EEPROM.

ps - the Axon ships internationally, although shipping is a bit pricey :P
pps - I thought the Arduino Mega used the 1280, which is also the same but with 128kb? Perhaps they changed it, realizing the 1280 and the 2560 cost exactly the same?
Title: Re: Wavefront algorithm and sharp ir sensors
Post by: sparty on February 15, 2012, 11:41:33 PM
dear rbyting and admin,
thanks for your replies again :)

@rbyting yes..that's what I wanted to convey...the extra libraries on top makes things a tad too easier...and I am really not working on the 'inside' stuff...I am using libraries built by others...which contains much more efficient code..and that makes me feel guilty sometimes.

I am sorry about that...I forgot that the arduino does not run an os :| I was thinking along the lines of virtual memory and I thought that the ram won't be a problem...I was wrong :|

@admin yeah...I realize that now...256 kb seemed too little when I bought it :|

a 'bit' pricey...lol..that's the problem :P

The new mega uses the 2560 and old one used 1280...I am not very sure though.

@rbyting and admin Thanks for your help again :)
Title: Re: Wavefront algorithm and sharp ir sensors
Post by: sparty on February 15, 2012, 11:59:08 PM
admin,
your erp is awesome btw :D wish I could build something like that someday...