PREVENT Artificial Intelligence Practical Session (UVIGO) - GR

Τεχνητή Νοημοσύνη - Έργο PREVENT

Εργαστηριακή Συνεδρία

Ξεκινήστε

Εργαστηριακή συνεδρία τεχνητής νοημοσύνης

Οι ολοκληρωμένες ασκήσεις αυτής της συνεδρίας έχουν σχεδιαστεί για να αναπτύξουν μια ολοκληρωμένη κατανόηση της τεχνητής νοημοσύνης, από βασικούς αλγόριθμους αναζήτησης μέχρι προηγμένες τεχνικές μηχανικής μάθησης, διατηρώντας το ενδιαφέρον των μαθητών μέσω οπτικής ανάδρασης και προκλήσεων που αντικατοπτρίζουν εφαρμογές στον πραγματικό κόσμο. Βασίζεται στα υλικά του μαθήματος Εισαγωγή στην Τεχνητή Νοημοσύνη (CS188) του Πανεπιστημίου της Καλιφόρνια στο Μπέρκλεϊ

Λόγω περιορισμών χρόνου, τα εργαστήρια θα καθοδηγούνται/επιδεικνύονται από τους καθηγητές.

Φιλοσοφία και Στόχοι του Έργου

Οπτικοποίηση

Τα έργα επιτρέπουν στους μαθητές να οπτικοποιούν άμεσα τα αποτελέσματα των τεχνικών ΤΝ που εφαρμόζουν στην πράξη, παρέχοντας άμεση ανατροφοδότηση και καλύτερη κατανόηση των αφηρημένων εννοιών.

Ελάχιστη Κλιμάκωση

Κάθε έργο περιέχει σαφείς οδηγίες και παραδείγματα κώδικα χωρίς υπερβολικό αρχικό κώδικα, ενθαρρύνοντας τους μαθητές να αναπτύξουν και να κατανοήσουν τις δικές τους λύσεις.

Πρόκληση του Πραγματικού Κόσμου

Το Pac-Man παρουσιάζει ένα πραγματικά απαιτητικό περιβάλλον που απαιτεί δημιουργικές λύσεις, αντικατοπτρίζοντας την πολυπλοκότητα που συναντάται στις εφαρμογές τεχνητής νοημοσύνης στον πραγματικό κόσμο.

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

Εκκίνηση: Οδηγός UNIX/Python

Βασικές γνώσεις Python

Περιβάλλον UNIX

Εισαγωγή στις βασικές έννοιες της γλώσσας προγραμματισμού Python με έμφαση στις συναρτήσεις που χρησιμοποιούνται στα έργα Pac-Man, συμπεριλαμβανομένων δομών δεδομένων και αντικειμενοστραφούς προγραμματισμού.

Βασικές εντολές UNIX και διαμόρφωση του περιβάλλοντος για αποτελεσματική ανάπτυξη, δοκιμή και αποσφαλμάτωση των απαιτούμενων εφαρμογών τεχνητής νοημοσύνης για τα επόμενα έργα.

Ροή εργασίας ανάπτυξης

Καλές πρακτικές για τη διαχείριση κώδικα, την εκτέλεση πειραμάτων και την ανάλυση αποτελεσμάτων με συστηματικό τρόπο, προετοιμάζοντας τους μαθητές για τη διαδοχική φύση της ανάπτυξης τεχνητής νοημοσύνης.

Αυτό το προκαταρκτικό σεμινάριο διασφαλίζει ότι όλοι οι μαθητές διαθέτουν τη βασική τεχνική βάση πριν εισέλθουν στους conceptos της τεχνητής νοημοσύνης. Με την τυποποίηση της χρήσης της Python χωρίς εξωτερικές εξαρτήσεις, το μάθημα διατηρεί την προσβασιμότητά του ενώ διδάσκει πρακτικές δεξιότητες προγραμματισμού που παραμένουν σχετικές στην σύγχρονη ανάπτυξη AI.

Αλγόριθμοι Αναζήτησης

Αναζήτηση σε Βάθος

Οι μαθητές υλοποιούν αυτόν τον θεμελιώδη αλγόριθμο όπου το Pac-Man εξερευνά όσο το δυνατόν πιο μακριά σε κάθε κλάδο πριν επιστρέψει, μαθαίνοντας για τα σύνορα βασισμένα σε στοίβες και την περιήγηση γραφημάτων.

Αναζήτηση σε Πλάτος

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

