I don't know how you'd represent your map, but if it's just a 2D grid of occupied/clear cells then you're going to need large amounts of data to get anything worth while. Are you planning to put it on an SD card, or something?Calculating position by dead reckoning is not going to be very accurate and trying to use the previously-discovered map results to tell you where you are I think would actually be very hard to do effectively.If any of the obstructions in the room/maze are moving/moveable, all bets are off.
I'm thinking a 2D matrix of booleans or integers
What you are wanting to do is doable, but it is not a trivial problem to solve; in fact, it's not a problem that's been completely solved yet - so good luck with the project!If you are serious about pursuing this to the fullest measure, though, I suggest you look into a couple of things.The first, of course, is SLAM (Simultaneous Localization and Mapping):http://en.wikipedia.org/wiki/Simultaneous_localization_and_mappingThat is what you are trying to do. It isn't simple, there's a ton of math involved - you need to understand linear algebra and probability, among other things. But there are tons of resources out there to help and help guide you, so do your research.The other thing you may be interested in is the following self-paced course:http://www.udacity.com/overview/Course/cs373/CourseRev/apr2012It's Udacity's CS373 "Programming A Robotic Car" course, being taught by Professor Sebastian Thrun from Stanford; with a tagline of "Learn how to program all the major systems of a robotic car from the leader of Google and Stanford's autonomous driving teams", believe me, it's exactly what you are wanting. Then again, I am kinda biased; I am currently taking this course (on Unit 3 this week). It isn't easy, but it is fun!Regarding ultrasonic sensor suggestions: One of the best ultrasonic sensors you can buy is the SensComp (http://www.senscomp.com/) 6500 series; it combines long distance with a fairly narrow beam-width. They aren't cheap though - at least buying them new. However, an almost identical sensor can be had for much less if you are willing to hack an old Polaroid camera (specifically the Sun 660 and Spectra models, but there are others). You can find these cameras in thrift stores and other similar outlets, for $5.00 or so.Other possibilities would be sensors from MaxBotix (http://www.maxbotix.com/) and Hexamite (http://www.hexamite.com/)...
Thanks! I never realized how much academic interest this topic has. I'm going to watch the course, it seems fun.
So far the best option seems to be the maxbotix sensors, even though they aren't cheap. All the other ones aren't close range enough. I have also decided I am not
going to use servos, and just keep the sensors stationary, as it simplifies everything a great deal. Maybe get 4 sensors and place them all facing to the sides or front of the robot, or maybe have an extra facing straight back.
I have also thought about using IR sensors. They seem to be cheaper, but larger and have less range. Are there any you would recommend, or should I focus on sonar?