How to search an openworld map?

I’m writing an NPC that just needs to spawn and move through the reachable NAV 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 small outdoor island. The behavior I’m trying to create is essentially breaking down the nav mesh into separate sections that the npc spends time wandering around in before deeming the area “searched” and picking a new area to move to, simulating a wide ranging outdoor search. I’m seeing some conflicting answers about whether I should be looking into EQS or AI perception and nav mesh invoking or something else. Looking for educated suggestions as to where I should start or any clever ideas on how to execute this.
Thanks! ^^

I made a video trying to better explain my question ^^ Question - UE4 NPC Navigation - How to create searching behavior - YouTube