Openworld Search/Hunt NPC

I need help figuring out how to approach blueprinting an NPC that progresses through the reachable navigation mesh of an open world map, roaming to sections it hasn’t seen yet. The map has a few small structures on it but is essentially a medium sized outdoor island. The behavior I’m trying to create is essentially breaking down the navigation mesh into separate sections that the npc spends time wandering around in, before deeming the area “searched” and picking a new adjacent or nearby area to move to, simulating a wide ranging outdoor search. Almost like the searching of the investigators in the Evil Genius games. I want to be able to spawn a number of them and have them spread out across the map, covering it eventually if given time. I’m still learning working with blueprints and I’m not 100% sure where to start. I’m seeing some conflicting answers about whether I should be looking into EQS or AI perception and navigation mesh invoking or something else all together because the map is large. Looking for educated suggestions as to where I should start or any clever ideas on how to execute this. Thank you!

I created a previs animation to hopefully make the concept more clear