Άσκηση – Robot Path Planning

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

Το πρώτο βήμα γνωστό από θεωρία path planning είναι να προσπαθήσουμε να λύσουμε το πρόβλημα σε ένα χώρο απλούστερο (αλλά συνήθως μεγαλύτερης διάστασης) όπου το ρομπότ μας αντιπροσωπεύεται από ένα σημείο (configuration space). Εδώ είμαστε τυχεροί καθότι είναι δυνατόν να αντικαταστήσουμε το ρομπότ με ένα σημείο και να επιλύσουμε ένα πρόβλημα πάλι σε δύο διαστάσεις (η ευκολία αυτή έγκειται στον περιορισμό κίνησης του ρομπότ καθότι απαγορεύονται περιστροφικές κινήσεις). Ο νέος διδιάστατος χώρος προκύπτει διαστέλλοντας κατάλληλα τα εμπόδια. Η διαστολή γίνεται χρησιμοποιώντας κατάλληλα το (τριγωνικό) σχήμα του ρομπότ.

Θα θέλαμε να λύσουμε επίσης το εξής πρόβλημα: να βρούμε μια λύση-κίνηση του ρομπότ από την αρχική στην τελική θέση. Η βέλτιστη λύση εδώ, νοείται σαν η λύση που ελαχιστοποιεί το συνολικό μονοπάτι που ακολουθεί το ρομπότ. Αν και το πρόβλημα αυτό επιδέχεται βέλτιστη λύση (μέσω διαγραμμάτων Voronoi), εντούτοις θα θέλαμε να κάνουμε μια απλούστερη προσέγγιση και μέσω της μεθοδολογίας των έμπειρων συστημάτων. Από το χώρο configuration περνάμε και φτιάχνουμε το γράφο ορατότητας (όπου δημιουργούμε κάποιους κόμβους – συνήθως συμπίπτουν με τις κορυφές των πολυγωνικών εμποδίων), και εντέλει δημιουργείται ο γράφος όλων των δυνατών μονοπατιών.

Ας θεωρήσουμε τώρα έναν αλγόριθμο έρευνας A₁ με την εξής ευρετική συνάρτηση αποτίμησης του κόστους μετάβασης από τον αρχικό κόμβο (S) στον τελικό (Ε) μέσω ενός ενδιάμεσου κόμβου Ν:

f_S,E(N) = g_S(N) + h_E(N)

όπου η συνάρτηση g_S(N) για ένα μονοπάτι όπου πατέρας του Ν είναι ο κόμβος L από την εξής σχέση:

g_S(N) = g_S(L) + ||N-L||₂

ενώ η συνάρτηση h_E(N) δίνεται από τη σχέση:

h_E(N) = ||E-N||₂

Επίσης, ας θεωρήσουμε τον αλγόριθμο Α₂ παρόμοιο με τον Α₁ με τη διαφορά ότι η συνάρτηση g_S για αυτόν ορίζεται από τη σχέση:

g_S(N) = ||S-N||₂

i. Δείχτε ότι οι αλγόριθμοι έρευνας Α₁ και Α₂ είναι αλγόριθμοι τύπου Α^*.

ii. Είναι κάποιος εκ των Α₁, Α₂ που περιμένουμε θεωρητικά να αναπτύξει λιγότερους κόμβους από τον άλλο;

iii. Υπάρχει κάποιος εκ των Α₁, Α₂ που να ικανοποιεί τη συνθήκη μονοτονικότητας;

Λύση

i. Είναι φανερό από τη μορφή της ευρετικής συνάρτησης ότι οι αλγόριθμοι Α₁, Α₂ είναι αλγόριθμοι τύπου Α. Τώρα για να αποδείξουμε ότι επιπλέον είναι τύπου Α*, θα πρέπει να δείξουμε ότι h_Ε(N)£h^*_E(N) για κάθε ενδιάμεσο κόμβο Ν.
Η συνάρτηση h^*_E(N) δίνεται από τη συνολική απόσταση που θα καλύψει το ρομπότ πηγαίνοντας από τον κόμβο N στον τελικό κόμβο Ε. Εάν περνά από τους κόμβους Ν₁, Ν₂, ... Ν_k, τότε από την ανισότητα τριγώνου θα έχουμε:
h_Ε(N)=||Ν-Ε||₂ £ h^*_E(N)=||Ν-Ν₁||₂+||Ν₁-Ν₂||₂+...||Ν_k-E||₂
Άρα η πρόταση αποδείχτηκε.

ii. Οι Α₁, Α₂ έχουν ακριβώς την ίδια συνάρτηση h άρα κανείς εκ των δύο δεν είναι περισσότερο πληροφορημένος του άλλου. Έτσι, δεν μπορούμε θεωρητικά να πούμε ότι κάποιος εκ των δύο θα είναι ταχύτερος δηλ. θα αναπτύξει λιγότερους κόμβους.

iii. Η συνθήκη μονοτονικότητας ισχύει όταν f_S,E(N)£f_S,E(N_j) για όλους τους απογόνους N_j του ενδιάμεσου κόμβου N.
Για τον Α₁ θα έχουμε:
f_S,E(N_j)=g_S(N_j)+h_E(N_j)=g_S(N)+||N-N_j||₂+h_E(N_j)=g_S(N)+||N-N_j||₂+||Nj-E||₂£ g_S(N)+||N-E||₂
εξαιτίας της ανισότητας τριγώνου. Άρα ο Α₁ ικανοποιεί τη συνθήκη μονοτονικότητας.
Για τον Α₂ είναι εύκολο να αποδειχθεί με ένα αντιπαράδειγμα και με χρήση πάλι της ανισότητας τριγώνου ότι δεν ισχύει η ανισότητα τριγώνου (πως ακριβώς;).