Encoders are fine, in fact you'll find it harder to solve the problem without them. All your guide is telling you is that you can't assume that driving from one room to another is a standard, pre-specified operation - you may have to adjust your route on the way to avoid obstacles. You can still use encoders for dead reckoning, but you can't say that to get from room one to room two you turn east and go forward for 20,000 encoder clicks - circumstances may have changed this time.
1. SLAM: seems a quite popular field at the moment, but it quite complex and non-intuitive to implement. It also requires a lot of memory - more than the arduino has.