New robot:battery drainage advice, mechanical design improvement

supercap:
motors are from radioshack, says 9-18v on package, 1.98A, 18000rpm

Got a part number for them? I wonder if 18000 RPM is @ 18 volts? Even if it were 1000 RPM per volt (?), that would still be 9000 RPM on the low end...

Hmm...

You're either going to want to get lower voltage motors, or use a 9-12 VDC supply from AA cells (6-8 cells in series). In either case, you are going to want much larger wheels, or figure out a way to gear the motors down in some other manner (maybe with pulleys and rubber bands or similar).