Protocols for stochastic shortest path problems with dynamic learning

The research problem considered in this dissertation, in its most broad setting, is a stochastic shortest path problem in the presence of a dynamic learning capability (SDL). Specifically, a spatial arrangement of possible-obstacles needs to be traversed as swiftly as possible, and the status of the obstacles may be disambiguated (at a cost) en route. The central question is to find a protocol that decides what and where to disambiguate so as to minimize the expected length of the traversal. No efficiently computable optimal protocol is known and many similar problems have been proven intractable.; Chapter 1 defines SDL in continuous and discrete settings, and introduces the Random Disambiguation Paths Problem (RDP), a continuous variant of SDL wherein the possible-obstacles are disc-shaped regions in the plane. For any RDP instance, the continuous plane can be approximated by a graph (a lattice), giving rise to the Discrete RDP Problem (DRDP).; Chapter 2 casts SDL as a Markov Decision Process and develops the corresponding Bellman equation. Introduced in this chapter is a new improvement on the well-known AO* Algorithm, called the BAO* Algorithm, which employs stronger pruning techniques and substantially shortens the running time needed to find an exact solution to relatively small DRDP instances. The chapter also presents a Partially Observable Markov Decision Process (POMDP) formulation of RDP.; Chapter 3 discusses visibility graphs and introduces the tangent arc graph data structure (TAG). TAG is a new data structure comprised of the topological superimposition of all of the visibility graphs generated by a collection of all subsets of disc-shaped obstacles. Although there are exponentially many such subsets, TAG is polynomially-sized. The chapter then points out that the well-known A* Algorithm with a slightly stronger admissibility requirement on the heuristic function is equivalent to Dijkstra's Algorithm under a change of variable.; Chapter 4 introduces the simulated risk disambiguation protocol (SR)---a suboptimal but, effective and efficiently computable algorithm for RDP and DRDP. This protocol initially assumes that all discs are riskily traversable. Then, a chosen "undesirability function" is used (for each such possible traversal) to combine length and risk into a single measure of traversal undesirability. A shortest traversal in this undesirability sense is what the DM traverses until the first ambiguous disc is encountered, at which point a disambiguation is performed and the problem data is updated accordingly. This procedure is iteratively repeated until arrival at the destination.; In Chapter 5, another suboptimal, but very efficiently computable protocol is proposed for RDP and DRDP, called the continually reactivated (CR) disambiguation protocol. The CR protocol is defined as the optimal protocol in an altered RDP setting wherein the discs are continually reactivated, and this CR protocol is efficiently computed in the RDP setting through the use of TAG. The CR protocol is then proved to be optimal for parallel graphs in the discrete SDL setting, and this theorem is extended to yield optimal protocols for a broader class of SDL problems where the DM's choice is just between parallel avenues under fixed policies within the avenues.; Chapter 6 presents summary, conclusions, and directions for future research.