Προσομοίωση τυχαίας κίνησης


Αντικείμενο

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


Περιγραφή αλγορίθμων και παράμετροι

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

Αντίστοιχα μπορεί να υλοποιηθεί και η τυχαία μετακίνηση σε μία από τις οκτώ γειτονικές θέσεις:

Οι παραπάνω αλγόριθμοι παράγουν επιτόπιες μικρές μετακινήσεις (ή αλλιώς κινήσεις Brown), ενώ πολλές φορές η τυχαία κίνηση ορίζεται ως κατ' αρχήν σταθερά προσανατολισμένη (directed) κίνηση με τυχαία αλλαγή κατεύθυνσης κίνησης. Η εκδοχή αυτή υλοποιείται παρακάτω για τέσσερεις δυνατές κατευθύνσεις, όπου θεωρούμε ότι η τρέχουσα κατεύθυνση κίνησης είναι η direction και αλλάζει με πιθανότητα P:

Αντίστοιχα μπορεί να υλοποιηθεί τυχαία προσανατολισμένη κίνηση και για οκτώ δυνατές κατευθύνσεις:

Οπως ήδη αναφέρθηκε, οι παραπάνω αλγόριθμοι επιχειρούν μετακίνηση η οποία αποτυγχάνει όταν η θέση-στόχος δεν είναι διαθέσιμη. Οι αλγόριθμοι αυτοί ονομάζονται μυωπικοί (myopic) ή τυφλοί (blind), σε αντιδιαστολή με τους ευφυέστερους πληροφορημένους (informed) αλγορίθμους που δείχνουν κάποιας μορφής look-ahead. Ο προφανής πληροφορημένος αλγόριθμος τυχαίας κίνησης είναι αυτός που από τις τέσσερεις (ή οκτώ) φυσικά δυνατές κατευθύνσεις εξετάζει μόνον εκείνες οι οποίες είναι διαθέσιμες.

Δίνονται παρακάτω οι αλγόριθμοι τύπου Brown με look-ahead για τέσσερεις και οκτώ κατευθύνσεις μετακίνησης αντίστοιχα:

Κίνηση Brown με look-ahead προς τέσσερεις κατευθύνσεις

Κίνηση Brown με look-ahead προς οκτώ κατευθύνσεις

Επίσης δίνονται οι αλγόριθμοι τυχαίας προσανατολισμένης κίνησης με look-ahead για τέσσερεις και οκτώ κατευθύνσεις μετακίνησης αντίστοιχα:

Προσανατολισμένη κίνηση με look-ahead προς τέσσερεις κατευθύνσεις

Προσανατολισμένη κίνηση με look-ahead προς οκτώ κατευθύνσεις


Διάφορα μονοπάτια

Η εικόνα του προγράμματος που υλοποιεί τα παραπάνω δίνεται στο επόμενο σχήμα αριστερά. Με το κουμπί Start η προσομοίωση ξεκινά ή σταματά, με το κουμπί Step η προσομοίωση προχωρά κατά ένα βήμα, με το κουμπί Restart σβήνονται τα μέχρι στιγμής μονοπάτια (οι γραμμές που δείχνουν την πορεία που ακολουθεί η μπλε σφαίρα καθώς κινείται), ενώ με το κουμπί Edit ανοίγει το παράθυρο που φαίνεται στα δεξιά και που επιτρέπει τον έλεγχο των παραμέτρων της προσομοίωσης όπως περιγράφηκαν παραπάνω (με το κουμπί Reset οι αλλαγές μεταφέρονται στην προσομοίωση). Με control-κλικ σε κάποιο σημείο της περιοχής μετακίνησης εισάγεται νέο εμπόδιο στη θέση αυτή ή, εάν υπάρχει ήδη, διαγράφεται (τα εμπόδια σχεδιάζονται ως γκρι κουτάκια).

 

Οι περιοχές που δείχνουν να είναι πυκνά "σύννεφα" από κουκίδες είναι περιοχές στις οποίες η κίνηση είναι τύπου Brown (επειδή πολλές διαδοχικές θέσεις είναι μέσα στην ίδια περιοχή, οπτικά δεν υπάρχει διαφορά ανάμεσα στις περιπτώσεις των τεσσάρων και των οκτώ κατευθύνσεων μετακίνησης). Οι περιοχές με ευθύγραμμα μονοπάτια είναι περιοχές στις οποίες η κίνηση είναι προσανατολισμένη (μπορεί να καταλάβει κανείς εάν είναι προς τέσσερεις ή προς οκτώ κατευθύνσεις, επειδή στην πρώτη περίπτωση δε θα υπάρχουν διαγώνια τμήματα διαδρομής). Η έλλειψη look-ahead σε κάθε περίπτωση θα εκδηλώνεται ως καθυστέρηση δίπλα σε εμπόδια. Τέλος όσο μεγαλύτερη είναι η πιθανότητα P αλλαγής κατεύθυνσης στα μοντέλα προσανατολισμένης κίνησης, τόσο περισσότερο η κίνηση που προκύπτει μοιάζει με κίνηση Brown (στην ακραία περίπτωση όπου P=1 η προσανατολισμένη κίνηση είναι ισοδύναμη με κίνηση Brown). Ο χρήστης μπορεί να δοκιμάσει τους διαφόρους συνδυασμούς παραμέτρων και να διερευνήσει αυτές τις συμπεριφορές.


Τελευταία ενημέρωση 08 Νοεμβρίου 2010.
Στείλτε μου mail (etzafestas@phs.uoa.gr)