Σε αυτή την υποενότητα, θα μελετήσω

ένα αναλυτικό παράδειγμα ενός απλού γενετικού αλγορίθμου,

που παράγει προγράμματα ελέγχου για εικονικά ρομπότ.

Το εικονικό μας ρομπότ λέγεται "Robby". Είναι ένα πολύ απλό ρομπότ

που ζει σε μία "προσομοιωμοίωση" του κόσμου.

Το περιέγραψα για πρώτη φορά στο βιβλίο μου: "Πολυπλοκότητα: Μία καθοδηγούμενη περιήγηση",

και η "δουλειά" του είναι να περιπλανιέται, μαζεύοντας άδεια κουτάκια σόδας.

Τον Robbie τον εμπνεύστηκα από ένα αληθινό ρομπότ, που ονομαζόταν "Herbert",

και που λειτουργούσε στη δεκαετία του '80, στο Εργαστήριο Τεχνητής Νοημοσύνης του M.I.T.

O Herbert περιπλανιόταν μέσα στο Εργαστήριο με τα ροδάκια του, πηγαίνοντας στα διάφορα γραφεία

και μαζεύοντας άδεια κουτάκια σόδας, για να τα πάει μετά στον κάδο ανακύκλωσης.

Ο Herbert ήταν μία δημιουργία του Jonathan Connell, ενός μεταπτυχιακού φοιτητή του MIT που εργαζόταν μαζί

με τον Rod Brooks και τον Peter Ning, και επρόκειτο για ένα πολύ εντυπωσιακό ρομπότ

που χρησιμοποιούσε πολύ απλούς αλγορίθμους για τον έλεγχο της συμπεριφοράς του.

Η δική μας εκδοχή του "Herbert" λέγεται "Robby" και είναι ένα εικονικό ρομπότ,

το οποίο ζει σε έναν μικρο-κόσμο προσομοίωσης, αποτελούμενο από ένα πλέγμα 10 x 10 τετραγώνων.

Μπορείτε να σκεφτείτε τα τετραγωνάκια αυτά σαν ένα είδος εικονικών "γραφείων" (όπως στο ΜΙΤ)

και κάθε γραφείο ή είναι άδειο ή περιέχει ένα άδειο κουτάκι σόδας.

Να ένα παράδειγμα ενός κουτιού σόδας.

Και η δουλειά του Robby είναι να κινείται μέσα σε αυτόν τον μικρόκοσμο, μαζεύοντας τα άδεια κουτάκια σόδας.

Έτσι, πρέπει να φτιάξουμε για τον Robby ένα πρόγραμμα που να του λέει τι να κάνει σε κάθε βήμα.

Θα μπορούσα να προγραμματίσω ένα τέτοιο πρόγραμμα μόνη μου, αλλά αντί γι αυτό, θα χρησιμοποιήσω

ένα γενετικό αλγόριθμο, που εξελίσσει προγράμματα ώστε να κάνουν αυτή τη δουλειά.

Κατ' αρχήν πρέπει να σας πω τι μπορεί να δει και τι να κάνει ο Robby.

Eίναι ένα πολύ απλό ρομπότ, με κακή όραση, οπότε το μόνο πράγμα

που μπορεί να δει είναι το περιεχόμενο του "τετραγώνου' στο οποίο βρίσκεται,

καθώς και των τετραγώνων βόρεια, νότια, ανατολικά και δυτικά αυτού.

Άρα βλέπει: την τρέχουσα θέση του, βόρεια, νότια, ανατολικά και δυτικά αυτής.

Στην τρέχουσα θέση του, ο χώρος του είναι άδειος.

Στα Βόρεια υπάρχει τοίχος, στα Δυτικά υπάρχει τοίχος,

στα Νότια υπάρχει ένα άδειο τετράγωνο και στα Ανατολικά υπάρχει ένα κουτάκι.

Αυτά είναι όσα μπορεί να δει.

Χρησιμοποιεί αυτά που μπορεί να δει, ώστε να αποφασίσει τι ενέργεια να κάνει σε κάθε χρονικό βήμα.

Και εδώ έχει επτά πιθανές ενέργειες: μπορεί να κινηθεί προς τα Βόρεια,

προς τα Νότια, προς τα Ανατολικά,

