Efficient Lazy Theta* Path Planning over a Sparse Grid to Explore Large 3D Volumes with a Multirotor UAV

Area of Science:

• Robotics
• Artificial Intelligence
• Autonomous Systems

Background:

• Unmanned Aerial Vehicles (UAVs) are crucial for inspecting large structures but face challenges in unknown, unstructured environments.
• Real-time path planning for UAVs in 3D scenarios is computationally intensive, especially with safety distance constraints.
• Existing algorithms struggle with the high number of obstacle detection queries in dynamic, unknown environments.

Purpose of the Study:

• To adapt the Lazy Theta* path-planning algorithm for efficient, real-time outdoor navigation of UAVs in large, unknown 3D environments.
• To address the computational bottleneck caused by safety distance requirements in obstacle detection.
• To improve the performance and scalability of UAV path planning.

Main Methods:

• Revisiting and adapting the Lazy Theta* path-planning algorithm for real-time outdoor applications.
• Reducing problem dimensionality by leveraging geometrical properties to accelerate computations.
• Implementing a non-regular grid representation (octree) for efficient spatial organization and merging of environmental data.
• Optimizing neighbor search within the sparse octree structure to minimize obstacle detection queries.
• Utilizing Test-Driven Development (TDD) methodology for algorithm development.

Main Results:

• Achieved over a 90% reduction in overall path generation computation time.
• Demonstrated effective real-time path planning capabilities in outdoor flights with a multirotor UAV.
• Validated that the approach scales well with increasing safety distance requirements.
• Confirmed the efficiency of the octree-based spatial representation and reduced neighbor queries.

Conclusions:

• The adapted Lazy Theta* algorithm offers a significant performance improvement for UAV path planning in large, unknown 3D environments.
• The use of geometrical properties and an octree-based grid representation effectively tackles computational bottlenecks.
• This enhanced path-planning approach enables safer, more efficient real-time navigation and inspection by UAVs, even with larger safety margins.