The latest issue of IEEE Trans. on Robotics is all about SLAM. There are some interesting new algorithms, and articles on all the old ones. This stuff actually works now, with nothing more than a camera as input.
Willow Garage is implementing some SLAM algorithms and open sourcing the code by putting it back into OpenCV.
If your robot has at least PC-level compute power, there's no reason any more that it shouldn't know where it is and what's around it.
John Nagle