Finding ways to intercept illicit nuclear materials and weapons destined for the U.S. via the maritime transportation system is an exceedingly difficult task. Today, only a small percentage of ships entering U.S. ports have their cargoes inspected. The purpose of this study is to develop decision support algorithms that will help us to optimally intercept illicit materials and weapons and to test the algorithms on real data arising from port-of-entry inspection. The algorithms sought will find inspection schemes that minimize total cost, including "cost" of false positives and false negatives.
Imagine a stream of entities arriving at a port and a decision maker having to decide how to inspect them, which to subject to further inspection and which to allow to pass through with only minimal levels of inspection. This is a complex sequential decision making problem. The ultimate goal of an inspection scheme is to classify an entity into important categories and states. In the simplest case, there are two categories ("ok" and "suspicious") and two states ("present" or "absent"). This classification can be described as involving a boolean decision function. Different binary tree representations for a boolean decision function have different inspection costs associated with them and an optimal decision tree representation is sought. Modeling sensors used to test for attributes makes the problem more realistic and brings in possible inspection errors and false positives and negatives. Extending the problem to more than two categories and more than two states also makes the problem more realistic.
The project will be carried out in collaboration between a university team and a team from the Los Alamos National Laboratory and will initially follow an approach pioneered at Los Alamos. Four graduate students will be key participants in the project and many others will be involved through associated public events. The topic lends itself well to undergraduate research and participating faculty will coordinate topics with an existing undergraduate research program that caters to students from all over the U.S. To broaden the impact of the project, a seminar series will be publicized to neighboring institutions and a public workshop will be held. The workshop will include talks of an expository/tutorial nature, making it appealing to non-specialists and students. A project website and a project book will help to disseminate project results and ideas widely.
Seaports are the gateway to our nation’s economy. As much as 95% of foreign trade and virtually 100% of key commodities (such as oil) enters the country through seaports. The proximity to urban centers and volume and diversity of seaport activities make seaports vulnerable targets. Yet, it is widely recognized that full inspection of all shipping containers, or even a sizable sample, would introduce unacceptable economic costs, including cost to effect the examination and costs incurred by delay of goods Our project aimed to provide more efficient strategies for inspecting containers at ports of entry. In practice, a range of "tests" are available for cargo screening. Of these, document screening is the least expensive; physical methods, such as gamma ray detection, are more expensive; and manual unpacking is most expensive. Introducing more tests could reduce the time and expense of opening containers, but only with good methods for dealing with realistic complications like false positives. From a computational standpoint, finding efficient inspection algorithms presents serious challenges due to the explosion in the number of choices of tests to apply and the order to apply them. Algorithmic approaches to container inspection quickly run afoul when more than a small number of tests is used. This project built on previous work done by researchers at Los Alamos National Laboratory. They envisioned a stream of containers arriving at a port and a decision maker having to decide which tests to apply to each container and in what order. The result is a complex sequential decision making problem. Using exhaustive search they were able to optimize inspection when there were four available tests with simple 0-1 output, but considering five tests in this manner was not practically feasible. Our goal was to enable consideration of more tests with a larger number of potential outputs. One particular practical problem variation we studied involved maximizing detection rate under inadequate inspection budgets. We developed and solved a dynamic programming (DP) formulation of the problem of optimally combining independent tests into an inspection policy that achieves maximal detection rate under limited operating budget. We introduced a precise mathematical model, defined domination between policies, and showed that all undominated policies can be generated by DP. The new DP methods are vastly more efficient than previous strategies, and can solve problems that can generate billions of possible decision trees in just a few minutes. With this method, solving problems with up to 20 different screening tests is now well within reach. Other parts of the project looked at minimizing the total cost of inspection where cost includes both cost of performing a test and potential cost of a successful attack resulting from missed detection. The approach taken by the Los Alamos team involved finding optimal (least cost) binary decision trees (BDTs), but because of the explosion in the number of such trees, they limited their analysis to trees corresponding to special classes of Boolean decision functions, namely complete, monotone Boolean functions. Our team defined a notion of complete and monotone BDTs, which provided a richer space of solutions that proved easier to search. We developed new probabilistic search methods that explored this larger space and discovered BDTs for four tests significantly lower in cost than those discovered previously. Computational experiments showed that the methods could provide good solutions for significantly more than four tests. The research outcomes from this project are also applicable to other modern problems. For example, many problems of epidemiology and public health can be looked at as sequential decision making problems where later decisions depend upon feedback from earlier ones. By modifying tools developed for container inspection, we developed new methods for making decisions such as which public health intervention to try next against a disease outbreak, given outcomes of earlier interventions. This project was motivated by the vitally important problem of screening containers entering the country for dangerous and destructive materials. To bring our results to a larger community, we organized a workshop on port security and included participants with practical port security experience from the national labs, U.S. Customs and Border Protection, U.S. Coast Guard, NJ Office of Homeland Security and Preparedness, Canada Border Services Agency, and the shipping industry. This workshop was very successful in connecting people who play a wide variety of roles in port security. Outreach to government agencies with responsibility for port protection has been an area of particular emphasis for our project and we have built and grown relationships with many of these agencies.