Αναζήτηση με Ομοιόμορφο Κόστος

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

Αναζήτηση A*

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

Μέσω αυτών των υλοποιήσεων, οι μαθητές παρατηρούν πώς το Pac-Man πλοηγείται σε λαβύρινθους αυξανόμενης πολυπλοκότητας, οπτικοποιώντας με συγκεκριμένο τρόπο πώς διαφορετικοί αλγόριθμοι εξερευνούν το χώρο των καταστάσεων. Η παραλλαγή του προβλήματος του ταξιδιώτη πωλητή προτρέπει τους μαθητές να βελτιστοποιήσουν τις διαδρομές συλλογής σημείων, εισάγοντάς τους σε υπολογιστικά ακατόρθωτα προβλήματα.

Αναζήτηση Multi-Agent

Alpha-Beta Περικοπή

Αντίστροφη Αναζήτηση

Η υλοποίηση αυτής της τεχνικής βελτιστοποίησης βελτιώνει δραστικά την αποδοτικότητα της αναζήτησης ελαχίστου-μέγιστου, απομακρύνοντας κλάδους που δεν θα επηρεάσουν την τελική απόφαση.

Οι μαθητές μοντελοποιούν τον Pac-Man και τους φαντάσματα ως ανταγωνιστικούς πράκτορες, εφαρμόζοντας στρατηγικές ελαχίστου-μέγιστου αναζήτησης όπου ο Pac-Man μεγιστοποιεί το σκορ ενώ τα φαντάσματα το ελαχιστοποιούν.

Expectimax

Συναρτήσεις Αξιολόγησης

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

Το έργο προκαλεί τους μαθητές να σχεδιάσουν και να υλοποιήσουν εξατομικευμένες συναρτήσεις αξιολόγησης κατάστασης που ποσοτικοποιούν την "καλοσύνη" των θέσεων στο παιχνίδι όταν η προγνωστική αναζήτηση είναι περιορισμένη.

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

Ενίσχυση μάθησης

Iteración de valor

Los estudiantes implementan este algoritmo basado en modelos que calcula la política óptima dado un modelo completo del entorno, aprendiendo cómo los Procesos de Decisión de Markov formalizan los problemas de decisión secuenciales.

Q-Learning

Pasando al aprendizaje sin modelo, los estudiantes implementan este algoritmo de diferencia temporal, donde Pac-Man aprende un comportamiento óptimo mediante la interacción de prueba y error con el entorno.

Q-Learning Aproximado

Los estudiantes extienden su implementación para usar representaciones basadas en características, permitiendo aprender en el juego completo de Pac-Man donde el espacio de estados es demasiado grande para métodos tabulares.

Ρομπότ που περπατά

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

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

Εικασία Probabilística: Φάντασμα κυνηγός

Μοντέλα κρυφής Markov

Ακριβής Εικασία

Φιλτράρισμα Σωματιδίων

Οι μαθητές υλοποιούν εικασία probabilística σε ένα κρυφό μοντέλο Markov όπου ο Pac-Man πρέπει να εντοπίσει αόρατους φαντάσματα βασιζόμενοι σε θορυβώδεις αναγνώσεις αισθητήρων, μαθαίνοντας για καταστάσεις πεποίθησης και αναδρομική εκτίμηση της κατάστασης.

Η υλοποίηση του αλγορίθμου προόδου επιτρέπει στον Pac-Man να διατηρεί μια ακριβή κατανομή πιθανοτήτων σχετικά με τις τοποθεσίες των φαντασμάτων, δείχνοντας πώς η κανόνας του Bayes επιτρέπει στους πράκτορες να σκέπτονται υπό αβεβαιότητα.

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

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

Κατάταξη στη Μηχανική Μάθηση

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

Η κορύφωση συμβαίνει όταν οι μαθητές εφαρμόζουν αυτές τις τεχνικές για να δημιουργήσουν έναν πράκτορα Pac-Man που μαθαίνει μέσω παρατήρησης παιχνιδιών εμπειρογνωμόνων. Αυτό συνδέει την ταξινόμηση με τη λήψη αποφάσεων και αποδεικνύει πώς η εποπτευόμενη μάθηση επιτρέπει στους πράκτορες να μιμούνται τη ανθρώπινη συμπεριφορά—μια τεχνική που χρησιμοποιείται όλο και περισσότερο σε εφαρμογές όπως τα αυτόνομα οχήματα και οι εικονικοί βοηθοί.

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

