pathfinding

Gwiazda wieczoru – algorytm A* (A star)

Algorytm UCS był przez nas stosowany ostatnio z dużym powodzeniem. Dlaczego więc mamy z niego rezygnować i szukać czegoś innego? Ponieważ nie jest on zbyt inteligentny. Spójrzmy na trywialną instancję problemu labiryntu.

00000Człowiek od razu zauważy, że wystarczy iść w prawo. A co zobaczy UCS?

00000

Czerwone kropki oznaczają rozwinięte wierzchołki, czyli te które były brane pod uwagę jako potencjalnie prowadzące do celu.

Czy nie można było po prostu iść prosto do celu zamiast marnować czas na szukanie dookoła a nawet wstecz? Poradziliśmy sobie lepiej niż komputer ponieważ intuicyjnie czujemy, że idąc w lewo oddalamy się od celu. Jak teraz przełożyć naszą intuicję na kod?

Heurystyka

Aby komputer wiedział w który kierunek poszukiwań jest dobry, a który zły potrzebujemy pewnej funkcji która będzie szacować odległość stanu od rozwiązania. Taką funkcję nazywamy heurystyką. Idealna heurystyka zwraca wartość będącą dokładnym kosztem przejścia z bieżącego stanu do rozwiązania. Pozwala to na bezbłędną pracę algorytmu, bez rozwijania zbędnych wierzchołków. Oczywiście uzyskanie dokładnej wartości może być skomplikowane i czasochłonne, przez co w praktyce niemożliwe do zastosowania.
Okazuje się że do znalezienia optymalnego rozwiązania wystarczy aby była ona dopuszczalna oraz spójna. Co oznaczają te pojęcia? Intuicyjnie, spójność oznacza, że funkcja nigdy nie zwraca wartości większej niż faktyczny koszt przejścia z danego wierzchołka do wyjścia. Formalnie
\forall_{v \in V} h(v) \le C(v)
gdzie V to zbiór wszystkich wierzchołków (stanów), h to heurystyka, a C to rzeczywisty koszt. Spójność natomiast można kojarzyć z nierównością trójkąta. Spójrzmy na schemat:

consistencyJeżeli zachodzi:
h(v) \le C(v,u) + h(u)
wtedy heurystyka jest spójna. Jak można to interpretować? Poprzedni warunek gwarantował, że „globalnie” nie przeszacujemy kosztu do celu. Spójność gwarantuje że to samo dzieje się lokalnie (dla każdego wierzchołka). Skoro h(v) podał nam pewną wartość oznacza to, że nie istnieje żadna droga o mniejszym koszcie – nie tylko bezpośrednio v->t ale również przez inne wierzchołki np. v->u->t. Dodatkowo spójność implikuje dopuszczalność

Wróćmy do problemu labiryntu (bez monet) i zastanówmy się nad heurystyką. Niezależnie od układu ścian nie da się przejść drogą krótszą niż tą wyznaczoną linią prostą (po prostej też może się nie dać ale jest to OK – warunek spójności jest spełniony). Taka heurystyka prezentuje się następująco (v to wierzchołek dla którego szacujemy koszt, g to wierzchołek docelowy).
h(v, g) = \sqrt{(v_x - g_x)^2 + (g_x - v_x)^2}
Jeśli poruszamy się jedynie w kierunkach NSWE możemy pójść o krok dalej i zastosować metrykę taksówkową.
h(v, g) = |v_x - g_x| + |v_y - g_y|

Algorytm A*

Mamy już sposób oceny potencjału wierzchołka. Jak to wykorzystać? Wystarczy do priorytetu dodać wartość heurystyki, to sprawi że bardziej obiecujące wierzchołki będą rozwijane wcześniej. Taka modyfikacja nosi nazwę algorytmu A*. Co ważne przy spójnej heurystyce nadal mamy gwarancję uzyskania optymalnego rozwiązania. Porównanie do UCS można przedstawić następująco:

astar vs ucs

