4 x AA NiMH batteries in series give you 4,8-5,2 V (depending on the state of discharge)
You can select between models with up to 3Ah (4,5 hours work of your robot)
The advantage is that you can use the battery block without 7805 regulator so you will not loose power for reduceing 9V to 5 V (40% of battery power goes for 7805 heating).
The size is about the same.
4 x AAA batteries are smaller, but available capacites are limited to 1Ah, may be 1,2 Ah.
If you have other devices in your robot , that needs for example 3,3 V supply
the inductance type switched mode supply is more efficent that linear stabilisators. (like 7805, LM317).