Article ID: | iaor201112787 |
Volume: | 58 |
Issue: | 8 |
Start Page Number: | 804 |
End Page Number: | 820 |
Publication Date: | Dec 2011 |
Journal: | Naval Research Logistics (NRL) |
Authors: | Polak Elijah, Royset Johannes O, Chung Hoam, Sastry Shankar |
Keywords: | programming: critical path, combinatorial optimization, control, programming: nonlinear |
Given a number of patrollers that are required to detect an intruder in a channel, the channel patrol problem consists of determining the periodic trajectories that the patrollers must trace out so as to maximized the probability of detection of the intruder. We formulate this problem as an optimal control problem. We assume that the patrollers' sensors are imperfect and that their motions are subject to turn-rate constraints, and that the intruder travels straight down a channel with constant speed. Using discretization of time and space, we approximate the optimal control problem with a large-scale nonlinear programming problem which we solve to obtain an approximately stationary solution and a corresponding optimized trajectory for each patroller. In numerical tests for one, two, and three underwater patrollers, an underwater intruder, different trajectory constraints, several intruder speeds and other specific parameter choices, we obtain new insight–not easily obtained using simply geometric calculations–into efficient patrol trajectory design under certain conditions for multiple patrollers in a narrow channel where interaction between the patrollers is unavoidable due to their limited turn rate.