| The main problem considered in this thesis is to navigate an agent that is capable of disambiguating to safely and swiftly traverse a terrain populated with possible hazardous regions that can overlap. The problem has three main features. First, the planning is made under uncertainty but without blindness. Second, the agent can disambiguate the true-false status of any potential hazard as it approaches the vicinity. Third, the replanning can be made with less uncertainty if there is new information collected en route. We formulate this problem as a dynamic shortest path problem in directed, positively weighted graph, that is, any plan is a shortest path from the agent's location to the target node in the graph. Each time when a plan is made, the agent moves accordingly until it encounters uncertainty. The agent then disambiguates, at a cost, the local uncertainty, adds the disambiguation result(s) to the knowledge of the world, and replans a new shortest path from where it is to the goal.;In consideration of real-world practice and simulation efficiency, we apply the A* algorithm for the deterministic shortest path subproblem. We also give the A* algorithm a new explanation within the primal-dual framework. For the terrain, we assume that besides the natural topological information, which facilitates the use of the A* search, there is also additional prior information regarding the likelihood of the true-false status of the potential hazards. This additional prior information forms the initial knowledge of the world. We present a navigation policy called CR and its various versions. The policy integrates the prior information and the information collected en route. We provide both theoretical and experimental results under different settings. As part of this dissertation research, a computer program that simulates an agent to traverse a minefield was developed. As an important tool, the program, combined with Monte Carlo simulations, helps us dealing with complicated real-world scenarios that are beyond the reach of any known analytical method. As an application, we used the program to process the Navy's reconnaissance data and obtained exiting results. |
