title: Auction-based coordination for task allocation in Drone teams
title: Συντονισμός με εικονικές δημοπρασίες για ανάθεση εργασιών σε ομάδες από Drones
Creators: name: Βασταρδης Γεωργιος
Publisher: name: Technical University of Crete
Year: 2019

description: In our days, natural disasters occur on a daily basis and typically require immediate human rescue team intervention, in order to minimize casualties. In most cases, the scene conditions may be prohibitive for human rescuers to intervene and the rescue mission may be delayed, possibly with serious consequences. Such scenarios are ideal for deploying autonomous mobile robot systems, which may provide assistance to the human rescuers by autonomously searching for threatened individuals and, in general, by providing information about the current situation. In this thesis, we present the use of a multi-drone team as a support tool to search-and-rescue missions. Using drones can potentially help to reduce the search time, because they can provide useful information from various locations through their sensors. Particularly, we focus on the optimization of the task allocation problem among the drone team members by using a distributed sequential auction method. The (simulated) auction has low computation and communication requirements, is purely decentralized, and eliminates the need for a centralized auctioneer. A number of tasks (target locations) that the drones must visit for the purpose of acquiring information is communicated to all drones at the start of the process. Then, the drones localize themselves in the environment and they initiate the auction mechanism for negotiating the targets, one at a time. Within the auction, we implemented and tested different objectives for the calculation of bids, which serve a variety of team goals in different missions this project may be used on. At the end of the auction, the drones have allocated all tasks among themselves and they proceed to visiting each one of the won tasks in the already determined order. A simple, collision-free navigation method ensures that the drones will not collide during path following. The entire project has been implemented within the Robot Operating System (ROS) and is available as an open source package. All experiments were conducted on the Gazebo robot simulator in obstacle-free environments to demonstrate the results of the proposed approach on smaller and larger problems with as many as 20 drones and 50 tasks. The main advantage of the proposed scheme is the ability to run in a fully-distributed manner over a team of inter-connected drones, or other mobile robots in general, and to provide an efficient approach for task allocation, a key problem in search-and-rescue missions.
description: Στις μέρες μας, συμβαίνουν φυσικές καταστροφές σε καθημερινή βάση και συνήθως απαιτείται άμεση ανθρώπινη επέμβαση ομάδων διάσωσης, ώστε να μειωθούν οι ανθρώπινες απώλειες. Στις περισσότερες περιπτώσεις, οι συνθήκες στο χώρο του συμβάντος ενδέχεται να είναι απαγορευτικές για την παρέμβαση των διασωστών και η αποστολή διάσωσης μπορεί να καθυστερήσει, ενδεχομένως με σοβαρές συνέπειες. Τέτοια σενάρια είναι ιδανικά για χρήση αυτόνομων κινητών ρομποτικών συστημάτων, τα οποία μπορούν να παρέχουν βοήθεια στους διασώστες με αυτόνομη αναζήτηση απειλούμενων ατόμων και γενικότερα με την παροχή πληροφοριών σχετικά με την τρέχουσα κατάσταση. Στην παρούσα διπλωματική εργασία, παρουσιάζουμε τη χρήση μιας ομάδας από drones ως εργαλείο υποστήριξης σε αποστολές αναζήτησης και διάσωσης. Με τη χρήση drones έχουμε μείωση του χρόνου έρευνας σε αυτές τις αποστολές, καθώς μπορούν να παρέχουν χρήσιμες πληροφορίες από διάφορες τοποθεσίες μέσω των αισθητήρων τους. Ιδιαίτερα, επικεντρωνόμαστε στη βελτιστοποίηση του προβλήματος ανάθεσης καθηκόντων μεταξύ των μελών της ομάδας, χρησιμοποιώντας μια κατανεμημένη μέθοδο ακολουθιακής δημοπρασίας. Η (εικονική) δημοπρασία έχει χαμηλές απαιτήσεις υπολογιστικής ισχύος και επικοινωνίας, είναι πλήρως κατανεμημένη και εξαλείφει την ανάγκη ενός κεντρικού δημοπράτη. Κατά την έναρξη της διαδικασίας, ένας αριθμός καθηκόντων (τοποθεσίες στόχων), που πρέπει να επισκεφθούν τα drones για την απόκτηση πληροφοριών, διαβιβάζεται σε όλα τα μέλη της ομάδας. Στη συνέχεια, τα drones εντοπίζουν τη θέση τους στο περιβάλλον και ξεκινούν τον μηχανισμό δημοπράτησης για το διαμοιρασμό των στόχων, έναν σε κάθε γύρο δημοπρασίας. Στο πλαίσιο της δημοπρασίας, υλοποιήσαμε και δοκιμάσαμε διαφορετικά αντικειμενικά κριτήρια για τον υπολογισμό των προσφορών, τα οποία εξυπηρετούν ποικίλους στόχους σε διαφορετικές αποστολές, όπου η παρούσα εργασία μπορεί να χρησιμοποιηθεί. Στο τέλος της δημοπρασίας, τα drones έχουν κατανείμει όλα τα καθήκοντα μεταξύ τους και προχωρούν στην επίσκεψη κάθε ενός από τα ανατεθέντα καθήκοντα με την σειρά που έχει ήδη οριστεί. Μια απλή μέθοδος πλοήγησης με αποφυγή συγκρούσεων διασφαλίζει ότι τα drones δεν θα συγκρουστούν κατά τη διάρκεια της διαδρομής που θα ακολουθήσουν. Η εργασία στο σύνολό της έχει υλοποιηθεί στο πλαίσιο του Robot Operating System (ROS) και διατίθεται ως πακέτο ανοιχτού κώδικα. Όλα τα πειράματα διεξήχθησαν στον προσομοιωτή ρομπότ Gazebo, μέσα σε ένα περιβάλλον χωρίς εμπόδια, για να επιδειχθούν τα αποτελέσματα της προτεινόμενης προσέγγισης τόσο σε μικρότερα όσο και σε μεγαλύτερα προβλήματα (20 drones, 50 tasks). Το κύριο πλεονέκτημα της προτεινόμενης μεθόδου είναι η ικανότητα να εκτελείται με πλήρως κατανεμημένο τρόπο σε μια ομάδα διασυνδεδεμένων drones ή γενικότερα άλλων κινητών ρομπότ και να παρέχει μια αποδοτική προσέγγιση για ανάθεση καθηκόντων, ένα βασικό πρόβλημα στις αποστολές έρευνας και διάσωσης.