There is in essence no change in weight as a battery discharges.
Batteries are electrochemical devices. A chemical reduction reaction occurs, which includes an electron exchange to convert one molecule of "stuff" in the battery into another. A battery is set up so that an electron has to travel from one plate through the wire to the other plate to become "available" to complete reduction of a molecule of the battery chemistry to a lower energy form.
The power derived in a battery is the total energy
difference between the two molecular forms, times the number of molecules in the battery involved in the chemical reaction. (In other words, a bigger battery = more chemicals to react = more total power. <Add Tim Allen Grunts here...>

)
Since all of the atoms involved are still
in the battery before
and after this action (in this case, air is not significantly involved as would be in a gas engine) and only their
combination has changed, there is
NO change in weight as it discharges.
However, what Al said is correct in that as you
recharge the battery, you'll typically "boil off" some of the liquid in the electrolyte, or form a gas such as Hydrogen as a byproduct, which
does reduce the weight
slightly with each recharge. However, this change is
very small WRT the total weight of the battery. Hardly noticeable (unless your charger is broken and boils away ALL of the electrolyte, in which case you have OTHER problems!

.
For our purposes, since the weight while discharging remains the same, your robot will <i>not</i> become lighter as it runs out of power (like a car does as by using up gasoline and throwing the chemical byproducts away as exhaust).
I believe you'll find the differences in plastic molding or plate material between serial numbers of a battery will <i>far</i> outweigh <i>any</i> chemistry "vanishing" effects from multiple recharges over the entire useful life of the battery.
I hope that clears this up.
- Keith McClary, Advisor, Huron High Team 830 "Rat Pack"