Evaluating options every time the A.I move and with that information, perhaps changing actions is what was done in Heroes III and that worked.
I just don't understand what takes a great deal of CPU power. The A.I needs to keep the wandering monsters (WMs) in memory and then manouver around them.
It can also attack a monster and then run around the battlefield while the Sovereign blasts the monster with spells and conjures monsters of his own.
An important thing about this is sightdistance and movementspeed. How far into the FoW can units see? Do all units see the same distance or do some see further? How much will the 'Scout Pack' enhance sightdistance?
How far do different monsters move? Do some low-midlvl monsters have both a good sightdistance AND a good movementrate? They are death for pioneers then. But put a military unit with them and you can fight that monster.