Back to search

University of Washington

Robot Motion Planning with Uncertainty and Urgency

Abstract

dc:description.abstract

As robots are introduced to a wider variety of real-world domains–factories, roads, and homes–they must be able to reliably operate with incomplete knowledge of the cluttered-but-structured environment. This dissertation considers the problem of motion planning with uncertainty, where a robot navigates to a goal without knowing the environment's exact obstacle geometry. How can uncertainty be efficiently incorporated into decision-making, without ballooning planning times on computationally-constrained systems and paralyzing robots into indecision? How can algorithms leverage the structure of uncertainty to efficiently plan high-quality paths? This dissertation proposes Bayesian strategies for integrating uncertainty throughout the sampling-based motion planning framework. We formalize uncertainty with an informative posterior distribution over latent environment parameters. In this component, roboticists express their domain expertise about a robot's environment, sensor suite, and interactions between the two. Bayesian planning algorithms aim to navigate the exploration-exploitation tradeoff with respect to this distribution of environments that the robot anticipates seeing at test time. We develop efficient Bayesian search algorithms motivated by regret minimization. This objective captures the urgency of a planner's sequential decision-making process by comparing with the optimal decision-maker at each iteration. The cumulative difference, or regret, penalizes suboptimality at each iteration as well as the time expended to reduce that suboptimality. We demonstrate that algorithms based on posterior sampling are effective for Bayesian anytime lazy motion planning and Bayesian dynamic motion planning. We propose a variational inference algorithm for roadmap optimization, which aims to match the distribution of roadmap samples to the target distribution of collision-free states. We demonstrate that optimized sparse roadmaps concisely approximate the uncertain environment and can be searched more efficiently than conventional uniform or low-discrepancy dense roadmaps.

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Hou, Brian
Advisor dc:contributor.advisor
  • Srinivasa, Siddhartha S.

Subjects

dc:subject × 3

Rights

dc:rights
Statement dc:rights
  • CC BY-NC-ND
Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1773/49877

Chain of custody

source
Harvested from
University of Washington
Base URL
digital.lib.washington.edu/server/oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Hou, Brian. Robot Motion Planning with Uncertainty and Urgency. 2023. http://hdl.handle.net/1773/49877