• Nov 04, 2023

Time-Optimal Path Planning in a Constant Wind for Uncrewed Aerial Vehicles using Dubins Set Classification

Brady Moon* , Sagar Sachdev* , Junbin Yuan , Sebastian Scherer
Carnegie Mellon University
* denotes equal contribution

Video

Abstract

Time-optimal path planning in high winds for a turning-rate constrained UAV is a challenging problem to solve and is important for deployment and field operations. Previous works have used trochoidal path segments comprising straight and maximum-rate turn segments, as optimal extremal paths in uniform wind conditions. Current methods iterate over all candidate trochoidal trajectory types and select the one that is time-optimal; however, this exhaustive search can be computationally slow. In this paper, we introduce a method to decrease the computation time. This is achieved by reducing the number of candidate trochoidal trajectory types by framing the problem in the air-relative frame and bounding the solution within a subset of candidate trajectories. Our method reduces overall computation by 37.4% compared to pre-existing methods in Bang-Straight-Bang trajectories, freeing up computation for other onboard processes and can lead to significant total computational reductions when solving many trochoidal paths. When used within the framework of a global path planner, faster state expansions help find solutions faster or compute higher-quality paths. We also release our open-source codebase as a C++ package.

Interactive Demo

Plotly.js Demo
Modify the inputs using the sliders to see the path computed in realtime. RSL is shown as red, RSR as orange, LSL as green, LSR as blue, LRL as black, and RLR as grey. When wind is toggled off, the paths are found using the Dubins method with Dubins set classification. Path display option "Optimal" shows only the optimal path, "Reduced" shows the reduced set of paths found using our method, and "Possible" plots all of the possible paths. This demo was created by converting our C++ codebase into JavaScript purely for demonstration purposes, so please refer to our github repo for usage of our method.

Results

Qualitative

Fig. 1: Randomly sampled candidate BSB trajectories for randomly selected initial and final states in a uniform wind-vector field. RSL is shown as red, RSR as orange, LSL as green, and LSR as blue. The bolded path in each subfigure is the optimal one.

Quantitative

The average run-time over 10,000 random configurations for BSB trajectories on a 3.40 GHz CPU was 1.4224 ms compared to the baseline method of 2.2711 ms (Fig. 1 shows six randomly sampled trajectories). The testing results yielded a 37.4% improvement over the baseline method.

BibTex

@article{moon2023timeoptimal,
        title={Time-Optimal Path Planning in a Constant Wind for Uncrewed Aerial Vehicles using Dubins Set Classification}, 
        author={Brady Moon and Sagar Sachdev and Junbin Yuan and Sebastian Scherer},
        year={2023},
        journal = {IEEE Robotics and Automation Letters},
        publisher = {IEEE},
        doi = {10.1109/LRA.2023.3333167},
        url = {https://arxiv.org/pdf/2306.11845.pdf},
        video = {https://youtu.be/qOU5gI7JshI}
}