Abstract
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 \(p_i\), \(i=1,\ldots ,n\). If the item is placed in location i, a query trial by any of the robots reveals the item with probability \(p_i\). Each robot j is assigned a subset \(A_j\) 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 \(\{A_j\}_{j=1,\ldots ,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 \(A_j\) are restricted to be either pairwise disjoint or identical. Our findings allow us to obtain optimal solutions, when sets \(A_j\) are exclusively pairwise disjoint, requiring time \(n^{O(k)}\). In our second contribution, we devise an optimal polynomial time algorithm for querying with \(k=2\) robots even when the sets \(A_1,A_2\) 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.
K. Georgiou and E. Kranakis—Research supported in part by NSERC Discovery grant.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Agarwal, P.K., Aronov, B., Har-Peled, S., Phillips, J.M., Yi, K., Zhang, W.: Nearest neighbor searching under uncertainty ii. In: Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pp. 115–126. ACM (2013)
Ahlswede, R., Wegener, I.: Search Problems. Wiley-Interscience, Hoboken (1987)
Alpern, S., Gal, S.: The Theory of Search Games and Rendezvous, vol. 55. Kluwer Academic Publishers, Dordrecht (2002)
Alpern, S., Gal, S.: The Theory of Search Games and Rendezvous. Springer, Heidelberg (2003). https://doi.org/10.1007/b100809
Baeza Yates, R., Culberson, J., Rawlins, G.: Searching in the plane. Inf. Comput. 106(2), 234–252 (1993)
Beck, A.: On the linear search problem. Isr. J. Math. 2(4), 221–228 (1964)
Beck, A., Warren, P.: The return of the linear search problem. Isr. J. Math. 14(2), 169–183 (1973)
Bellman, R.: An optimal search. SIAM Rev. 5(3), 274 (1963)
Chakravarty, A.K., Orlin, J.B., Rothblum, U.G.: Technical note–a partitioning problem with additive objective with an application to optimal inventory groupings for joint replenishment. Oper. Res. 30(5), 1018–1022 (1982)
Chrobak, M., Gąsieniec, L., Gorry, T., Martin, R.: Group search on the line. In: Italiano, G.F., Margaria-Steffen, T., Pokorný, J., Quisquater, J.-J., Wattenhofer, R. (eds.) SOFSEM 2015. LNCS, vol. 8939, pp. 164–176. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46078-8_14
Czyzowicz, J., Georgiou, K., Kranakis, E., Krizanc, D., Narayanan, L., Opatrny, J., Shende, S.: Search on a line with byzantine robots. In: ISAAC. LIPCS (2016)
Czyzowicz, J., Kranakis, E., Krizanc, D., Narayanan, L., Opatrny, J.: Search on a line with faulty robots. In: Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, pp. 405–414. ACM (2016)
Deng, X., Kameda, T., Papadimitriou, C.: How to learn an unknown environment. In: FOCS, pp. 298–303. IEEE (1991)
Feinerman, O., Korman, A.: Memory lower bounds for randomized collaborative search and implications for biology. In: Aguilera, M.K. (ed.) DISC 2012. LNCS, vol. 7611, pp. 61–75. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-33651-5_5
Fomin, F.V., Thilikos, D.M.: An annotated bibliography on guaranteed graph searching. Theoret. Comput. Sci. 399(3), 236–245 (2008)
Hanusse, N., Ilcinkas, D., Kosowski, A., Nisse, N.: Locating a target with an agent guided by unreliable local advice: how to beat the random walk when you have a clock? In: Proceedings of the 29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, pp. 355–364. ACM (2010)
Hanusse, N., Kavvadias, D.J., Kranakis, E., Krizanc, D.: Memoryless search algorithms in a network with faulty advice. TCS 402(2–3), 190–198 (2008)
Kao, M.-Y., Ma, Y., Sipser, M., Yin, Y.: Optimal constructions of hybrid algorithms. J. Algorithms 29(1), 142–164 (1998)
Kao, M.-Y., Reif, J.H., Tate, S.R.: Searching in an unknown environment: an optimal randomized algorithm for the cow-path problem. Inf. Comput. 131(1), 63–79 (1996)
Kranakis, E., Krizanc, D.: Searching with uncertainty. In: 6th International Colloquium on Structural Information & Communication Complexity, SIROCCO 1999, Lacanau-Ocean, France, 1–3 July 1999, pp. 194–203 (1999)
Stone, L.: Theory of Optimal Search. Academic Press, New York (1975)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Chuangpishit, H., Georgiou, K., Kranakis, E. (2017). Querying with Uncertainty. In: Fernández Anta, A., Jurdzinski, T., Mosteiro, M., Zhang, Y. (eds) Algorithms for Sensor Systems. ALGOSENSORS 2017. Lecture Notes in Computer Science(), vol 10718. Springer, Cham. https://doi.org/10.1007/978-3-319-72751-6_7
Download citation
DOI: https://doi.org/10.1007/978-3-319-72751-6_7
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-72750-9
Online ISBN: 978-3-319-72751-6
eBook Packages: Computer ScienceComputer Science (R0)