Does Distance-to-Termination Matter? A Study of the DT Algorithm in the Stochastic Obstacle Scene Problem

Abstract

In the stochastic obstacle scene problem (SOSP), a navigating agent traverses a region containing obstacles of uncertain status. The agent can disambiguate/probe the status of an obstacle in the boundary at a cost to determine if the obstacle is traversable or not. In a navigation algorithm involving a penalty function, the central problem is determining an appropriate weight to assign to each edge that crosses the boundaries of obstacles. ``Distance-to-Termination'' (DT) algorithm is a widely-used navigation algorithm that utilizes a metric distance-to-target $d_t$. In this thesis, we examine how much influence the metric distance-to-terminal has on the performance of the algorithm and the total number of disambiguations using three simulation designs. In the first design, we propose a fixed DT (fDT) algorithm where the metric $d_t$ is fixed and compare the local behaviors of DT and fDT at each obstacle configuration. We use the Bayesian logistic mixed model (BLMM) in the second design to analyze the predictor impact on disambiguation. In the last design, we use sensitivity analysis to measure how a change in $d_t$ influences the probability that the obstacle is disambiguated. Our experiments suggest that the marginal effect of $d_t$ on the decision appears limited compared to that of the obstacle's probability, and the effect of the obstacle's probability $p$ has a larger effect on the algorithm's decision.