C-Uniform Trajectory Sampling For Fast Motion Planning

O. Goktug
Poyrazoglu
Yukang
Cao
Volkan
Isler
Robotic Sensor Network Lab, University of Minnesota
Paper

Abstract

We study the problem of sampling robot trajectories and introduce the notion of C-Uniformity. As opposed to the standard method of uniformly sampling control inputs (which lead to biased samples of the configuration space), C-Uniform trajectories are generated by control actions which lead to uniform sampling of the configuration space. After presenting an intuitive closed-form solution to generate C- Uniform trajectories for the 1D random-walker, we present a network-flow based optimization method to precompute C- Uniform trajectories for general robot systems. We apply the notion of C-Uniformity to the design of Model Predictive Path Integral controllers. Through simulation experiments, we show that using C-Uniform trajectories significantly improves the performance of MPPI-style controllers, achieving up to 40% coverage performance gain compared to the best baseline. We demonstrate the practical applicability of our method with an implementation on a 1/10th scale racer.

Comparison of uniformly sampling the actions versus C-Uniform trajectories for the 1-D random walk system

Overview Video

What is C-Uniformity?

C-Uniformity is a new notion for sampling robot trajectories where we seek to generate trajectories with the following property: Let \( L(t) \) be the set of configurations reachable by the robot in time \( t \). C-uniform trajectories are a collection of trajectories such that, for each \( t \), configurations in \( L(t) \) are sampled uniformly at random.

General Methodology: We generate level sets by densely sampling control inputs and tiling \( \delta \)-measure regions over each level set. To compute the action probabilities, a flow network is generated whose maximum-flow yields C-Uniformity.

Coverage Analysis

Trajectories with Uniformly Selected Actions

Trajectories with C-Uniform Trajectory Sampling

Coverage Performance Comparison of MPPI, log-MPPI, and C-Uniform at Varying Sample Sizes

Number of Sampled Trajectories MPPI log-MPPI C-Uniform
Low Medium High Low Medium High
250 21 (0.09%) 86 (0.36%) 329 (1.37%) 74 (0.31%) 271 (1.13%) 674 (2.81%) 737 (3.08%)
500 23 (0.10%) 94 (0.39%) 356 (1.48%) 79 (0.33%) 345 (1.44%) 897 (3.74%) 995 (4.15%)
1000 26 (0.11%) 103 (0.43%) 410 (1.71%) 76 (0.32%) 390 (1.63%) 1140 (4.75%) 1382 (5.83%)
2500 28 (0.12%) 112 (0.47%) 529 (2.20%) 93 (0.39%) 470 (1.96%) 1420 (5.92%) 1851 (7.71%)
5000 27 (0.11%) 120 (0.50%) 584 (2.43%) 100 (0.42%) 525 (2.19%) 1637 (6.82%) 2271 (9.46%)
10000 29 (0.12%) 131 (0.55%) 653 (2.72%) 104 (0.43%) 568 (2.37%) 1838 (7.66%) 2578 (10.74%)

Real World Experiments

C-Uniform (Cluttered)

MPPI (Cluttered)

log-MPPI (Cluttered)

C-Uniform (U-Shaped)

MPPI (U-Shaped)

log-MPPI (U-Shaped)

BibTeX


                @misc{poyrazoglu2024cuniformtrajectorysamplingfast,
                    title={C-Uniform Trajectory Sampling For Fast Motion Planning}, 
                    author={O. Goktug Poyrazoglu and Yukang Cao and Volkan Isler},
                    year={2024},
                    eprint={2409.12266},
                    archivePrefix={arXiv},
                    primaryClass={cs.RO},
                    url={https://arxiv.org/abs/2409.12266}, 
              }