προς τα Δυτικά, δηλαδή γενικά να κινηθεί κατά ένα τετράγωνο.

Μπορεί να κάνει μία τυχαία κίνηση: να διαλέξει μία τυχαία διεύθυνση προς την οποία να κινηθεί.

Μπορεί να μείνει στη θέση του, χωρίς να κάνει τίποτα ή μπορεί να μαζέψει ένα κουτάκι.

Και, εάν πάει να μαζέψει ένα κουτάκι και όντως υπάρχει ένα κουτάκι εκεί, τα καταφέρνει.

Ή μπορεί να προσπαθήσει να μαζέψει εσφαλμένα ένα κουτάκι από ένα άδειο τετράγωνο.

Και έχει συγκεκριμένες αμοιβές και ποινές που παίρνει από αυτές του τις ενέργειες.

Εάν μαζέψει ένα κουτάκι παίρνει 10 πόντους, αυτό είναι δηλαδή καλό.

Εάν προσπαθήσει να μαζέψει ένα κουτάκι σε τετράγωνο που είναι άδειο, παίρνει μείον έναν πόντο,

και αν πέσει πάνω σε έναν τοίχο, παίρνει μείον πέντε πόντους.

Και το ολικό του σκορ, καθώς κινείται στο χώρο

είναι το άθροισμα των αμοιβών και των ποινών που παίρνει.

Ο στόχος είναι να χρησιμοποιήσουμε έναν γενετικό αλγόριθμο για να αναπτύξουμε ένα πρόγραμμα ελέγχου,

δηλαδή μία στρατηγική για τον Robby.

Οπότε, ας μιλήσουμε για το τι είναι "στρατηγική".

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

για κάθε πιθανή κατάσταση.

Όπου: πιθανές καταστάσεις είναι τα δεδομένα που εισάγονται για τον Robby,

δηλ. τα πιθανά δεδομένα που εισάγονται και που μπορεί να δει.

Οπότε ας κάνουμε μία λίστα πιθανών καταστάσεων στις οποίες μπορεί να βρεθεί ο Robby.

Οι πιθανές καταστάσεις θα ήταν ό,τι βλέπει

στα Βόρεια, Νότια, Ανατολικά και Δυτικά της θέσης όπου βρίσκεται.

Και μία στρατηγική θα ήταν να υπάρχει μία πιθανή ενέργεια που θα έκανε, για κάθε μία πιθανή κατάσταση.

Οπότε να εδώ μία πιθανή κατάσταση - ίσως η πλέον απλή -

όπου όλα τα τετράγωνα είναι άδεια.

Βρίσκεται σε ένα άδειο "κελί" και όλα τα γειτονικά του "κελιά", προς όλες τις κατευθύνσεις είναι άδεια.

Αυτή είναι μία πιθανή κατάσταση. Να μία άλλη πιθανή κατάσταση:

όλα τα γύρω τετράγωνα είναι άδεια, εκτός από την τρέχουσα θέση του, που έχει ένα κουτάκι.

Και μπορούμε να συνεχίσουμε έτσι, παραθέτοντας και άλλες πιθανές καταστάσεις.

Και πολύ γρήγορα, θα βρίσκαμε πόσες πιθανές καταστάσεις υπάρχουν,

αλλά για να βεβαιωθούμε ότι το καταλαβαίνετε όλο αυτό, ας σταματήσουμε για ένα σύντομο κουίζ.

Το κουίζ αποτελείται από δύο ερωτήσεις. Η πρώτη λέει: κοιτάξτε αυτήν εδώ την κατάσταση,

και υποθέστε ότι ο Robby έχει σκορ μηδέν ως τώρα,

και κάνει αυτές τις ενέργειες με τη σειρά: κινείται ανατολικά, κινείται ανατολικά, μαζεύει ένα κουτάκι

κινείται ανατολικά, μαζεύει ένα κουτάκι και κινείται νότια.

Οπότε κάνει αυτές τις έξι ενέργειες, και πρέπει να απαντήσετε: ποια είναι

η κατάστασή του μετά από αυτές τις έξι ενέργειες, και ποιο είναι το σκορ του;

Και εδώ σας υπενθυμίζω ποιοι είναι οι κανόνες για το σκορ του.