Environments with regions of uncertain traversability can be modeled as roadmaps with probabilistic edges for efficient planning under uncertainty. We would like to generate roadmaps that enable planners to efficiently find paths with expected low costs through uncertain environments. The roadmap must be sparse so that the planning problem is tractable, but still contain edges that are likely to contribute to low-cost plans under various realizations of the environmental uncertainty. Determining the optimal set of edges to add to the roadmap without considering an exponential number of traversability scenarios is challenging. We propose the use of a heuristic that bounds the ratio between the expected path cost in our graph and the expected path cost in an optimal graph to determine whether a given edge should be added to the roadmap. We test our approach in several environments, demonstrating that our uncertainty-aware roadmaps effectively trade off between plan quality and planning efficiency for uncertainty-aware agents navigating in the graph.

We would like to enable a robot to navigate efficiently and robustly in known, structured environments that are large enough to cause traditional planning approaches to incur considerable computational cost. Hierarchical planners are a promising way to increase planning efficiency in such environments because high-level abstract plans can be used to reduce the size of the search space over which detailed planning occurs. However, useful high-level representations of planning problems can be challenging to generate without prior domain knowledge. In this work, we propose a high-level planning representation which can be learned from previous plans considered in the environment and used online during hierarchical, multi-query robot navigation. We treat previous planning results as noisy measurements of high-level navigation properties, then update these properties over time using recursive estimation. We test our approach in standard and risk-aware hierarchical planning schemes, and demonstrate up to an 86% decrease in the number of nodes expanded and a 66% decrease in wallclock time as compared to a baseline A* planner while finding plans that are only 2-10% more expensive.

We would like to enable a robotic agent to quickly and intelligently find promising trajectories through structured, unknown environments. Many approaches to navigation in unknown environments are limited to considering geometric information only, which leads to myopic behavior. In this work, we show that learning a sampling distribution that incorporates both geometric information and explicit, object-level semantics for sampling-based planners enables efficient planning at longer horizons in partially-known environments. We demonstrate that our learned planner is up to 2.7 times more likely to find a plan than the baseline, and can result in up to a 16% reduction in traversal costs as calculated by linear regression. We also show promising qualitative results on real-world data.