Πολυπλεξία Τροχιών Κινούμενων Αντικειμένων

Abstract

Σκοπός της διπλωματικής εργασίας είναι η σχεδίαση και η υλοποίηση ενός αλγορίθμου που παρακολουθεί την κίνηση αντικειμένων στο χώρο σε πραγματικό χρόνο και εντοπίζει ανάμεσά τους ομάδες αντικειμένων με κοινή τροχιά. Για κάθε τέτοια ομάδα, ο αλγόριθμος επιστρέφει μία κατασκευασμένη τροχιά ως αποτέλεσμα της πολυπλεξίας των επιμέρους τροχιών των αντικειμένων.Οι πληροφορίες για την κίνηση των αντικειμένων φτάνουν στο σύστημα με τη μορφή ρεύματος δεδομένων. Τα κινούμενα αντικείμενα θεωρούνται σημειακά και η θέση τους μεταβάλλεται δυναμικά. Κάθε αντικείμενο αποστέλλει ανά τακτά χρονικά διαστήματα την ανανεωμένη θέση του σε ένα κεντρικό επεξεργαστή ο οποίος εκτελεί τον αλγόριθμο πολυπλεξίας.Ο αλγόριθμος δουλεύει επαναληπτικά. Κάθε κύκλος εκτέλεσης περιλαμβάνει πέντε διεργασίες. Αρχικά, υπολογίζει την κατεύθυνση που ακολούθησε κάθε αντικείμενο σε σχέση με την θέση του κατά τον προηγούμενο κύκλο (εξομάλυνση κίνησης). Στη συνέχεια, η κατεύθυνση αυτή κωδικοποιείται και συνδυάζεται με προηγούμενες κωδικοποιήσεις για την δημιουργία μιας συμβολικής αναπαράστης της πρόσφατης κίνησης του κάθε αντικειμένου (προσέγγιση πορείας). Κάνοντας χρήση των συμβολικών αναπαραστάσεων, ο αλγόριθμος εντοπίζει αντικείμενα που είχαν παράλληλη κίνηση στο πρόσφατο παρελθόν (ομαδοποίηση). Στο επόμενο βήμα, εντοπίζονται ομάδες αντικειμένων που εκτός από παράλληλη κίνηση είχαν όντως κοινή τροχιά (εύρεση αντικειμένων με κοινές τροχιές). Τέλος, υπολογίζεται η πολυπλεγμένη τροχιά για κάθε ομάδα, ώστε να προσεγγίζει τις τροχιές που εμπίπτουν σε αυτήν με όσο το δυνατόν καλύτερο τρόπο (πολυπλεξία τροχιών).Ο αλγόριθμος δοκιμάστηκε σε συνθετικά δεδομένα που προσομοίωναν την κίνηση 10000 αυτοκινήτων στο οδικό δίκτυο της Αθήνας. Τα αποτελέσματα ήταν πολύ ενθαρρυντικά, αφού οι χρόνοι εκτέλεσης που επιτεύχθηκαν για τον εντοπισμό πολυπλεγμένων τροχιών ήταν της τάξεως μερικών δευτερολέπτων. Η πολυπλεγμένη τροχιά προσεγγίζει με ικανοποιητική πιστότητα τις επιμέρους κινήσεις των αντικειμένων και το σφάλμα δεν υπερβαίνει τα όρια ανοχής που τίθενται από τον χρήστη.Τα αποτελέσματα δείχνουν πώς ο αλγόριθμος αυτός θα μπορούσε να χρησιμοποιηθεί με επιτυχία για τον εντοπισμό πομπών αντικειμένων σε διάφορα πεδία εφαρμογής (οχήματα, πλοία, πανίδα κ.α), καθώς επίσης και για τον εντοπισμό αντικειμένων που κινούνται μαζικά προς την ίδια κατεύθυνση σε διάταξη μετώπου.