Text

theses

Sequential diagnosis is an old subject, but one that has become increasingly important recently. There exists a need for new models and algorithms as the traditional methods for making decisions sequentially do not scale. Motivated by the problem of container inspection at the U.S. ports, we investigate the problem of finding efficient algorithms for sequential diagnosis. More specifically, we formulate the port of entry inspection sequencing task as a problem of finding an optimal binary decision tree for an appropriate Boolean decision function. We provide new algorithms that are computationally more efficient than those previously presented by Stroud and Saeger [31] and Anand et al [1]. We achieve these efficiencies through a combination of specific numerical methods for finding optimal thresholds for sensor functions and two novel binary decision tree search algorithms that operate on a space of potentially acceptable binary decision trees. The improvements enable us to analyze substantially larger applications than was previously possible.
We try to solve the problem of finding an optimal inspection strategy by breaking it into two sub-problems - 1. Finding sensor threshold values that minimize the cost for a given binary decision tree and 2. ``Searching'' for the cheapest binary decision tree in a large space of trees or equivalence classes of trees. For solving the first problem, we explore various standard non-linear optimization techniques and also propose a novel algorithm by combining the gradient descent method and Newton's method in optimization to compute optimal thresholds for any given tree. We propose two novel search algorithms - A stochastic search method and a genetic algorithms based search method, as a solution to the second sub-problem. We also propose ``neighborhood'' operations to move from one tree to another in the proposed tree space and prove that the tree space is irreducible under these neighborhood operations.
We report results from numerous experiments with and without imposing restrictions on the tree space and examine how the optimal binary decision trees vary with these changes. For example, for most of the work in this thesis, we restrict the tree space to constitute only ``complete'' and ``monotonic'' binary decision trees. Later, we ``shrink'' the tree space by discovering equivalence classes of trees while we ``expand'' the tree space by removing the monotonicity constraint.

M.S.

Includes bibliographical references (p. 61-63).

http://hdl.rutgers.edu/1782.2/rucore10001600001.ETD.17352

ETD_780

doi:10.7282/T3CJ8DTS

ETD graduate

The author owns the copyright to this work.

application/x-tar

1832448

671a22cf75c47d6e624833f9928bf8b9cacb5312

ETD

other

windows xp

application/x-tar