Miesiąc: Marzec 2015

Chodź, pomaluj mój świat – kolorowanie mapy (grafu)

Ostatnim razem opracowaliśmy reprezentację niezbyt ogólną. Zanim zaczniemy ulepszać algorytm poprawmy implementację. Zamiast używać zmiennych i ograniczeń zamodelujemy całość w postaci grafu.

geo-map-australia-and-new-zealand-contour

Weźmy następujący problem. (Przykład pochodzi z książki Artificial Intelligence: A Modern Approach).
Mamy mapę Australii podzieloną na okręgi administracyjne. Należy ją pokolorować, oczywiście tak aby żadne dwa sąsiadujące nie używały tego samego koloru. Zgodnie z ostatnio używanymi oznaczeniami mamy 7 zmiennych:
\text{WA}, \text{NT}, \text{ST}, \text{Q}, \text{NSW}, \text{V}, \text{T} \in \{ \text{R}, \text{G}, \text{B} \}
gdzie R, G i B są kolorami. Ograniczenia prezentują się następująco:
\text{WA} \neq \text{ST} \newline  \text{NT} \neq \text{ST} \newline  \text{NSW} \neq \text{ST} \newline  \text{V} \neq \text{ST} \newline  \text{NT} \neq \text{Q} \newline  \text{NSA} \neq \text{V}\newline  \text{NSA} \neq \text{Q} \newline  \text{WE} \neq \text{NT}

Całość problemu można przedstawić jako graf. Zmienne będą wierzchołkami, ograniczenia – krawędziami między węzłami oznaczającymi związane zmienne.aus

Skutkiem ubocznym takiej reprezentacji jest natychmiastowe zauważenie, że Tasmania (T) nie ma narzuconych żadnych ograniczeń. Jeśli taki graf nie jest spójny (czyli da się go „rozdzielić” na kilka części) oznacza to, że poszczególne „kawałki” (składowe spójne) są osobnymi podproblemami, niezależnymi od siebie. Bardzo pożądana sytuacja.

Zaraz, wszystko super kiedy w ramach jednego ograniczenia występują dwie zmienne. A co jeśli jest ich więcej? Wtedy wprowadzamy inny typ wierzchołków do oznaczenia więzów. Dla przykładu z poprzedniego posta (kwadraty magiczne, wersja 3×3 aby było mniej bazgrołów):

magicsquaregraph3x3

Kolory nie wskazują na nic szczególnego, służą jedynie podniesieniu czytelności. Kwadraty są węzłami symbolizującymi ograniczenia miedzy zmiennymi.

Uaktualnijmy implementację.

Na początek ponumerujmy wierzchołki od zera do 6 (włącznie) w kolejności: WA, NT, ST, Q, NSW, V, T.

Wprowadzamy dziedzinę zmiennych jako obiekty klasy Color

class Color:
    def __init__(self):
        pass

    Red, Green, Blue = range(3)

Zmienne przyjmują teraz wartości z dziedziny {Red, Green, Blue} przez co zmienia się konstruktor klasy Variable.

class Variable(object):
    def __init__(self, fixed_value=None):
        self.domain =  [Color.Red, Color.Green, Color.Blue] if fixed_value is None else [fixed_value]
        self._value = fixed_value
	#...

W klasie Color będącej odpowiednikiem poprzedniej MagicSquare definiujemy graf. Robię to poprzez listę krawędzi, gdyż tak będzie mi później bardzo wygodnie.

class Color(object):
    def __init__(self):
        self.constraints = [(0, 1), (0, 2), (1, 2), (1, 3), (2, 3), (2, 4), (2, 5), (3, 4), (4, 5)]
	#...

Modyfikuję początkowe przypisanie tak aby składało się z samych wartości None

def get_initial_assignment(self):
        return Assingment(self.get_variables_from_values([None] * 7))

Dodaję drobną metodę sprawdzającą czy dla pojedynczej krawędzi są spełnione warunki. Jeśli zmienne są sobie równe to nastąpiło naruszenie, jeżeli nie wszystko jest OK. Oczywiście sytuacja gdzie obie są równe None jest jak najbardziej dozwolona.

