Rather than adjusting the PID constants in relation to the battery voltage, you should be able to scale the drive signal (the output of the PID loop) to the motors in relation to the battery voltage. Higher battery voltage->smaller drive signal for a given PID state. Done properly, this should give you a constant relationship between the drive signal from the PID and the motor torque.
Another option would be to regulate the motor current and have the output of the PID loop control the setpoint for the current loop. Obviously this requires additional hardware that you may not have in your robot, but it eliminates the battery voltage from the equation--as long as you design the system to operate effectively even at minimum battery voltage, since this will affect the possible current drive range. The current loop doesn't even necessarily need to be PID--a simple threshold detector that steers a PWM signal can be effective, if it's fast enough, and comes with dithering built-in. More advanced implementations could use an MCU's DAC and analog comparator peripherals to implement a comparator-based current loop. See app notes for MCU-based switching converters for some hints.