qweqwe

Wiódł ślepy kulawego czyli o wyszukiwaniu drogi [część 1] – AI TUTORIAL 5

Do tej pory skupiliśmy się na zbieraniu wiedzy i poszukiwaniu pewnych wzorców, które pozwolą nam zamodelować rzeczywistość. Dzisiaj zastanówmy się nad podejmowaniem decyzji. Od naszej AI oczekujemy, że będzie podejmować racjonalne decyzje. Np. robot stojący przed jezdnią ma za zadanie przejść bezpiecznie na drugą stronę. W tym celu raczej nie wejdzie prosto pod koła samochodu, ale poczeka na wolną drogę. AI musi zdecydować czy już iść czy jeszcze nie. Podany przykład jest oczywiście bardzo prosty, ale idąc tym tropem rozszerzmy problem.

Weźmy klasyczne zagadnienie znajdowania najkrótszej drogi. Jak się potem okaże, nasze rozumowanie będzie bardzo przydatne w innych problemach. Rozważmy postać znajdującą się w labiryncie. Wiemy gdzie jesteśmy, dokąd zmierzamy oraz znamy układ ścian. Chcemy się stąd wydostać, najlepiej jak najszybciej. Aby nieco urozmaicić problem załóżmy, że koszt poruszania się zależy od typu podłoża.

0

Przykładowa instancja problemu. Niebieski – ściany, żółty – miejsce startowe, zielony – wyjście, brązowy – bagno w którym poruszamy się wolniej.

 

Za każdym razem możemy podjąć jedną z kilku decyzji – ruch w kierunku N/S/E/W. (Płn, Płd, Wsch, Zach. – dalej będę używał tych oznaczeń).
Oczekujemy znalezienia ciągu decyzji które zaprowadzą nas do wyjścia (np. NEESSENNNNNWWWNNE).

Potrzebujemy pewnego modelu świata. Zauważmy, że rozważane uniwersum może być w jednym z wielu stanów. Taki stan jest opisany jednoznacznie przez pozycję bohatera. Ile jest tych stanów? Dla labiryntu MxN jest ich również MN. Oczywiście pewne z nich są niepoprawne – robot nie może być wewnątrz ściany ale interesuje nas rząd wielkości a nie konkretna liczba. Gdybyśmy mieli dwójkę bohaterów było by to (MN)^2.

Pomiędzy tymi stanami możemy poruszać się w określony sposób. Można to doskonale przedstawić w postaci grafu. Wierzchołki reprezentują poszczególne stany (dozwolone/poprawne). A krawędzie/łuki między nimi określone decyzje. W takim grafie jak najbardziej mogą pojawić się cykle, choć intuicyjnie czujemy że błądzenie NSNSNSNSNS nie jest racjonalne. Spójrzmy na prosty labirynt i graf dla niego.

4x4 4x4

W tym momencie problem sprowadził się do znalezienia pewnej ścieżki, od stanu (wierzchołka) początkowego (żółtego) do stanu końcowego (zielonego). Jeżeli uwzględnimy różny koszt przejścia pomiędzy stanami, możemy opisać nim poszczególne krawędzie. Dodatkowo jeśli można przejść od stanu A do B ale nie od B do A to zamiast krawędzi umieszczamy łuk. (Inny przykład: podejmując decyzję „wciśnij czerwony guzik” przechodzimy ze stanu „bomba uzbrojona” do stanu „bomba zdetonowana” bez możliwości powrotu.)

bomb(1)

Liczby w nawiasach oznaczają koszt przejścia między stanami.

 

Drzewo decyzji.

Kolejno podejmowane decyzje możemy przedstawić w postaci drzewa. Korzeniem jest sytuacja początkowa kiedy jeszcze nic nie zdecydowaliśmy. Z każdego wierzchołka możemy przejść do tylu innych ile jest dozwolonych decyzji. Liśćmi tego drzewa są miejsca gdzie nie ma żadnej dozwolonej decyzji, lub miejsca gdzie cel jest spełniony. Jak możemy przypuszczać, omawiane grafy i drzewa mogą być BARDZO duże – z tego powodu będziemy generować je leniwie tj. kolejne części pojawią się dopiero gdy są niezbędne. Jak się za chwile okaże bardzo często będą one nieskończenie duże. Łuki między wierzchołkami oczywiście mogą mieć wagi podobnie jak w grafie. Zobaczmy jak będą wyglądało drzewo dla przedstawionego wcześniej labiryntu.

4x4tree

