{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T04:28:12Z","timestamp":1772252892578,"version":"3.50.1"},"reference-count":58,"publisher":"MDPI AG","issue":"11","license":[{"start":{"date-parts":[[2020,10,29]],"date-time":"2020-10-29T00:00:00Z","timestamp":1603929600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Information"],"abstract":"<jats:p>The problem of evacuating two robots from the disk in the face-to-face model was first introduced by Czyzowicz et al. [DISC\u20192014], and has been extensively studied (along with many variations) ever since with respect to worst-case analysis. We initiate the study of the same problem with respect to average-case analysis, which is also equivalent to designing randomized algorithms for the problem. In particular, we introduce constrained optimization problem 2EvacF2F, in which one is trying to minimize the average-case cost of the evacuation algorithm given that the worst-case cost does not exceed w. The problem is of special interest with respect to practical applications, since a common objective in search-and-rescue operations is to minimize the average completion time, given that a certain worst-case threshold is not exceeded, e.g., for safety or limited energy reasons. Our main contribution is the design and analysis of families of new evacuation parameterized algorithms which can solve 2EvacF2F, for every w for which the problem is feasible. Notably, the worst-case analysis of the problem, since its introduction, has been relying on technical numerical, computer-assisted calculations, following tedious robot trajectory analysis. Part of our contribution is a novel systematic procedure, which given any evacuation algorithm, can derive its worst- and average-case performance in a clean and unified way.<\/jats:p>","DOI":"10.3390\/info11110506","type":"journal-article","created":{"date-parts":[[2020,10,29]],"date-time":"2020-10-29T09:44:53Z","timestamp":1603964693000},"page":"506","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["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"],"prefix":"10.3390","volume":"11","author":[{"given":"Huda","family":"Chuangpishit","sequence":"first","affiliation":[{"name":"Department of Mathematics, Ryerson University, 350 Victoria St., Toronto, ON M5B 2K3, Canada"}]},{"given":"Konstantinos","family":"Georgiou","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Ryerson University, 350 Victoria St., Toronto, ON M5B 2K3, Canada"}]},{"given":"Preeti","family":"Sharma","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Ryerson University, 350 Victoria St., Toronto, ON M5B 2K3, Canada"}]}],"member":"1968","published-online":{"date-parts":[[2020,10,29]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Czyzowicz, J., Gasieniec, L., Gorry, T., Kranakis, E., Martin, R., and Pajak, D. (2014, January 12\u201315). Evacuating Robots via Unknown Exit in a Disk. Proceedings of the DISC, Austin, TX, USA.","DOI":"10.1007\/978-3-662-45174-8_9"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1007\/BF02759737","article-title":"On the linear search problem","volume":"2","author":"Beck","year":"1964","journal-title":"Isr. J. Math."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1137\/1005070","article-title":"An optimal search","volume":"5","author":"Bellman","year":"1963","journal-title":"SIAM Rev."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"525","DOI":"10.1287\/opre.16.3.525","article-title":"A survey of search theory","volume":"16","author":"Dobbie","year":"1968","journal-title":"Oper. Res."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"469","DOI":"10.1002\/1520-6750(199108)38:4<469::AID-NAV3220380404>3.0.CO;2-E","article-title":"A survey of the search theory literature","volume":"38","author":"Benkoski","year":"1991","journal-title":"Nav. Res. Logist. (NRL)"},{"key":"ref_6","unstructured":"Stone, L. (1975). Theory of Optimal Search, Academic Press."},{"key":"ref_7","unstructured":"Ahlswede, R., and Wegener, I. (1987). Search Problems, Wiley-Interscience."},{"key":"ref_8","unstructured":"Alpern, S., and Gal, S. (2002). The Theory of Search Games and Rendezvous, Kluwer Academic Publishers."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Alpern, S., Fokkink, R., Gasieniec, L., Lindelauf, R., and Subrahmanian, V. (2013). Ten Open Problems in Rendezvous Search. Search Theory: A Game Theoretic Perspective, Springer.","DOI":"10.1007\/978-1-4614-6825-7"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"1164","DOI":"10.1137\/S009753979732428X","article-title":"Exploring unknown environments","volume":"29","author":"Albers","year":"2000","journal-title":"SIAM J. Comput."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1007\/s00453-001-0067-x","article-title":"Exploring unknown environments with obstacles","volume":"32","author":"Albers","year":"2002","journal-title":"Algorithmica"},{"key":"ref_12","unstructured":"Deng, X., Kameda, T., and Papadimitriou, C. (1991, January 1\u20134). How to learn an unknown environment. Proceedings of the 32nd Annual Symposium of Foundations of Computer Science, San Juan, Puerto Rico."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"577","DOI":"10.1137\/S0097539799348670","article-title":"The polygon exploration problem","volume":"31","author":"Hoffmann","year":"2001","journal-title":"SIAM J. Comput."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"376","DOI":"10.1109\/TRO.2004.839232","article-title":"Coordinated multi-robot exploration","volume":"21","author":"Burgard","year":"2005","journal-title":"IEEE Trans. Robot."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1177\/02783640122067435","article-title":"A probabilistic on-line mapping algorithm for teams of mobile robots","volume":"20","author":"Thrun","year":"2001","journal-title":"Int. J. Robot. Res."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Yamauchi, B. (1998, January 9\u201313). Frontier-based exploration using multiple robots. Proceedings of the Second International Conference on Autonomous Agents, Minneapolis, MI, USA.","DOI":"10.1145\/280765.280773"},{"key":"ref_17","unstructured":"Kleinberg, J. (1994, January 23\u201325). On-line search in a simple polygon. Proceedings of the SODA, Arlington, VA, USA."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"633","DOI":"10.1016\/B978-044482537-7\/50016-4","article-title":"Geometric shortest paths and network optimization","volume":"334","author":"Mitchell","year":"2000","journal-title":"Handb. Comput. Geom."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C.H., and Yannakakis, M. (1989). Shortest paths without a map. ICALP, Springer.","DOI":"10.1007\/BFb0035787"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1007\/s10514-011-9241-4","article-title":"Search and pursuit-evasion in mobile robotics","volume":"31","author":"Chung","year":"2011","journal-title":"Auton. Robot."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1016\/j.tcs.2008.02.040","article-title":"An annotated bibliography on guaranteed graph searching","volume":"399","author":"Fomin","year":"2008","journal-title":"Theor. Comput. Sci."},{"key":"ref_22","unstructured":"Lidbetter, T. (2013). Hide-and-Seek and other Search Games. [Ph.D. Thesis, The London School of Ecoomics and Political Science (LSE)]."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Nahin, P. (2012). Chases and Escapes: The Mathematics of Pursuit and Evasion, Princeton University Press.","DOI":"10.1515\/9781400842063"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1287\/moor.1090.0382","article-title":"Earliest arrival flows with multiple sources","volume":"34","author":"Baumann","year":"2009","journal-title":"Math. Oper. Res."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Fekete, S., Gray, C., and Kr\u00f6ller, A. (2010). Evacuation of rectilinear polygons. Combinatorial Optimization and Applications, Springer.","DOI":"10.1007\/978-3-642-17458-2_3"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Czyzowicz, J., Georgiou, K., Kranakis, E., Narayanan, L., Opatrny, J., and Vogtenhuber, B. (2015, January 20\u201322). Evacuating Robots from a Disc Using Face to Face Communication. Proceedings of the CIAC 2015, Paris, France.","DOI":"10.1007\/978-3-319-18173-8_10"},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Brandt, S., Laufenberg, F., Lv, Y., Stolz, D., and Wattenhofer, R. (2017, January 24\u201326). Collaboration without Communication: Evacuating Two Robots from a Disk. Proceedings of the Algorithms and Complexity\u201410th International Conference, CIAC, Athens, Greece.","DOI":"10.1007\/978-3-319-57586-5_10"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1007\/978-3-030-24922-9_14","article-title":"Evacuating two robots from a disk: A second cut","volume":"Volume 11639","author":"Flammini","year":"2019","journal-title":"International Colloquium on Structural Information and Communication Complexity"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1016\/j.tcs.2016.11.019","article-title":"Evacuating two robots from multiple unknown exits in a circle","volume":"709","author":"Czyzowicz","year":"2018","journal-title":"Theor. Comput. Sci."},{"key":"ref_30","unstructured":"Bellavista, P., and Garg, V.K. (2018, January 4\u20137). Evacuating Two Robots from Two Unknown Exits on the Perimeter of a Disk with Wireless Communication. Proceedings of the 19th International Conference on Distributed Computing and Networking, ICDCN 2018, Varanasi, India."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"101624","DOI":"10.1016\/j.comgeo.2020.101624","article-title":"Evacuating equilateral triangles and squares in the face-to-face model","volume":"89","author":"Chuangpishit","year":"2020","journal-title":"Comput. Geom."},{"key":"ref_32","unstructured":"Czyzowicz, J., Kranakis, E., Krizanc, D., Narayanan, L., Opatrny, J., and Shende, S. (July, January 29). Wireless Autonomous Robot Evacuation from Equilateral Triangles and Squares. Proceedings of the Ad-hoc, Mobile, and Wireless Networks, ADHOC-NOW, Athens, Greece."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1016\/j.tcs.2018.10.032","article-title":"Wireless evacuation on m rays with k searchers","volume":"811","author":"Brandt","year":"2020","journal-title":"Theor. Comput. Sci."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1016\/j.dam.2019.01.039","article-title":"The expanding search ratio of a graph","volume":"260","author":"Angelopoulos","year":"2019","journal-title":"Discret. Appl. Math."},{"key":"ref_35","first-page":"228","article-title":"Distributed Evacuation in Graphs with Multiple Exits","volume":"Volume 9988","author":"Suomela","year":"2016","journal-title":"Structural Information and Communication Complexity, Proceedings of the 23rd International Colloquium, SIROCCO 2016, Helsinki, Finland, 19\u201321 July 2016"},{"key":"ref_36","doi-asserted-by":"crossref","unstructured":"Chrobak, M., Gasieniec, L.T.G., and Martin, R. (2015). Group Search on the Line. SOFSEM 2015, Springer.","DOI":"10.1007\/978-3-662-46078-8_14"},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Georgiou, K., and Lucier, J. (2020, January 7\u201311). Weighted Group Search on a Line. Proceedings of the 16th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS, Pisa, Italy.","DOI":"10.1007\/978-3-030-62401-9_9"},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"234","DOI":"10.1006\/inco.1993.1054","article-title":"Searching in the plane","volume":"106","author":"Culberson","year":"1993","journal-title":"Inf. Comput."},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Czyzowicz, J., Georgiou, K., Godon, M., Kranakis, E., Krizanc, D., Rytter, W., and W\u0142odarczyk, M. (2017). Evacuation from a disc in the presence of a faulty robot. International Colloquium on Structural Information and Communication Complexity, Springer.","DOI":"10.1007\/978-3-319-72050-0_10"},{"key":"ref_40","first-page":"192","article-title":"Optimal Cycle Search Despite the Presence of Faulty Robots","volume":"Volume 11931","author":"Dressler","year":"2019","journal-title":"Algorithms for Sensor Systems, Proceedings of the 15th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2019, Munich, Germany, 12\u201313 September 2019"},{"key":"ref_41","first-page":"177","article-title":"Chauffeuring a Crashed Robot from a Disk","volume":"Volume 11931","author":"Dressler","year":"2019","journal-title":"Algorithms for Sensor Systems, Proceedings of the 15th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2019, Munich, Germany, 12\u201313 September 2019"},{"key":"ref_42","doi-asserted-by":"crossref","unstructured":"Bonato, A., Georgiou, K., MacRury, C., and Pralat, P. (2020, January 25\u201329). Probabilistically Faulty Searching on a Half-Line. Proceedings of the 14th Latin American Theoretical Informatics Sumposium, University of Sao Paulo, Sao Paulo, Brazil.","DOI":"10.1007\/978-3-030-61792-9_14"},{"key":"ref_43","first-page":"559","article-title":"Searching with Advice: Robot Fence-Jumping","volume":"25","author":"Georgiou","year":"2017","journal-title":"J. Inf. Process."},{"key":"ref_44","doi-asserted-by":"crossref","unstructured":"Czyzowicz, J., Georgiou, K., Killick, R., Kranakis, E., Krizanc, D., Narayanan, L., Opatrny, J., and Shende, S. (2020). Priority Evacuation from a Disk: The case of n \u2265 4. Theor. Comput. Sci., accepted.","DOI":"10.1016\/j.tcs.2020.09.023"},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"595","DOI":"10.1016\/j.tcs.2019.09.026","article-title":"Priority evacuation from a disk: The case of n = 1, 2, 3","volume":"806","author":"Czyzowicz","year":"2020","journal-title":"Theor. Comput. Sci."},{"key":"ref_46","unstructured":"Georgiou, K., Karakostas, G., and Kranakis, E. (2016). Search-and-Fetch with One Robot on a Disk\u2014(Track: Wireless and Geometry). Algorithms for Sensor Systems, Proceedings of the 12th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2016, Aarhus, Denmark, 25\u201326 August 2016, Springer. Revised Selected Papers."},{"key":"ref_47","unstructured":"Georgiou, K., Karakostas, G., and Kranakis, E. (2019). Search-and-Fetch with 2 Robots on a Disk: Wireless and Face-to-Face Communication Models. Discret. Math. Theor. Comput. Sci., 21."},{"key":"ref_48","first-page":"137:1","article-title":"Energy Consumption of Group Search on a Line","volume":"Volume 132","author":"Baier","year":"2019","journal-title":"Leibniz International Proceedings in Informatics (LIPIcs), Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), Patras, Greece, 8\u201312 July 2019"},{"key":"ref_49","first-page":"185","article-title":"Time-Energy Tradeoffs for Evacuation by Two Robots in the Wireless Model","volume":"Volume 11639","author":"Flammini","year":"2019","journal-title":"Structural Information and Communication Complexity, Proceedings of the 26th International Colloquium, SIROCCO 2019, L\u2019Aquila, Italy, 1\u20134 July 2019"},{"key":"ref_50","doi-asserted-by":"crossref","unstructured":"Lamprou, I., Martin, R., and Schewe, S. (2016, January 27\u201329). Fast two-robot disk evacuation with wireless communication. Proceedings of the DISC, Paris, France.","DOI":"10.1007\/978-3-662-53426-7_1"},{"key":"ref_51","first-page":"430","article-title":"Linear Search with Terrain-Dependent Speeds","volume":"Volume 10236","author":"Fotakis","year":"2017","journal-title":"Algorithms and Complexity, Proceedings of the 10th International Conference, CIAC 2017, Athens, Greece, 24\u201326 May 2017"},{"key":"ref_52","doi-asserted-by":"crossref","unstructured":"Flocchini, P., Prencipe, G., and Santoro, N. (2019). Group Search and Evacuation. Distributed Computing by Mobile Entities; Current Research in Moving and Computing, Springer. Chapter 14.","DOI":"10.1007\/978-3-030-11072-7"},{"key":"ref_53","unstructured":"L\u00f3pez-Ortiz, A., and Sweet, G. (2001, January 13\u201315). Parallel searching on a lattice. Proceedings of the CCCG."},{"key":"ref_54","first-page":"471","article-title":"Solving the ANTS Problem with Asynchronous Finite State Machines","volume":"Volume 8573","author":"Esparza","year":"2014","journal-title":"Automata, Languages, and Programming, Proceedings of the 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, 8\u201311 July 2014"},{"key":"ref_55","unstructured":"Halld\u00c33rsson, M.M., and Dolev, S. (2014). Trade-offs Between Selection Complexity and Performance when Searching the Plane Without Communication. ACM Symposium on Principles of Distributed Computing, Proceedings of the PODC \u201914, Paris, France, 15\u201318 July 2014, ACM."},{"key":"ref_56","first-page":"26:1","article-title":"Lower Bounds for Shoreline Searching With 2 or More Robots","volume":"Volume 153","author":"Felber","year":"2019","journal-title":"Proceedings of the 23rd International Conference on Principles of Distributed Systems (OPODIS\u201919)"},{"key":"ref_57","doi-asserted-by":"crossref","unstructured":"Dobrev, S., Kralovic, R., and Pardubska, D. (2020). Improved Lower Bounds for Shoreline Search. Structural Information and Communication Complexity, Proceedings of the 27th International Colloquium, SIROCCO 2020, Paderborn, Germany, 29 June\u20131 July 2020, Springer. Lecture Notes in Computer Science.","DOI":"10.1007\/978-3-030-54921-3_5"},{"key":"ref_58","first-page":"1","article-title":"Nonlinear multiobjective optimization","volume":"Volume 12","author":"Miettinen","year":"1998","journal-title":"International Series in Operations Research and Management Science"}],"container-title":["Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2078-2489\/11\/11\/506\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T10:30:29Z","timestamp":1760178629000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2078-2489\/11\/11\/506"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,10,29]]},"references-count":58,"journal-issue":{"issue":"11","published-online":{"date-parts":[[2020,11]]}},"alternative-id":["info11110506"],"URL":"https:\/\/doi.org\/10.3390\/info11110506","relation":{"has-preprint":[{"id-type":"doi","id":"10.32920\/24231046","asserted-by":"object"},{"id-type":"doi","id":"10.32920\/24231046.v1","asserted-by":"object"}]},"ISSN":["2078-2489"],"issn-type":[{"value":"2078-2489","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,10,29]]}}}