TL;DR
BPMP-Tracker is a high-performance trajectory planning pipeline that allows drones to track multiple moving targets through complex, obstacle-ridden environments in real-time. By leveraging the unique mathematical properties of Bernstein polynomials, the system can evaluate thousands of candidate flight paths in milliseconds, ensuring the drone avoids collisions and maintains a clear line of sight even in crowded dynamic scenes.
What Problem Does This Paper Address?
Aerial tracking is a balancing act. A drone must follow a target while simultaneously avoiding static obstacles (like trees), dodging dynamic obstacles (like other drones or people), and staying within its own physical limits (velocity and acceleration).
The "hardest" part of this problem is handling non-convex constraints—specifically occlusion. It’s not enough to just not hit a wall; the drone must also ensure the wall doesn't get between it and the target. Most existing methods either simplify the environment too much or use heavy optimization techniques that are too slow for the limited "onboard brains" of small drones. Scaling this to track multiple targets at once makes the math exponentially more difficult.
Methods
The authors introduce a sample-check-select strategy powered by Bernstein Polynomial Motion Primitives (BPMP).
- Bernstein Polynomials: Instead of standard power-series polynomials, the authors represent trajectories using the Bernstein basis. This offers three "superpowers":
- Non-negativity: If the coefficients are positive, the whole path is positive (useful for distance checks).
- Convex Hull Property: The entire trajectory is guaranteed to stay within the "box" formed by its control points, allowing for lightning-fast collision checks without calculating every point on the curve.
- Multiplication/Integration: Complex operations like finding the distance between two curves become simple algebraic sums.
- Sample-Check-Select:
- Sample: The drone generates a "bundle" of 1,000 potential future paths (primitives).
- Check: Each path is instantly checked against constraints: Is it too fast? Does it hit a wall? Is the target hidden? Does it keep all targets in the camera's Field of View (FOV)?
- Select: The "best" valid path is chosen based on a cost function that prioritizes smoothness and maintaining an ideal following distance.
- Safe Corridor Generation: The paper includes a custom algorithm (Algorithm 1) that generates "safe flight corridors" that are not only obstacle-free but also "occlusion-free," ensuring the target remains visible.
Datasets & Evaluation
The researchers evaluated the BPMP-Tracker using a mix of high-fidelity simulations and real-world hardware:
- Simulations: Conducted in AirSim, featuring a city park (single target) and a futuristic building (dual target).
- Stress Tests: A custom environment with 69 dynamic obstacles (spheres/cylinders) moving at high speeds in a confined space.
- Hardware Experiments:
- A Jetson Xavier NX-powered drone tracking humans moving from indoor to outdoor environments.
- A swarm of 10 Crazyflie 2.1 micro-quadrotors (one chaser, one target, eight dynamic obstacles).
Key Insights and Ideas
- Efficiency through Algebra: By using Bernstein properties, the "check" phase for a single primitive takes only a few microseconds. This allows the drone to be "smarter" by considering more options in less time.
- Target Prediction is Key: The tracker doesn't just react to where the target is; it predicts where the target will be while assuming the target itself will try to avoid obstacles.
- Multi-Target Scalability: The framework naturally extends to multiple targets. The drone calculates a "deadzone" (a cylinder between targets) where it cannot fly if it wants to keep both targets in its FOV.
- Linear Complexity: Unlike optimization-based trackers that get exponentially slower as you add obstacles, BPMP-Tracker’s computation time grows linearly with the number of constraints.
Key Results
- Speed: The entire planning pipeline completes in under 30 milliseconds, even on edge computing hardware.
- Success Rate: In dense environments with 70 moving objects, BPMP-Tracker maintained a ~70-80% success rate, significantly outperforming traditional optimization-based benchmarks which often dropped below 20% success in the same conditions.
- Robustness: The system successfully handled dual-target tracking and complex transitions (like flying through a narrow doorway while following a person) without losing sight or crashing.
Limitations and Future Work
- Unavoidable Occlusions: The authors note that if a dynamic obstacle moves directly between the drone and the target in a way that no valid path can circumvent, the tracker may still fail. This is a physical limitation of using a single chaser.
- Sample Density: While 1,000 samples are effective, the "best" possible path might fall between the samples. Future work could involve refining the sampling distribution based on the environment.
- Communication: In the multi-drone hardware tests, the system relied on an external motion capture system (Optitrack). Moving toward fully onboard vision for all obstacles remains a challenge for micro-drones.
Summary updated