Επίλυση Προβλημάτων Ανάθεσης Μετρήσεων Και Ιχνών Στο Ν-διάστατο Χώρο Για Παρακολούθηση Κινουμένων Αντικειμένων

Abstract

Η ιχνηλασία πολλαπλών στόχων σε ένα περιβάλλον ενός ή πολλαπλών αισθητήρων είναι υψίστης σημασίας για πολλές εφαρμογές, ιατρική απεικόνιση, συστήματα ιχνηλασίας και γεωεπιστήμες. Τμήμα του αλγορίθμου ιχνηλασίας αποτελεί και το πρόβλημα της σύνδεσης δεδομένων, το οποίο είναι το αντικείμενο αυτής της διπλωματικής εργασίας. Κατά την θεωρητική παρουσίαση των βασικότερων μεθόδων σύνδεσης δεδομένων δόθηκε ιδιαίτερη έμφαση στους αλγορίθμους ανάθεσης, μέσω των οποίων η σύνδεση δεδομένων παρουσιάζεται ως ένα πρόβλημα βελτιστοποίησης με περιορισμούς. Οι αλγόριθμοι ανάθεσης που υλοποιήθηκαν είναι ο αλγόριθμος JVC για το αντίστοιχο διδιάστατο πρόβλημα και η τεχνική χαλάρωσης του Lagrange για το Ν-διάστατο πρόβλημα της ανάθεσης. Ο αλγόριθμος JVC συγκρίθηκε ως προς τον χρόνο εκτέλεσης με τον αλγόριθμο του πλειστηριασμού, καταλήγοντας στο συμπέρασμα ότι ο JVC έχει μικρότερο χρόνο εκτέλεσης για πυκνές μήτρες ανάθεσης. Αντίθετα ο αλγόριθμος του πλειστηριασμού ανταποκρίνεται καλύτερα στην περίπτωση αραιών μητρών ανάθεσης. Η συμπληρωματική αυτή ιδιότητα των δύο αλγορίθμων είναι ιδιαίτερα σημαντική, καθώς η εναλλαγή μεταξύ των δύο αλγορίθμων ανάθεσης για προβλήματα πυκνών ή αραιών μητρών αντίστοιχα θα έδινε πιο αοτελεσματικές λύσεις στο πρόβλημα σύνδεσης δεδομένων ιδιαίτερα σε δυναμικά περιβάλλοντα. Η τεχνική χαλάρωσης του Lagrange εφαρμόστηκε στα ακόλουθα τρία συστήματα ιχνηλασίας:a) σε σύστημα ιχνηλασίας κεντρικού επιπέδου 2 αισθητήρωνb) σε σύστημα ιχνηλασίας επιπέδου αισθητήρα 3 αισθητήρωνc) σε σύστημα ιχνηλασίας κεντρικού επιπέδου 3 αισθητήρωνΣτις δύο πρώτες περιπτώσεις εφαρμόστηκε η τεχνική χαλάρωσης του Lagrange για ένα τρισδιάστατο πρόβλημα ανάθεσης, ενώ στην τρίτη περίπτωση για ένα τετραδιάστατο πρόβλημα ανάθεσης. Θα πρέπει βέβαια να διευκρινιστεί ότι στην πρώτη και τρίτη περίπτωση το πρόβλημα της σύνδεσης δεδομένων αφορούσε την συσχέτιση μετρήσεων με ίχνη. Αντίθετα στην δεύτερη περίπτωση η σύνδεση δεδομένων αφορούσε την συσχέτιση ιχνών από διαφορετικούς αισθητήρες.Και για τις τρεις προαναφερθείσες περιπτώσεις δημιουργήθηκαν διάφορα σενάρια ενός ή περισσότερων κινούμενων στόχων : ευθύγραμμος στόχος, ευθύγραμμος στόχος με ελιγμό, δύο παράλληλοι ευθύγραμμοι στόχοι, δύο παράλληλοι ευθύγραμμοι στόχοι με καθυστέρηση της εκκίνησης του ενός, δύο ευθύγραμμοι στόχοι που προσεγγίζουν μεταξύ τους, συγκρούονται και στην συνέχεια απομακρύνονται, ένας ευθύγραμμος στόχος με απώλειες παρατηρήσεων από τον ένα αισθητήρα. Παράλληλα θεωρούνταν οτι κάθε αισθητήρας ανίχνευε ένα τυχαίο πλήθος πιθανών στόχων. Για αυτά τα σενάρια εκτελέστηκαν οι αντίστοιχοι αλγόριθμοι και για τα τρία συστήματα ιχνηλασίας, όπου και διαπιστώθηκε η σωστή λειτουργία της διαδικασίας της σύνδεσης δεδομένων. Θα πρέπει βέβαια να σημειωθεί ότι στους ελισσόμενους στόχους η απόκλιση της εκτιμώμενης θέσης από την πραγματική είναι αρκετά μεγάλη και διαρκώς αυξάνει, το οποίο οφείλεται στο γεγονός οτι το επιλεγμένο μοντέλο κίνησης (μοντέλο σταθερής επιταχύνσεως) δεν ανταποκρίνεται στην πραγματική κίνηση του στόχου.Καταλληλότερο μοντέλο για αυτήν την περίπτωση θα ήταν το μοντέλο σταθερής γωνιακής ταχύτητας. Επιπλέον θα πρέπει να αναφερθεί οτι σε ορισμένα σενάρια κίνησης και κυρίως στο σύστημα ιχνηλασίας επιπέδου αισθητήρα παρατηρήθηκαν ψευδείς συναγερμοί και απώλεια επιβεβαίωσης του στόχου. Αναφορικά με το σύστημα ιχνηλασίας κεντρικού επιπέδου 3 αισθητήρων θα πρέπει να σημειωθεί ότι η καθυστέρηση σε κάθε σάρωση ήταν μεγάλη. Η διαδικασία που καθυστερούσε το σύστημα διαπιστώθηκε ότι ήταν η διαδικασία αρχικοποίησης νέων ιχνών από παρατηρήσεις που δεν συσχετίζονταν με κάποιο ήδη επιβεβαιωμένο ίχνος.Θέματα τα οποία είναι δυνατόν να ερευνηθούν μελλοντικά είναι η παραλληλοποίηση ορισμένων υποδιαδικασιών της μεθόδου χαλάρωσης του Lagrange, όπως η εύρεση των μεγίστων για τα αντίστοιχα υποπροβλήματα, καθώς και η ανάπτυξη μεθόδων ανανέωσης των πολλαπλασιαστών Lagrange, οι οποίες θα λαμβάνουν υπόψη τόσο την γρήγορη σύγκλιση του αλγορίθμου όσο και την ποιότητα της λύσης.Τέλος, είναι αξιοσημείωτο ότι η τεχνική χαλάρωσης του Lagrange καθιστά δυνατή την υλοποίηση της μεθόδου ΜΗΤ (ιχνηλασία πολλαπλών υποθέσεων) με εύρος χρονικού παραθύρου Ν, αφού η ΜΗΤ με άπειρο εύρος χρονικού παραθύρου ( ‘εξαντλητική’ ΜΗΤ) είναι δύσκολο να υλοποιηθεί λόγω των τεράστιων απαιτήσεων της σε χρόνο και μνήμη. Η διπλωματική εργασία εκπονήθηκε στο εργαστήριο Μικροκυμάτων και Οπτικών Ινών της σχολής Ηλεκτρολόγων Μηχανικών & Μηχανικών Η/Υ (ΗΜΜΥ) του ΕΜΠ στα πλαίσια των ερευνητικών δραστηριοτήτων της ομάδας I-SENSE.