def edge_invalid(self, a, b):
	if not a.is_assigned or not b.is_assigned:
		return False

	return a.value == b.value

Na koniec uaktualniam is_violating_constraints

def is_violating_constraints(self, assignment):
	# alias co by mniej pisać 😉
	v = assignment.variables

	for a, b in self.constraints:
		if self.edge_invalid(v[a],v[b]):
			return True

        return False

Wynik wykonania:

geo-map-australia-and-new-zealand-contour

Mamy teraz bazę, gotową do dalszego szlifowania, o czym już wkrótce.

Całość kodu

Obrazek tytułowy pochodzi ze slajdów do kursu CS 188: Artificial Intelligence prowadzonego przez UC Berkeley.

Reklamy

A Kind of Magic – problemy spełnialności więzów (Constraint Satisfaction Problems) – część 1

Nie zawsze sposób osiągnięcia rozwiązania jest ważny, czasem liczy się tylko poprawna odpowiedź. Przykładem takiego problemu może być sudoku – trzeba wymyślić co wpisać w wolne pola, nie jest istotne w jakiej kolejności i w jaki sposób. Innym przykładem może być kolorowanie mapy – żadne dwa sąsiadujące kraje nie mogą używać tego samego koloru. Podobnie jak ustalenie planu zajęć: wykładowca i student może być tylko w jednym miejscu na raz, sala nie może mieścić dwóch wykładów jednocześnie, niektóre zajęcia wymagają określonego sprzętu etc. Tego typu problemy określa się tytułowym mianem Constraint Satisfaction Problems (CSP) lub w języku Mickiewicza: Problemy spełnialności więzów.

Jako przykładowy problem weźmy kwadraty magiczne. Chyba wszyscy spotkali się z nimi na wczesnym etapie edukacji, ale dla przypomnienia: jest to tabela (macierz) NxN z liczbami posiadająca następująca własność: suma każdego wiersza jest taka sama jak suma każdej kolumny jak również sumy obu przekątnych.

180px-Magicsquareexample.svgFormalizacja

Sformalizujmy nieco zagadnienie (przykład dla kwadratu 4×4 o sumie równej 34).
\text{Magic Square} =  \begin{pmatrix}  v_{0} & v_{1} & v_{2} & v_{3} \\  v_{4} & v_{5} & v_{6} & v_{7} \\  v_{8} & v_{9} & v_{10} & v_{11} \\  v_{12} & v_{13} & v_{14} & v_{15}  \end{pmatrix}
Mamy 16 zmiennych – po jednej na każde pole. Niektóre z nich mogą mieć już na początku ustalone wartości (mała dygresja: skoro są już ustalone to nie muszą być zmiennymi, ale takie podejście ułatwi w tym wypadku implementację).
V = (v_0, v_1, \dotsc v_{14}, v_{15})
Każda ze zmiennych przyjmuje wartości z określonej dziedziny. Ogólnie dziedzina może być dowolnym niepustym zbiorem, także ciągłym lub nieskończonym. W rozważanym przypadku jest to skończony zbiór liczb naturalnych powiedzmy od 1 do 20. (Dalsze rozważania są prowadzone dla problemów które mają skończoną dziedzinę). Każda zmienna może mieć różną dziedzinę – w szczególności gdy jej wartość jest ustalona może być to zbiór jednoelementowy.
\forall_{v \in V} \in \{1 \dotsc 20\}
Pomiędzy zmiennymi zachodzą pewne ograniczenia (więzy) mówiące o tym jak pewne zmienne mają się do siebie. Tutaj ograniczenia mówią o sumach poszczególnych wierszy/kolumn/przekątnych.
v_0 + v_1 + v_2 + v_3 = 34 \newline  v_4 + v_5 + v_6 + v_7 = 34 \newline  \vdots

Przypisaniem nazwiemy pewne przyporządkowanie (podstawienie) wartości do poszczególnych zmiennych (niekoniecznie wszystkich na raz). Przypisanie które spełnia ograniczenia będę nazywać spójnym.
Przypisanie spójne oraz kompletne (uwzględniające wszystkie zmienne) to rozwiązanie.

