Just a random list, if you post your schematic it would probably be easier:
1.8V lithium Coin cells are very easy to find, but more likely your serial interface needs 3.3v? Unless your receiving end will deal with 1.8V.
Leakage current does generally go up as your voltage increases, so lower is better usually. Also consider the brown-out point for the system vs the battery characteristics. The 'death' characteristics of the battery will be determines by the battery chemistry you use. For instance if your uC browns out at 1.7V you may actually want to use a higher voltage battery as with some batteries the output voltage will lower slowly as the battery dies. You'd get more life out of a 3.3V battery as when it begins to die its output will slowly drop and you can operate all the way down to 1.8V. If you use a 1.8V battery your going to shut down fairly quickly as the battery dies. This all assumes your serial interface or other components can deal with a wide voltage range (I know the AVR can).
LED's use a lot of power, unless you use a very low power LED and are controlling its current draw it's probably drawing a lot more current than the AVR is. If its just there for debug, don't populate it for production or only have it blink once in a while or something to minimize its on time, and definitely control its current draw.
If you can, pick the polarity / rest state of your serial interface to draw as little power as possible, it's rest state should not be drawing power. If pull ups are required use the largest resistor possible to maintain signal integrity but minimize current usage. If power is a huge concern use a signally scheme that favor's bits that don't draw power. For instance if you have pull ups, using a protocol that results in lots of 1's in the signal will leave the serial interface in a state that isn't drawing as much power most of the time. Such optimizations are only worthwhile if your making heavy use of the serial bus. If its very lightly used just make sure its rest state isn't drawing power.
Generally speaking you can assume all instructions (reading GPIO, etc) require the same amount of power. Its not really true but the power difference is minimal.
Power usage is much more dependent on the number/type of peripherals you have powered on, and the amount of time the micro spends active vs sleeping. So the ADC uses more power, EEPROM writes use a fair amount of power. Specifically something like the EEPROM writes are usually done in fairly large 'chunks' so you should accumulate as much information as you can before doing the write to the EEPROM (if your even using it of course). For the ADC that micro supports doing the ADC read during 2 of its sleep states, as ADC conversion takes a relatively long time this is a good time to sleep.
You should probably just read the sections on power management, sleep states and minimizing power using in the microcontroller's data sheet: linky page 35 on. Keep the AVR in the deepest sleep state possible as long as possible. The only exception to this is that you have to consider the start up and shutdown time. Its not worth it to sleep for 10 cycles if waking back up takes 25, etc.
Do resistors use up battery life? Do capacitors? Do diodes?
They all do to some extent. Resistors dissipate the most in most applications:
P = V*I
P = V^2 / R or P = I^2 * R (where V is the voltage drop across the resistor)
Diode's have a (relatively) fixed voltage drop, so power dissipation is almost exclusively tied to current passing through the diode. For instance a diode with a 0.7V forward voltage drop, P = 0.7 * I if current is moving forward through the diode. This is a simplification of course and you should check out the operating mode based on the diode's I-V characteristics.
Capacitors theoretically shouldn't dissipate any power, but in reality they have a finite series resistance and non-zero leakage current which means they do dissipate some power, generally not something you should worry about with such low voltages though. That being said choosing capacitors with minimal leakage current and ESR is a power win.
As far as using them to smooth out battery draw, this doesn't really help for power usage, its more for filtering. Also battery chemistry comes into play here, some chemistries will be happier with a constant draw, some deal better with spiky current draws.
Did you read the battery life specs for your smartphone? Did you believe them? Calculating battery life for a smartphone is easier than doing it for a robot. There are many ways to calculate this, and @geometrikal gave a reasonable summary of it. But there is a problem with this approach. The accuracy of your calculations are only as accurate as your data-- and your data is terrible. I posit that while you can do these calculations, the results will be meaningless to the point that you're better off not trying (very hard).
Let's just look at your main drive motors. Some things that can effect the current draw of these motors are: speed, weight, dirt/tile/carpet/floor, acceleration, breaking, etc. Can you accurately predict the usage of your robot and figure out how much power your motor will require? Probably not.
Now look at the arm motors. Same thing applies here. Can you predict how the arm will be used? How much current will the arm require when picking up something heavy vs. something light?
How about your CPU? The power consumption of the CPU depends on what the software is doing. Doing lots of complex calculations with massive memory accesses will consume a lot of current, but sitting idle the CPU power consumption will be less. Many CPU's also have ways to achieve lower power modes by reducing the clock rate, going into a sleep mode, and turning off various peripherals. Have you mapped out how your software is going to work? Does your OS support various power-down modes, and if so then which ones?
Then there is your power system. What is the efficiency of your power supplies at different loads? A typical SMPS efficiency can vary from 60% to 95% depending on the design and what load it is at. If the load is constant then the efficiency of the power supply and the wiring will be different than if the load is pulsed (a.k.a. PWM-ing the motors). Have you worked all this out?
The accuracy of this data is going to directly effect the accuracy of your battery life estimates. The problem is that your accuracy is going to be terrible. There might be a 2x to 20x difference between your low and high estimates.
Here is what I recommend doing:
Go through the exercise with worst case and reasonable numbers. Don't worry about getting it super accurate (since it won't be anyway). Basically all you are doing is seeing if the size of battery is "somewhere near correct". Then, if possible, choose the next larger battery size!
Once the robot is built, build something like a robot course. This is a basic set of operations/movements/etc that the robot can do over and over-- exactly the same way each time. Hopefully this course will approximate what you think will be a typical use for the robot. This course does two things: it tells you what you can expect, but more importantly it gives you a way to judge if any power improvements you made really worked!
Note: The battery life figures that you get from step 2 are only estimates. Even those are only as accurate as your test course. It won't be super accurate for real world uses, but it will be a whole lot more accurate than what you did for step #1 and more accurate for what you might have gotten if you spent weeks calculating everything out.
Best Answer
You are not a million miles away with your estimate. BUT you need to think about what your device is going to be doing to make a real estimate. Use your calculations of:
500mAh / 59mA = 8.47h if your device is only going to be used as a receiver.
Or use the higher value of:
500mAh / 278mA = 1.8h if the device is going to be used as a transmitter.
But you may want to take some other possibilities into your calculations, if you dont need to device actually doing anything for some of the time, you can use the hibernate mode on the device. The current consumption in this mode is 4uA. So if your device lived in this hibernation mode for the whole of its life cycle:
500mAh / 0.004mA = 125,000h or 14 years...
but in general the low power deep sleep is 250uA so:
500mAh / 0.25mA = 2000h so a measly 8.3 days.
One other consideration is the battery life itself, when you look at datasheets, the battery capacity changes with the discharge current. For instance, in this datasheet, at 300mA discharge, the battery has just under 400mAh of capacity, a reduction of 20% from your calculations! but at 25mA, the battery could last over 600mAh, an increase of over 20% from your calculations.
One final thing to consider is that your device doesn't run at 9v, it runs at 3. This means that you need to do some trickery with the voltage. If you want to use regulator, you will instantly reduce your battery life by 60% due to current losses. Another way is to look into buck converters, where you could get a decent efficiency, you might only lose 20% of the battery life. The final consideration would be to change the batteries; if you were to use AA batteries, not only would you increase battery life (much higher mAh rating), you wouldn't get the same losses related to regulation because the voltage would already be lower.
Also, have you thought about using multiple chips instead of a single chip solution? may be easier to quantise current draw for each part. Just a thought