I know its complex but you could keep a list of the poly's of your terrain in an array of some type, along with their position's and whatever data about them you need.. along with a flag as to whether or not it is "walkable" or "unpassable" or whatever it happens to be, basically you would setup the poly's to be like nodes that the algorithm can navigate through.
or you can build a set of nodes into the map itself as you build it in whichever app you are using, that can be used by your ai to navigate with, like your "ai map" idea.
Once you have an environment that can be navigated through, you can setup groups of nodes to minimize the amount of initial checks, for instance you wouldnt even consider the ones that are unpassable, a set of nodes flagged as flat ground or road would make travel faster so would be the desired route if possible, hills or rough terrain would be lowest priority as it would slow travel. assuming that your ai would know where it wanted to go, it would have a destination for the algorithm to work bak from to find the quickest way to the destination.
you could also for instance, setup node properties that tell your ai where it can find the best cover cover when its being shot at as its moving around, or which is the best route to drive that tank along to run over the player.
In relation to agents getting stuck, you would need to have some kind of contingency for that, if they are meant to be doing one action, like walking to a destination, and you know roughly how long it should take, if it hasnt occured in a reasonable time, you could maybe rotate the agent and walk it a little in a different direction, or teleport it a short way from where it is etc.
with nodes, you could also pre-define paths for your ai to get from certain areas of your map to other areas, roads from one town to another, or along a trench from bunker to bunker for example, and have it prioritize using them to reduce pathfinding calculations during runtime, of course then you have to worry about it becoming predictable..
If it ain't broke.... DONT FIX IT !!!
