New multi-objective evolutionary game theory algorithm for border security

The complexity of border security relays on the diversity and volume of illegal activity that must be controlled, and the variety of resources that can be deployed to secure the border. A key operational problem encountered by those charged with the task of border security is the scheduling and deployment of patrols. Patrolling can be defined as the act of walking or traveling around an area—network—, at regular intervals, in order to protect or supervise it. The problem of optimizing schedules for patrolling open areas is one that arises in many contexts, and has attracted significant attention from researchers. For example, many problems in defense and national security can naturally be framed as patrolling problems, including problems in Homeland Security. One of the primary components of the Department of Homeland Security is the U.S. Customs and Border Protection (CBP) agency. CBP is a federal law enforcement agency charged with the mission of enforcing border security policy, among some other tasks. The border region includes thousands of miles of both land and maritime borders, that must be controlled, as well as commercial transportation networks. To address such a large problem, it is critical that CBP makes intelligent use of limited resources to provide efficient and effective security. Additionally, given the complexity of the CBP patrolling problem (and other similar security/defense problems), it is clear that computational decision support tools have the potential to greatly improve resource allocation policies, and to reduce the burden on human schedulers. Although during the past years there has been a large and growing literature on patrolling problems, there are still some important features of the CBP domain that have been relatively neglected in the literature. First, the CBP problem is very large, both in the size of the physical domain and in the number of resources that need to be coordinated in the patrolling policy. Hence, highly scalable algorithms are needed for cases with many patrolling resources. Second, the CBP problem can be naturally thought of as a multi-objective optimization problem, due to the large variety of different types of illegal activity that CBP must consider, in addition to cost considerations and other factors. Most of the literature on patrolling considers only a single objective function. Therefore, this thesis presents new methods for generating solutions to large-scale, multi-objective patrolling problems. The first approach formulates the patrolling problem as a multiple objective optimization problem considering multiple agents. The second approach proposes the use of a hybrid evolutionary game theory algorithm to solve the problem. For both approaches, our solution methodology is based on evolutionary optimization techniques in the interests of scalability. Using this approach, a variety of Pareto-optimal patrolling strategies are generated, which can then be presented to human analysts for decision making, visualization, or further post-Pareto analysis