In this paper, we study the problem of exploring an unknown grid graph by multiple searchers. All searchers start from a single vertex, and each vertex in the graph must be visited by at least one searcher. The objective is to minimize the time required until every vertex has been visited and all searchers have returned to the starting vertex. We assume that the searchers can communicate with each other by reading and writing information at any vertex they visit. In prior work, Ortolf and Schindelhauer proposed an online exploration algorithm for an \(n \times n\) grid graph with disjoint rectangular obstacles. They showed that its competitive ratio is \(\mathcal {O}(\log ^{2} n)\) . We propose an online algorithm for arbitrary grid graphs that achieves a competitive ratio of \(\varTheta (k / \log k + \min (c, k))\) , where \(k\) is the number of searchers and \(c\) is the number of hole corners in the grid graph. Our result improves on that of Ortolf and Schindelhauer when \(c\) and \(k\) are relatively small compared to the graph size. In particular, when \(c\) is a constant, our algorithm achieves a constant competitive ratio that is independent of the graph size.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Online Exploration of Grid Graphs with Multiple Searchers

  • Yuya Higashikawa,
  • Shuichi Miyazaki,
  • Daiki Okayama

摘要

In this paper, we study the problem of exploring an unknown grid graph by multiple searchers. All searchers start from a single vertex, and each vertex in the graph must be visited by at least one searcher. The objective is to minimize the time required until every vertex has been visited and all searchers have returned to the starting vertex. We assume that the searchers can communicate with each other by reading and writing information at any vertex they visit. In prior work, Ortolf and Schindelhauer proposed an online exploration algorithm for an \(n \times n\) grid graph with disjoint rectangular obstacles. They showed that its competitive ratio is \(\mathcal {O}(\log ^{2} n)\) . We propose an online algorithm for arbitrary grid graphs that achieves a competitive ratio of \(\varTheta (k / \log k + \min (c, k))\) , where \(k\) is the number of searchers and \(c\) is the number of hole corners in the grid graph. Our result improves on that of Ortolf and Schindelhauer when \(c\) and \(k\) are relatively small compared to the graph size. In particular, when \(c\) is a constant, our algorithm achieves a constant competitive ratio that is independent of the graph size.