Drone Path Planning

December 1, 2021

This was a project done as part of a coursework. The goal was to design a system that needed to account for various constraints, including the drone’s limited battery and movement, no-fly zones around buildings, and the requirement to deliver food orders one at a time.

I opted for an object-oriented approach, decomposing the system into interacting classes like Drone, FoodOrder, and DeliveryPlanner to maximize abstraction and reusability.

Illustration 1: Class diagram showcasing the system’s architecture

For pathfinding, I chose the deterministic A* algorithm over non-deterministic options due to its simplicity, speed, and guaranteed consistency. The search space was represented as a triangular mesh with equidistant nodes, allowing the drone to move between nodes in a single step while adhering to angle constraints.

Illustration 2: Diagram illustrating the grid representation and A* pathfinding

However, the generated paths often followed a zigzag pattern. To address this, I implemented a post-smoothing process – a six-layer pipeline that eliminates redundant nodes and ensures adherence to movement constraints.

Illustration 3: Before and after comparison of paths with and without smoothing

To further optimize delivery, I employed a heuristic-based order queuing system. By prioritizing orders based on their cost-to-travel-distance ratio, the system could handle denser, higher-value orders more efficiently.

A more detailed overview can be found in the report TODO