I don't think using NiCads on a robot would be ideal. NiCads have a nasty habit of forming "memories," meaning it's best to discharge them most of the way before recharging them. NiMH would be cool, LiIon would rock. I'm not sure about the charge rate for LiIon, but I've read the ideal charge rate for NiMH to be .1C, with a charge rate of 1C causing a few hundred cycle reduction in life. Hydrogen fuel cells would grab attention, but they are quite impractical at present
*shrug* I really think the Lead-Acids do the job just fine.