The Collision-less Conjecture for the Go-To-The-Gabriel-Center (GTGC) algorithm

Abstract

Στην παρούσα διπλωματική εργασία, μελετήθηκαν και παρουσιάστηκαν διάφοροι αλγόριθμοι συγκέντρωσης (gathering algorithms) που υπάρχουν στη βιβλιογραφία. Οι αλγόριθμοι συγκέντρωσης έχουν σαν στόχο τη συλλογή ενός αυθαίρετου n αριθμού από ρομπότ που υπάρχουν στο ευκλείδειο επίπεδο σε ένα μη προκαθορισμένο σημείο. Συγκεκριμένα, δόθηκε περισσότερη έμφαση σε αλγορίθμους συνεχούς χρόνου που ακολουθούν το μοντέλο Look - Compute - Move. Δηλαδή, τον εντοπισμό των γειτόνων τους από το κοντινό τους περιβάλλον, τον υπολογισμό του σημείου προορισμού τους και τέλος, την κίνηση τους προς το σημείο προορισμού τους. Από αυτούς τους αλγόριθμους, ξεχώρισε ο Go-To-The-Gabriel-Center (GTGC) αλγόριθμος, ο οποίος αποδείχθηκε ότι είναι collision-less στη μια διάσταση του ευκλείδειου επιπέδου και εικάζεται ότι είναι collision-less και στις δύο διαστάσεις. Κάτι το οποίο δεν αποδείχθηκε, παρά μόνο πάρθηκε το συμπέρασμα βάση προσομοιώσεων. Σε αυτή την διπλωματική εργασία, ο κυριότερος στόχος ήταν να γίνει μια προσπάθεια να αποδειχθεί αυτή η εικασία ή να καταρριφθεί. Να αποδειχθεί δηλαδή αν ο αλγόριθμος Go-To-The-Gabriel-Center (GTGC) είναι collision-less ή όχι. Αρχικά, αναλύθηκαν όλες οι πιθανές καταστάσεις που μπορεί να βρεθεί ένα ρομπότ και έγιναν κάποιες προσομοιώσεις βάση αυτών των καταστάσεων. Χρησιμοποιώντας τις προσομοιώσεις, τον τρόπο εκτέλεσης του αλγορίθμου και θεωρήματα από τη βιβλιογραφία, έγινε μια προσπάθεια να ληφθούν κάποια συμπεράσματα για το κατά πόσο μπορούν να υπάρξουν συγκρούσεις και υπό ποιες προϋποθέσεις. Λαμβάνοντας υπόψη τα συμπεράσματα και τις προσομοιώσεις, προσπάθησε να αποδειχθεί η εικασία με μαθηματικό τρόπο. Αφού δημιουργήθηκε ένα σύστημα ανισοτήτων με εξισώσεις που πηγάζουν από τα συμπεράσματα, ελέγχθηκε αν υπάρχουν λύσεις στο σύστημα ανισοτήτων, και αν υπάρχουν, τι συμπεράσματα μπορούν να ληφθούν. Όπως παρουσιάζεται και στη συνέχεια, ο συγκεκριμένος αλγόριθμος αποδείχθηκε ότι μπορεί να θεωρηθεί collision-less εκτός από το σενάριο όπου μπορεί να βρεθεί σε μια συγκεκριμένη κατάσταση (cross-shaped graph). Λόγω του ότι η πιθανότητα να βρεθεί σε μια τέτοια κατάσταση (cross-shaped graph) τείνει στο 0, τότε λαμβάνεται σαν γενικό συμπέρασμα ότι ο αλγόριθμος Go-To-The-Gabriel-Center (GTGC) είναι collision-less (Lebesgue measure).

In this thesis, various gathering algorithms that exist in the literature were studied and presented. Gathering algorithms aim to gather an arbitrary number of n robots that exist in the Euclidean plane at a non predefined point. In particular, more emphasis was placed on continuous-time algorithms that follow the Look - Compute - Move model. That is, the detection of their neighbors from their immediate environment, the calculation of their target point and finally, their movement towards their target point. Among these algorithms, the Go-To-The-Gabriel-Center (GTGC) algorithm stood out, which was shown to be collision-less in one dimension of the Euclidean plane and conjectured to be collision-less in both dimensions. Something that was not proven, but was only concluded based on simulations. In this thesis, the main aim was to make an attempt to prove this conjecture or to demolish it. That is, to prove whether the Go-To-The-Gabriel-Center (GTGC) algorithm is collision-less or not. First, all the possible situations that a robot can find itself in, were analyzed and some simulations were made based on these situations. Using the simulations, how the algorithm is executed, and theorems from the literature, an attempt was made to draw some conclusions about whether collisions can occur and under what conditions. Taking into account the conclusions and simulations, an attempt was made to prove the conjecture in a mathematical way. After creating a system of inequalities with equations derived from the conclusions, it is checked whether there are solutions to the system of inequalities, and if there are, what conclusions can be drawn. As shown below, this particular algorithm is shown to be collision-less except for the scenario where it can be in a specific state (cross-shaped graph). Since the probability of being in such a state (cross-shaped graph) tends to 0, then it is taken as a general conclusion that the algorithm Go-To-The-Gabriel-Center (GTGC) is collision-less (Lebesgue measure).