Wiódł ślepy kulawego – Uniform-Cost Search [Część 2] – AI Tutorial 6

Część pierwsza

Rozwiązanie zaproponowane przez BFS nie jest optymalne – nie uwzględnia wyższego kosztu przechodzenia przez bagna. Potrzebujemy czegoś lepszego.

Uniform-Cost Search (metoda jednolitego kosztu)

Bazą dla dalszej pracy będzie algorytm BFS. Jak się okazuje jest to jego przypadek szczególny. Będziemy potrzebowali kolejki priorytetowej jako zbioru otwartego. W skrócie jest to struktura do której wrzucamy elementy skojarzone z pewnym priorytetem. Wyciągamy zawsze element o najniższym priorytecie.
Ustalmy czym jest priorytet w naszym problemie. Szukamy ścieżki najkrótszej, to jest o najniższym koszcie przejścia. Wynika z tego że najpierw chcemy zbadać ścieżki tańsze. Koszt przejścia między stanami nada się doskonale jako wartość priorytetu. Wróćmy do najprostszego przykładu:

4x4

Oryginalny graf wyglądał następująco:

4x4

Zmodyfikujmy sytuację tak aby wejście na pole (2,1) było bardziej kosztowne. Uaktualniony graf:

4x4(1)

Liczby w nawiasach oznaczają koszt przejścia.

Teraz drzewo. Zwróćmy uwagę, że każdy węzeł drzewa musi pamiętać całkowity koszt dojścia do niego – chcemy przecież zminimalizować koszt całej ścieżki. Gdybyśmy brali pod uwagę tylko koszt podjęcia danej decyzji dostalibyśmy algorytm który wybierał by zawsze najpierw tańszą decyzję – co globalnie wcale nie musi przekładać się na jakość rozwiązania.

4x4 ucs(1)Przeanalizujmy sytuację. W pierwszym kroku do kolejki trafiają dwa węzły na drugim poziomie drzewa (fioletowe). Zgodnie z regułą priorytetów do rozwinięcia wybierany jest lewy (ma niższy priorytet). Prawy pozostaje w kolejce (zbiorze otwartym). Po rozwinięciu dodawane są zielony i niebieski.
Teraz w kolejce są trzy węzły – prawy fioletowy, niebieski i zielony. Wszystkie mają priorytet równy dwa. Warto jednak zauważyć że fioletowy ma 0+2 (koszt rodzica albo koszt wsteczny + koszt własny) kiedy zielony i niebieski mają po 1+1.
Załóżmy że wybrany do rozwinięcia został fioletowy. Dodajemy czerwony i szary do kolejki. Stan kolejki:
zielony – 1+1=2
niebieski – 1+1=2
szary – 2+1=3
czerwony – 2+1=3
Do wyboru jest zielony i niebieski. Złożyło się pechowo i trafiło na niebieski. Po jego rozwinięciu powstaną węzły o koszcie co najmniej 3. Stan kolejki:
zielony – 1+1=2
szary – 2+1=3
czerwony – 2+1=3
kilka innych co najmniej 3 (koszt wsteczny = 2 + koszt własny co najmniej 1)
Wyciągamy z kolejki zielony (ma najniższy priorytet), jest to rozwiązanie. Znaleźliśmy drogę SE omijającą drogie pole (2,1).

Wcześniej było powiedziane, że BFS jest szczególnym przypadkiem UCS. Dlatego implementacja będzie bardzo podobna.

# coding=utf-8
from Queue import PriorityQueue


