While the AI problem of Fire Emblem isn't easy, it's likely a magnitude smaller than the Hero Academy on.

IIRC, in Fire Emblem every character gets some small amount of actions per turn, whereas in Hero Academy you have a pool of action points that you can spend among all your characters.

I mean there's some complexity beyond that simple description in FE (which hero moves first, their positioning and abilities can affect effectiveness of subsequent moves), but fundamentally the tree you must traverse is a lot wider and deeper with Hero Academy.