Sequencing questions to ferret out terrorists: Models and heuristics

Consider the problem of granting boarding clearance for a large population of air travelers while ferreting out any potential terrorists and denying them entry, in a short time. It is assumed that the probability of having a terrorist in the group is very small. Further assume that the process consists of asking a series of questions and the decision to clear or deny is dependent on the answer set. An efficient sequencing of the questions may reduce the number of questions needed to be asked in order to reach a decision. This problem is modeled as a question sequencing problem. The problem is intrinsically hard and hence we develop two approaches to solving the problem. The first uses a traditional greedy heuristic approach exploiting the relationship between answers and the outcome. The second adopts the decision tree approach used in classification problems to this problem. We also report on the performance of the two heuristics which does exceptionally well on problems with a very low probability of occurrence.