Sequential Planning Algorithms for Navigation under Uncertainty

Abstract

Applications such as search-and-rescue, warehouse robotics, infrastructure inspection, and autonomous transportation require agents to navigate environments whose conditions are only partially known. Information about hazards, route feasibility, and other agents often becomes available gradually through local observations and interactions during traversal, requiring plans to be revised as information evolves. Existing planning methods often simplify these settings by assuming unrestricted information acquisition, independent environmental hazards, or centralized coordination. This dissertation develops sequential planning algorithms for adaptive navigation when one or more of these assumptions do not hold. Three related settings are considered. First, resource-constrained navigation is studied in settings where resolving uncertain hazards consumes a limited operational budget, and a planning framework is developed to support selective information acquisition and adaptive replanning. Second, spatial dependence among environmental hazards is modeled using Gaussian random fields, and the resulting navigation problem is addressed through a two-stage learning framework combining information-guided offline policy learning with online rollout and periodic belief adaptation. Third, decentralized multi-agent navigation is addressed through Bayesian belief updating, adversarial risk analysis-based agent modeling, and multi-step rollout, enabling agents to predict one another’s behavior and coordinate without centralized control or direct communication. Theoretical analyses establish solution guarantees, characterize the value of correlation modeling and information acquisition, and provide convergence and stability results. Empirical studies show that the proposed frameworks reduce traversal cost and improve resource allocation, environmental risk management, and multi-agent coordination across settings. Overall, the dissertation demonstrates how inference, learning, and optimization can be integrated within a closed-loop planning process for efficient and adaptive navigation under uncertainty.