Αναζήτηση εξόδου σε κύκλο υπό την παρουσία faulty robot

Abstract

Η αναζήτηση αποτελεί κύριο μέρος της καθημερινότητας των ανθρώπων. Για αυτό το λόγο προβλήματα αναζήτησης αποτελούν σημαντική ερευνητική περιοχή της επιστήμης των υπολογιστών. Στην παρούσα διπλωματική εργασία θα ασχοληθούμε με τη μελέτη ενός τέτοιου προβλήματος. Συγκεκριμένα προτείνουμε λύσεις για το το πρόβλημα αναζήτησης εξόδου, η οποία βρίσκεται στην περιφέρεια ενός κύκλου. Την αναζήτηση την πραγματοποιούν σημειακά ρομπότ. Αυτά έχουν ως αρχική θέση το κέντρο του κύκλου και κινούνται με ταχύτητα ίση με ένα. Επικοινωνούν μεταξύ τους ασύρματα και το μήνυμα που στέλνει το κάθε ρομπότ περιέχει την ταυτότητα του ρομπότ, η οποία δεν μπορεί να αλλαχθεί με κανένα τρόπο. Μελετάμε την περίπτωση που έχουμε n ρομπότ από τα οποία τα f είναι faulty. Το πρόβλημα θεωρούμε ότι έχει λυθεί όταν ένα non-faulty ρομπότ έχει βρει την έξοδο και τα υπόλοιπα non-faulty ξέρουν με σιγουριά την θέση της εξόδου. Τα faulty χωρίζονται σε δύο κατηγορίες, στα crash και στα Byzantine. Τα crash είναι ελαττωματικά και μπορεί να σταματήσουν να λειτουργούν οποιαδήποτε στιγμή. Τα Byzantine έχουν ως στόχο να αποπροσανατολίσουν τα υπόλοιπα ρομπότ και μεταφέρουν ψευδείς πληροφορίες για την θέση της εξόδου. Συγκεκριμένα θα μελετηθεί η περίπτωση όπου διαθέτουμε δύο Byzantine. Η κύρια συνεισφορά της εργασίας είναι η ανάπτυξη ενός αλγορίθμου που πετυχαίνει χρόνο 1+8π/n για την περίπτωση (n,2,2) και 1+2π(f-1)/n + 2sin(4π/n) για την περίπτωση (n,f,2). Πρώτα παρουσιάζουμε μια αναλυτική περιγραφή του αλγορίθμου και αποδεικνύουμε την ορθότητα και τα άνω φράγματα στον χρόνο εκτέλεσης. Στη συνέχεια παρουσιάζονται διάφορα παραδείγματα που δείχνουν την δυσκολία στην ύπαρξη αλγορίθμου που επιλύει το ίδιο πρόβλημα σε λιγότερο χρόνο. Στο τέλος γίνεται μία εισαγωγή στην επίλυση της περίπτωσης (n,f,f), που βρίσκεται υπό ολοκλήρωση αυτή την περίοδο. Ο χρόνος που έχουμε καταλήξει είναι 1+2f2π/n για f≤6, 1+2+(f+2)2π/n για f≤16 και 1+2+(f+3)2π/n για τις υπόλοιπες περιπτώσεις.