Mapless-Planner: A Robust and Fast Planning Framework for Aggressive Autonomous Flight without Map Fusion

Jialin Ji, Zhepei Wang, Yingjian Wang, Chao Xu, Fei Gao

Abstract

Maintaining a map online is resource-consuming while a robust navigation system usually needs environment abstraction via a well-fused map. In this paper, we propose a mapless planner which directly conducts such abstraction on the unfused sensor data. A limited-memory data structure with a reliable proximity query algorithm is proposed for maintaining raw historical information. A sampling-based scheme is designed to extract the free-space skeleton. A smart waypoint selection strategy enables to generate high-quality trajectories within the resultant flight corridors. Our planner differs from other mapless ones in that it can abstract and exploit the environment information efficiently. The online replan consistency and success rate are both significantly improved against conventional mapless methods.

Introduction

Autonomous drone navigation typically faces a trade-off between the foresight of map-based planners and the agility of mapless planners. Map-based systems fuse sensor data into global representations (e.g., occupancy grids), which are computationally expensive and sensitive to localization drift. Conversely, reactive mapless systems are lightweight but often "short-sighted," struggling with complex geometries like U-shaped obstacles.

Overview of the Mapless-Planner framework. (a) Real-world forest testing. (b-d) Visualization of the extracted environment skeleton, safe flight corridor (spheres), and the final optimized trajectory.

The proposed Mapless-Planner bridges this gap by performing environment abstraction directly on unfused sensor data. This allows the system to maintain the structural understanding of a map-based planner with the low latency of a reactive method.

Methodology

The framework consists of three primary components designed for efficient abstraction and trajectory generation.

PicoMap: Reliable Proximity Queries

PicoMap is an evolution of the "NanoMap" concept, storing a sliding window of historical sensor frames as a list of k-d trees. A key innovation is the redesigned query algorithm that accounts for sensor field-of-view (FOV) boundaries. By calculating the distance to the FOV edge ($d_{edge}$), the system avoids overestimating safety in "blind spots" where obstacles might exist just outside the current view.

Forward Spanning Tree (FST)

The FST serves as the "brain" of the environment abstraction. The system samples points in free space and constructs a tree structure. Each node is scored based on its proximity to obstacles and its alignment with the global goal.

The Forward Spanning Tree (FST) process. Points are sampled and scored (0 to 1) to identify the most promising 'skeleton' for navigation through obstacles.

By pruning branches that lead to dead ends or high-risk areas, the FST extracts a "skeleton" of the navigable space. This skeleton provides the long-range foresight necessary for aggressive flight in dense environments.

Smart Waypoint Selection

Once a safe path is identified within a Safe Flight Corridor (SFC)—a sequence of overlapping spheres—the planner generates a smooth trajectory. Rather than using heavy optimization, it employs a heuristic waypoint selection strategy inspired by the Douglas-Peucker algorithm. It recursively identifies points where a straight-line path would violate the SFC and inserts waypoints to "nudge" the trajectory back into safety, ensuring high-speed feasibility.

Experimental Results

The framework was validated in both simulation and real-world environments:

  • Simulation: In high-density environments with up to 300 obstacles, Mapless-Planner achieved a 90-96% success rate, whereas reactive methods like RAPPIDS dropped to 22%. It also reached goals 19% faster than NanoMap-based systems by planning through narrower gaps.
  • Real-World: A quadrotor equipped with a depth camera successfully navigated a dense natural forest at speeds of 3m/s, demonstrating robustness to sensor noise and complex natural structures.
  • Efficiency: The entire planning pipeline (abstraction to trajectory generation) takes only 4.5ms on a standard i7 CPU.

Conclusion

Mapless-Planner demonstrates that robust, high-speed autonomous flight does not require the overhead of global map fusion. By extracting structural skeletons from raw sensor data and utilizing smart waypoint heuristics, the system achieves superior performance in dense, unknown environments. Future work will focus on adapting the system for platforms with coarse localization.

Summary updated

Abstract

Maintaining a map online is resource-consuming while a robust navigation system usually needs environment abstraction via a well-fused map. In this paper, we propose a mapless planner which directly conducts such abstraction on the unfused sensor data. A limited-memory data structure with a reliable proximity query algorithm is proposed for maintaining raw historical information. A sampling-based scheme is designed to extract the free-space skeleton. A smart waypoint selection strategy enables to generate high-quality trajectories within the resultant flight corridors. Our planner differs from other mapless ones in that it can abstract and exploit the environment information efficiently. The online replan consistency and success rate are both significantly improved against conventional mapless methods.
BibTeX
@inproceedings{ji2021mapless,
  author = {Jialin Ji and Zhepei Wang and Yingjian Wang and Chao Xu and Fei Gao},
  title = {{Mapless-Planner: A Robust and Fast Planning Framework for Aggressive Autonomous Flight without Map Fusion}},
  booktitle = {IEEE International Conference on Robotics and Automation},
  year = {2021},
  url = {https://openreview.net/forum?id=6f0Qid9fdm},
}
Figure