Structural Bias in Heuristic Search (Student Abstract)
Keywords:Heuristic Error, Tie-breaking, Uncertainty Quantification
AbstractIn this line of work, we consider the possibility that some fast heuristic search methods introduce structural bias, which can cause problems similar to sampling-bias for downstream statistical learning methods. We seek to understand the source of this kind of bias and to develop efficient alternatives. Here we present some preliminary results in developing a variation of canonical A* that can overcome the structural bias introduced by first-in-first-out duplicate detection, which we observed under the condition of variable heuristic error. These results inspire a model of greedy-best-first-search for this problem in the satisficing setting. We hope to apply our approach in a novel planning application--activity selection for agent-based modeling for epidemiology--where planning technology should avoid introducing structural bias if possible.