Halbert, Tyler Raymond (2015-08). An Improved Algorithm for Sequential Information-Gathering Decisions in Design under Uncertainty. Master's Thesis.
Thesis
In engineering decision making, particularly in design, engineers must make decisions under varying levels of uncertainty. While not always the case, oftentimes one of the options available to an engineer is the ability to gather information that will reduce the uncertainty. With the reduced uncertainty, the engineer then returns to the same decision with more information. This sequential information-gathering decision problem is difficult to analyze and solve because the engineer must predict the value of gathering information in order to determine if the value outweighs the cost of the resources expended to gather the information. In practice, heuristics, intuition, and deadlines are often used to decide whether or not to gather information. A more complete and formal approach for quantifying the value of gathering information would benefit engineers in design decision making. Recent work proposed that a Partially Observable Markov Decision Process (POMDP) is an appropriate formalism for modeling sequential information-gathering decisions. A POMDP appears capable of capturing the salient features of such decisions. However, existing POMDP solution algorithms scale poorly with problem size. This thesis introduces an improved algorithm for solving POMDPs that takes advantage of certain characteristics inherent to information-gathering decision problems. The new algorithm is orders of magnitude faster and also is capable of handling specific problem parameters that existing methods cannot. The improvement is shown with a detailed case study, where the case study also performs a comparison of using the POMDP formalism for solving information-gathering decision problems to widely known approximate methods, such as Expected Value of Information methods. The study demonstrates that the use of the POMDP formalism, along with the improved algorithm, provides a valuable method for solving certain information-gathering decision problems.
In engineering decision making, particularly in design, engineers must make decisions under varying levels of uncertainty. While not always the case, oftentimes one of the options available to an engineer is the ability to gather information that will reduce the uncertainty. With the reduced uncertainty, the engineer then returns to the same decision with more information. This sequential information-gathering decision problem is difficult to analyze and solve because the engineer must predict the value of gathering information in order to determine if the value outweighs the cost of the resources expended to gather the information. In practice, heuristics, intuition, and deadlines are often used to decide whether or not to gather information. A more complete and formal approach for quantifying the value of gathering information would benefit engineers in design decision making.
Recent work proposed that a Partially Observable Markov Decision Process (POMDP) is an appropriate formalism for modeling sequential information-gathering decisions. A POMDP appears capable of capturing the salient features of such decisions. However, existing POMDP solution algorithms scale poorly with problem size. This thesis introduces an improved algorithm for solving POMDPs that takes advantage of certain characteristics inherent to information-gathering decision problems. The new algorithm is orders of magnitude faster and also is capable of handling specific problem parameters that existing methods cannot. The improvement is shown with a detailed case study, where the case study also performs a comparison of using the POMDP formalism for solving information-gathering decision problems to widely known approximate methods, such as Expected Value of Information methods. The study demonstrates that the use of the POMDP formalism, along with the improved algorithm, provides a valuable method for solving certain information-gathering decision problems.