Arduino & Motors on Battery Power

you could use gel-cells. They have a super high Ah for a lower price than LiPoly's/LiIon's. You can even recharge them with a solar cell.

P.S. - AVRman - You couldn't have picked a funnier picture!