A* przeszukuje przestrzeń stanów szybciej w kierunku rozwiązania niż w innych kierunkach. Sprawdźmy:

EsF688

so_good

Idealnie…

Implementacja

W związku z powyższym implementacja będzie wymagała jedynie niewielkich zmian.
Na początek funkcja heurystyczna

def heuristics(node, instance):
    node_pos = (node[0], node[1])
    target_pos = (instance.get_target_state()[0], instance.get_target_state()[1])
    return taxi(node_pos, target_pos)


def taxi(p1, p2):
    return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])

W obiekcie instance pojawiła się metoda get_target_state() która zwraca stan końcowy.

def astar(instance, h):
    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 to:
    #(priorytet,[(stan, decyzja, koszt), rodzic])
    #jest to wymagane przez kolejkę.
    root_node = Node()
    root_node.parent = None
    root_node.cost = 0
    root_node.step = None
    root_node.state = instance.get_start_state()
    fringe.put((0, root_node))
    #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
        #ignorujemy koszt pobrany z kolejki, zamiast niego używamy własności cost węzła
        node = fringe.get()[1]
        node_cost = node.cost

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

        #jeśli węzeł nie był rozwijany
        if node.state not in closed:
            #dodaj go do zbioru zamkniętego (innymi słowy oznacz jako rozwinięty)
            closed.add(node.state)
            #rozwiń go
            children = instance.get_children(node.state)

            #print node.state, children
            #i dla każdego następnika
            for child in children:
                child_state, child_step, child_cost = child
                #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()
                heuristic_cost = h(child_state, instance) #koszt do wyjścia oszacowany przez heurystykę
                vertex = Node()
                vertex.step = child_step
                vertex.cost = child_cost + node_cost
                vertex.parent = node
                vertex.state = child_state
                new_node = (vertex.cost + heuristic_cost, vertex) #priorytetem jest dotychczasowy
                #koszt + wartość heurystyki.
                #i wrzuć do kolejki (zbioru otwartego)
                fringe.put(new_node)

    #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.parent is not None:
        #dodaj decyzję która nas tutaj doprowadziła
        solution.append(i.step)
        #przejdź do rodzica
        i = i.parent
    #podążaliśmy od wyjścia do startu przez co trzeba odwrócić kolejność
    solution.reverse()

    return solution

Na koniec zobaczmy na porównanie UCS oraz A* dla kilku przykładowych problemów. Użyto heurystyki jak w powyższym kodzie.

Bez żadnych zmian możemy zastosować A* do problemu ze zbieraniem monet. (Heurystyka pozostała taka samo, dla lepszych efektów należało by w niej uwzględnić monety pozostałe na planszy). Tutaj niestety trudno jest pokazać dokładnie, które stany zostały odwiedzone.

Tak jak UCS, A* można wykorzystać do całkowicie innych problemów. „Wystarczy” opracować dobrą heurystykę.

Następnym razem zmusimy komputer do rozwiązania sudoku.

Wilk, koza i kapusta – o UCS raz jeszcze

