Esercizio - Confronto degli algoritmi di ricerca con CountCalls, report e grafici (laboratorio 3)

Parte finale del laboratorio 3 del corso di Intelligenza Artificiale, Ing. dell'Informazione UniPD: misurare quanto lavoro fanno gli algoritmi di ricerca di Esercizio - Algoritmi di ricerca in Python con Problem, Node e best-first search (laboratorio 3) sui problemi di Esercizio - Route finding sulla Romania e pancake sorting con euristica del gap (laboratorio 3). Teoria del confronto: 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 → e 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 →. I piccoli strumenti Python (Counter, __getattr__) sono provati in Esercizio - Materiale supplementare di ricerca in Python - multimap, zip, slicing e Counter (laboratorio 3).

Testo

Riepilogo sulle statistiche degli algoritmi di ricerca (traduzione). Si raccolgono delle metriche su quanto bene si comporta ogni algoritmo. Si usa CountCalls per avvolgere un oggetto Problem in modo che le chiamate ai suoi metodi siano delegate al problema originale, ma ogni chiamata incrementi un contatore. Una volta risolto il problema, si stampano le statistiche riassuntive. report(searchers, problems) riceve un iterabile di algoritmi e un iterabile di problemi, risolve ogni problema con ogni algoritmo e aggiorna i conteggi con Counter.update.

1. Applicare uniform_cost_search a r1 (Arad $\to$ Bucarest). Qual è il costo?
2. Applicare breadth_first_search a c2 (il problema delle 7 frittelle (1, 3, 7, 5, 2, 6, 4)). Qual è il numero di azioni necessarie a risolvere il problema?
3. Confrontare i diversi algoritmi di ricerca secondo le metriche usate da report. Rappresentare i risultati con un grafico a barre per ogni metrica e per ogni problema, per esempio con matplotlib; per farlo, modificare report perché restituisca i valori invece di stamparli soltanto.

CountCalls e report

from collections import Counter

class CountCalls:
    """Delega a un oggetto ogni lettura di attributo e la conta in ._counts."""
    def __init__(self, obj):
        self._object = obj
        self._counts = Counter()

    def __getattr__(self, attr):
        "Delega all'oggetto originale, dopo aver incrementato un contatore."
        self._counts[attr] += 1
        return getattr(self._object, attr)

__getattr__ è chiamato da Python solo quando la ricerca normale dell'attributo fallisce: CountCalls ha solo _object, _counts (e i metodi della classe), quindi p.result, p.is_goal, p.actions, p.action_cost, p.initial passano tutti di lì. Ogni lettura incrementa il contatore di quel nome e restituisce l'attributo vero dell'oggetto avvolto (il metodo, che poi viene chiamato). Quindi prob._counts['result'] è il numero di volte che l'algoritmo ha chiamato result, cioè il numero di nodi generati (un figlio per chiamata). Si conta solo l'accesso al problema, non l'euristica: un oggetto h letto una volta (h = h or problem.h) conta 1.

def report(searchers, problems, verbose=True):
    """Statistiche per ogni algoritmo (e per ogni problema se verbose)."""
    for searcher in searchers:
        print(searcher.__name__ + ':')
        total_counts = Counter()
        for p in problems:
            print(p)
            prob   = CountCalls(p)
            soln   = searcher(prob)
            counts = prob._counts
            counts.update(actions=len(soln), cost=soln.path_cost)
            total_counts += counts
            if verbose: report_counts(counts, str(p)[:40])
        report_counts(total_counts, 'TOTAL\n')

def report_counts(counts, name):
    print('{:9,d} nodes |{:9,d} goal |{:5.0f} cost |{:8,d} actions | {}'.format(
          counts['result'], counts['is_goal'], counts['cost'], counts['actions'], name))

Le quattro colonne stampate:

• nodes = chiamate a result = nodi generati;
• goal = chiamate a is_goal = test dell'obiettivo (le espansioni per gli algoritmi che testano all'estrazione, i nodi generati per breadth_first_search);
• cost = costo del cammino trovato (soln.path_cost);
• actions = vedi sotto.

Risposte alle due domande

1. Costo di uniform_cost_search su r1.

report([uniform_cost_search], [r1])

uniform_cost_search:
RouteProblem('A', 'B')
       30 nodes |       13 goal |  418 cost |      16 actions | RouteProblem('A', 'B')
       30 nodes |       13 goal |  418 cost |      16 actions | TOTAL

Il costo è 418 (il cammino A, S, R, P, B: $140 + 80 + 97 + 101 = 418$, il più economico), con 30 nodi generati e 13 test dell'obiettivo (13 espansioni, di cui l'ultima è Bucarest).

2. "Numero di azioni" di breadth_first_search su c2.

report([breadth_first_search], [c2])

breadth_first_search:
   25,945 nodes |   25,946 goal |    8 cost |   4,333 actions | PancakeProblem((1, 3, 7, 5, 2, 6, 4), (1, 2, 3, 4, 5, 6, 7))

