What did you observe about performance?
Nickel metal hydride rechargeable AA could work, and would deliver 9.6V when charged, declining to 6.6V when near end of charge. A suitable capacity of battery may help; what capacity did you select? Capacity is measured in millamp-hours, mAh.
Have you confidence in the cells? Cells that have been used for other purposes for a long time will underperform, causing imbalance.
Have you confidence in the charger? A charger that underperforms will give you some cells fully charged, and some not. When you use them in the Makeblock Ultimate 2.0, the cells that are not fully charged may become exhausted, and the rest of the batteries may then force the exhausted cell into reverse polarity, which will do further damage. The battery pack doesn’t have a battery management system to prevent this. You can prove it happens by measuring each cell voltage with a multimeter at the time the robot is underperforming; a voltage under 1.1V is trouble.
I have seen car boosters on aliexpress and in other places. These are three lithium batteries in series with a battery management system. They have discharge and charge protection. They provide a nominal 12V output. It may be difficult to find one to fit the space available.
I have seen remote control (toy) car battery packs with a nominal 9V output, along with a midpoint connection for use by purpose-built chargers. These chargers prevent cell imbalance. You may be more able to find one with suitable size, and get the corresponding charger.
You could use a couple of 18650 cells, but you’ll need a battery management system to prevent cell imbalance in the pack. You can get protected 18650 cells, which trade-off some of the space for a cell protection circuit.
Charging with USB would be difficult though; the voltage and power available may be insufficient. A special step-up charger could do it, at a loss; i.e. longer charge times.
