An Iterative Linear Programming Approach to Solving Large Cumulative Search-Evasion Games

Abstract

Cumulative search-evasion games (CSEGs) involve two players, a searcher and an evader, who move among some finite set of cells. Neither player is aware of the other player's position during any stage of the game. When the payoff for the game is assumed to be the number of times the searcher and evader occupy the same cell, Eagle and Washburn proposed two solution techniques: one by fictitious play and the other by solving equivalent linear programming formulations. However, both have proved to be time consuming even for moderately sized problems. This thesis considers two alternate linear programming formulations for CSEGs. Since both contain a large number of variables and constraints, the linear programming problems are initially solved with many of the constraints removed. If the solution to this relaxed problem is not a feasible optimal solution, additional constraints are added and the problem is solved again. This process continues until a feasible optimal solution is found. The results from a numerical experimentation with various solution techniques are also presented.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Mar 01, 1990
Accession Number
ADA227256

Entities

People

  • Brian P. Bothwell

Organizations

  • Naval Postgraduate School

Tags

Communities of Interest

  • Human Systems

DTIC Thesaurus Topics

  • Algorithms
  • Computations
  • Computer Programming
  • Detection
  • Equations
  • Game Theory
  • Linear Programming
  • Mainframe Computers
  • Markov Processes
  • Moving Targets
  • New York
  • Operations Research
  • Probability
  • Probability Distributions
  • Search Theory
  • Two Dimensional
  • United States

Readers

  • Computational Modeling and Simulation
  • Finite Element Method (FEM) for solving Partial Differential Equations (PDEs)
  • Game Theory.