Πρακτική συνεδρία τεχνητής νοημοσύνης

Εφαρμογή

Το έργο Pacman

Τα έργα του Pac-Man αναπτύχθηκαν για το εισαγωγικό μάθημα τεχνητής νοημοσύνης στο Πανεπιστήμιο της Καλιφόρνια στο Μπέρκλεϊ. Περιλαμβάνουν τα διάφορα έργα που παρουσιάστηκαν προηγουμένως:

• Αναζήτηση: Οι φοιτητές υλοποιούν αλγόριθμους αναζήτησης βάθους, πλάτους, με σταθερό κόστος και A*. Αυτοί οι αλγόριθμοι χρησιμοποιούνται για την επίλυση προβλημάτων πλοήγησης και του ταξιδιώτη σε έναν κόσμο Pacman.
• Πολυπαραγοντική αναζήτηση: Το κλασικό Pacman μοντελοποιείται ως ένα πρόβλημα ανταγωνιστικής και τυχαίας αναζήτησης. Οι φοιτητές υλοποιούν αλγόριθμους minimax και expectimax για πολλαπλούς παράγοντες, καθώς και σχεδιάζουν λειτουργίες αξιολόγησης.
• Ενίσχυση μάθησης: Οι φοιτητές υλοποιούν αλγόριθμους ενίσχυσης μάθησης βασισμένους σε μοντέλα και χωρίς μοντέλα.
• Φαντάσματα: Η πιθανοτική υπόθεση σε ένα κρυφό μοντέλο Markov παρακολουθεί την κίνηση των κρυφών φαντασμάτων στον κόσμο του Pacman. Οι φοιτητές υλοποιούν ακριβή συμπερασματολογία χρησιμοποιώντας τον αλγόριθμο προόδου και προσεγγιστική συμπερασματολογία μέσω φίλτρων σωμάτων.
• Κατηγοριοποίηση: Οι φοιτητές υλοποιούν τυπικούς αλγόριθμους κατηγοριοποίησης στη μηχανική μάθηση χρησιμοποιώντας Naive Bayes, Perceptron και μοντέλα MIRA για την ταξινόμηση ψηφίων. Επιπλέον, επεκτείνουν αυτό υλοποιώντας έναν πράκτορα Pacman που πραγματοποιεί κλωνοποίηση συμπεριφοράς.

Αναζήτηση (Ι)

• Α agents προγραμματισμού:

• Να ρωτάτε «τι θα συνέβαινε αν»
• Αποφάσεις βασισμένες σε (υποθετικές) συνέπειες ενεργειών
• Πρέπει να έχει ένα μοντέλο για το πώς εξελίσσεται ο κόσμος ως αντίδραση στις ενέργειες
• Πρέπει να διαμορφώσει έναν στόχο (δοκιμή)
• Να λαμβάνει υπόψη πώς ΘΑ ήταν ο κόσμος
• Βέλτιστη έναντι ολοκληρωτικής σχεδίασης

Αναζήτηση (II)

• Ένα πρόβλημα αναζήτησης αποτελείται από:
• Ένα χώρο καταστάσεων
• Μια λειτουργία διαδοχικών καταστάσεων(με ενέργειες, κόστη)

• Μια αρχική κατάσταση και μια δοκιμασία στόχου
• Λύση
είναι μια ακολουθία ενεργειών (ένα πλάνο) που μετατρέπει την αρχική κατάσταση σε κατάσταση στόχου

“N”, 1.0

“E”, 1.0

Αναζήτηση (III): Παράδειγμα: Ταξίδι στη Ρουμανία

• Χώρος καταστάσεων:
• Πόλεις
• Λειτουργία διαδοχής:
• Δρόμοι: Πήγαινε στην γειτονική πόλη με κόστος = απόσταση
• Αρχική κατάσταση:
• Άραδ
• Έλεγχος στόχου:
• Είναι η κατάσταση == Βουκουρέστι;
• Λύση;

Αναζήτηση (IV): Χώρος καταστάσεων

Η κατάσταση του κόσμου περιλαμβάνει μέχρι την τελευταία λεπτομέρεια του περιβάλλοντος

Μία κατάσταση αναζήτησης κρατά μόνο τις απαραίτητες λεπτομέρειες για τον προγραμματισμό (αφηρημένη)

• Πρόβλημα: Δρομολόγηση
• Καταστάσεις: (x,y) θέση
• Ενέργειες: Β. Ν. Α. Δ.
• Διάδοχος: ενημέρωση μόνο της θέσης
• Έλεγχος στόχου: αν (x,y)=ΤΕΛΟΣ

