Search game

Last updated

A search game is a two-person zero-sum game which takes place in a set called the search space. The searcher can choose any continuous trajectory subject to a maximal velocity constraint. It is always assumed that neither the searcher nor the hider has any knowledge about the movement of the other player until their distance apart is less than or equal to the discovery radius and at this very moment capture occurs. The game is zero sum with the payoff being the time spent in searching. As mathematical models, search games can be applied to areas such as hide-and-seek games that children play or representations of some tactical military situations. The area of search games was introduced in the last chapter of Rufus Isaacs' classic book "Differential Games" [1] and has been developed further by Shmuel Gal [2] [3] and Steve Alpern. [3] The princess and monster game deals with a moving target.

Contents

Strategy

A natural strategy to search for a stationary target in a graph (in which arcs have lengths) is to find a minimal closed curve L that covers all the arcs of the graph. (L is called a Chinese postman tour). Then, traverse L with probability 1/2 for each direction. This strategy seems to work well if the graph is Eulerian. In general, this random Chinese postman tour is indeed an optimal search strategy if and only if the graph consists of a set of Eulerian graphs connected in a tree-like structure. [4] A misleadingly simple example of a graph not in this family consists of two nodes connected by three arcs. The random Chinese postman tour (equivalent to traversing the three arcs in a random order) is not optimal, and the optimal way to search these three arcs is complicated. [2]

Unbounded domains

In general, the reasonable framework for searching an unbounded domain, as in the case of an online algorithm, is to use a normalized cost function (called the competitive ratio in Computer Science literature). The minimax trajectory for problems of these types is always a geometric sequence (or exponential function for continuous problems). This result yields an easy method to find the minimax trajectory by minimizing over a single parameter (the generator of this sequence) instead of searching over the whole trajectory space. This tool has been used for the linear search problem, i.e., finding a target on the infinite line, which has attracted much attention over several decades and has been analyzed as a search game. [5] It has also been used to find a minimax trajectory for searching a set of concurrent rays. Optimal searching in the plane is performed by using exponential spirals. [2] [3] [6] Searching a set of concurrent rays was later re-discovered in Computer Science literature as the 'cow-path problem'. [7]

Related Research Articles

<span class="mw-page-title-main">Search algorithm</span> Any algorithm which solves the search problem

In computer science, a search algorithm is an algorithm designed to solve a search problem. Search algorithms work to retrieve information stored within particular data structure, or calculated in the search space of a problem domain, with either discrete or continuous values.

A* is a graph traversal and pathfinding algorithm that is used in many fields of computer science due to its completeness, optimality, and optimal efficiency. Given a weighted graph, a source node and a goal node, the algorithm finds the shortest path from source to goal.

Alpha–beta pruning is a search algorithm that seeks to decrease the number of nodes that are evaluated by the minimax algorithm in its search tree. It is an adversarial search algorithm used commonly for machine playing of two-player combinatorial games. It stops evaluating a move when at least one possibility has been found that proves the move to be worse than a previously examined move. Such moves need not be evaluated further. When applied to a standard minimax tree, it returns the same move as minimax would, but prunes away branches that cannot possibly influence the final decision.

<span class="mw-page-title-main">Chinese postman problem</span> Finding shortest walks through all graph edges

In graph theory and combinatorial optimization, Guan's route problem, the Chinese postman problem, postman tour or route inspection problem is to find a shortest closed path or circuit that visits every edge of an (connected) undirected graph at least once. When the graph has an Eulerian circuit, that circuit is an optimal solution. Otherwise, the optimization problem is to find the smallest number of graph edges to duplicate so that the resulting multigraph does have an Eulerian circuit. It can be solved in polynomial time, unlike the Travelling Salesman Problem which is NP-hard. It is different from the Travelling Salesman Problem in that the travelling salesman cannot repeat visited nodes and does not have to visit every edge.

In computer science and artificial intelligence, combinatorial search studies search algorithms for solving instances of problems that are believed to be hard in general, by efficiently exploring the usually large solution space of these instances. Combinatorial search algorithms achieve this efficiency by reducing the effective size of the search space or employing heuristics. Some algorithms are guaranteed to find the optimal solution, while others may only return the best solution found in the part of the state space that was explored.

The rendezvous dilemma is a logical dilemma, typically formulated in this way:

In computer science, local search is a heuristic method for solving computationally hard optimization problems. Local search can be used on problems that can be formulated as finding a solution that maximizes a criterion among a number of candidate solutions. Local search algorithms move from solution to solution in the space of candidate solutions by applying local changes, until a solution deemed optimal is found or a time bound is elapsed.

<span class="mw-page-title-main">Eulerian path</span> Trail in a graph that visits each edge once

