Experiments in Adaptive Replanning for Fast Autonomous Flight in Forests

Xu Liu, Laura Jarin-Lipschitz, Xu Liu 0007, Yuezhan Tao, Vijay Kumar

TL;DR

This paper introduces an adaptive search-based motion planning framework that dynamically adjusts its graph sampling density to enable fast, autonomous flight in complex forest environments. By intelligently trading off planning time and optimality, the system achieves robust navigation in varying terrain densities, outperforming traditional planners.

What Problem Does This Paper Address?

Flying fast and autonomously through cluttered environments like forests presents a significant challenge for robots. Traditional motion planning algorithms struggle with this because dense obstacles require very detailed maps (large graphs) to ensure a robot can find a safe path, but these large graphs dramatically slow down the planning process. This creates a dilemma: to be safe in dense areas, you need a slow planner, and to be fast, you often have to sacrifice safety or the ability to navigate complex terrain. This paper tackles this by developing a planning system that can adapt its planning strategy in real-time to match the local environment's complexity, allowing for faster flight in sparser areas and safer, albeit slower, flight in denser areas, all while staying within computational limits.

Methods

The core of the proposed solution is an adaptive, minimum-dispersion search-based motion planning algorithm. This approach builds upon existing search-based planning techniques that use graphs to represent possible robot states and transitions. The novelty lies in how the planning graph is constructed and adapted:

  • Minimum Dispersion Graphs: The paper utilizes a concept called "dispersion" to define the quality of the planning graph. Dispersion quantifies how well the graph vertices cover the state space relative to the cost of traversing between states. A lower dispersion means the graph is more "complete" for a given size, ensuring that optimal plans are more likely to be found.
  • Adaptive Dispersion: Instead of using a fixed dispersion for the entire mission, the planner dynamically adjusts this parameter online. This adaptation is triggered by three key events:
  • Planner Violates Time Constraint: If the planner takes too long to find a path, the dispersion is increased. This leads to a sparser graph with fewer vertices and edges, making the search faster, even if it means a slightly less optimal plan.
  • Planner Fails to Find a Plan: If the planner exhausts all possibilities and cannot find a path (potentially due to missing narrow corridors), the dispersion is decreased. This results in a denser graph, increasing the chances of finding a path in complex areas.
  • Planner Performing Well with Large Time Margin: If the planner is consistently fast and well within its time budget, the dispersion is decreased to compute more optimal and potentially faster trajectories.
  • Search-Based Planning: The underlying planning mechanism uses graph search algorithms like Dijkstra's or A* on these dynamically generated graphs.

Datasets

The paper uses simulated environments customized based on real-world tree position data obtained from previous work [10]. They also conducted real-world experiments in the Wharton State Forest, NJ, USA, which features a natural variance in tree density. No new datasets were introduced; rather, existing environments were used to test the adaptive capabilities.

Key Insights and Ideas

  • Dispersion as a Tunable Parameter: The paper highlights that "dispersion" is a single, powerful parameter that effectively controls the trade-off between planning computation time and the optimality/completeness of the generated plan.
  • Real-time Adaptation is Crucial: The ability to adapt the planning strategy in real-time based on environmental feedback (e.g., planning time) is key to achieving robust and fast autonomous flight in dynamic and varied environments.
  • Forests as a Challenging Testbed: Forests, with their varying and often dense clutter, serve as an excellent, realistic environment to demonstrate the effectiveness of adaptive planning strategies.
  • Beyond Uniform Sampling: The work moves beyond traditional, arbitrary uniform or random sampling in motion planning by using a principled metric (dispersion) to guide graph construction, leading to more efficient and effective planning.

Key Results

  • Simulated Experiments: The adaptive planner demonstrated improved performance compared to a traditional uniform input sampling motion primitive planner. In simulations, the proposed planner approached the goal much faster and successfully reached it, while the benchmark planner struggled and ultimately failed in dense areas.
  • Real-world Experiments: The system achieved autonomous flight speeds of up to 2.5 m/s in cluttered pine forests. The adaptive planner successfully navigated through areas of varying density, adjusting its dispersion to maintain flight within the time budget. For instance, it increased dispersion when encountering dense undergrowth and decreased it when flying in sparser areas.
  • Outperforming Baselines: The adaptive planner showed superior performance in environments with varying clutter compared to non-adaptive planners, which would likely time out and fail in similar situations.

Limitations and Future Work

  • 2D vs. 3D Planning: For real-world experiments, the paper used graphs in a 2D configuration space due to computational limitations of the platform. The authors suggest that extending this to 3D planning would increase mission success in complex environments.
  • "S" Path in Uncluttered Environments: A current limitation is that even in completely uncluttered environments, the robot rarely flies perfectly straight, often following an "S" path. This is attributed to the quasirandomness in vertex selection.
  • Theoretical Guarantees: The authors aim to theoretically prove that the minimum dispersion graph is nearly as sparse as possible for a given dispersion and that the updated dispersion definition maintains completeness properties.
  • Integration with Semantic Mapping: Future work includes integrating semantic mapping capabilities to improve localization and obstacle detection, further enhancing planner performance for faster and safer flight.
  • State Constraint Reduction: If planning becomes too difficult, a potential future extension is to reduce state constraints (e.g., max velocity) to artificially decrease dispersion and computational load.

Summary updated

Abstract

Fast, autonomous flight in unstructured, cluttered environments such as forests is challenging because it requires the robot to compute new plans in realtime on a computationally-constrained platform. In this paper, we enable this capability with a search-based planning framework that adapts sampling density in realtime to find dynamically-feasible plans while remaining computationally tractable. A paramount challenge in search-based planning is that dense obstacles both necessitate large graphs (to guarantee completeness) and reduce the efficiency of graph search (as heuristics become less accurate). To address this, we develop a planning framework with two parts: one that maximizes planner completeness for a given graph size, and a second that dynamically maximizes graph size subject to computational constraints. This framework is enabled by motion planning graphs that are defined by a single parameter, dispersion, which quantifies the maximum trajectory cost to reach an arbitrary state from the graph. We show through real and simulated experiments how the dispersion can be adapted to different environments in realtime, allowing operation in environments with varying density. The simulated experiment demonstrates improved performance over a baseline search-based planning algorithm. We also demonstrate flight speeds of up to 2.5m/s in real-world cluttered pine forests.
BibTeX
@inproceedings{liu2022experiments,
  author = {Xu Liu and Laura Jarin-Lipschitz and Xu Liu and Yuezhan Tao and Vijay Kumar},
  title = {{Experiments in Adaptive Replanning for Fast Autonomous Flight in Forests}},
  booktitle = {IEEE International Conference on Robotics and Automation},
  year = {2022},
  doi = {10.1109/icra46639.2022.9812235},
}

Loading related content...

Figure