Optimal Discrete Search with a Map.

点击翻译按钮获取中文摘要

Effective search strategies are necessary in a wide range of real-world situations. The unsuccessful search for Malaysian Airlines flight 370 cost more than two hundred million Australian dollars. It is therefore important to understand how such large amounts of money can be used in the most efficient way possible were a similar even to happen in the future. Not only can the act of searching be very expensive but the risk of not finding the target of the search in time can be even more costly. For example, the earlier a rescue squad can find a missing person after a natural disaster the greater that person's chances of survival.The classical search problem assumes that the target of the search is hidden in one of multiple distinct locations and that when searching the correct location there is a known probability of discovery. In this case, the best possible order to search the locations can be found by modelling the search process as a multi-armed bandit. This is a well-studied mathematical model inspired by slot machines where a series of decisions are made to maximise some reward. In the existing literature, most search models assume that these locations can be moved between instantaneously and at no additional cost. This assumption massively simplifies the problem but doesn't hold in many real-world applications. Over the course of this PhD, our aim is to develop and evaluate the effectiveness of search strategies that incorporate the time or financial costs of traveling between locations.In partnership with Naval Postgraduate School (Monterey, US).