Motors on a Micromouse consumes most of the power. For most micromice, each stepper typically consumes 1.5W to 3W on the average. For differential steering, two stepper motors consume up to 6W. By comparison, the logic components typically draw a total of about 80mA. Even at a supply voltage of 12V, the logic component only consumes 1W.
If we assume the whole robot consume 7W, it requires 6300J of energy to last 15 minutes. If we use a 12V battery, it must have a capacity of 6300J/12V=525Asec or 145.8mAH. This may imply that getting a battery of 150mAH is sufficient. Unfortunately, the discharge curve of a 150mAH will not sustain the required voltage for 15 minutes.
It is not an overkill to double or triple the capacity estimate. In addition to just making sure there is enough energy to last 15 minutes, a battery of high capacity can also deliver power better due to a lower internal resistance. Most NiMH or NiCd batteries are specified to discharge healthily at 1C. This means a battery with a capacitor of 150mAH can healthily discharge at 150mA. You must take this into consideration when choosing the capacity of your battery. In our current example, it is actually very reasonable to use a battery with a capacity of 500mAH (at 12V).