def ucs(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 UCS jest kolejką priorytetową (niższy priorytet powoduje szybsze zdjęcie
    #elementu
    #enqueue - put
    #dequeue - get
    fringe = PriorityQueue()
    #format wierzchołka jest nieco inny teraz to:
    #(priorytet,[((x,y), decyzja, koszt), rodzic])
    #jeżeli przez 'node' oznaczyć strukturę wierzchołka używaną poprzednio (w bfs i dfs)
    #to teraz jest to: (priorytet, node)
    #jest to wymagane przez kolejkę.
    fringe.put((0, [(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 kolejki - ten o najniższym priorytecie
        #zmiena node jest takie samego typu jak poprzednio (pobrany wierzchołek
        #rozpakowaliśmy)
        node_cost, 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:
                #sprawdź koszt następnika
                child_cost = child[2]
                #dodaj informację o poprzedniku (node jest rodzicem child)
                #jako koszt ustaw sumę następnika i koszt dojścia do rodzica -
                #został on odczytany przy rozpakowywaniu krotki zwróconej przez
                #fringe.get()
                vertex = (node_cost + child_cost, [child, node])
                #i wrzuć do kolejki (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

Spójrzmy na poprzednio używaną instancję i sprawdźmy jak poradzi sobie UCS.

3MdZLMUdało się! Zobaczmy jeszcze jeden przykład gdzie będzie lepiej widać, że komputer omija kosztowne pola jeśli jest inna opcja. Jeśli jednak prowadzi przez nie krótsza droga, wykorzystuje je.

06ORB7

Obiekt instance

Przeanalizujmy omijany do tej pory obiekt instance. Z poprzedniej części wiemy, że dostarcza metod:

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).

Zobaczmy implementację na potrzeby labiryntu. (nieistotne fragmenty zostały wycięte – cały plik będzie wkrótce dostępny w repozytorium).

# Możliwe decyzje. Wartość to ruch w osi X i Y.
Directions = {
    'East': (1, 0),
    'North': (0, -1),
    'South': (0, 1),
    'West': (-1, 0)}


# Typy pól (kafli). Kolejno: puste, ściana, bagno, pole startowe, wyjście
class Tile:
    def __init__(self):
        pass

    Blank, Wall, Swamp, Start, Target = range(5)


# Klasa reprezentująca problem znajdowania drogi w labiryncie.
class Maze:
    def __init__(self):
        # układ pól na planszy
        self.layout = []
        # miejsce startowe (ustawiany przy wczytywaniu mapy)
        self.startState = None

    # pobierz kafel pod daną pozycją. state jest krotką (x,y)
    def get_tile(self, state):
        x, y = state
        return self.layout[y][x]

    # sprawdź czy podany stan (x,y) jest stanem końcowym
    def is_target_state(self, state):
        return self.get_tile(state) == Tile.Target

    # pobierz stan początkowy
    def get_start_state(self):
        return self.startState

    # pobierz stan po podjęciu decyzji d w stanie state
    def get_after_decision(self, state, d):
        x, y = state
        dx, dy = Directions[d]
        return x + dx, y + dy

    # rozwiń wierzchołek
    def get_children(self, state):
        x, y = state
        children = []
        # dla wszystkich potencjalnie możliwych ruchów
        for d in Directions:
            dx, dy = Directions[d]
            # w zależności od typu kafla ustaw koszt przejścia
            t = self.get_tile((x + dx, y + dy))
            cost = 2 if t == Tile.Swamp else 1
            # jeżeli kafel nie jest ścianą dodaj do następników
            if t != Tile.Wall:
                children.append(((x + dx, y + dy), d, cost))
        # zapamiętaj fakt rozwinięcia (póki co nieistotne)
        self.expanded[y][x] = True

        return children

Ruch po skosie

Wprowadźmy jeszcze jedną drobną zmianę – umożliwienie ruchu po skosie.

Dodajemy 4 nowe kierunki:

Directions = {
    'East': (1, 0),
    'North': (0, -1),
    'South': (0, 1),
    'West': (-1, 0),
    'NorthEast': (1, -1),
    'NorthWest': (-1, -1),
    'SouthEast': (1, 1),
    'SouthWest': (-1, 1)
}

Jeśli poruszamy się po skosie mnożymy koszt razy \sqrt{2} \approx 1,41 – tyle razy dłuższe jest przejście po skosie względem przejścia po prostej pionowej/poziomej.

# [...]
cost = 2 if t == Tile.Swamp else 1
if dx != 0 and dy != 0:
	cost *= 1.41
# jeżeli kafel nie jest ścianą dodaj do następników
# [...]

Glnt5w

Podsumowanie

Potrafimy już znaleźć drogę do wyjścia. Następnym razem poszerzymy zagadnienie o zebranie wszystkich monet przed wyjściem, a także zastanowimy się czy pokazaną metodę można wykorzystać w innych sytuacjach, niezwiązanych z szukaniem drogi.

Reklamy

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ń )

Facebook photo

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

Google+ photo

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

Connecting to %s