Multi-Sample Long Range Path Planning under Sensing Uncertainty for Off-Road Autonomous Driving
We focus on the problem of long-range dynamic replanning for off-road autonomous vehicles, where a robot plans paths through a previously unobserved environment while continuously receiving noisy local observations. An effective approach for planning under sensing uncertainty is determinization, where one converts a stochastic world into a deterministic one and plans under this simplification. This makes the planning problem tractable, but the cost of following the planned path in the real world may be different than in the determinized world. This causes collisions if the determinized world optimistically ignores obstacles, or causes unnecessarily long routes if the determinized world pessimistically imagines more obstacles. We aim to be robust to uncertainty over potential worlds while still achieving the efficiency benefits of determinization. We evaluate algorithms for dynamic replanning on a large real-world dataset of challenging long-range planning problems from the DARPA RACER program. Our method, Dynamic Replanning via Evaluating and Aggregating Multiple Samples (DREAMS), outperforms other determinization-based approaches in terms of combined traversal time and collision cost.
DREAMS
Dynamic Replanning Evaluating and Aggregating Multiple Samples
Below is an overview of DREAMS. The key feature of DREAMS is it maintains the efficiency of determinization while also being able to reason about the whole distribution of costs. This is done by evaluating each sampled plan on a sampled set of worlds. Further, DREAMS is highly flexible as it allows users to define their own cost function and aggregation function to fit the needs of their application. DREAMS can also evaluate each plan over other parameters like speed and acceleration to determine the best way to track the trajectory for the application.
Sample & Plan: Sample many worlds from the posterior distribution, and plan the optimal path on a subsample of worlds (ϕ 1 , ϕ 10 , ϕ 50 above).
Evaluate: Evaluate the cost of each resulting plan against the full set of sampled worlds.
Aggregate: Aggregate the resulting cost distribution with a summary statistic (e.g., mean or CVaR)
Select: Select the plan with minimal aggregated cost.
Execute & Sense: Execute first edge of plan, take sensor readings and replan. In practice, execution is as quick as the replanning cycle can be repeated
Experiments
We evaluate DREAMS against Sampled A* and DRPS, two performent determinization approaches on 135 real world costmaps collected from an offroad autonomous vehicle perception system. In these tests, planning and execution are interleaved requiring the robot to re-plan many times to eventually find a path through the noise to the goal. Sensing is simulated to behave like a real perception system, in particular, sensing becomes noisier further from the robot.
To make the tests as realistic as possible, collisions are also recorded and factored into the total cost of an episode. Further, the robot can traverse edges at different speeds trading off speed for risk of a dangerous collision and less observations.
Sensor Noise Levels
Low Noise
Medium Noise
High Noise
Personal Robotics Lab