Υπολογισμός Γράφου Ορατότητας για Μετακίνηση Διαμέσου Εμποδίων με χρήση Εξελικτικών Αλγορίθμων

  1. MSc thesis
  2. Πανάρετος, Αθανάσιος
  3. Μεταπτυχιακή Εξειδίκευση στα Πληροφοριακά Συστήματα (ΠΛΣ)
  4. 18 Σεπτεμβρίου 2021 [2021-09-18]
  5. Ελληνικά
  6. 298
  7. Καρυώτης, Βασίλειος
  8. Υπολογιστική γεωμετρία | Computational Geometry | Γράφος ορατότητας | Visibility graph | Βέλτιστη διαδρομή | Optimal path | Εξελικτικοί αλγόριθμοι | Evolutionary algorithms | Πολυγωνικά εμπόδια | Polygon obstacles | Σχεδιασμός διαδρομής | Path planning
  9. 3
  10. 5
  11. 47
  12. Περιέχει: πίνακες, διαγράμματα, εικόνες
    • Στην παρούσα εργασία παρουσιάζουμε δύο γενετικούς αλγορίθμους σχεδιασμού κίνησης για ένα ρομπότ το οποίο μετακινείται διαμέσου πολυγωνικών εμποδίων, τον Γενετικό Αλγόριθμο #1 και τον Γενετικό Αλγόριθμο #2. Στον Αλγόριθμο #1 χρησιμοποιούμε αρχικά μια απλοϊκή μέθοδο για να κατασκευάσουμε το γράφο ορατότητας, δηλαδή το γράφο που έχει ως κόμβους τις κορυφές των εμποδίων και ακμές τα ευθύγραμμα τμήματα που ενώνουν τις ορατές μεταξύ τους κορυφές. Ακολούθως χρησιμοποιούμε γενετικές διαδικασίες για να υπολογίσουμε το συντομότερο μονοπάτι από έναν τυχαίο κόμβο-εκκίνηση προς έναν τυχαίο κόμβο-προορισμού. Κωδικοποιήσαμε τα χρωμοσώματα του πληθυσμού ως λίστες, τα στοιχεία των οποίων αποτελούν τους κόμβους από τους οποίους διέρχεται το συντομότερο μονοπάτι. Στον Αλγόριθμο #2 υπολογίζουμε το γράφο ορατότητας με εξελικτικές διαδικασίες και εντοπίζουμε το συντομότερο μονοπάτι με χρήση του αλγορίθμου Dijkstra. Σε αυτό τον αλγόριθμο κωδικοποιήσαμε τα μέλη του πληθυσμού ως δισδιάστατους πίνακες οι οποίοι αντιστοιχούν στους πίνακες γειτνίασης του κάθε γράφου. Αρχικά περιγράφουμε την έννοια του χώρου διαμόρφωσης μέσα στον οποίο κινείται το ρομπότ. Στη συνέχεια εξετάζουμε τις πιο βασικές μεθόδους απεικόνισης του χώρου αυτού, την απεικόνιση με χρήση πλέγματος και την απεικόνιση με χρήση οδικών χαρτών. Έπειτα παρουσιάζουμε τον αλγόριθμο Compute Path (Berg, 2008) ο οποίος δέχεται ως είσοδο έναν οδικό χάρτη και επιστέφει ένα μονοπάτι μεταξύ του σημείου εκκίνησης και τερματισμού το οποίο αποφεύγει συγκρούσεις με τυχόν εμπόδια κατά μήκος της διαδρομής. Ακολούθως, αναφέρουμε εν συντομία διάφορες μεθόδους βελτιστοποίησης. Αφού παραθέσουμε τα χαρακτηριστικά των γενετικών αλγορίθμων, περιγράφουμε τον τρόπο υλοποίησης του Γενετικού Αλγορίθμου #1 σε γλώσσα προγραμματισμού Python. Ο αλγόριθμος δέχεται ως είσοδο τον επιθυμητό από το χρήστη αριθμό πολυγωνικών εμποδίων καθώς και δύο σημεία στο επίπεδο, στη συνέχεια χρησιμοποιεί τη συνάρτηση generatePolygon() η οποία παράγει τυχαία πολύγωνα στο επίπεδο και κατασκευάζει τον γράφο ορατότητας που δημιουργείται από τις κορυφές των εμποδίων και τα σημεία εκκίνησης-τερματισμού. Έπειτα δημιουργεί αρχικό πληθυσμό ατόμων, δηλαδή πιθανά μονοπάτια τα οποία όμως έχουν ως πρώτο και τελευταίο κόμβο τα σημεία εκκίνησης και τερματισμού. Από τον αρχικό πληθυσμό δημιουργούνται με κάθε επανάληψη της γενετικής διαδικασίας νέες γενιές ατόμων. Κάθε γενιά όμως περιέχει όλο και πιο σύντομα μονοπάτια, ενώ στην τελική επανάληψη επιλέγεται η καλύτερη λύση. Στο Κεφάλαιο 5 παρουσιάζουμε τα αποτελέσματα των εκτελέσεων του Γενετικού Αλγορίθμου #1 για διάφορα σενάρια. Παρατηρούμε ότι το μονοπάτι που επιστρέφει κάθε φορά ο Αλγόριθμος #1 προσεγγίζει σε μεγάλο βαθμό το μονοπάτι που επιστρέφει ο αλγόριθμος Dijkstra, ενώ σε ορισμένες περιπτώσεις τα δύο μονοπάτια ταυτίζονται. Στο Κεφάλαιο 6 περιγράφουμε τον τρόπο υλοποίησης του Γενετικού Αλγορίθμου #2 και στο Κεφάλαιο 7 παρουσιάζουμε σε διαγράμματα τα αποτελέσματα από την εκτέλεση του για διαφορετικό πλήθος κόμβων και εμποδίων. Σε κάθε σενάριο αποτυπώνουμε τις ποσοστιαίες διαφορές στα μήκη των μονοπατιών που προκύπτουν αν σε κάθε μέλος-γράφο του αρχικού και τελικού πληθυσμού εφαρμοσθεί ο αλγόριθμος Dijkstra. Με αυτό τον τρόπο γίνεται πιο κατανοητή στον αναγνώστη η μεταβολή στο μέσο όρο των τιμών της αντικειμενικής συνάρτησης που προκαλούν οι γενετικές διαδικασίες στα μέλη κάθε γενιάς. Τέλος, σχεδιάζουμε το διάγραμμα με την επίδοση των παρακάτω αλγορίθμων:  Γενετικός Αλγόριθμος #2  αλγόριθμος brute-force  αλγόριθμος Lee Ο Γενετικός Αλγόριθμος #1 αν και είναι αρκετά πιο αργός (χρόνος κατασκευής πλήρους γράφου ορατότητας και χρόνος γενετικών διαδικασιών) σε σχέση με τις παραδοσιακές μεθόδους εύρεσης συντομότερου μονοπατιού (π.χ., αλγόριθμος Dijkstra) καταλήγει ορισμένες φορές στη βέλτιστη λύση , ενώ τις περισσότερες φορές οι λύσεις που βρίσκει την προσεγγίζουν. Το πλεονέκτημα του Γενετικού Αλγορίθμου #1 είναι ότι επιστρέφει πολλαπλές λύσεις (όσες και τα διαφορετικά μέλη/μονοπάτια του πληθυσμού της τελευταίας γενιάς). Επίσης με κατάλληλη τροποποίηση στον υπολογισμό του μήκους των μονοπατιών μπορεί να λειτουργήσει και με αρνητικά βάρη στις ακμές. Ο Γενετικός Αλγόριθμος #2 είναι πιο γρήγορος από τη μέθοδο brute-force λόγω του ότι χρειάζεται να υπολογίσει ένα μικρό μέρος μόνο από το σύνολο των ακμών του πλήρους γράφου ορατότητας και επιπλέον τα μονοπάτια τα οποία βρίσκει έχουν μήκος που διαφέρει ελάχιστα από τη βέλτιστη λύση. Ο χρόνος εκτέλεσης του Γενετικού Αλγορίθμου #2 μπορεί να βελτιωθεί ακόμη περισσότερο αν σε κάθε γενιά αποθηκεύσουμε π.χ., σε ένα λεξικό τα μέλη (γράφους) του πληθυσμού με το αντίστοιχο συντομότερο μονοπάτι έτσι ώστε κατά τον υπολογισμό του μέσου όρου της αντικειμενικής συνάρτησης να μην επαναϋπολογίζουμε τις τιμές των συναρτήσεων για τα μέλη που προϋπήρχαν.
    • In this work we present two different genetic motion planning algorithms, Genetic Algorithm #1 and Genetic Algorithm #2. In the first one, we use a simple (naïve) method to construct the visibility graph that is the graph created from the vertices of polygonal obstacles and the ‘visible’ edges. Next we use genetic operators to calculate the shortest path between the start and end point. For that purpose we have coded the population chromosomes as lists whose elements are the nodes that belong to the path connecting source and destination. In the second algorithm we first use genetic operators to construct the visibility graph and then calculate the shortest path using the Dijkstra algorithm. In this approach, we have coded the population chromosomes as two dimensional arrays corresponding to the adjacency matrices of each graph. At first, we present a description of the configuration space. Afterwards, we examine two approaches in environmental modeling, grid-based approach and roadmaps. Then we present the Compute Path algorithm that uses a road map and reports a collision free path between start and end point, and next we briefly mention some improvement methods. After listing the characteristics of Genetic Algorithms, we present Genetic Algorithm #1. The algorithm is implemented in Python programming language and uses the desired number of polygonal obstacles and two points in the plane as input and then it calls GeneratePolygons() function. This function generates random polygons in the plane. Then the Genetic Algorithm #1 constructs the visibility graph created by the barrier peaks and start-end points. It then creates an initial population of possible solutions representing paths, which consist of start and end point as their first and last node respectively. With each repetition of genetic process, new generations of individuals are created from the initial population. However, each generation consists from shorter paths compared with the previous one, while in the final generation the best solution is chosen. In Chapter 5 we present the results produced by Genetic Algorithm #1 for various scenarios. We observed that the path/solution returned each time by the Genetic Algorithm #1 approaches the path returned by Dijkstra’s algorithm, while in some cases the paths are identical. In Chapter 6, we describe the implementation method of Genetic Algorithm #2, while in Chapter 7 we present the results produced for different number of nodes and obstacles. In each scenario we capture the percentage differences in the lengths of the paths that result if the Dijkstra algorithm is applied to each-graph member of the initial and final population. In this way, the change in the average of the values of the objective function caused by the genetic processes in the members of each generation, becomes more comprehensible. Finally, we design the diagram with the performance of the following algorithms:  Genetic Algorithm #2  Brute-force algorithm  Lee’s algorithm Regarding Genetic Algorithm #1, although much slower (complete graph construction time plus genetic process time) compared to traditional search methods (e.g., Dijkstra algorithm), while most of the time it approaches the optimal solution , sometimes the solution coincides with it. The advantage of Genetic Algorithm #1 is that it returns multiple solutions (as many as the different members/paths of last generation). Also with a suitable modification in the calculation of the length of the paths, it can work with negative weights at the edges. Genetic Algorithm #2 is faster than the brute-force method because it needs to calculate only a small part of the total edges of the complete visibility graph and in addition the resulting path lengths differ slightly than the optimal path length. The execution time of Genetic Algorithm #2 can be further improved if in each generation we store, for example in a dictionary, the members (graphs) of the population with the corresponding shortest path so that when calculating the average of the objective function, we avoid recalculating the values of the objective function of the pre-existing members.
  14. Items in Apothesis are protected by copyright, with all rights reserved, unless otherwise indicated.