How big are the "dots"? You could (in theory) create a very low-res "eye" using a bunch of phototransistors in a matrix (say 8x8, or 64 phototransistors), and row/column scan them (very similar to row/column scanning an LED array). Focus an image on the array using a lens. You might even be able to figure out a way to do greyscale measurements in a fashion (you'd need some tweaks to the circuit). Your "dots", depending on their size, would show up as crude circles in the array.
Another possibility (which would probably be simpler and cheaper to implement) would be to use the camera device from an optical mouse; you would have to come up with your own optics system again, and used in this way (raw image dumping), such devices are pretty slow (1-3 frames per second) - but they might work ok for your application. Plenty of articles out there on how to use such devices with microcontrollers and such.
If you aren't going to use GPS, and are going for strict dead-reckoning using wheel encoders (note that such a system is very, very inaccurate), adding a compass module can only help. I would seriously rethink about adding GPS, though.
Finally - for wall/edge detection, I would use a combination of sensors, but at minimum, IR or Ultrasonic + physical feeler switches. IR is ok for wall/edge surfaces that will reflect IR light; should the edge/wall be a flat black color, it will probably fail. Ultrasonics are good when the surface to be detected is a fairly solid surface capable of reflecting an ultrasonic signal; hard and flat surfaces work best - a fluffy pillow (or an ornate or rought wall surface) less so...