Arduino works bad when powered by 9V battery
I got a fresh 9 V out of a packet and measured it.

 9.58 volts


Now with a load of 500 mA (which you quite likely would get with a robot) it dropped to:

 7.4 volts


With a load of 750 mA the voltage dropped to 6.6 V which is below what you are supposed to supply via the power jack.

And that was with a fresh battery, testing for a few seconds.

Those 9 V batteries are just not designed to drive motors.

I suggest a somewhat heavier-duty battery, like 5 x AA batteries, at least for the robot part.