Motor polarity

I am working on a robotic project and am in need of some help. I need a way to flip the polarity of the motor leads so it can go either forward or backwards. I first tried to use a motor shield but for some reason it doesn't work out. As soon as I put the robot on the rug it wont budge and on my desk it barely moves. Now if I hook the motor up directly to the battery it is really strong and fast even on the carpet. So I am assuming that the motor shield isn't letting all the current through or limiting it somehow.

I currently have a set up like this which is working perfectly as far as being able to move:
http://www.instructables.com/file/F9LKDFGGU7FXUMH

I use a TIP120 and can control the motor to move forwards but obviously not backwards yet. I know there are H-Bridges but I was trying researching about them and from what I read (I don't know if it's true), but the arduino and the motor would have to be sharing the voltage supply which I really don't want. An H-Bridge would work out good as long as I can somehow have the motor's running on their own battery.

I also considered just using two SPDT relay's and connect them up to switch the polarity. Only problem then is it would be either always forward or always backwards and never just at a rest without adding another relay or getting a transistor or two in there. Anyone have ideas on how I can do this?

What's the motor? supply? motor shield?

Sounds like you're victim to the voltage drop from the darlington H-bridges
which lose 2 to 3V in their output drivers. MOSFET H-bridges don't have this
problem.

If your handy
There are Electronic Speed Controls with reverse in the RC World..They could be used here, They work on PWM ..

If your motor's dont draw to much current a guy could use a servo control board from just about any standard servo to run the motor.

The motors are generic because its from an RC car, probably nothing too fancy though. The shield is a Motor Shield V1.2 by Seeed studio

I ended up just building my own motor shield using two relays. When I really thought about, the robot isn't going to be stopped anyway. If I get into the project and realize I do need them stopped I'll look back into it. But as far as the shield goes, does that mean if I had a different shield I wouldn't run into this problem?