AI (for the most part) doesn't require that much processing power because practically all AI is scripted; to produce smarter AI you usually just write more scripts in order to cover all of the scenerios.
With that in mind, technically speaking you could have done a lot of this stuff earlier and I see very little reason why it wouldn't have been possible on the XBox. The graphics would have probably taken quite a large hit though.