Optimal Search Problems

One active area of research within STOR-i is the problem of how to optimally search for something or someone. This is a problem of practical importance with it being used for many real world applications. Bomb disposal squads need to search for unexploded ordinance, search parties want to look for survivors of disasters and the police want to find people on the run from the law.

Like most things the best way to build intuition to a problem is to start by constructing smaller toy models of the system. We can represent the places where an object might be hidden as arcs in a network which are connected to each other with nodes. This type of structure is deliberately similar to that of a road system, the arcs represent streets and the nodes are the street corners. The object that we want to find will be hidden along one of the streets and the job of those searching is to find it as quickly as possible.

search

Example Network for Optimal Searches

The p_i‘s are the probabilities of detecting the object along the arc i. These are prior probabilities, what you think the probability of the object being hidden there are before you start. The arrows denote the direction that the searcher can travel along the arc, you can go in either direction or in some cases only one. This reflects the geography of the search space in the problem, not all areas are accessible in multiple directions like a one-way street.

The idea is that the object or person is hidden along one of these arcs and there is also a person trying to find them. This searcher wants to move along the arcs in such a way along the directed arcs such that it minimises the expected time to discover the object.

Speed vs Accuracy

A more realistic extension to this simple model is to take into account the fact that we can search at different speeds and accuracies. There is clearly a trade-off to be had between how quickly you search and how carefully you search. Consider looking for survivors after an air crash. You might be able to cover vast distances in an aeroplane, but the chances of seeing any people on the ground are quite small. On the other hand sending a ground team to check out the area will be very likely to find survivors if they are there, but it make time them a very long time to move across a small area.

ship

Patrol boats can vary speeds

The simplest way of implementing this into our model would be look at two speeds of a patrol boat, fast and slow. When the boat is moving slowly it has a higher chance of detection than when it is travelling quickly, q_i^F < q_i^S. Conversely the time that it takes to patrol a region is shorter when going quickly so t_i^F < t_i^S.

This means that every arc now has a choice of two speeds and a probability of detection for each speed. Of course in reality speed and detection’s will be continuous distributions rather than the discrete values we are using.

search2

Now a choice of two actions: fast and slow

Multi-Armed Bandit Approach

One way of looking at solving this problem is to notice its similarities with the Multi-Armed Bandit problem. In this case we have a trade-off between speed and accuracy whilst wanting to minimise the time to find something, whereas in the classic Multi-Armed Bandit problem we have a balance between exploration and exploitation.

There are however a couple of factors that have to be considered that don’t naturally fit into the MAB framework.

  • The choice of arms to play is restricted

In classic MAB problems you can play any bandit that you want to. In our case the pattern of the network limits your choice. For example if you’ve just played p_3 in the network above, you can only play p_4 or p_7 next.

  • Each arm has two options for playing it

Normally bandits only have a single arm to pull and a single payoff. In the search problem we not only have to decide whether to play a particular arm or not, but which speed to select as well. This is known as a super-process.

Matters are even more complicated if you are searching for someone who doesn’t want to be found. In this case you can be sure that adversary will try to hide in a hard to find location in order to maximise the time it takes for the searcher to find them. This leads the problem into some other aspects of mathematics such as game theory.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s