Optimal patrol to detect attacks at dispersed heterogeneous locations
dc.contributor.advisor | Lin, Kyle Y. | |
dc.contributor.author | McGrath, Richard G., Jr. | |
dc.date | December 2013 | |
dc.date.accessioned | 2016-05-03T16:03:33Z | |
dc.date.available | 2016-05-03T16:03:33Z | |
dc.date.issued | 2013-12 | |
dc.identifier.uri | https://hdl.handle.net/10945/48616 | |
dc.description.abstract | We study a patrol problem where several patrollers move between heterogeneous locations dispersed throughout an area of interest in order to detect enemy attacks. To formulate an e ective patrol policy, the patrollers must take into account travel time between locations, as well as location-speci c parameters, which include patroller inspection times, enemy attack times, and cost incurred due to an undetected attack. We consider both random and strategic attackers. A random attacker chooses a location to attack according to a probability distribution, while a strategic attacker plays a two-person zero-sum game with the patrollers. In some cases, we can compute the optimal solution using linear programming. This method, however, becomes computationally intractable as the problem size grows. Therefore, our research focuses on developing e cient heuristics, based on aggregate index values, ctitious play, and shortest paths. Numerical experiments demonstrate that our heuristics produce excellent results with computation time orders of magnitude less than what is required to compute the optimal solution. | en_US |
dc.description.uri | http://archive.org/details/optimalpatroltod1094548616 | |
dc.publisher | Monterey, California. Naval Postgraduate School | en_US |
dc.rights | This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States. | en_US |
dc.title | Optimal patrol to detect attacks at dispersed heterogeneous locations | en_US |
dc.type | Thesis | en_US |
dc.contributor.department | Operations Research | en_US |
dc.subject.author | Optimal patrol | en_US |
dc.subject.author | Multi-agent patrol | en_US |
dc.subject.author | Semi-Markov decision process | en_US |
dc.subject.author | Sequential decision making under uncertainty | en_US |
dc.description.service | Commander, United States Navy | en_US |
etd.thesisdegree.name | Doctor of Philosophy in Operations Research | en_US |
etd.thesisdegree.level | Doctoral | en_US |
etd.thesisdegree.discipline | Operations Research | en_US |
etd.thesisdegree.grantor | Naval Postgraduate School | en_US |
dc.description.distributionstatement | Approved for public release; distribution is unlimited. |
Files in this item
This item appears in the following Collection(s)
-
1. Thesis and Dissertation Collection, all items
Publicly releasable NPS Theses, Dissertations, MBA Professional Reports, Joint Applied Projects, Systems Engineering Project Reports and other NPS degree-earning written works.