• Πρόβλημα: Καταναλώστε όλα τα σημεία
• Καταστάσεις: {(x,y), boolean σημεία}
• Ενέργειες: Β. Ν. Α. Δ.
• Διάδοχος: ενημέρωση θέσης και πιθανώς ενός boolean σημείου
• Έλεγχος στόχου: όλα τα σημεία είναι ψευδή

Αναζήτηση (V): Γράφοι του χώρου καταστάσεων

• Γράφος του χώρου καταστάσεων: Μια μαθηματική αναπαράσταση ενός προβλήματος αναζήτησης
• Οι κόμβοι είναι διαμορφώσεις του κόσμου (αφηρημένες)
• Οι ακμές αντιπροσωπεύουν διαδοχικούς (αποτελέσματα ενεργειών)
• Η δοκιμασία στόχου είναι ένα σύνολο κόμβων στόχων (μπορεί να είναι μόνο ένας)

• Σε ένα γράφο του χώρου καταστάσεων, κάθε κατάσταση εμφανίζεται μόνο μία φορά!

• Σπάνια μπορούμε να κατασκευάσουμε αυτόν τον πλήρη γράφο στη μνήμη (είναι πολύ μεγάλος), αλλά είναι μια χρήσιμη ιδέα

Αναζήτηση (VI): Δέντρα αναζήτησης

Αυτό τώρα / αρχή

“E”, 1.0

“N”, 1.0

Δυνητικά μέλλοντα

• Ένα δέντρο αναζήτησης:
• Ένα δέντρο "Τι αν...?" σχεδίων και τα αποτελέσματά του
• Η αρχική κατάσταση είναι ο ριζικός κόμβος
• Οι γιοι αντιστοιχούν στους διαδόχους
• Οι κόμβοι δείχνουν καταστάσεις, αλλά αντιστοιχούν σε ΣΧΕΔΙΑ που φτάνουν σε αυτές τις καταστάσεις
• Για τα περισσότερα προβλήματα, ποτέ δεν μπορούμε να κατασκευάσουμε ολόκληρο το δέντρο

Αναζήτηση (VII): Αναζητώντας με ένα δέντρο αναζήτησης

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

Αναζήτηση (VIII): Βαθιά αναζήτηση

Αναζήτηση (IX): Αναζήτηση σε πλάτος

Κωδικός για την υλοποίηση του αλγορίθμου αναζήτησης

Λήψη κώδικα:

• git clone https://github.com/felipexil/pacman.git

Χρησιμοποιώντας Python 2, δοκιμάστε το παιχνίδι:

• cd pacman/search/search
• python pacman.py

Ο Pacman ζει σε έναν λαμπερό και μπλε κόσμο από διαδρόμους στριμωγμένους και νόστιμες μπάλες. Η αποτελεσματική πλοήγηση σε αυτόν τον κόσμο θα είναι το πρώτο βήμα του Pacman για να κυριαρχήσει στο περιβάλλον του. Ο πιο απλός πράκτορας στο searchAgents.py ονομάζεται GoWestAgent, που πηγαίνει πάντα προς τα Δυτικά (μια απλή αντανακλαστική ομάδα πρακτόρων). Αυτός ο πράκτορας μπορεί να κερδίσει περιστασιακά:

• python pacman.py --layout testMaze --pacman GoWestAgent

Αλλά, τα πράγματα γίνονται πιο πολύπλοκα για αυτόν τον πράκτορα όταν χρειάζεται να στρίψει:

• python pacman.py --layout tinyMaze --pacman GoWestAgent

Εάν ο Pacman παγώσει, μπορείτε να βγείτε από το παιχνίδι πατώντας CTRL-c στο τερματικό σας. Λάβετε υπόψη ότι το pacman.py υποστηρίζει πολλές επιλογές που μπορούν να εκφραστούν είτε με μακρύ όνομα (π.χ., --layout) είτε με σύντομο (π.χ., -l). Μπορείτε να δείτε τη λίστα όλων των επιλογών και των προεπιλεγμένων τιμών τους με:

• python pacman.py -h

Βρίσκοντας ένα Σταθερό Σημείο Φαγητού χρησιμοποιώντας Αναζήτηση Βάθους (I)

