Searching for a hidden target is a common task in everyday life, and an important computational problem with numerous applications. Searching in Operations Research and Theoretical Computer Science is often studied as an online problem under the framework of competitive analysis. In contrast, online searching has not caught sufficiently the attention of the AI world. In this research proposal we address some of the reasons behind this disconnect, and propose several directions for bringing online search closer to the AI domain. Our objective is to make online search more efficient in practice but also applicable to more realistic settings, without compromising the worst-case, theoretical guarantees.
This PhD research project has been submitted for a funding request to “Sorbonne Center for Artificial Intelligence (SCAI)”. The PhD candidate selected by the project leader will therefore participate in the project selection process (including a file and an interview) to obtain funding.