Jeśli ktoś pisał w Prologu to można nazwać to mniej więcej deklarowaniem ograniczeń, które wbudowany mechanizm wnioskowania będzie próbował spełnić 😉

Problem spełnialności więzów.

Tak sformułowane zagadnienie można określić jako Constraint Satisfaction Problem albo problem spełnialności więzów.

Zastanówmy się nad rozwiązaniem. Tradycyjnie zaczniemy od najprostszego a z czasem będziemy je ulepszać.

Brute force

Najprościej było by wygenerować wszystkie możliwe kombinacje. Można się jednak domyślić, że sprawdzenie tego zajmie wieki, ponadto nie ma to zbyt wiele wspólnego z jakąkolwiek inteligencją.

Backtracking search (przeszukiwanie z nawrotami)

Pomysł najlepiej będzie przedstawić na przykładzie. Załóżmy, że mamy 3 zmienne a,b,c \in \{1,2,3\} przy następujących ograniczeniach: a \ne b, b \ne c, a \ne c

csp1

Zaczynamy w korzeniu (z pustym przypisaniem). Schodzimy w dół (najpierw po lewej). Podstawienie a = 1 spełnia ograniczenia. Idziemy dalej otrzymując a = 1, b = 1. Nie spełnia ono warunków przez co cofamy się (wykonujemy nawrót). Bierzemy kolejnego potomka wierzchołka a = 1. Jest to b = 2. Podstawienie a = 1, b = 2 jest spójne. Przechodzimy w dół do węzła c = 1. Nie spełnia on warunków więc idziemy do c = 2. Tutaj podobnie: trafiamy w końcu na c = 3. Podstawienie a = 1, b = 2, c = 3 jest spójne i kompletne przez co jest rozwiązaniem.

Węzły oznaczone na czerwono to miejsca nawrotów, szare – wierzchołki nieodwiedzone.

Rekurencyjnie algorytm można zapisać w postaci:

Backtracking Search:
 1. Jeśli przypisanie jest rozwiązaniem, zakończ.
 2. v = pobierz nieprzypisaną zmienną
 3. Dla każdej wartości val z dziedziny zmiennej v:
 3.1. v = val
 3.2. Jeśli przypisanie nie spełnia ograniczeń:
 3.2.1 Oznacz v jako nieprzypisaną (lub równoważnie usuń z przypisania)
 3.2.2. Wróć do 4. (continue)
 3.3. wynik = wywołaj rekurencyjnie Backtracking Search
 3.4 Jeśli wynik jest różny od "rozwiązanie nie istnieje" zwróć wynik
 3.5 W przeciwnym wypadku ustaw v jako nieprzypisaną.
 3.6 Zwróć "rozwiązanie nie istnieje"

Implementacja

Zacznijmy od klasy reprezentującej zmienną. Przechowuje ona jej wartość lub informację, że jest nieustalona (_value = None) oraz domenę (domain). Jeśli jej wartość jest ustalona na stałe (fixed_value != None) jest to ustalane już na etapie konstrukcji obiektu. Metody __radd__, __repr__ oraz getter i setter dla value nie są istotne dla algorytmu – to szczegół implementacyjny.

class Variable(object):
    def __init__(self, fixed_value=None):
        # załpżono, że dziedzina dla wszystkich zmiennych jest taka sama [1..20]
        # ale równie dobrze może być przekazywana do konstruktora
        self.domain =  range(1,21) if fixed_value is None else [fixed_value]
        self._value = fixed_value

    # pozwala skorzystać z wbudowanej funkcji sum()
    def __radd__(self, other):
        if other is None: raise ValueError("Cannot sum None variable")
        return self.value + other

    # getter i setter dla value, rzuca wyjąktiem przy próbie przypisania
    # wartości spoza dziedziny
    @property
    def value(self):
        return self._value

    @value.setter
    def value(self, val):
        if val != None and not val in self.domain:
            raise DomainException(str(val))
        self._value = val

    def __repr__(self):
        return str(self.value)

    # informacja czy jest przypisana, tj czy value != None
    @property
    def is_assigned(self):
        return self.value != None