Il numero di inversioni necessarie è 8 (la colonna cost: ogni inversione costa 1). La colonna actions dice 4.333, ma non è il numero di azioni della soluzione: è la somma di due cose diverse mescolate nello stesso Counter. Prima counts['actions'] conta quante volte l'algoritmo ha letto problem.actions (una per nodo espanso: 4325), poi counts.update(actions=len(soln), ...) somma la lunghezza della soluzione ($8$): $4325 + 8 = 4333$ (verificato). Anche per il costo uniforme su r1: 12 nodi espansi (il tredicesimo è l'obiettivo, non si espande) più 4 azioni del cammino $= 16$. Quindi la risposta alla domanda è 8, e la colonna actions del corso non va letta come lunghezza della soluzione: per quella serve len(soln) (o soln.path_cost con costi unitari).

Il confronto: sei algoritmi su dieci problemi

Il notebook confronta astar_search, greedy_bfs, uniform_cost_search, breadth_first_bfs, breadth_first_search e depth_limited_search (limite 10) sui dieci problemi r0, ..., r4, c0, ..., c4. Nodi generati per problema (esecuzione verificata, i valori coincidono con quelli del corso):

Costo del cammino trovato:

Totali sui dieci problemi (nodi generati / costo somma, la riga TOTAL del report):

Cosa si legge:

• A∗ e costo uniforme sono ottimi (stesso costo totale, 2 613), ma A∗ genera quasi 300 volte meno nodi (7 896 contro 2 329 850): l'euristica fa tutta la differenza. Sulle frittelle l'euristica del gap riduce i nodi di c4 da 2,27 milioni a 2 256.
• Greedy genera ancora meno nodi (375), ma il costo totale è peggiore (3 107): veloce, non ottimo.
• breadth_first_bfs (ampiezza con coda con priorità su len) e breadth_first_search (coda FIFO, test alla generazione) trovano lo stesso numero di passi; sulle frittelle, dove ogni passo costa 1, breadth_first_bfs genera gli stessi nodi del costo uniforme (f = len e f = g coincidono). La versione FIFO risparmia un po' (test alla generazione: non espande l'ultimo livello) ma sulle mappe non è ottima nel costo ($r1$: 450 contro 418).
• depth_limited_search con limite 10 trova qualche soluzione, non la migliore: il costo sulle frittelle è sempre 10 (contro 5, 7, 8, 6, 9 degli ottimi) e sulle mappe è alto ($r1$: 733); inoltre genera 23 milioni di nodi solo per c4 (nove frittelle). Un limite scelto male dà soluzioni lunghe; per questo si usa l'approfondimento iterativo (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 →).

Grafici a barre per metrica e per problema

Per tracciare i grafici bisogna avere i valori: si modifica report perché restituisca una lista di dizionari metrics, uno per coppia (algoritmo, problema), con il nome del problema (i primi 40 caratteri di str(p)), il nome dell'algoritmo e i conteggi. Poi si raggruppano per problema e si fa un grafico a barre per ogni metrica:

import matplotlib.pyplot as plt

def report(searchers, problems):
    "Come prima, ma restituisce i valori."
    metrics = []
    for searcher in searchers:
        for p in problems:
            prob = CountCalls(p)
            soln = searcher(prob)
            counts = prob._counts
            counts.update(actions=len(soln), cost=soln.path_cost)
            metrics.append(dict(problem_name=str(p)[:40],
                                searcher_name=searcher.__name__,
                                values=counts))
    return metrics

def plot_data(metrics, metric, problem_name):
    righe = [m for m in metrics if m['problem_name'] == problem_name]
    nomi = [m['searcher_name'] for m in righe]
    valori = [m['values'][metric] for m in righe]
    plt.figure()
    plt.bar(range(len(nomi)), valori)
    plt.title(metric.upper() + ' ' + problem_name.upper())
    plt.xlabel('Search algorithms')
    plt.ylabel(metric + ' count')
    plt.xticks(range(len(nomi)), nomi, rotation=30, ha='right')
    plt.tight_layout()

searchers = [astar_search, greedy_bfs, uniform_cost_search, breadth_first_search]
metrics = report(searchers, [r1, r2, c0, c1])
for nome in sorted({m['problem_name'] for m in metrics}):
    for metric in ('result', 'is_goal', 'cost', 'actions'):
        plot_data(metrics, metric, nome)
plt.show()

Il codice del corso fa la stessa cosa estraendo le colonne in array NumPy (np.zeros(len(metrics), dtype=int)) e raggruppando con np.unique; qui si evita la conversione agli interi, che fallirebbe per un algoritmo che restituisce failure o cutoff (costo inf: int(inf) solleva OverflowError). Per esempio, sul problema c1 i nodi generati (metrica result) dei quattro algoritmi sono [1285, 40, 3590, 2951], e i costi [7, 7, 7, 7]; su r1 i costi sono [418, 450, 418, 450]: il grafico a barre dei costi mostra subito che A∗ e costo uniforme coincidono e che greedy e ampiezza pagano più di 30 km.

Altri problemi di lettura da tenere presenti per un confronto corretto:

• le etichette dei problemi sono troncate a 40 caratteri: restano distinte perché la parte che cambia è nei primi caratteri, ma è facile sbagliare con nomi più lunghi;
• l'ordine dei vicini nelle liste (la multimappa) influenza l'ordine di espansione a parità di punteggio, quindi i conteggi sono riproducibili solo con lo stesso ordine;
• depth_limited_search su c4 impiega circa due minuti (23 milioni di nodi): conviene escluderlo dai confronti rapidi.