Multiple unmanned aerial vehicles motion planning and routing for optimized remote sensing operations

Abstract

In the context of this dissertation we deal with the problem of motion planning and routing for multiple unmanned aerial vehicles (UAVs) to perform effective and efficient remote sensing operations (RS). The largest part of the presented work focuses on Coverage Path Planning (CPP) and multi-agent CPP (mCPP), that is the problem of having to completely cover a designated region of interest (ROI) with one or more unmanned vehicles, while simultaneously respecting any restrictions enforced by the ROI, vehicle(s), user(s), and operational or legal frameworks. Additionally, a gap in literature for a specific type of UAV RS operations is identified, the problem of Fast Inspection of Scattered Regions (FISR) is formulated and described in detail, and a novel method to deal with it is introduced. As part of this work, a novel mCPP method tailored to real-world UAV RS operations has been introduced, that supports very complex-shaped, non-convex ROIs with additional no-fly zones (NFZs) inside them, manages operational resources like time and energy wisely, and manages to achieve almost complete coverage in all cases. To realize that, an optimization scheme based on simulated annealing has been introduced to efficiently apply grid-based path planning methodologies in real-world ROIs. Moreover, a heuristic is applied for the Spanning Tree Coverage (STC) path planning method to reduce the number of turns in the generated trajectories, and a modification to a state-of-the-art (SoA) method for area allocation is performed to support proportional area division and enable the simultaneous utilization of heterogeneous vehicles. The introduced method is extensively evaluated through a series of simulated runs and a comparison with an alternative SoA method. A multi-agent marginal utility study is performed to provide information on how and when the deployment of multiple UAVs can benefit coverage missions. Two indicative real-world scenarios regarding precision agriculture and search and rescue (SAR) operations are deployed, collecting and processing data to provide relative results. As a next step, building upon the aforementioned work, a CPP method with three ad-hoc coverage modes that intend to fulfill different objectives—each of them more appropriate for different applications, operational demands, and vehicles—is introduced. This work focuses on resolving any remaining issues when applying grid-based path planning missions to real-world operations. While the introduced heuristics are tailored to the STC method, this work can serve as a practical guide for most grid-based methods. The presented CPP solution is evaluated using the same simulation setup and benchmark ROIs as in the previous work, providing a direct comparison with it and the alternative SoA method. The evaluations indicate that all claimed benefits are achieved, while simultaneously the method manages to overcome the issues inherited from its grid-based nature. Finally, a new problem of UAV path planning for RS operations has been identified, described in detail, and resolved by introducing a novel method tailored to this purpose. The FISR problem, as stated above, is about the inspection of multiple disjoint ROIs with one or more UAVs in the shortest amount of time possible. The methodology introduced to resolve it is the multi-UAV Disjoint Areas' Inspection (mUDAI). mUDAI treats the FISR problem as two discrete optimization sub-problems: first, the optimal viewpoints for capturing each defined ROI are calculated, and second, a set of trajectories that minimize time and respect the specifications and limitations of the vehicles used is generated. The introduced method is validated via two sets of real-world UAV deployments for FISR missions. To enable easy and user-friendly deployment of UAVs for testing and evaluating the presented methodologies in real-world conditions, an end-to-end mission planning platform for RS operations has been developed. This platform, introduced in the first part of this work and updated continuously since then, includes everything needed to design, store, manage, and deploy multi-UAV missions for RS operations with commercial devices. The combination of state-of-the-art performance with increased levels of readiness and ease of use takes steps toward closing the gap between commercial platforms that use simplistic approaches but provide robust and trusted solutions for real-world operations, and research methods that introduce novel features and benefits but are usually not ready or easy to deploy in the field. Additionally, the development of solutions that allow the efficient and safe deployment of multiple UAVs working cooperatively to perform RS operations contributes to overcoming one of the major current limitations of multi-copter UAVs: their limited operational duration. In this way, the inspection of larger areas during the nominal operational duration of the vehicles is achieved, and time-critical operations and applications involving the detection of moving objects of interest are handled much more efficiently.