Nawet dla tak prostego problemu jest ono nieskończenie duże! Wynika to bezpośrednio z faktu istnienia cyklu w grafie. Nie będzie to jednak trudne do ominięcia.

Przeszukiwanie grafu

Pod pojęciem rozwinięcia wierzchołka rozumiem pobranie jego następników.

Wciąż szukamy wyjścia (najkrótszego) z labiryntu. Dla podanego wyżej przykładu oczywistym jest SE lub ES. Teraz pora na komputer.
Przypomnijmy, że w przedstawionym modelu świata szukamy ścieżki która pozwoli przejść od stanu startowego do stanu końcowego. Po drodze mamy cykle których chcielibyśmy uniknąć. Jak to zrobić? Wystarczy, że będziemy zapamiętywać już odwiedzone wierzchołki w tzw. zbiorze zamkniętym.
Idea jest następująca. Przechowujemy zbiór kandydatów do rozwinięcia(zbiór otwarty) oraz listę już rozwiniętych wierzchołków (zbiór zamknięty). Zgodnie z pewną strategią decydujemy który element zbioru otwartego wybrać do badania. Sprawdzamy czy jest on stanem końcowym, jeżeli nie – rozwijamy. Sprawdzamy czy był już rozwinięty. Jeżeli nie – rozwijamy a wszystkie następniki dodajemy zbioru otwartego zgodnie ze strategią. Procedurę kontynuujemy tak długo aż znajdziemy rozwiązanie lub skończą się elementy w zbiorze otwartym. Bardziej systematycznie:

Graph Search
S – stan/wierzchołek początkowy
T – stan/wierzchołek docelowy
1. zbiór otwarty = {S}
2. zbiór zamknięty = {}
3. Jeżeli zbiór otwarty jest pusty zwróć błąd.
4. akt = wybierz element ze zbioru otwartego zgodnie ze strategią.
5. jeśli akt == S zwróć sukces
6. jeśli akt nie jest w zbiorze zamkniętym
6.1. dodaj v do zbioru zamkniętego
6.2. dla każdego v w rozwiń(akt):
6.1.1 dodaj v do zbioru otwartego
7. Wróć do 3

Gdzie zbiór zamknięty jest zbiorem w sensie zbioru, a zbiór otwarty może być listą, stosem, etc lub w ogólności kolejką priorytetową.

No dobrze, w ten sposób dojdziemy do wierzchołka z rozwiązaniem – dowiedzieliśmy się że taka droga istnieje. Nie jest to zbyt satysfakcjonujące gdyż potrzebujemy konkretnych, kolejno podejmowanych decyzji. Możemy to zrobić na przynajmniej dwa sposoby.
1. Dla każdego węzła pamiętać decyzję która nas do niego doprowadziła oraz wykorzystanego poprzednika przechowywane w dedykowanym słowniku/mapie.
2. Zmienić nieco format wierzchołka tak aby pamiętał ścieżkę która do niego doprowadziła. Np:

4x4 full

W pokazanej implementacji używam drugiego sposobu.

Do pozyskiwania informacji o problemie (miejsce startu, cel, następniki, etc) używam obiektu instance który zapewnia metody:

get_start_state – zwraca stan początkowy (x,y)
is_target_state((x,y)) – sprawdza czy podany stan jest stanem docelowym
get_children((x,y)) – pobiera następniki podanego stanu w formacie ((x,y), Decyzja(kierunek), Koszt).

Dodatkowo fringe to zbiór otwarty. Wierzchołki są pamiętane w formacie:
[((x,y), Decyzja, Koszt), Poprzednik]

Zmieniając funkcję strategię modyfikujemy sposób przeszukiwania drzewa. Zastanówmy się teraz nad możliwościami.

DFS & BFS

Algorytmów Deep First Search i Breadth First Search nie będę szeroko omawiał – zostało to już zrobione milion razy w innych miejscach w sieci. Pokażę tylko jak wyglądają strategie dla nich.
DFS
W tym wypadku zbiorem otwartym jest stos, w punkcie 4.1 zdejmujemy element z wierzchu stosu, w 6.1.2 odkładamy na szczyt.
Implementacja:

