Esercizio - Algoritmi di ricerca in Python con Problem, Node e best-first search (laboratorio 3)

Laboratorio 3 del corso di Intelligenza Artificiale, Ing. dell'Informazione UniPD: gli algoritmi di ricerca della teoria (Ricerca nello spazio degli stati - formulazione dei problemi e ricerca non informataUn agente risolutore di problemi è un agente basato su obiettivi con rappresentazione atomica: formula un problema (stato iniziale, azioni, modello di transizione, test dell'obiettivo, costo dei passi) e cerca una sequenza di azioni che porta a uno stato obiettivo costruendo un albero di ricerca. Le strategie non informate usano solo la definizione del problema e si distinguono per l'ordine di espansione della frontiera: ampiezza (coda FIFO), costo uniforme (coda con priorità sul costo g), profondità (pila LIFO), profondità limitata, approfondimento iterativo e ricerca bidirezionale. Si confrontano per completezza, ottimalità, tempo e spazio in funzione di b, d, m; tutte sono casi di best-first search con una diversa funzione di valutazione f.Ricerca nello spazio degli stati - formulazione dei problemi e ricerca non informata →, Ricerca informata - greedy best-first, A* ed euristicheLa ricerca informata usa una funzione euristica h(n) che stima il costo da n all'obiettivo. Greedy best-first espande il nodo con h minima (f = h): veloce ma non ottima né in generale completa. A∗ usa f = g + h e, con h ammissibile (mai sopra il costo vero) e, sul grafo con tabella dei raggiunti, consistente, è completa e ottima; il fattore di diramazione effettivo b∗ misura la qualità di h, e un'euristica che ne domina un'altra espande meno nodi. A∗ pesato (f = g + W h) rinuncia all'ottimalità per espandere meno nodi. Per i problemi in cui conta solo lo stato finale esiste la ricerca locale (hill climbing, simulated annealing, beam search, algoritmi genetici). In appendice, cenni di ricerca avversaria (minimax e potatura alfa-beta).Ricerca informata - greedy best-first, A* ed euristiche →) realizzati in Python con classi, con il codice del corso commentato. Argomenti del laboratorio: formulazione di un problema, albero di ricerca, nodo, code, best-first search; greedy best-first, A∗, A∗ pesato, costo uniforme; ampiezza; approfondimento iterativo. Il laboratorio usa le classi del laboratorio 2 (Esercizio - Programmazione a oggetti in Python - listino, carrello, copie e ristorante (laboratorio 2)). Le applicazioni (mappa della Romania, pancake sorting) sono in Esercizio - Route finding sulla Romania e pancake sorting con euristica del gap (laboratorio 3), il confronto tra gli algoritmi in Esercizio - Confronto degli algoritmi di ricerca con CountCalls, report e grafici (laboratorio 3).

Testo (traduzione delle slide)

Introduzione. La ricerca si può definire come i passi per trovare una sequenza di azioni che porta allo stato obiettivo.

Formulazione del problema.

• Stato iniziale: lo stato in cui l'agente si trova all'inizio.
• Azioni: l'insieme delle azioni applicabili nello stato corrente; ACTIONS(s) restituisce le azioni applicabili in $s$.
• Modello di transizione: definisce la conseguenza di ogni azione sullo stato; RESULT(s, a) restituisce lo stato raggiunto applicando $a$ in $s$.
• Spazio degli stati: (a) è definito dallo stato iniziale, dalle azioni e dal modello di transizione; (b) contiene tutti gli stati ottenibili applicando una sequenza di azioni.
• Test dell'obiettivo: verifica quando è raggiunto uno stato obiettivo; IS_GOAL(s) restituisce True se $s$ è uguale all'obiettivo.
• Funzione di costo del cammino: misura la qualità di una soluzione valutando il costo di ogni cammino (la sequenza di stati dello spazio degli stati data da una sequenza di azioni); $c(s, a, s')$ è il costo di un passo per raggiungere $s'$ da $s$ con l'azione $a$ (ACTION_COST(s, a, s')). La soluzione ottima ha il costo di cammino minimo.

Albero di ricerca. Si considerano algoritmi che sovrappongono un albero di ricerca al grafo dello spazio degli stati, formando vari cammini a partire dallo stato iniziale e cercando di trovarne uno che raggiunge uno stato obiettivo. Ogni nodo dell'albero corrisponde a uno stato dello spazio degli stati e i rami corrispondono alle azioni. La radice corrisponde allo stato iniziale.