In graph theory, an Eulerian trail is a trail in a finite graph that visits every edge exactly once. Similarly, an Eulerian circuit or Eulerian cycle is an Eulerian trail that starts and ends on the same vertex. They were first discussed by Leonhard Euler while solving the famous Seven Bridges of Königsberg problem in 1736. The problem can be stated mathematically like this:

<span class="mw-page-title-main">Feedback arc set</span> Edges that hit all cycles in a graph

In graph theory and graph algorithms, a feedback arc set or feedback edge set in a directed graph is a subset of the edges of the graph that contains at least one edge out of every cycle in the graph. Removing these edges from the graph breaks all of the cycles, producing an acyclic subgraph of the given graph, often called a directed acyclic graph. A feedback arc set with the fewest possible edges is a minimum feedback arc set and its removal leaves a maximum acyclic subgraph; weighted versions of these optimization problems are also used. If a feedback arc set is minimal, meaning that removing any edge from it produces a subset that is not a feedback arc set, then it has an additional property: reversing all of its edges, rather than removing them, produces a directed acyclic graph.

Pursuit–evasion is a family of problems in mathematics and computer science in which one group attempts to track down members of another group in an environment. Early work on problems of this type modeled the environment geometrically. In 1976, Torrence Parsons introduced a formulation whereby movement is constrained by a graph. The geometric formulation is sometimes called continuous pursuit–evasion, and the graph formulation discrete pursuit–evasion. Current research is typically limited to one of these two formulations.

In computational complexity theory, Yao's principle relates the performance of randomized algorithms to deterministic (non-random) algorithms. It states that, for certain classes of algorithms, and certain measures of the performance of the algorithms, the following two quantities are equal:

God's algorithm is a notion originating in discussions of ways to solve the Rubik's Cube puzzle, but which can also be applied to other combinatorial puzzles and mathematical games. It refers to any algorithm which produces a solution having the fewest possible moves. The allusion to the deity is based on the notion that an omniscient being would know an optimal step from any given configuration.

A princess and monster game is a pursuit–evasion game played by two players in a region.

Arc routing problems (ARP) are a category of general routing problems (GRP), which also includes node routing problems (NRP). The objective in ARPs and NRPs is to traverse the edges and nodes of a graph, respectively. The objective of arc routing problems involves minimizing the total distance and time, which often involves minimizing deadheading time, the time it takes to reach a destination. Arc routing problems can be applied to garbage collection, school bus route planning, package and newspaper delivery, deicing and snow removal with winter service vehicles that sprinkle salt on the road, mail delivery, network maintenance, street sweeping, police and security guard patrolling, and snow ploughing. Arc routings problems are NP hard, as opposed to route inspection problems that can be solved in polynomial-time.

In computational complexity theory, the linear search problem is an optimal search problem introduced by Richard E. Bellman and independently considered by Anatole Beck.

<span class="mw-page-title-main">Shmuel Gal</span> Israeli mathematician and professor of statistics

Shmuel Gal is a mathematician and professor of statistics at the University of Haifa in Israel.

The mixed Chinese postman problem (MCPP or MCP) is the search for the shortest traversal of a graph with a set of vertices V, a set of undirected edges E with positive rational weights, and a set of directed arcs A with positive rational weights that covers each edge or arc at least once at minimal cost. The problem has been proven to be NP-complete by Papadimitriou. The mixed Chinese postman problem often arises in arc routing problems such as snow ploughing, where some streets are too narrow to traverse in both directions while other streets are bidirectional and can be plowed in both directions. It is easy to check if a mixed graph has a postman tour of any size by verifying if the graph is strongly connected. The problem is NP hard if we restrict the postman tour to traverse each arc exactly once or if we restrict it to traverse each edge exactly once, as proved by Zaragoza Martinez.

References

  1. ↑ Rufus Isaacs, Differential Games, John Wiley and Sons, (1965),
  2. 1 2 3 S. Gal, Search Games, Academic Press, New York (1980)
  3. 1 2 3 S. Alpern and S. Gal, The Theory of Search Games and Rendezvous , Springer (2003).
  4. ↑ Gal, Shmuel (2001). "On the optimality of a simple strategy for searching graphs". International Journal of Game Theory. 29 (4): 533–542. doi: 10.1007/s001820000056 .
  5. ↑ Beck, Anatole; Newman, D.J. (1970). "Yet More on the linear search problem". Israel Journal of Mathematics . 8 (4): 419–429. doi: 10.1007/BF02798690 .
  6. ↑ M. Chrobak, A princess swimming in the fog looking for a monster cow, ACM Sigact news, 35(2), 74–78 (2004).
  7. ↑ MY Kao, JH Reif and SR Tate, Searching in an unknown environment: an optimal randomized algorithm for the cow-path problem, SODA 1993.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.