One could break down your problem to three areas: memory, speed and I/O.
Memory is pretty straightforward, but you have to estimate it yourself. Things to consider: Are you doing a map? Are you saving past state? If yes how long/much? etc.
Speed is a bit different: Assume you are building a quadcopter: If you have high latency in the controller's feedback loops the thing will not even fly. If you have a ground vehicle on the other hand you could simply drive slower.
Consider how you want to structure the program's control flow: Do you poll for new data all the time or do it interrupt-driven?
How fast should your control loop run and what do you need to calculate during it? How many floating point operations do you need? How large is your map for obstacle avoidance?
Lastly what peripherals, sensors, debugging tools etc. do you want to connect and does the uC have enough connections to allow that?
If this is going to be a rather serious project, I would shy away from arduino, because if you need to have more control over the program and write low-level code things are likely to get messy. The learning curve to develop with Atmel Controllers directly is not that high.
With the meager information you provided I feel like the ATmega32 will be suitable, but if you need a fast control loop consider ARM with a floating point unit.