Algorithms for \(p\)-Faulty Search on a half-line. (English) Zbl 07729252
Summary: We study p-Faulty Search, a variant of the classic cow-path optimization problem, where a unit speed robot searches the half-line (or 1-ray) for a hidden item. The searcher is probabilistically faulty, and detection of the item with each visitation is an independent Bernoulli trial whose probability of success \(p\) is known. The objective is to minimize the worst case expected detection time, relative to the distance of the hidden item to the origin. A variation of the same problem was first proposed by Gal (Search games, Academic Press, New York, 1980). Alpern and Gal (The theory of search games and rendezvous, Springer, Berlin, 2003) proposed a so-called monotone solution for searching the line (2-rays); that is, a trajectory in which the newly searched space increases monotonically in each ray and in each iteration. Moreover, they conjectured that an optimal trajectory for the 2-rays problem must be monotone. We show that an analogous conjecture for the case where the search domain is the half-line cannot be correct. Indeed, we provide a lower bound for all monotone algorithms, which we also match with an upper bound. Our main contribution is the design and analysis of a sequence of refined search strategies, outside the family of monotone algorithms, which we call t-sub-monotone algorithms. Such algorithms induce performance that is strictly decreasing with \(t\), and for all \(p \in (0,1)\). The value of \(t\) quantifies, in a certain sense, how much our algorithms deviate from being monotone, demonstrating that monotone algorithms are sub-optimal when searching the half-line.
References:
| [1] | Ahlswede, R.; Wegener, I., Search Problems (1987), New York: Wiley-Interscience, New York · Zbl 0647.90023 |
| [2] | Albers, S.; Henzinger, MR, Exploring unknown environments, SIAM J. Comput., 29, 4, 1164-1188 (2000) · Zbl 0947.68165 · doi:10.1137/S009753979732428X |
| [3] | Alpern, S.; Fokkink, R.; Gasieniec, L.; Lindelauf, R.; Subrahmanian, V., Search Theory: A Game Theoretic Perspective, 223-230 (2013), New York: Springer, New York · Zbl 1356.91014 · doi:10.1007/978-1-4614-6825-7_14 |
| [4] | Alpern, S.; Gal, S., The Theory of Search Games and Rendezvous (2003), Berlin: Springer, Berlin · Zbl 1034.91017 |
| [5] | Angelopoulos, S.: Further connections between contract-scheduling and ray-searching problems. In: Q.Y. 0001, M.J. Wooldridge (eds.) Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2015, Buenos Aires, Argentina, July 25-31, 2015, pp. 1516-1522. AAAI Press (2015). http://ijcai.org/proceedings/2015 |
| [6] | Angelopoulos, S.; Dürr, C.; Lidbetter, T., The expanding search ratio of a graph, Discrete Appl. Math., 260, 51-65 (2019) · Zbl 1425.90123 · doi:10.1016/j.dam.2019.01.039 |
| [7] | Baeza Yates, R.; Culberson, J.; Rawlins, G., Searching in the plane, Inf. Comput., 106, 2, 234-252 (1993) · Zbl 0781.68044 · doi:10.1006/inco.1993.1054 |
| [8] | Beck, A., On the linear search problem, Israel J. Math., 2, 4, 221-228 (1964) · Zbl 0168.39502 · doi:10.1007/BF02759737 |
| [9] | Bellman, R., An optimal search, SIAM Rev., 5, 3, 274-274 (1963) · doi:10.1137/1005070 |
| [10] | Bose, P.; De Carufel, JL, A general framework for searching on a line, Theor. Comput. Sci., 703, 1-17 (2017) · Zbl 1380.68453 · doi:10.1016/j.tcs.2017.08.023 |
| [11] | Bose, P.; De Carufel, JL; Durocher, S., Searching on a line: a complete characterization of the optimal solution, Theor. Comput. Sci., 569, 24-42 (2015) · Zbl 1312.68210 · doi:10.1016/j.tcs.2014.12.007 |
| [12] | Brandt, S., Foerster, K.T., Richner, B., Wattenhofer, R.: Wireless evacuation on m rays with k searchers. In: SIROCCO, pp. 140-157 (2017) · Zbl 1437.68202 |
| [13] | Brandt, S., Laufenberg, F., Lv, Y., Stolz, D., Wattenhofer, R.: Collaboration without communication: evacuating two robots from a disk. In: CIAC, pp. 104-115 (2017) · Zbl 1487.68241 |
| [14] | Brandt, S., Uitto, J., Wattenhofer, R.: A tight lower bound for semi-synchronous collaborative grid exploration. In: DISC, pp. 13:1-13:17 (2018) · Zbl 1497.68037 |
| [15] | Burgard, W.; Moors, M.; Stachniss, C.; Schneider, FE, Coordinated multi-robot exploration, IEEE Trans. Robot., 21, 3, 376-386 (2005) · doi:10.1109/TRO.2004.839232 |
| [16] | Chuangpishit, H.; Georgiou, K.; Sharma, P., A multi-objective optimization problem on evacuating 2 robots from the disk in the face-to-face model; trade-offs between worst-case and average-case analysis, Information, 11, 11, 506 (2020) · doi:10.3390/info11110506 |
| [17] | Cohen, L., Emek, Y., Louidor, O., Uitto, J.: Exploring an infinite space with finite memory scouts. In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 207-224. SIAM (2017) · Zbl 1411.68078 |
| [18] | Czyzowicz, J., Gasieniec, L., Gorry, T., Kranakis, E., Martin, R., Pajak, D.: Evacuating robots via unknown exit in a disk. In: F. Kuhn (ed.) Distributed Computing—28th International Symposium, DISC 2014, Austin, TX, USA, October 12-15, 2014. Proceedings, Lecture Notes in Computer Science, vol. 8784, pp. 122-136. Springer (2014) · Zbl 1393.68164 |
| [19] | Czyzowicz, J.; Georgiou, K.; Killick, R.; Kranakis, E.; Krizanc, D.; Lafond, M.; Narayanan, L.; Opatrny, J.; Shende, S., Time-energy tradeoffs for evacuation by two robots in the wireless model, Theor. Comput. Sci., 852, 61-72 (2020) · Zbl 1477.68313 · doi:10.1016/j.tcs.2020.11.014 |
| [20] | Czyzowicz, J., Georgiou, K., Killick, R., Kranakis, E., Krizanc, D., Lafond, M., Narayanan, L., Opatrny, J., Shende, S.M.: Energy consumption of group search on a line. In: C. Baier, I. Chatzigiannakis, P. Flocchini, S. Leonardi (eds.) 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, LIPIcs, vol. 132, pp. 137:1-137:15. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2019). http://www.dagstuhl.de/dagpub/978-3-95977-109-2 · Zbl 1498.68028 |
| [21] | Czyzowicz, J.; Georgiou, K.; Killick, R.; Kranakis, E.; Krizanc, D.; Narayanan, L.; Opatrny, J.; Shende, S., Priority evacuation from a disk: the case of n= 1, 2, 3, Theor. Comput. Sci., 806, 595-616 (2020) · Zbl 1437.68173 · doi:10.1016/j.tcs.2019.09.026 |
| [22] | Czyzowicz, J.; Georgiou, K.; Killick, R.; Kranakis, E.; Krizanc, D.; Narayanan, L.; Opatrny, J.; Shende, S., Priority evacuation from a disk: The case of \(n\ge 4\), Theor. Comput. Sci., 846, 91-102 (2020) · Zbl 1464.68401 · doi:10.1016/j.tcs.2020.09.023 |
| [23] | Czyzowicz, J.; Georgiou, K.; Kranakis, E.; Flocchini, P.; Prencipe, G.; Santoro, N., Chapter 14: Group search and evacuation, Distributed Computing by Mobile Entities; Current Research in Moving and Computing, 335-370 (2019), Berlin: Springer, Berlin · doi:10.1007/978-3-030-11072-7_14 |
| [24] | Czyzowicz, J., Kranakis, E., Krizanc, D., Narayanan, L., Opatrny, J., Shende, M.: Linear search with terrain-dependent speeds. In: CIAC, pp. 430-441 (2017) · Zbl 1486.68188 |
| [25] | Czyzowicz, J., Kranakis, E., Krizanc, K., Narayanan, L., Opatrny, J., Shende, S.: Wireless autonomous robot evacuation from equilateral triangles and squares. In: ADHOCNOW, pp. 181-194. Springer (2015) |
| [26] | Demaine, ED; Fekete, SP; Gal, S., Online searching with turn cost, Theor. Comput. Sci., 361, 2, 342-355 (2006) · Zbl 1097.68031 · doi:10.1016/j.tcs.2006.05.018 |
| [27] | Feinerman, O., Korman, A., Lotker, Z., Sereni, J.S.: Collaborative search on the plane without communication. In: Proceedings of the 2012 ACM symposium on Principles of Distributed Computing, pp. 77-86 (2012) · Zbl 1301.68230 |
| [28] | Fraigniaud, P.; Korman, A.; Rodeh, Y., Parallel Bayesian search with no coordination, J. ACM, 66, 3, 1-28 (2019) · Zbl 1427.68359 · doi:10.1145/3304111 |
| [29] | Gal, S., Search Games (1980), New York: Academic Press, New York · Zbl 0439.90102 |
| [30] | Gal, S.: Search Games. Wiley Encyclopedia for Operations Research and Management Science (2011) |
| [31] | Georgiou, K., Karakostas, G., Kranakis, E.: Search-and-fetch with 2 robots on a disk: wireless and face-to-face communication models. Discrete Math. Theor. Comput. Sci. 21(3) (2019). https://dmtcs.episciences.org/5528 · Zbl 1416.68191 |
| [32] | Georgiou, K., Kranakis, E., Leonardos, N., Pagourtzis, A., Papaioannou, I.: Optimal cycle search despite the presence of faulty robots. In: 15th International Symposium on Algorithms and Experiments for Wireless Sensor Networks (ALGOSENSORS’19), Lecture Notes in Computer Science, to appear. Springer (2019) · Zbl 07691950 |
| [33] | Georgiou, K., Lucier, J.: Weighted group search on a line. In: International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics, pp. 124-139. Springer (2020) · Zbl 1475.68391 |
| [34] | Jeż, A.; Łopuszański, J., On the two-dimensional cow search problem, Inf. Process. Lett., 109, 11, 543-547 (2009) · Zbl 1215.68276 · doi:10.1016/j.ipl.2009.01.020 |
| [35] | Kagan, E.; Ben-Gal, I., Search and Foraging: Individual Motion and Swarm Dynamics (2015), Boca Raton: CRC Press, Boca Raton · Zbl 1327.68006 · doi:10.1201/b18604 |
| [36] | Kao, MY; Reif, JH; Tate, SR, Searching in an unknown environment: An optimal randomized algorithm for the cow-path problem, Inf. Comput., 131, 1, 63-79 (1996) · Zbl 0876.68030 · doi:10.1006/inco.1996.0092 |
| [37] | Koutsoupias, E., Papadimitriou, C., Yannakakis, M.: Searching a fixed graph. In: ICALP 96, pp. 280-289. Springer (1996) · Zbl 1045.90532 |
| [38] | Lamprou, I., Martin, R., Schewe, S.: Fast two-robot disk evacuation with wireless communication. In: DISC, pp. 1-15 (2016) · Zbl 1393.68166 |
| [39] | Pattanayak, D., Ramesh, H., Mandal, P., Schmid, S.: Evacuating two robots from two unknown exits on the perimeter of a disk with wireless communication. In: ICDCN, pp. 20:1-20:4 (2018) |
| [40] | Reingold, O.: Undirected st-connectivity in log-space. In: STOC, pp. 376-385 (2005) · Zbl 1192.68374 |
| [41] | Schwefel, HPP, Evolution and Optimum Seeking: The Sixth Generation (1993), Hoboken: Wiley, Hoboken |
| [42] | Stone, L., Theory of Optimal Search (1975), New York: Academic Press, New York · Zbl 0343.90030 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
