Hide-and-Seek Games on a Network, Using Combinatorial Search Paths

• 成果类型: Article
• 署名作者: Alpern, Steve
• 署名单位: University of Warwick
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2017.1594
• 发表日期: 2017
• 页码: 1207-1214
• 关键词: rendezvous search; immobile hider; line

摘要

This paper introduces a new search paradigm to hide-and-seek games on networks. The Hider locates at any point on any arc. The Searcher adopts a combinatorial path when searching the network: a sequence of arcs, each adjacent to the last, and traced out at unit speed. In previous literature the Searcher was allowed simple motion, any unit speed path, including ones that turn around inside an arc. The new approach more closely models real problems such as search for improvised explosive devices using vehicles that can only turn around at particular locations on a road. The search game is zero sum, with the time taken to find the Hider as the payoff.& para;& para;Using a lemma giving an upper bound for the expected search time on a semi Eulerian network, we solve the search game on a network Q(3) consisting of two nodes connected by three arcs of arbitrary lengths. When two Q(3) networks with unit length arcs are linked by two small central arcs incident at the start node, one of these arcs must be traversed at least three times in an optimal search. This property holds for both combinatorial paths and simple motion paths, and the latter makes it a counterexample to a conjecture of Gal, which said that two traversals were always sufficient.