Skip to Main Content
Frequently Asked Questions
Submit an ETD
Global Search Box
Need Help?
Keyword Search
Participating Institutions
Advanced Search
School Logo
Files
File List
osu1092770142.pdf (1.17 MB)
ETD Abstract Container
Abstract Header
In pursuit of a hidden evader
Author Info
Bohn, Christopher A.
Permalink:
http://rave.ohiolink.edu/etdc/view?acc_num=osu1092770142
Abstract Details
Year and Degree
2004, Doctor of Philosophy, Ohio State University, Computer and Information Science.
Abstract
We define a game of pursuers seeking evaders on a grid, originally motivated by, but not limited to, the problem of unmanned aerial vehicles searching for moving targets. The pursuers have a speed advantage over the evaders but are incapable of determining an evader’s location unless a pursuer occupies the same location as that evader. The evaders, on the other hand, operate with unlimited luck and cunning: if it is possible for them to avoid the pursuers, they will. By treating the players as nondeterministic finite automata, we can model the game and use it as the input for a model checker. While model checkers normally are used to verify program correctness, we use the model checker to generate a pursuer-winning search strategy. We demonstrate this technique for the full model and then develop heuristics to reduce the model so we can address larger problem sizes. We further prove an upper bound on the minimum pursuer-winning speed; moreover, we show the bound is tight for a particular class of search strategies.
Committee
Paolo Sivilotti (Advisor)
Pages
211 p.
Subject Headings
Computer Science
Keywords
Model checking
;
Unmanned aerial vehicle
;
Pursuer-evader game
Recommended Citations
Refworks
EndNote
RIS
Mendeley
Citations
Bohn, C. A. (2004).
In pursuit of a hidden evader
[Doctoral dissertation, Ohio State University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=osu1092770142
APA Style (7th edition)
Bohn, Christopher.
In pursuit of a hidden evader.
2004. Ohio State University, Doctoral dissertation.
OhioLINK Electronic Theses and Dissertations Center
, http://rave.ohiolink.edu/etdc/view?acc_num=osu1092770142.
MLA Style (8th edition)
Bohn, Christopher. "In pursuit of a hidden evader." Doctoral dissertation, Ohio State University, 2004. http://rave.ohiolink.edu/etdc/view?acc_num=osu1092770142
Chicago Manual of Style (17th edition)
Abstract Footer
Document number:
osu1092770142
Download Count:
807
Copyright Info
© 2004, all rights reserved.
This open access ETD is published by The Ohio State University and OhioLINK.