We introduce and study a new optimization problem on querying with uncertainty. k robots are required to locate a hidden item that is placed uniformly at random in one of n different locations, each associated with a probability pi, i= 1, …, n. If the item is placed in location i, a query trial by any of the robots reveals the item with probability pi. Each robot j is assigned a subset Aj of the locations, and is allowed to perform a random walk among them, each time step querying the current location (being visited) for the item. We are interested in determining sets {Aj}j=1,…,k so as to minimize the expected discovery time of the item. We measure the cost by the number of queries, while there is no cost for hopping from node to node. Our first contribution is to prove a closed formula for the expected number of steps until the treasure is found when the robots execute unanimous queries. Then we focus on querying problems where the sets Aj are restricted to be either pairwise disjoint or identical. Our findings allow us to obtain optimal solutions, when sets Aj are exclusively pairwise disjoint, requiring time nO(k). In our second contribution, we devise an optimal polynomial time algorithm for querying with k=2 robots even when the sets A1, A2 are allowed to overlap. All our algorithms are based on special concavity-type properties of the expected termination time when the robots execute unanimous queries, thus inducing special structural properties of optimal solutions for the general problem.

Additional Metadata
Keywords Assignment, Optimization, Partition, Querying, Random walk, Searching
Persistent URL dx.doi.org/10.1007/978-3-319-72751-6_7
Series Lecture Notes in Computer Science
Chuangpishit, H. (Huda), Georgiou, K. (Kostantinos), & Kranakis, E. (2017). Querying with uncertainty. In Lecture Notes in Computer Science. doi:10.1007/978-3-319-72751-6_7