Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Tìm Kiếm Trực Tuyến Trong Môi Trường Hai Chiều
Tóm tắt
Chúng tôi xem xét bài toán truy đuổi - tránh né trực tuyến sau đây. Một nhóm các tác nhân di động được gọi là người tìm kiếm bắt đầu từ một nút tùy ý trong một mạng lưới không xác định. Mục tiêu của họ là thực hiện một chiến lược tìm kiếm đảm bảo việc bắt giữ một kẻ xâm nhập nhanh chóng và vô hình bất kể di chuyển của nó, bằng cách sử dụng càng ít người tìm kiếm càng tốt. Chúng tôi yêu cầu rằng chiến lược này phải liên kết và đơn điệu, tức là, tại mỗi điểm thực hiện, phần của đồ thị được đảm bảo là miễn nhiễm với kẻ chạy trốn phải liên kết và mỗi khi một nút có được thuộc tính mà nó không thể bị chiếm bởi kẻ chạy trốn, chiến lược phải hoạt động theo cách giữ thuộc tính này cho đến cuối. Như một cách để mô hình hóa các hình dạng hai chiều, chúng tôi giới hạn sự chú ý của mình vào các mạng lưới được nhúng vào lưới một phần: các nút được đặt trên mặt phẳng tại các tọa độ nguyên và chỉ các nút cách nhau một đơn vị có thể là kề nhau. Các tác nhân không có bất kỳ kiến thức nào về đồ thị trước đó, nhưng họ nhận ra hướng của cạnh góc (lên, xuống, trái hoặc phải). Chúng tôi đưa ra một thuật toán trực tuyến cho những người tìm kiếm cho phép họ tính toán một chiến lược liên kết và đơn điệu đảm bảo tìm kiếm bất kỳ lưới một phần không xác định với việc sử dụng $O(\sqrt {n})$ người tìm kiếm, trong đó n là số nút trong lưới. Về mặt giới hạn dưới, có tồn tại các lưới một phần yêu cầu ${\varOmega }(\sqrt {n})$ người tìm kiếm. Hơn nữa, chúng tôi chứng minh rằng đối với mỗi thuật toán tìm kiếm trực tuyến, có một lưới một phần buộc thuật toán phải sử dụng ${\varOmega }(\sqrt {n})$ người tìm kiếm nhưng $O(\log n)$ người tìm kiếm là đủ trong kịch bản ngoại tuyến. Điều này đưa ra một giới hạn dưới về ${\varOmega }(\sqrt {n}/\log n)$ về tỷ lệ cạnh tranh có thể đạt được của bất kỳ thuật toán trực tuyến nào.
Từ khóa
#truy đuổi #tránh né #thuật toán trực tuyến #mạng lưới #tìm kiếm #lưới hai chiềuTài liệu tham khảo
Altshuler, Y., Yanovski, V., Wagner, I.A., Bruckstein, A.M.: Multi-agent cooperative cleaning of expanding domains. I. J. Robot. Res. 30(8), 1037–1071 (2011)
Barrière, L., Flocchini, P., Fomin, F.V., Fraigniaud, P., Nisse, N., Santoro, N., Thilikos, D.M.: Connected graph searching. Inf. Comput. 219, 1–16 (2012)
Best, M.J., Gupta, A., Thilikos, D.M., Zoros, D.: Contraction obstructions for connected graph searching. Discrete Applied Mathematics. https://doi.org/10.1016/j.dam.2015.07.036 (2015)
Bhadauria, D., Klein, K., Isler, V., Suri, S.: Capturing an evader in polygonal environments with obstacles The full visibility case. I. J. Robot. Res. 31 (10), 1176–1189 (2012)
Blin, L., Burman, J., Nisse, N.: Perpetual graph searching. Technical report INRIA 〈hal-00675233〉(2012)
Blin, L., Fraigniaud, P., Nisse, N., Vial, S.: Distributed chasing of network intruders. Theor Comput. Sci. 399(1-2), 12–37 (2008)
Borowiecki, P., Dereniowski, D., Kuszner, L.: Distributed graph searching with a sense of direction. Distrib. Comput. 28(3), 155–170 (2015)
Cai, J., Flocchini, P., Santoro, N.: Decontaminating a network from a black virus. IJNC 4(1), 151–173 (2014)
Chrobak, M., Kenyon-Mathieu, C.: Sigact news online algorithms column 10: competitiveness via doubling. ACM SIGACT News 37(4), 115–126 (2006)
Chung, T.H., Hollinger, G.A., Isler, V.: Search and pursuit-evasion in mobile robotics - A survey. Auton. Robot. 31(4), 299–316 (2011)
Daadaa, Y.: Network Decontamination with Temporal immunity, Master Thesis. Master Thesis. University of Ottawa, Ottawa (2012)
Daadaa, Y., Flocchini, P., Zaguia, N.: Network decontamination with temporal immunity by cellular automata. In: ACRI’10: Proceedings of the 9th International Conference on Cellular Automata for Research and Industry, Ascoli Piceno, pp. 287–299 (2010)
D’Angelo, G., Navarra, A., Nisse, N.: Gathering and exclusive searching on rings under minimal assumptions. In: ICDCN ’14: Proc. of the 15th International Conference on Distributed Computing and Networking, Coimbatore, pp. 149–164 (2014)
Dereniowski, D.: Connected searching of weighted trees. Theor. Comp. Sci. 412, 5700–5713 (2011)
Dereniowski, D.: Approximate search strategies for weighted trees. Theor. Comput. Sci. 463, 96–113 (2012)
Dereniowski, D.: From pathwidth to connected pathwidth. SIAM J. Discret. Math. 26(4), 1709–1732 (2012)
Durham, J.W., Franchi, A., Bullo, F.: Distributed pursuit-evasion without mapping or global localization via local frontiers. Auton. Robot. 32(1), 81–95 (2012)
Ellis, J., Warren, R.: Lower bounds on the pathwidth of some grid-like graphs. Discret. Appl. Math. 156(5), 545–555 (2008)
Flocchini, P., Huang, M.J., Luccio, F.L.: Decontaminating chordal rings and tori using mobile agents. Int. J. Found. Comput. Sci. 18(3), 547–563 (2007)
Flocchini, P., Huang, M.J., Luccio, F.L.: Decontamination of hypercubes by mobile agents. Networks 52(3), 167–178 (2008)
Flocchini, P., Luccio, F., Pagli, L., Santoro, N.: Optimal network decontamination with threshold immunity. In: CIAC’13: Proc. of the 8th International Conference on Algorithms and Complexity, Barcelona, pp. 234–245 (2013)
Flocchini, P., Luccio, F., Pagli, L., Santoro, N.: Network decontamination under m-immunity. Discret. Appl. Math. 201, 114–129 (2016)
Flocchini, P., Mans, B., Santoro, N.: Tree decontamination with temporary immunity. In: Algorithms and Computation, 19th International Symposium, ISAAC, 2008, Gold Coast, Australia, pp. 330–341. Proceedings (2008)
Fomin, F.V., Thilikos, D.M.: An annotated bibliography on guaranteed graph searching. Theor. Comput. Sci. 399(3), 236–245 (2008)
Fraigniaud, P., Ilcinkas, D., Pelc, A.: Oracle size: a new measure of difficulty for communication tasks. In: PODC’06: Proc. of the Twenty-Fifth Annual ACM Symposium on Principles of Distributed Computing, pp. 179–187 (2006)
Gonċalves, V. C. F., Lima, P.M.V., Maculan, N., Franċa, F.M.G.: A distributed dynamics for webgraph decontamination. In: ISoLA ’10 Proceedings of the 4th International Symposium on Leveraging Applications of Formal Methods, Verification and Validation, Heraklion, Crete, pp. 462–472 (2010)
Hollinger, G.A., Singh, S., Djugash, J., Kehagias, A.: Efficient multi-robot search for a moving target. I. J. Robot. Res. 28(2), 201–219 (2009)
Ilcinkas, D., Nisse, N., Soguet, D.: The cost of monotonicity in distributed graph searching. Distrib. Comput. 22(2), 117–127 (2009)
Karaivanov, B., Markov, M., Snoeyink, J., Vassilev, T.S.: Decontaminating planar regions by sweeping with barrier curves. In: CCCG ’14: Proceedings of the 26th Canadian Conference on Computational Geometry (2014)
Kolling, A., Carpin, S.: Multi-robot pursuit-evasion without maps. In: ICRA’10: Proceedings of IEEE International Conference on Robotics and Automation, pp. 3045–3051 (2010)
LaPaugh, A.S.: Recontamination does not help to search a graph. J. ACM 40 (2), 224–245 (1993)
Luccio, F., Pagli, L., Santoro, N.: Network decontamination in presence of local immunity. Int. J. Found Comput. Sci. 18(3), 457–474 (2007)
Markov, M., Haralampiev, V., Georgiev, G.: Lower bounds on the directed sweepwidth of planar shapes. Serdica J. Comput. 9(2), 151–166 (2015)
Megiddo, N., Hakimi, S.L., Garey, M.R., Johnson, D.S., Papadimitriou, C.H.: The complexity of searching a graph. J. ACM 35(1), 18–44 (1988)
Moraveji, R., Sarbazi-azad, H., Zomaya, A.Y.: Performance modeling of cartesian product networks. J. Parallel Distrib. Comput. 71(1), 105–113 (2011)
Nisse, N., Soguet, D.: Graph searching with advice. Theor. Comput. Sci. 410(14), 1307–1318 (2009)
Parsons, T.D.: Pursuit-evasion in a graph. In: Theory and Applications of Graphs, Lecture Notes in Mathematics, vol. 642, pp. 426–441. Springer (1978)
Petrov, N.N.: A problem of pursuit in the absence of information on the pursued. Differ. Uravneniya 18, 1345–1352 (1982)
Raboin, E., Kuter, U., Nau, D.S.: Generating strategies for multi-agent pursuit-evasion games in partially observable euclidean space. In: AAMAS ’12 Proceedings of the International Conference on Autonomous Agents and Multiagent Systems, Valencia, Spain, pp. 1201–1202 (2012)
Robin, C., Lacroix, S.: Multi-robot target detection and tracking: taxonomy and survey. Auton. Robot. 40(4), 729–760 (2016)
Rodríguez, S., Denny, J., Burgos, J., Mahadevan, A., Manavi, K., Murray, L., Kodochygov, A., Zourntos, T., Amato, N.M.: Toward realistic pursuit-evasion using a roadmap-based approach. In: ICRA ’11: Proceedings of the IEEE international conference on robotics and automation, Shanghai, China, pp. 1738–1745 (2011)
Sachs, S., LaValle, S.M., Rajko, S.: Visibility-based pursuit-evasion in an unknown planar environment. I. J Robot. Res. 23(1), 3–26 (2004)
Stiffler, N.M., O’Kane, J.M.: A complete algorithm for visibility-based pursuit-evasion with multiple pursuers. In: ICRA ’14: Proceedings of the IEEE International Conference on Robotics and Automation, Hong Kong, China, pp. 1660–1667 (2014)
Yang, B., Dyer, D., Alspach, B.: Sweeping graphs with large clique number. Discret. Math. 309(18), 5770–5780 (2009)