There are quite a few optimizations you can use. For one, you dont have to get ALL agents, especially if you have a current target. Most of the time you want to focus on firing at a specific target until the threat is neutralized or a new higher priority threat is detected. That rate of detection is kind of the key to optimizing, in that you don’t have to detect all new agents every frame. So in essence you can maintain your current target and then infrequently check for new ones, bearing in mind that if no new threats have entered the scene, then no new target selection is required.
Have a look at Damian Isla’s stuff from GDC about Halo’s AI (its called “building a better battle”).
For the most part you want to avoid physics checks wherever you can. So you might even want to communicate with your enemy target to coordinate the visibility checks. For instance an enemy could have an “I am behind cover” flag that you can check so that he is only targetted whilst out of cover. Turn that into an event and have your BT respond such that you get the event and start firing at him, rather than checking visibility every update.
Then there’s the classic task-list approach, where you do the LOS checks over multiple frames, with a queue of checks to be carried out and some frequency of update control (i.e. you can do 3 checks per frame, so you have to have all total agents doing less than 3 requests per frame to be able to service the queue).
Its a funky problem to play with. Have a look at Matthew Jack’s stuff from CryEngine too (his classification for cover selection and the like is interesting).