Στο searchAgents.py, θα βρείτε έναν ολοκληρωμένο SearchAgent, που σχεδιάζει μια διαδρομή μέσω του κόσμου του Pacman και στη συνέχεια εκτελεί αυτή τη διαδρομή βήμα προς βήμα. Οι αλγόριθμοι αναζήτησης για το σχεδιασμό ενός πλάνου δεν έχουν υλοποιηθεί — αυτή είναι η εργασία σου. Πρώτα, δοκίμασε ότι ο SearchAgent λειτουργεί σωστά εκτελώντας:

• python pacman.py -l tinyMaze -p SearchAgent -a fn=tinyMazeSearch

Η παραπάνω εντολή υποδεικνύει στον SearchAgent να χρησιμοποιήσει το tinyMazeSearch ως τον αλγόριθμο αναζήτησής του, ο οποίος υλοποιείται στο search.py. Ο Pacman θα πρέπει να πλοηγηθεί επιτυχώς στο λαβύρινθο. Όλες οι λειτουργίες αναζήτησής σου πρέπει να επιστρέφουν μια λίστα ενεργειών που οδηγούν τον πράκτορα από την αρχή μέχρι τον στόχο. Αυτές οι ενέργειες πρέπει να είναι νόμιμες κινήσεις (έγκυρες κατευθύνσεις, χωρίς να περνούν μέσα από τοίχους). Φρόντισε να χρησιμοποιείς τις δομές δεδομένων Stack, Queue και PriorityQueue που παρέχονται στο util.py! Υλοποίησε τον αλγόριθμο αναζήτησης σε βάθος (DFS) στη συνάρτηση depthFirstSearch στο search.py. Για να γίνει ο αλγόριθμός σου πλήρης, γράψε την έκδοση DFS με γραφήματα, που αποφεύγει την επέκταση καταστάσεων που έχουν ήδη επισκεφθεί.

Βρίσκοντας ένα Σταθερό Σημείο Φαγητού με Χρησιμοποίηση Αναζήτησης Βάθους (II)

ΑΛΓΟΡΙΘΜΟΣ διαδικασία DFS(G,v): /* G  Γράφος, v  αρχική κορυφή */ αφήστε το S ως μια στοίβα S.push(v) όσο το S δεν είναι άδειο v = S.pop() αν το v δεν έχει σημαδευτεί ως ανακαλυφθείσα: σημειώστε το v ως ανακαλυφθείσα για όλες τις ακμές από v σε w στο G.adjacentEdges(v) κάνε S.push(w)

• python pacman.py -l tinyMaze -p SearchAgent -a fn=bfs
• python pacman.py -l mediumMaze -p SearchAgent -a fn=bfs
• python pacman.py -l bigMaze -z .5 -p SearchAgent -a fn=bfs

Encontrar un Punto de Comida Fijo usando Búsqueda en Profundidad (III)

def depthFirstSearch(problem): # Estructuras de datos necesarias st = util.Stack() parent = dict steps = lista have_visited = conjunto start_state = (problem.getStartState(), None, None) st.push(start_state) while (no st.isEmpty()): state = st.pop() have_visited.add(state[0]) # Visitar el estado actual # Estado objetivo encontrado si (problem.isGoalState(state[0])): # Rastrear el camino y invertirlo para obtener la secuencia correcta de pasos mientras (state != start_state): steps.append(state[1]) state = parent[state] steps.reverse() return steps # Expandir sucesores successors = problem.getSuccessors(state[0]) para sucesor en sucesores: si (successor[0] no en have_visited): parent[successor] = state st.push(successor) # La solución o camino no existe return Ninguno

Encontrar un Punto de Comida Fijo usando Búsqueda en Anchura

ALGORITMO nodo ← un nodo con ESTADO = problem.INITIAL-STATE, COSTE-DE-RUTA = 0 si problem.GOAL-TEST(nodo.ESTADO) entonces devolver SOLUCIÓN(nodo) frontera ← una cola FIFO con el nodo como único elemento explorado ← un conjunto vacío bucle hacer si VACÍO?(frontera) entonces devolver fallo nodo ← POP(frontera) /*elige el nodo superficial en la frontera*/ agregar nodo.ESTADO a explorado para cada acción en problem.ACCIONES(nodo.ESTADO) hacer hijo ← NODO-HIJO(problem,nodo,acción) si hijo.ESTADO no está en explorado o frontera entonces si problem.GOAL-TEST(hijo.ESTADO) entonces devolver SOLUCIÓN(hijo) frontera ← INSERTAR (hijo,frontera)