无人系统与自主计算实验室

Trajectory Generation

Introduction

AM-Traj: A waypoint-based trajectory generator. This project proposes a framework for large-scale waypoint-based trajectory generation, with highlights on its superior computational efficiency and simultaneous spatial-temporal optimality. Exploiting the implicitly decoupled structure of the problem, we conduct alternating minimization between boundary conditions and time durations of trajectory pieces. Algebraic convenience of both sub-problems is leveraged to escape poor local minima and achieve the lowest time consumption. Moreover, based on polynomial theory, an extremely fast feasibility checker is designed for various kinds of constraints. By incorporating it into our alternating structure, a constrained minimization algorithm is constructed to optimize trajectories on the premise of feasibility. Benchmark evaluation shows that our algorithm outperforms state-of-the-art waypoint-based methods regarding efficiency, optimality, and scalability. The algorithm can be incorporated in a high-level waypoint planner, which can rapidly search over a three-dimensional space for aggressive autonomous flights. The capability of our algorithm is experimentally demonstrated by quadrotor fast flights in a limited space with dense obstacles.

Large-Scale Trajectory Generation in Flight Corridors: For quadrotor trajectory planning, describing a polynomial trajectory through coefficients and end-derivatives both enjoy their own convenience in energy minimization. We name them double descriptions of polynomial trajectories. The transformation between them, causing most of the inefficiency and instability, is formally analyzed in this paper. Leveraging its analytic structure, we design a linear-complexity scheme for both jerk/snap minimization and parameter gradient evaluation, which possesses efficiency, stability, flexibility, and scalability. With the help of our scheme, generating an energy optimal (minimum snap) trajectory only costs 1 μs per piece at the scale up to 1,000,000 pieces. Moreover, generating large-scale energy-time optimal trajectories is also accelerated by an order of magnitude against conventional methods.

Related Researches:

  1. Generating Large-Scale Trajectories Efficiently using Double Descriptions of Polynomials, Zhepei Wang, Hongkai Ye, Chao Xu, Fei Gao, the International Conference on Robotics and Automation (ICRA 2021). [paper] [code]
  2. Alternating Minimization Based Trajectory Generation for Quadrotor Aggressive Flight, Zhepei Wang, Xin Zhou, Chao Xu, Jian Chu, Fei Gao, IEEE Robotics and Automation Letter (RA-L with IROS2020 option). [paper] [code]

Videoes:

  1. AM-Traj: https://www.bilibili.com/video/BV1H7411T71n
  2. Generating Large-Scale Trajectories Efficiently: https://www.bilibili.com/video/BV1DA411j7m7