Ostatnio udało nam się znaleźć optymalne wyjście z labiryntu, uwzględniając różne czasy przejścia przez różne miejsca. Skomplikujmy zadanie. Niech robot przed wyjściem zbierze wszystkie monety. Jako bazę wykorzystajmy kod z poprzedniej części (przykładowe wyniki będą prezentowane dla wersji z czterema kierunkami ruchu zamiast ośmioma ale to nic nie zmienia. Rodzaje pól również zostają bez zmian (i również nie jest to istotne).

Reprezentacja stanu

Do tej pory stan świata był przedstawiony za pomocą pary współrzędnych (x,y). Teraz musimy dodać informację o monetach (sposób w jaki ich pozycje są ustalane nie będzie omawiany – nie jest to istotne z punktu widzenia rozważanego problemu). Najprostszym pomysłem wydaje się tablica wartości logicznych z informacją czy na danym polu znajduje się moneta. Zobaczmy ile będzie takich stanów. Labirynt ma rozmiar NM . Dla każdego pola są możliwe dwie wartości. Ilość możliwych kombinacji ustawień monet to 2^{MN} . W efekcie dostajemy coś koło 2^{MN} \ cdot MN . Dużo, nawet bardzo dużo. Spróbujmy inaczej – do informacji o pozycji robota dodajmy listę pól z monetami. Monet jest K. Możliwych list jest 2^K . Dostajemy 2^K \cdot MN. Jeśli monet jest znacząco mniej niż kafli labiryntu (K \ll MN) będzie to bardzo duża oszczędność. Osiągnęliśmy nie najgorszy efekt – 2^n rośnie wykładniczo (każde zmniejszenie n jest wartościowe) więc taka zmiana może być warta zachodu (innym miłym dodatkiem jest zmniejszenie użycia pamięci na reprezentację stanu wraz z rozwojem sytuacji kiedy monet jest coraz mniej).

Podsumowując, stan jest reprezentowany przez krotkę (x, y, coins_left) gdzie coins_left jest krotką z monetami pozostałymi na planszy.

Stan końcowy musi spełnić teraz dwa warunki. Stoimy na kaflu wyjściowym oraz nie pozostała żadna moneta do zebrania. (nic nie stoi ma przeszkodzie aby wystarczało tylko zebrać monety).

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

Pozostało jeszcze zaimplementować get_after_decision oraz get_children. Niewielkie modyfikacje służą jedynie sprawdzeniu czy wskutek działania została zebrana moneta. Jedyna magia w kodzie polega na zamianie krotki na listę i odwrotnie.

# pobierz stan po podjęciu decyzji d w stanie state
def get_after_decision(self, state, d):
	x, y, c = state
	cc = list(c)
	dx, dy = Directions[d]
	if (x, y) in cc:
		cc.remove((x, y))
	return x + dx, y + dy, tuple(cc)
	
def get_children(self, state):
	x, y, c = state
	children = []
	# dla wszystkich potencjalnie możliwych ruchów
	for d in Directions:
		cc = list(c)
		dx, dy = Directions[d]
		# w zależności od typu kafla ustaw koszt przejścia
		t = self.get_tile((x + dx, y + dy, c))
		cost = 2 if t == Tile.Swamp else 1
		# jeżeli kafel zawierał monetę ustaw ją jako zebraną
		if (x + dx, y + dy) in cc:
			cc.remove((x + dx, y + dy))

		# jeżeli kafel nie jest ścianą dodaj do następników
		if t != Tile.Wall:
			children.append(((x + dx, y + dy, tuple(cc)), d, cost))
	# zapamiętaj fakt rozwinięcia (póki co nieistotne)
	self.expanded[y][x] = True
	if (x, y) in self.coins:
		self.coins.remove((x, y))

	return children

Zobaczmy jak to działa w praktyce.

dzxMWf

Zebranie monet

CRiKgn

Zebranie monet oraz wyjście

Voilà!

Wilk, koza i kapusta

Ariadna straciła pracę na rzecz komputera – Tezeuszowi do znalezienia Minotaura wystarczy UCS, ale we wstępie było o decyzjach w ogólności. Okazuje się, że jest to metoda na tyle uniwersalna aby poradzić sobie także z innymi problemami. Weźmy wszystkim znaną zagadkę z przewiezieniem przez rzekę wilka, kozy i kapusty. Brzmi ona następująco:

Pewien kupiec ma wilka, kozę i kapustę. Musi się on przeprawić przez rzekę i ma do dyspozycji jedną łódkę, do której może wejść w jednym momencie tylko on sam i jeden z przewożonych towarów. Wiadomo, że koza zje kapustę, a wilk kozę, gdy tylko któraś z tych par zostanie bez opieki. W jaki sposób kupiec ma pokonać rzekę nie tracąc przy tym żadnego z przewożonych towarów?

Kiedy człowiek zacznie się nad nią zastanawiać może pomyśleć następująco: „Ok, za pierwszym razem nie mogę zabrać ani wilka ani kapusty – musi to być koza. Kiedy wrócę mogę zabrać dowolnego z nich ale nie mogę zostawić ich razem…”
W poprzednim problemie nie było stanów które powodowały by porażkę które teraz się pojawiły. Jak możemy je obsłużyć? Na przynajmniej 3 sposoby.

1. Wykrywać stan porażki i informować o tym algorytm żeby go unikał.
2. Nie dopuszczać do pojawienia się takiego stanu w liście następników po rozwinięciu wierzchołka.
3. Przy próbie rozwinięcia stanu porażki zwrócić pustą listę następników – algorytm będzie musiał poszukać innej drogi gdyż ta jest ślepą uliczką.

Zdecydowałem się na 3 sposób gdyż jest on wg mnie najłatwiejszy w implementacji.

W jaki sposób należy pamiętać stan? Korzystam z z krotki 4 wartości logicznych mówiących czy dany osobnik jest po właściwej stronie rzeki. Dla wygody opakowałem to w klasę State.

class State:
    def __init__(self):
        self.human = False
        self.wolf = False
        self.goat = False
        self.cabbage = False

    def to_tuple(self):
        return self.human, self.wolf, self.goat, self.cabbage

    def from_tuple(self, t):
        self.human = t[0]
        self.wolf = t[1]
        self.goat = t[2]
        self.cabbage = t[3]

    def __str__(self):
        return 'Human: ' + str(self.human) + ' Wolf: ' + str(self.wolf) + ' Goat: ' + str(
            self.goat) + ' Cabbage: ' + str(self.cabbage)

Stan startowy oznacza że wszyscy są po złej stronie (4xFalse).

self.startState = State()

Stan końcowy wskazuje, że wszyscy są po właściwej stronie.

# sprawdź czy podany stan jest stanem końcowym
def is_target_state(self, state):
	s = State()
	s.from_tuple(state)
	return s.human and s.wolf and s.goat and s.cabbage

Sprawdzenie czy stan oznacza porażkę opera się prostym warunku.

def is_lose_state(self, s):
	return s.wolf == s.goat and s.wolf != s.human or s.goat == s.cabbage and s.goat != s.human

Rozwijając wierzchołek sprawdzamy czy stan nie oznacza porażki, jeżeli nie generujemy listę dozwolonych przejść.

def get_children(self, state):
	s = State()
	s.from_tuple(state)
	children = []

	if self.is_lose_state(s):
		return []

	#zawsze można przepłynąć pustą łódką
	no_transport = State()
	no_transport.human = not s.human
	no_transport.wolf = s.wolf
	no_transport.goat = s.goat
	no_transport.cabbage = s.cabbage

	children.append((no_transport.to_tuple(), "MOVE HUMAN", 1))

	if s.human == s.wolf:
		xd = State()
		xd.human = not s.human
		xd.wolf = not s.wolf
		xd.goat = s.goat
		xd.cabbage = s.cabbage
		children.append((xd.to_tuple(), "MOVE WOLF", 1))
	if s.human == s.goat:
		xd = State()
		xd.human = not s.human
		xd.goat = not s.goat
		xd.wolf = s.wolf
		xd.cabbage = s.cabbage
		children.append((xd.to_tuple(), "MOVE GOAT", 1))
	if s.human == s.cabbage:
		xd = State()
		xd.human = not s.human
		xd.cabbage = not s.cabbage
		xd.goat = s.goat
		xd.wolf = s.wolf
		children.append((xd.to_tuple(), "MOVE CABBAGE", 1))

	return children
	

I to wszystko. UCS nawet nie dotykaliśmy, wystarczyło zapewnić implementację kilku metod dla obiektu instance w sposób charakterystyczny dla problemu.

Panaceum?

Jeśli metoda jednolitego kosztu gwarantuje nam optymalne rozwiązanie to czy potrzebujemy czegoś więcej? Skoro to pytanie zostało postawione można się domyślić, że tak. O tym co możemy zrobić lepiej już niedługo.

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.

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.