Klasa Assignment reprezentuje przypisanie, przechowuje listę wszystkich zmiennych. Pozwala sprawdzić kompletność oraz pobrać następną zmienną bez wartości.

class Assingment(object):
    # vars to lista zmiennych w problemie
    def __init__(self, vars):
        self.variables = vars

    # czy wszystkie zmienne mają wartość?
    def is_complete(self):
        not_assigned = [x for x in self.variables if x.value == None]
        return not not_assigned

    # weź pierwszą nieprzypisaną, jeśli takich nie ma rzuć wyjątek
    def get_unassigned_variable(self):
        for v in self.variables:
            if not v.is_assigned:
                return v
        raise AssertionError()

    # pokaż na ekranie w sensownym formacie
    def pretty_print(self):
        for i in range(0,4):
            print ' '.join(str(self.variables[i*4:i*4+4]))

Główna klasa problemu, pozwala odseparować ogólny algorytm rozwiązywania od szczegółów zagadnienia, co pozwoli łatwo korzystać z kodu dla różnych problemów. W podanej implementacji zakładamy znajomość sumy, jeżeli nie jest ona dostępna należy zmienić implementację funkcji is_violating_constraints tak aby nie przyrównywała do self.summary, ale sprawdzała czy wszystkie dają taki sam wynik.

    # sprawdza czy podstawienie narusza ograniczenia
    def is_violating_constraints(self, assigment):
        #alias coby mniej pisać 😉
        v = assigment.variables

        # spawdzenie wierszy
        for row_index in range(0,self.square_size):
            if not self.row_satisfies_constraint(row_index, v, self.summary):
                return True

        # i kolumn
        for col_index in range(0,self.square_size):
            if not self.col_satisfies_constraint(col_index, v, self.summary):
                return True

        # oraz przekątnych
        # tutaj oczywiście można zrobić to tego funkcje jak poprzednio ale już sobie odpuściłem

        if not assigment.is_complete():
            return False

        if v[0].value + v[5].value + v[10].value + v[15].value != self.summary:
            return True

        if v[3].value + v[6].value + v[9].value + v[12].value != self.summary:
            return True

        # sprawdziliśmy wszystkie warunki - dane przypisanie jest OK        
        return False

Na koniec właściwy algorytm. Warto zwrócić uwagę na fakt, że zmienna assignment jest pośrednio modyfikowana przy zmianach zmiennej var.

def backtracking_search(assignment, instance):
    # jeśli mamy rozwiązanie lub takowego nie ma - kończymy
    if assignment.is_complete() and not instance.is_violating_constraints(assignment):
        return assignment

    # pobierz zmienną bez wartości
    var = assignment.get_unassigned_variable()

    # dla wszystkich wartości z domeny zmiennej
    for val in var.domain:
        # przypisz tą wartość
        var.value = val
        # i sprawdź czy przypisanie spowodowało naruszenie więzów.
        if instance.is_violating_constraints(assignment):
            # jeśli tak cofnij przypisanie i spróbuj z następną wartością
            var.value = None
            continue
        # przypisanie było poprawne, powtórz dka kolejnej zmiennej (zejscie w dół drzewa)
        result = backtracking_search(assignment, instance)
        # mamy wynik, wróć w górę
        if result is not None:
            return result
        # niżej nie udało się spełnić ograniczeń, wyzeruj podstawienie
        else:
            var.value = None

    # nawrót
    return None

Przykładowe użycie:

magic = MagicSquare()
initial = magic.get_initial_assignment()
res = backtracking_search(initial, magic)
if res is None:
	print "Nope, nie da się."
else:
	res.pretty_print()

Sprawdźmy jak poradzi sobie z przykładowym problemem. S=34, D = \{1 \dotsc 20 \}

task

Rozwiązanie

solvedPodsumowanie

Zaprezentowany algorytm zawsze znajduje rozwiązanie (o ile oczywiście istnieje), niemniej można go znacząco ulepszyć. W następnej części sprawdzimy co jest nie tak (jak można się domyślić: wydajność) i zajmiemy się tym.

Cały kod jest dostępny na GitHubie.

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.