Abstract: | In military scenarios, agents (i.e., troops of soldiers, convoys, and unmanned vehicles) may often have to traverse environments with only a limited intelligence about the locations of adversaries. We study a particular instance of this problem that we refer to as path clearance problem. In path clearance, an agent has to navigate to its goal as quickly as possible without being detected by an adversary. When picking a path to follow, the agent does not know the precise locations of adversaries. Instead, it has a list of their possible locations, each associated with the probability of containing an adversary. Any of these locations can be sensed by either the agent itself at a distance close enough (provided the agent has a capability of long-range sensing) or by one of the scouts (if they are available). If no adversary is present at a sensed location, the agent can then safely traverse through it. Otherwise, the agent has to take a detour. |