Generating Sparse Probabilistic Graphs for Efficient Planning in Uncertain Environments

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.

Authors

• Yasmin Veys
• Martina Stadler
• Nicholas Roy

Keywords

• Measurement
• Costs
• Uncertainty
• Three-dimensional displays
• Probabilistic logic
• Satellite navigation systems
• Planning
• Uncertain Environment
• Probabilistic Graph
• Navigation
• Environmental Uncertainty
• Environmental Approach
• Plan Quality
• Cost Path
• Graph Optimization
• Weather
• Upper Bound
• Path Length
• Average Cost
• Shortest Path
• Semantic Segmentation
• Computationally Intractable
• Configuration Space
• Optimal Path
• Visibility Graph
• Pair Of Vertices
• Final Graph
• Synthetic Environment
• Navigation In Environments
• Free-space Path
• Planning Cost