Random Disambiguation Paths: Models, Algorithms, and Analysis

For a RDP problem, the central issue is to optimize the navigation/disambiguation protocol. In this study, we explore the idea of the dynamic shortest path algorithm for the planning and re-planning. We proposed a protocol called “CR”, in which the uncertainty is incorporated into the cost function. We have proved in simple theoretical setting that this strategy is optimal. We have implemented this strategy using dynamic A* algorithm and extensive simulation results appear to be very promising. Given a good protocol at hand, an important question is: does a better sensor imply a better traversal? This is the sensor information monotonicity problem that we have investigated thoroughly. Under some simple theoretical settings, we found that the CR-protocol can be proved to have the monotonicity property. For more realistic scenarios, we performed large scale Monte Carlo Simulations. The statistics still show amazing Monotonicity results. This finding is sensible for the decision making of the sensor deployment. For the CR protocol, empirically, it’s a realizable stratergy.