Code. Negli algoritmi di ricerca si usano tre tipi di coda: FIFO (primo a entrare, primo a uscire: deque), LIFO (ultimo a entrare, primo a uscire: list), coda con priorità (esce l'elemento di priorità più alta, classe PriorityQueue basata su heap; Code con prioritàEntry chiave-valore; ADT coda con priorità (insert, min, removeMin) con chiave minima = priorità massima; esempio di esecuzione; applicazioni; implementazioni con lista non ordinata e ordinata e relativi costi; ordinamento tramite coda con priorità.Code con priorità →).

Da implementare e capire: Problem, Node, best_first_search; da questa, greedy best-first, A∗, A∗ pesato, costo uniforme (e ampiezza e profondità come casi particolari); poi ampiezza con coda FIFO e approfondimento iterativo.

Il problema: la classe Problem

Una classe astratta che rappresenta il problema formale: ogni dominio (mappa, puzzle, ...) la estende ridefinendo actions e result (e, se serve, le altre) (Classi ed ereditarietà in PythonAttributi di istanza e di classe, metodi di istanza, di classe e statici; confronto e ordinamento con eq e lt; proprietà; ereditarietà, super(), override e polimorfismo; classi astratte come interfacce; eccezioni personalizzate; overloading e shadowing in Python.Classi ed ereditarietà in Python →). L'euristica predefinita è 0 e il costo predefinito di ogni azione è 1.

import math, sys, heapq
from collections import defaultdict, deque, Counter

class Problem(object):
    def __init__(self, initial=None, goal=None, **kwds):
        self.__dict__.update(initial=initial, goal=goal, **kwds)

    def actions(self, state):        raise NotImplementedError   # azioni applicabili
    def result(self, state, action): raise NotImplementedError   # stato raggiunto
    def is_goal(self, state):        return state == self.goal
    def action_cost(self, s, a, s1): return 1
    def h(self, node):               return 0                    # euristica nulla

    def __str__(self):
        return '{}({!r}, {!r})'.format(type(self).__name__, self.initial, self.goal)

self.__dict__.update(...) trasforma ogni argomento con nome in un attributo (graph=... diventa self.graph): così le sottoclassi non hanno bisogno di un costruttore.

Il nodo: la classe Node

Un nodo dell'albero di ricerca contiene stato, nodo genitore, azione che l'ha generato e costo del cammino $g$ (Ricerca nello spazio degli stati - formulazione dei problemi e ricerca non informataUn agente risolutore di problemi è un agente basato su obiettivi con rappresentazione atomica: formula un problema (stato iniziale, azioni, modello di transizione, test dell'obiettivo, costo dei passi) e cerca una sequenza di azioni che porta a uno stato obiettivo costruendo un albero di ricerca. Le strategie non informate usano solo la definizione del problema e si distinguono per l'ordine di espansione della frontiera: ampiezza (coda FIFO), costo uniforme (coda con priorità sul costo g), profondità (pila LIFO), profondità limitata, approfondimento iterativo e ricerca bidirezionale. Si confrontano per completezza, ottimalità, tempo e spazio in funzione di b, d, m; tutte sono casi di best-first search con una diversa funzione di valutazione f.Ricerca nello spazio degli stati - formulazione dei problemi e ricerca non informata →). Tre metodi speciali: __repr__ (come lo si stampa), __len__ (la profondità del nodo: 0 per la radice, altrimenti 1 più quella del genitore) e __lt__ (confronto per costo, che serve a heapq quando due nodi hanno la stessa priorità).

class Node:
    "Un nodo dell'albero di ricerca."
    def __init__(self, state, parent=None, action=None, path_cost=0):
        self.__dict__.update(state=state, parent=parent, action=action, path_cost=path_cost)

    def __repr__(self): return '<{}>'.format(self.state)
    def __len__(self):  return 0 if self.parent is None else (1 + len(self.parent))
    def __lt__(self, other): return self.path_cost < other.path_cost

failure = Node('failure', path_cost=math.inf)   # nessuna soluzione
cutoff  = Node('cutoff',  path_cost=math.inf)   # ricerca a profondità limitata troncata

def expand(problem, node):
    "Genera i figli di un nodo."
    s = node.state
    for action in problem.actions(s):
        s1 = problem.result(s, action)
        cost = node.path_cost + problem.action_cost(s, action, s1)
        yield Node(s1, node, action, cost)

def path_actions(node):
    "Le azioni dalla radice al nodo."
    if node.parent is None:
        return []
    return path_actions(node.parent) + [node.action]

def path_states(node):
    "Gli stati dalla radice al nodo."
    if node in (cutoff, failure, None):
        return []
    return path_states(node.parent) + [node.state]

failure e cutoff sono nodi "sentinella" con costo infinito: il valore restituito da una ricerca che non trova niente è ancora un Node, così search(...).path_cost e len(...) funzionano sempre. expand è un generatore (yield): produce un figlio alla volta. path_actions e path_states risalgono i genitori per ricostruire la soluzione.

Le code

FIFOQueue = deque        # coda: aggiungere con appendleft, togliere con pop (dalla parte opposta)
LIFOQueue = list         # pila: aggiungere con append, togliere con pop

class PriorityQueue:
    "Coda in cui l'elemento con f(item) minimo esce per primo."
    def __init__(self, items=(), key=lambda x: x):
        self.key = key
        self.items = []                      # uno heap di coppie (punteggio, elemento)
        for item in items:
            self.add(item)

    def add(self, item):
        heapq.heappush(self.items, (self.key(item), item))

    def pop(self):
        return heapq.heappop(self.items)[1]

    def top(self): return self.items[0][1]
    def __len__(self): return len(self.items)

heapq mantiene la lista come heap minimo: heappush e heappop costano $O(\log n)$. Gli elementi sono coppie (punteggio, nodo): se due punteggi sono uguali Python confronta i nodi, ed è per questo che Node definisce __lt__.

Best-first search

L'algoritmo generale: si estrae sempre il nodo con $f$ minima. È la ricerca su grafo con la tabella reached (degli stati raggiunti con il costo migliore):

def best_first_search(problem, f):
    "Cerca prima i nodi con f(node) minima."
    node = Node(problem.initial)
    frontier = PriorityQueue([node], key=f)
    reached = {problem.initial: node}
    while frontier:
        node = frontier.pop()
        if problem.is_goal(node.state):
            return node
        for child in expand(problem, node):
            s = child.state
            if s not in reached or child.path_cost < reached[s].path_cost:
                reached[s] = child
                frontier.add(child)
    return failure

Un figlio entra nella frontiera se il suo stato non è mai stato raggiunto, oppure se è raggiunto ora con un costo minore di prima. L'obiettivo si controlla all'estrazione (così il costo uniforme e A∗ sono ottimi). Esiste anche una versione senza reached (best_first_tree_search), che scarta solo i figli che formano un ciclo con i propri antenati (is_cycle, fino a profondità $k = 30$):

def is_cycle(node, k=30):
    "Il nodo forma un ciclo di lunghezza al più k?"
    def find_cycle(ancestor, k):
        return (ancestor is not None and k > 0 and
                (ancestor.state == node.state or find_cycle(ancestor.parent, k - 1)))
    return find_cycle(node.parent, k)

Osservazione sull'implementazione: quando un figlio è trovato per una seconda volta con un costo minore, la versione vecchia resta nello heap (heapq non sa rimuovere), e verrà estratta ed espansa comunque più tardi, producendo figli che reached poi scarta. È uno spreco, non un errore (vedi l'esempio sotto: il nodo $B$ è espanso due volte).

Da best-first search agli altri algoritmi

Basta cambiare la funzione di valutazione $f(n)$:

def g(n): return n.path_cost

def astar_search(problem, h=None):
    h = h or problem.h
    return best_first_search(problem, f=lambda n: g(n) + h(n))

def weighted_astar_search(problem, h=None, weight=1.4):
    h = h or problem.h
    return best_first_search(problem, f=lambda n: g(n) + weight * h(n))

def greedy_bfs(problem, h=None):
    h = h or problem.h
    return best_first_search(problem, f=h)

def uniform_cost_search(problem):
    return best_first_search(problem, f=g)

def breadth_first_bfs(problem):
    return best_first_search(problem, f=len)

def depth_first_bfs(problem):
    return best_first_search(problem, f=lambda n: -len(n))

Il peso predefinito di weighted_astar_search è $1{,}4$. Per breadth_first_bfs basta ricordare che len(n) è la profondità del nodo (Visite di grafi - BFS e DFSVisite in ampiezza (BFS) e in profondità (DFS) come design pattern; etichette discovery, cross e back edge; BFS tree e distanze; complessità Theta(n+m) con liste di adiacenza; applicazioni (connettività, componenti, spanning tree, cammini minimi non pesati, cicli, vertici a distanza al più d); esempio svolto su un grafo di 7 vertici.Visite di grafi - BFS e DFS →).

Ampiezza con coda FIFO, profondità limitata e approfondimento iterativo

L'ampiezza "vera" non ha bisogno di una coda con priorità: una coda FIFO basta. Il test dell'obiettivo si fa alla generazione del figlio (con costo uniforme dei passi non si perde l'ottimalità e si risparmia un livello), e un insieme reached evita i ripetuti:

def breadth_first_search(problem):
    "Cerca prima i nodi meno profondi."
    node = Node(problem.initial)
    if problem.is_goal(problem.initial):
        return node
    frontier = deque([node])
    reached = {problem.initial}
    while frontier:
        node = frontier.pop()                 # esce dalla destra
        for child in expand(problem, node):
            s = child.state
            if problem.is_goal(s):
                return child
            if s not in reached:
                reached.add(s)
                frontier.appendleft(child)    # entra da sinistra
    return failure

(appendleft e pop agiscono da lati opposti: è una FIFO.) La ricerca a profondità limitata è una DFS con pila (list) e limite sulla profondità; restituisce cutoff se il limite ha troncato qualcosa:

def depth_limited_search(problem, limit=10):
    "Cerca prima i nodi più profondi, fino alla profondità limit."
    frontier = [Node(problem.initial)]
    result = failure
    while frontier:
        node = frontier.pop()
        if problem.is_goal(node.state):
            return node
        elif len(node) >= limit:
            result = cutoff
        elif not is_cycle(node):
            for child in expand(problem, node):
                frontier.append(child)
    return result

def iterative_deepening_search(problem):
    "Ricerca a profondità limitata con limite crescente."
    for limit in range(1, sys.maxsize):
        result = depth_limited_search(problem, limit)
        if result != cutoff:
            return result

L'approfondimento iterativo prova $1, 2, 3, \dots$ e restituisce appena il risultato non è cutoff (cioè o si è trovato un obiettivo o l'albero è stato esplorato per intero: failure). Nel codice del corso c'è anche una depth_first_recursive_search, la DFS ricorsiva con controllo dei cicli.

Esempio completo: un grafo di prova

Per vedere gli algoritmi al lavoro, un piccolo problema su un grafo orientato pesato, definito estendendo Problem:

class GraphProblem(Problem):
    """graph[s] = {successore: costo}; heur[s] = h(s)."""
    def actions(self, s):            return list(self.graph[s])
    def result(self, s, a):          return a
    def action_cost(self, s, a, s1): return self.graph[s][s1]
    def h(self, node):               return self.heur[node.state]

graph = {'S': {'A': 1, 'B': 4}, 'A': {'B': 2, 'C': 6}, 'B': {'C': 1, 'G': 9}, 'C': {'G': 3}, 'G': {}}
heur  = {'S': 6, 'A': 5, 'B': 3, 'C': 3, 'G': 0}
p = GraphProblem(initial='S', goal='G', graph=graph, heur=heur)

for search in (breadth_first_search, uniform_cost_search, greedy_bfs, astar_search, iterative_deepening_search):
    n = search(p)
    print(search.__name__, path_states(n), n.path_cost)

I costi veri verso $G$ sono $C: 3$, $B: \min(9, 1 + 3) = 4$, $A: \min(2 + 4, 6 + 3) = 6$, $S: \min(1 + 6, 4 + 4) = 7$; l'euristica scelta sta sotto: $h = (6, 5, 3, 3, 0)$ è ammissibile (ogni $h(n)$ non supera il costo vero) e consistente (per esempio $h(A) = 5 \le c(A,B) + h(B) = 2 + 3$). Output:

breadth_first_search ['S', 'B', 'G'] 13
uniform_cost_search ['S', 'A', 'B', 'C', 'G'] 7
greedy_bfs ['S', 'B', 'G'] 13
astar_search ['S', 'A', 'B', 'C', 'G'] 7
iterative_deepening_search ['S', 'B', 'G'] 13

Ampiezza, approfondimento iterativo e greedy trovano il cammino con meno passi $S, B, G$ (costo 13); il costo uniforme e A∗ trovano il ottimo $S, A, B, C, G$ (costo 7). Il greedy ci arriva con 3 sole espansioni ($S$, $B$, $G$): sceglie $B$ perché $h(B) = 3 < h(A) = 5$ e poi $G$ con $h = 0$.

Traccia di A∗ ($f = g + h$, tra parentesi $g$ e $f$):

Cammino $S \to A \to B \to C \to G$, costo $1 + 2 + 1 + 3 = 7$. Il passo 4 è proprio lo spreco descritto sopra: la voce di $B$ con $g = 4$, rimasta nello heap, viene espansa inutilmente. Le chiamate a is_goal, che avvengono all'estrazione, seguono questo ordine: ['S', 'A', 'B', 'B', 'C', 'G'].

Applicazione alla mappa della Romania

Sulla mappa del laboratorio (vedi Esercizio - Route finding sulla Romania e pancake sorting con euristica del gap (laboratorio 3)), da Arad ($A$) a Bucarest ($B$), contando le espansioni e gli stati generati (result):

L'ordine di espansione di A∗ è $A, S, R, F, P, B$ (come nella teoria, con $R$ = Rimnicu Vilcea e $F$ = Fagaras), quello del costo uniforme $A, Z, T, S, O, R, L, F, M, P, C, D, B$. Il cammino della profondità (733) è il più costoso: la DFS non guarda né i passi né il costo. Il peso 1,4 basta a trasformare A∗ in greedy su questa mappa.