# coding=utf-8
def dfs(instance):
    closed = set()  # zbiór zamknięty
    #inicjujemy zbiór otwarty stanem początkowym. Decyzję ustawiamy na null
    #koszt na 0 - nie ma to znaczenia. Rodzicem jest również null (jest to
    #korzeń drzewa
    #formalnie jest to lista, ale jest używana jako stos
    #pop - pop
    #push - append
    fringe = [[(instance.get_start_state(), None, 0), None]]
    #znaleziony cel
    target = None

    while True:
        #jeśli zbiór otwarty jest pusty to nie istnieje droga do celu
        if len(fringe) == 0:
            return []
        #pobierz kolejny węzeł z wierchu stosu
        node = fringe.pop()

        #jeśli jesteśmy w stanie docelowym, ustaw cel i zakończ
        if instance.is_target_state(node[0][0]):
            target = node
            break

        #jeśli węzeł nie był rozwijany
        if node[0][0] not in closed:
            #dodaj go do zbioru zamkniętego (innymi słowy oznacz jako rozwinięty)
            closed.add(node[0][0])
            #rozwiń go
            children = instance.get_children(node[0][0])
            #i dla każdego następnika
            for child in children:
                #dodaj informację o poprzedniku (node jest rodzicem child)
                vertex = [child, node]
                #i wrzuć na szczyt stosu (zbioru otwartego)
                fringe.append(vertex)

    #lista decyzji prowadzących do rozwiązania
    solution = []
    #zaczynamy od węzła z wynikiem
    i = target
    #dopóki ma rodzica (nie jesteśmy w korzeniu)
    while i[1] is not None:
        #dodaj decyzję która nas tutaj doprowadziła
        solution.append(i[0][1])
        #przejdź do rodzica
        i = i[1]
    #podążaliśmy od wyjścia do startu przez co trzeba odwrócić kolejność
    solution.reverse()

    return solution

Spójrzmy jak to działa. Mamy przykładowy labirynt:

0

Białe koło to nasz robot. Jak poradzi sobie DFS?

nf0VJw

Wyjście znalazł ale trudno nazwać je optymalnym. Nie ma nawet pozorów optymalności.

BFS

Tutaj używamy kolejki – dodanie elementu to zakolejkowanie na końcu, element jest pobierany z początku.
Kod jest bardzo podobny do poprzedniego – zmieniła się tylko strategia dodawania i wybierania ze zbioru otwartego.

# coding=utf-8
from Queue import Queue

def bfs(instance):
    closed = set()  # zbiór zamknięty
    #inicjujemy zbiór otwarty stanem początkowym. Decyzję ustawiamy na null
    #koszt na 0 - nie ma to znaczenia. Rodzicem jest również null (jest to
    #korzeń drzewa
    #fringe dla BFS jest kolejką
    #enqueue - put
    #dequeue - get
    fringe = Queue()
    fringe.put([(instance.get_start_state(), None, 0), None])
    #znaleziony cel
    target = None

    while True:
        #jeśli zbiór otwarty jest pusty to nie istnieje droga do celu
        if fringe.empty():
            return []
        #pobierz kolejny węzeł z wierzchu stosu
        node = fringe.get()

        #jeśli jesteśmy w stanie docelowym, ustaw cel i zakończ
        if instance.is_target_state(node[0][0]):
            target = node
            break

        #jeśli węzeł nie był rozwijany
        if node[0][0] not in closed:
            #dodaj go do zbioru zamkniętego (innymi słowy oznacz jako rozwinięty)
            closed.add(node[0][0])
            #rozwiń go
            children = instance.get_children(node[0][0])
            #i dla każdego następnika
            for child in children:
                #dodaj informację o poprzedniku (node jest rodzicem child)
                vertex = [child, node]
                #i wrzuć na szczyt stosu (zbioru otwartego)
                fringe.put(vertex)

    #lista decyzji prowadzących do rozwiązania
    solution = []
    #zaczynamy od węzła z wynikiem
    i = target
    #dopóki ma rodzica (nie jesteśmy w korzeniu)
    while i[1] is not None:
        #dodaj decyzję która nas tutaj doprowadziła
        solution.append(i[0][1])
        #przejdź do rodzica
        i = i[1]
    #podążaliśmy od wyjścia do startu przez co trzeba odwrócić kolejność
    solution.reverse()

    return solution

aUZOyU

Wynik jest znacznie lepszy niż poprzednio. Ściślej mówiąc: jeżeli zignorować dodatkowy koszt przechodzenia przez bagno jest optymalny.

Ciąg dalszy nastąpi

W następnym odcinku zajmiemy się uwzględnieniem różnego kosztu przechodzenia różnych pól.

Reklamy

2 comments

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Wyloguj / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Wyloguj / Zmień )

Zdjęcie na Facebooku

Komentujesz korzystając z konta Facebook. Wyloguj / Zmień )

Zdjęcie na Google+

Komentujesz korzystając z konta Google+. Wyloguj / Zmień )

Connecting to %s