BPMP-Tracker: A Versatile Aerial Target Tracker Using Bernstein Polynomial Motion Primitives

Yunwoo Lee, Jungwon Park, Boseong Jeon, Seungwoo Jung, H. Jin Kim

Abstract

This letter presents a versatile trajectory planning pipeline for aerial tracking. The proposed tracker is capable of handling various chasing settings such as complex unstructured environments, crowded dynamic obstacles and multiple-target following. Among the entire pipeline, we focus on developing a predictor for future target motion and a chasing trajectory planner. For rapid computation, we employ the sample-check-select strategy: modules sample a set of candidate movements, check multiple constraints, and then select the best trajectory. Also, we leverage the properties of Bernstein polynomials for quick calculations. The prediction module predicts the trajectories of the targets, which do not overlap with static and dynamic obstacles. Then the trajectory planner outputs a trajectory, ensuring various conditions such as occlusion and collision avoidance, the visibility of all targets within a camera image and dynamical limits. We fully test the proposed tracker in simulations and hardware experiments under challenging scenarios, including dual-target following, environments with dozens of dynamic obstacles and complex indoor and outdoor spaces.

Introduction

Aerial tracking is a complex balancing act requiring a drone to follow targets while simultaneously avoiding static obstacles, dodging dynamic objects, and staying within its own physical limits. A primary challenge in this domain is handling non-convex constraints, specifically occlusion. It is insufficient to merely avoid physical collisions; the drone must also ensure that environmental structures do not obstruct its line of sight to the target. Most existing methods are either too computationally expensive for onboard processing or oversimplify the environment. BPMP-Tracker addresses these issues by leveraging the mathematical properties of Bernstein polynomials to evaluate thousands of candidate flight paths in real-time.

Methodology

The BPMP-Tracker utilizes a sample-check-select strategy powered by Bernstein Polynomial Motion Primitives (BPMP). This approach allows the system to maintain high performance even in crowded dynamic scenes.

The BPMP-Tracker pipeline consists of input data processing, target motion prediction, and trajectory generation using a sample-check-select strategy.

Bernstein Polynomial Properties

Instead of standard power-series polynomials, trajectories are represented using the Bernstein basis, which offers several advantages for real-time planning:

  • Convex Hull Property: The entire trajectory is guaranteed to stay within the volume formed by its control points, allowing for extremely fast collision checks without evaluating every point on the curve.
  • Computational Efficiency: Complex operations, such as calculating the distance between two curves or checking non-negativity, are reduced to simple algebraic sums.

The Planning Pipeline

  1. Sample: The drone generates a "bundle" of approximately 1,000 potential future paths (primitives).
  2. Check: Each path is instantly validated against constraints, including velocity/acceleration limits, collision avoidance, and target visibility within the camera's Field of View (FOV).
  3. Select: The optimal valid path is chosen based on a cost function prioritizing smoothness and ideal following distance.

Additionally, the system employs a custom algorithm to generate "safe flight corridors" that are both obstacle-free and occlusion-free, ensuring continuous target tracking.

Evaluation and Results

The researchers evaluated the BPMP-Tracker using high-fidelity simulations in AirSim and real-world hardware experiments, including a Jetson Xavier NX-powered drone and a swarm of Crazyflie micro-quadrotors.

Simulation results comparing single-target and dual-target tracking performance in top-down and side views.

Key Findings

  • Real-Time Performance: The entire planning pipeline completes in under 30 milliseconds, making it suitable for edge computing hardware.
  • High Success Rate: In dense environments featuring up to 70 moving objects, the tracker maintained a 70-80% success rate, significantly outperforming traditional optimization-based benchmarks which often fell below 20% in similar conditions.
  • Scalability: The framework naturally extends to multiple targets. By calculating a "deadzone" between targets, the drone can maintain both within its FOV simultaneously.

Conclusion

BPMP-Tracker provides a robust and efficient solution for aerial tracking in unstructured environments. By utilizing Bernstein properties, the system achieves linear computational complexity relative to the number of constraints. Future work will explore refining sampling distributions and transitioning toward fully onboard vision-based obstacle detection to reduce reliance on external motion capture systems.

Summary updated

Abstract

This letter presents a versatile trajectory planning pipeline for aerial tracking. The proposed tracker is capable of handling various chasing settings such as complex unstructured environments, crowded dynamic obstacles and multiple-target following. Among the entire pipeline, we focus on developing a predictor for future target motion and a chasing trajectory planner. For rapid computation, we employ the sample-check-select strategy: modules sample a set of candidate movements, check multiple constraints, and then select the best trajectory. Also, we leverage the properties of Bernstein polynomials for quick calculations. The prediction module predicts the trajectories of the targets, which do not overlap with static and dynamic obstacles. Then the trajectory planner outputs a trajectory, ensuring various conditions such as occlusion and collision avoidance, the visibility of all targets within a camera image and dynamical limits. We fully test the proposed tracker in simulations and hardware experiments under challenging scenarios, including dual-target following, environments with dozens of dynamic obstacles and complex indoor and outdoor spaces.
BibTeX
@article{lee2024bpmp,
  author = {Yunwoo Lee and Jungwon Park and Boseong Jeon and Seungwoo Jung and H. Jin Kim},
  title = {{BPMP-Tracker: A Versatile Aerial Target Tracker Using Bernstein Polynomial Motion Primitives}},
  journal = {IEEE Robotics Autom. Lett.},
  year = {2024},
  doi = {10.1109/lra.2024.3475879},
}
Figure