Στο πλαίσιο αυτής της διατριβής εξετάζεται το πρόβλημα του σχεδιασμού τροχιάς και δρομολόγησης για πολλαπλά μη επανδρωμένα εναέρια οχήματα (Unmanned Aerial Vehicles - UAVs), με στόχο την αποτελεσματική και αποδοτική εκτέλεση αποστολών τηλεπισκόπησης (Remote Sensing - RS). Το μεγαλύτερο τμήμα της παρούσας διατριβής επικεντρώνεται στο Σχεδιασμό Τροχιών Κάλυψης (Coverage Path Planning - CPP) και το Σχεδιασμό Τροχιών Κάλυψης με πολλαπλούς πράκτορες (multi-agent CPP - mCPP), δηλαδή το πρόβλημα της πλήρους κάλυψης μιας δεδομένης περιοχής ενδιαφέροντος (Region of Interest - ROI) με ένα ή περισσότερα UAVs, ενώ ταυτόχρονα τηρούνται οι περιορισμοί που μπορεί να επιβάλλονται από την περιοχή ενδιαφέροντος, τα οχήματα, τους χρήστες, καθώς επίσης και από τα επιχειρησιακά ή νομικά πλαίσια. Επιπλέον, εντοπίζεται ένα κενό στη βιβλιογραφία για έναν συγκεκριμένο τύπο επιχειρήσεων τηλεπισκόπησης με UAVs, διατυπώνεται, και περιγράφεται λεπτομερώς το πρόβλημα της Ταχείας Επιθεώρησης Διασκορπισμένων Περιοχών (Fast Inspection of Scattered Regions - FISR), και προτείνεται μια νέα μέθοδος για την αντιμετώπισή του. Αρχικά, παρουσιάζεται μια νέα μέθοδος mCPP, προσανατολισμένη σε επιχειρήσεις τηλεπισκόπησης πραγματικού κόσμου με UAVs, η οποία υποστηρίζει πολύ σύνθετες, μη-κυρτές περιοχές ενδιαφέροντος με επιπλέον ζώνες απαγόρευσης πτήσης (No-Fly-Zones - NFZs) στο εσωτερικό τους, διαχειρίζεται με σύνεση τους επιχειρησιακούς πόρους -όπως ο χρόνος και η ενέργεια- και επιτυγχάνει σχεδόν πλήρη κάλυψη σε όλες τις περιπτώσεις. Για την επίτευξη αυτού του στόχου, εισάγεται ένα σχήμα βελτιστοποίησης βασισμένο στον αλγόριθμο Simulated Annealing για την αποτελεσματική εφαρμογή αλγορίθμων σχεδιασμού τροχιάς με βάση το πλέγμα (grid-based) σε πραγματικές περιοχές ενδιαφέροντος. Επιπλέον, i) εφαρμόζεται μια ευρετική μέθοδος για τη μείωση των στροφών στις διαδρομές που παράγονται από τη μέθοδο Spanning Tree Coverage (STC), και ii) πραγματοποιείται τροποποίηση μιας μεθόδου αιχμής (state-of-the-art - SoA) για το διαμοιρασμό περιοχών σε πολλαπλά ρομπότ, ώστε να υποστηρίζεται η αναλογική διαίρεση των περιοχών και η ταυτόχρονη αξιοποίηση ετερογενών οχημάτων. Η προτεινόμενη μέθοδος αξιολογείται εκτενώς μέσω μιας σειράς προσομοιώσεων, συγκρίνεται με μια εναλλακτική μέθοδο αιχμής, ενώ πραγματοποιείται και μία μελέτη οριακής χρησιμότητας (marginal utility study) πολλαπλών πρακτόρων, για να προσδιοριστεί πότε και πώς η χρήση πολλαπλών UAVs μπορεί να είναι ωφέλιμη σε αποστολές κάλυψης περιοχών. Τέλος, εκτελούνται δύο ενδεικτικά σενάρια πραγματικού κόσμου, σχετικά με τη γεωργία ακριβείας και τις επιχειρήσεις έρευνας και διάσωσης, συλλέγονται δεδομένα, και επεξεργάζονται για την εξαγωγή και την παρουσίαση σχετικών αποτελεσμάτων. Στη συνέχεια, βασισμένη στη δουλειά που περιγράφεται στην προηγούμενη παράγραφο παρουσιάζεται μια μέθοδος CPP με τρεις διακριτές λειτουργίες κάλυψης, με την κάθε μία να εξυπηρετεί καλύτερα διαφορετικές εφαρμογές, επιχειρησιακές απαιτήσεις και τύπους οχημάτων. Αυτή η δουλειά εστιάζει στην επίλυση των εναπομεινόντων ζητημάτων που προκύπτουν κατά την εφαρμογή μεθόδων σχεδιασμού διαδρομής με βάση το πλέγμα σε επιχειρήσεις πραγματικού κόσμου. Παρόλο που οι ευρετικές μέθοδοι που παρουσιάζονται και εφαρμόζονται είναι προσαρμοσμένες στα χαρακτηριστικά της μεθόδου STC, η δουλειά αυτή μπορεί να λειτουργήσει ως πρακτικός οδηγός για την επίλυση αντίστοιχων ζητημάτων στις περισσότερες μεθόδους με πλέγμα. Η λύση CPP που παρουσιάζεται, αξιολογείται χρησιμοποιώντας την ίδια μεθοδολογία και περιοχές αναφοράς με την προηγούμενη δουλειά, παρέχοντας άμεση σύγκριση με αυτήν και την εναλλακτική μέθοδο αιχμής. Η αξιολόγηση αποδεικνύει ότι επιτυγχάνονται όλα τα υποσχόμενα οφέλη, ενώ ταυτόχρονα η μέθοδος καταφέρνει να ξεπεράσει τα προβλήματα που απορρέουν από τη βασισμένη-σε-πλέγμα φύση της. Τέλος, εντοπίζεται ένα νέο πρόβλημα σχεδιασμού διαδρομών UAVs για επιχειρήσεις τηλεπισκόπησης, το οποίο περιγράφεται λεπτομερώς και επιλύεται με την εισαγωγή μιας νέας μεθοδολογίας εστιασμένης στη βέλτιστη αντιμετώπισή του. Το πρόβλημα FISR -όπως αναφέρθηκε παραπάνω- αφορά την επίβλεψη πολλαπλών διακριτών περιοχών ενδιαφέροντος, με ένα ή περισσότερα UAVs, στο συντομότερο δυνατό χρόνο. Η μέθοδος που προτείνεται για την επίλυσή του είναι η Επιθεώρηση Διακριτών Περιοχών με Πολλαπλά UAVs (multi-UAV Disjoint Areas' Inspection - mUDAI). Η μέθοδος αυτή αντιμετωπίζει το πρόβλημα FISR ως δύο διακριτά υποπροβλήματα βελτιστοποίησης που αφορούν: i) τον υπολογισμό των βέλτιστων σημείων παρατήρησης για κάθε ορισμένη περιοχή ενδιαφέροντος και ii) τη δημιουργία διαδρομών που ελαχιστοποιούν το χρόνο και σέβονται τις προδιαγραφές και τους περιορισμούς των οχημάτων που χρησιμοποιούνται. Η προτεινόμενη μέθοδος αξιολογείται μέσω της εκτέλεσης δύο ομάδων αποστολών τηλεπισκόπησης για αποστολές FISR διαφορετικής κλίμακας, σε διαφορετικές τοποθεσίες. Για την εύκολη εκτέλεση αποστολών με UAVs, και τη δοκιμή και αξιολόγηση των προτεινόμενων μεθοδολογιών σε πραγματικές συνθήκες, αναπτύχθηκε μια ολοκληρωμένη πλατφόρμα σχεδιασμού και εκτέλεσης αποστολών τηλεπισκόπησης. Αυτή η πλατφόρμα αναπτύχθηκε και παρουσιάστηκε κατά την πρώτη δουλειά αυτής της διατριβής και ενημερώνεται διαρκώς έκτοτε. Σε αυτήν περιλαμβάνονται όλα τα απαραίτητα στοιχεία για το σχεδιασμό, την αποθήκευση, τη διαχείριση και την εκτέλεση αποστολών με πολλαπλά UAVs για επιχειρήσεις τηλεπισκόπησης με εμπορικές συσκευές. Ο συνδυασμός χαρακτηριστικών αιχμής -όσον αφορά την αποτελεσματικότητα και αποδοτικότητα των αποστολών- με τα αυξημένα επίπεδα ετοιμότητας και ευχρηστίας, αποτελεί ένα βήμα προς την κάλυψη του κενού μεταξύ εμπορικών εφαρμογών που χρησιμοποιούν απλοϊκές προσεγγίσεις σχεδιασμού τροχιάς, αλλά παρέχουν αξιόπιστες λύσεις για πραγματικές επιχειρήσεις, και των μεθόδων της βιβλιογραφίας που εισάγουν καινοτόμα χαρακτηριστικά και οφέλη, αλλά συνήθως δεν είναι αρκετά ώριμες ή εύκολες για χρήση στον πραγματικό κόσμο. Επιπλέον, η ανάπτυξη λύσεων που επιτρέπουν την αποδοτική και ασφαλή χρήση πολλαπλών UAVs για την εκτέλεση αποστολών τηλεπισκόπησης, συμβάλλει στην υπέρβαση ενός από τους σημαντικότερους -αυτή τη στιγμή- περιορισμούς των εμπορικών UAVs, δηλαδή τη μικρή διάρκεια πτήσης τους. Με αυτόν τον τρόπο, καθίσταται εφικτή η σάρωση μεγαλύτερων περιοχών ενδιαφέροντος κατά τη διάρκεια της ονομαστικής επιχειρησιακής διάρκειας των οχημάτων, ενώ επίσης οι χρονικά κρίσιμες επιχειρήσεις, και οι εφαρμογές που περιλαμβάνουν τον εντοπισμό κινούμενων αντικειμένων ενδιαφέροντος, διαχειρίζονται πολύ πιο αποτελεσματικά.