Enhancing the efficiency of multi-drone missions through strategic deployment and path planning optimizations

Abstract

Autonomous Unmanned Aerial Vehicle (UAV) operations—commonly referred to as drones—face critical challenges in energy efficiency and operational range due to power constraints. This thesis addresses some of these limitations through innovative path planning optimization approaches that minimize flight distances to enhance operational effectiveness. The research develops, validates, and integrates three complementary optimization methodologies that collectively advance both theoretical understanding and practical capability in drone deployment strategies. Initially, focus is applied on the positioning of the start and ending point of the path (provided it's acceptable to customize these) utilizing a decomposition methodology for multi-drone path planning through geometric optimization of launch pad positioning. By analyzing individual path components rather than treating flight distance as indivisible, this research develops new performance metrics to quantify launch pad positioning effects on mission’s efficiency. The proposed Geometric Median approach consistently demonstrates superior performance, achieving distance improvements between 4% and 25% across diverse operational configurations while maintaining computational efficiency with sub-second execution times. Extensive experimental validation encompassing approximately 1,320,000 tests across 130,000 unique scenarios supports robust performance characteristics. Then, the trade-off between the accuracy of identifying the positioning of the launch pad for multi-drone deployment and the computational requirements to reach an optimal, or suboptimal, but still acceptable solution, is addressed. Accordingly, the proposed methodology advances launch pad positioning into a continuous coordinate space through metaheuristic optimization, formulating the problem as a Planar Location Routing Problem. The genetic algorithm implementation devised achieves 97-100\% accuracy, compared to exhaustive search methods, while reducing computational requirements by up to four orders of magnitude. Smart initialization strategies and adaptive termination criteria, also proposed herein, further enhance convergence characteristics while maintaining solutions’ quality. Given the aforementioned promising results, the research aims at specializing on the path planning approaches, by focusing on the challenge of efficient path planning while path points present interactivity requirements, such as the data collection from Wireless Sensor Networks by use of drone aggregators through a hierarchical two-phase optimization framework. The proposed Integer Linear Programming approach provides mathematical optimality guarantees for strategic access point placement, achieving 38% mission time reduction compared to baseline no-clustering approaches in large deployments. Combined with Multiple Traveling Salesmen Problem formulations for coordinated routing, this hybrid approach achieves travel distance reductions up to 32% compared to direct sensor visitation methods. A comprehensive quality assessment framework is also proposed in order to evaluate the operational effectiveness across multiple performance dimensions. Collectively, these methodologies provide mission planners with validated frameworks and practical guidelines for improving operational efficiency across a plethora of applications in domains such as precision agriculture, environmental monitoring, infrastructure assessment, and emergency response coordination, to name but a few. The demonstrated distance reductions translate into significant energy savings, extended operational capabilities, and reduced environmental impact when scaled across the expanding global drone fleet.

Η παρούσα διδακτορική διατριβή αντιμετωπίζει κρίσιμες προκλήσεις στην ενεργειακή απόδοση και το επιχειρησιακό εύρος αυτόνομων αποστολών UAV μέσω τριών συμπληρωματικών μεθοδολογιών βελτιστοποίησης για τη συλλογή δεδομένων σε ασύρματα δίκτυα αισθητήρων (WSN). Οι προτεινόμενες προσεγγίσεις ελαχιστοποιούν τις αποστάσεις πτήσης με στόχο την ενίσχυση της επιχειρησιακής αποτελεσματικότητας και της περιβαλλοντικής βιωσιμότητας. Η πρώτη συνεισφορά εισάγει μεθοδολογία βελτιστοποίησης τοποθέτησης σημείου εκκίνησης βάσει Γεωμετρικού Διαμέσου, με νέες μετρικές απόδοσης (SPD και SPF) για την αποτίμηση της επίδρασης του σημείου εκκίνησης στην αποδοτικότητα της αποστολής. Η μέθοδος επιτυγχάνει βελτιώσεις απόστασης 4–25% σε υπολογιστικούς χρόνους κάτω του δευτερολέπτου, επικυρωμένη σε περίπου 1.320.000 δοκιμές που καλύπτουν διαμορφώσεις από 2 έως 60 drone και από 5 έως 800 σταθμούς. Η δεύτερη συνεισφορά διατυπώνει το πρόβλημα τοποθέτησης σημείου εκκίνησης στον συνεχή χώρο ως PLRP και το επιλύει με Γενετικό Αλγόριθμο, επιτυγχάνοντας ακρίβεια 97–100% έναντι εξαντλητικών μεθόδων με μείωση υπολογιστικού κόστους έως τέσσερις τάξεις μεγέθους. Στρατηγικές έξυπνης αρχικοποίησης και προσαρμοστικά κριτήρια τερματισμού ενισχύουν περαιτέρω την αποδοτικότητα, μειώνοντας την υπολογιστική προσπάθεια κατά ~94% με διατήρηση ποιότητας λύσης 98,8%. Η τρίτη συνεισφορά προτείνει υβριδικό πλαίσιο ILP-mTSP για στρατηγική τοποθέτηση σημείων πρόσβασης και συντονισμένη δρομολόγηση drone, υπερέχοντας έναντι έξι καθιερωμένων αλγορίθμων ομαδοποίησης και επιτυγχάνοντας μείωση απόστασης διαδρομής έως 32% σε σχέση με άμεση επίσκεψη αισθητήρων. Ένα ολοκληρωμένο πλαίσιο αξιολόγησης ποιότητας, που ενσωματώνει μετρικές μέσης ποιότητας, χειρότερης απόδοσης, συνέπειας και αξιοπιστίας, επιτρέπει τη συστηματική σύγκριση εναλλακτικών στρατηγικών ανάπτυξης. Οι τρεις μέθοδοι ενοποιούνται σε διαδοχική αρχιτεκτονική που αξιοποιεί τα δυνατά σημεία κάθε προσέγγισης στην κατάλληλη φάση βελτιστοποίησης. Από μεθοδολογική άποψη, η έρευνα καταδεικνύει πώς θεμελιώδεις μαθηματικές αρχές—γεωμετρικές διάμεσοι, εξελικτική υπολογιστική και ακέραιος προγραμματισμός—μπορούν να εφαρμοστούν αποτελεσματικά σε πολύπλοκες προκλήσεις σχεδιασμού διαδρομής, παρέχοντας στους σχεδιαστές αποστολών επικυρωμένα πλαίσια για βελτίωση της επιχειρησιακής απόδοσης σε ευρέα σενάρια ανάπτυξης drone.