Busqueda

• Fonamental en molts dominis
  • Jocs, Planificació...
• Funciona molt bé en altres tipus de problemes
  • Diagnòstic, Control, Aprenentatge, ...
• És una tècnica molt general
  • Podem aplicar-la a problemes sense solució específica
  • Molt útil per aproximar
• Les tècniques de cerca són la base de molts sistemes intel·ligents

Busqueda en espais d'estats

• Els problemes de búsqueda tindran

  • Un estat inicial
  • Una funció de succesió
    • Defineix els estats successors d'un estat i el cost per arribar a aquests estats
  • Un estat final

• Una solució és una seqüència d'estats (un plà) que ens porten de l'estat inicial a l'estat final

Exemple: Viatjar per Romania

• Espai d'estats: Ciutats
• Funcio de succesió: Carreteres. Cost: Distància
• Estat inicial: Arad
• Comprovar si un estat és final: Estat = Bucharest
• Solució: Seqüència de ciutats que ens porten d'Arad a Bucharest

Exemple: Botelles d'aigua (I)

Tenim dues botelles d'aigua, una de 4 litres i una altra de 3 litres. Volem obtenir 2 litres d'aigua.
Podem omplir les botelles, buidar-les o trasvasar l'aigua d'una a l'altra.

• Espai d'estats: Estat de les botelles
• Funcio de succesió: Operacions de buidar, omplir i trasvasar
• Estat inicial: (0,0)
• Comprovar si un estat és final: Estat = (2,0)
• Solució: Seqüència d'operacions que ens porten de (0,0) a (2,0)

Exemple: Botelles d'aigua (II)

Observacions

• Tal com està formulat el problema, no poden haver-hi estats no enters.
• Alguns estats són impossibles d'aconseguir. Ex: (1, 2)
• Algunes accions no produeixen canvis.
  • Ex: (0,0) + buidar(4) = (0,0)

Exemple: Puzzle 8 (I)

Tenim un tauler de 3x3 amb 8 peces numerades del 1 al 8 i un espai buit.
Volem moure les peces per aconseguir l'estat final.

• Espai d'estats: -
• Funcio de succesió: -
• Estat inicial: -
• Comprovar si un estat és final: -
• Solució: -

Exemple: Puzzle 8 (II)

• Espai d'estats: Les diferents posicions de les peces. Quantes?
• Funcio de succesió: Podem moure la peça buida en les 4 direccions. Podem sempre fer els 4?
• Estat inicial: P.e. el de la figura anterior
• Comprovar si un estat és final: Verificar que les peces estan a la posició correcta.
• Solució: Seqüència de moviments que ens porten a l'estat final

Exemple: Puzzle 8 (III)

Observacions

• El nombre d'estats és molt gran: estats
• Solament quan la peça buida està al centre del tauler podem fer els 4 moviments
• No tots els estats tenen solució
• Hi ha moltes solucions
  • Quina és la millor?

Situacions més complicades

• En els exemples anteriors, de cada estat coneixíem
  • Els estats successors
  • El cost de cada estat successor
• En altres problemes els resultat de cada acció és incert
• Veurem técniques per tractar algunes d'aquestes situacions
  • Métodes probabilístics: assignar probabilitats als estats successors
  • Métodes de cerca adversarial: els estats successors són determinats per un oponent

Representació dels problemes de cerca

Arbres de cerca

• Els problemes de cerca es poden representar com un arbre
• Els nodes són els estats
• Les arestes són les accions
• Els costos són els pesos de les arestes
• Podem aplicar algorismes de cerca de camins mínims
• L'espai de cerca ha de ser finit

Exemple: Viatjar per Romania

• Els nodes ja visitats es mostren en gris
• Els oberts en blanc i els encara per visitar en linees discontínues.

Definició

• Els algorismes de cerca són algorismes de propòsit general

  • Poden ser aplicats a qualsevol problema de cerca
  • Els problemes de cerca són un cas particular dels problemes de camins mínims

• Sortida:

  • Una serie d'accions que ens porten de l'estat inicial a l'estat final
  • El resultat pot ser una solució òptima en cost, óptima en temps o no tindre cap tipus de garantia d'optimalitat.

Funcionament general

• Tindrem una llista d'estats coneguts pero per visitar anomenada frontera. Inicialment la frontera conté l'estat inicial.
• En cada iteració, agafarem un estat de la frontera, aplicarem la funció de succesió i afegirem els nous estats a la frontera.
  • Si l'estat és final, hem acabat.
  • Si la frontera està buida, no hi ha solució.
  • Per cada estat anotarem el seu pare, per poder reconstruir la solució.
• En cada iteració, podem aplicar una estratègia per decidir quin estat de la frontera agafem.

Exemple de funcionament (Alternativa I)

• Frontera: {Arad}. Objectiu: Bucharest

1. Obrim Arad: {Z<A>, T<A>, S<A>},

2. Obrim Sibiu: {Z<A>, T<A>, A<S,A>, O<S,A>, F<S,A>, R<S,A>}

3. Obrim Fagaras: {Z<A>, T<A>, A<S,A>, O<S,A>, R<S,A>, S<F,S,A>, B<F,S,A>}

4. Tenim la solució en la frontera. Cost: 140+99+211 = 450

Exemple de funcionament (Alternativa II)

1. Frontera: {Arad}. Objectiu: Bucharest
2. Obrim Arad: {Z<A>, T<A>, S<A>},
3. Obrim Sibiu: {Z<A>, T<A>, A<S,A>, O<S,A>, F<S,A>, R<S,A>}
4. Obrim R.V: {Z<A>, T<A>, A<S,A>, O<S,A>, R<S,A>, S<R,S,A>, P<R,S,A>, C<R,S,A>}
5. Obrim Pitesti: {Z<A>, T<A>, A<S,A>, O<S,A>, R<S,A>, S<R,S,A>, P<R,S,A>, C<R,S,A>, R<P,R,S,A>, C<P,R,S,A>, B<P,R,S,A>}
6. Tenim la solució en la frontera. Cost: 140+80+97+101 = 418

Exemple de funcionament

Observacions

• En aquest exemple, els estats són les ciutats
• Problemes:
  • Poden apareixer estats repetits en la frontera
  • També es poden produir cicles
• L'ordre de les ciutats en la frontera determinarà:
  • Si trobem o no la solució
  • El cost de la solució
  • El temps d'execució i l'espai de memòria necessari

Propietats dels algorismes de cerca

• Criteris per comparar algorismes de cerca
  • Completitud: Garantia de trobar una solució si existeix
  • Optimalitat: Garantia de trobar la solució òptima
  • Complexitat temporal: Temps d'execució
  • Complexitat espacial: Memòria necessària

Búsqueda no informada

Característiques

• No utilitza cap informació sobre el problema
• Aplica una estratègia de cerca fins que troba la solució
• Aquesta estratègia determina l'ordre en què s'exploraran els estats
• L'estrategia serà fixa, no pot canviar en funció del problema
• Alguns algorismes de cerca no informada:
  • Amplitud, Profunditat, Cost uniforme, Profunditat limitada, Profunditat iterativa

Búsqueda en amplitud

• Estrategia utilitzable quan totes les accions tenen el mateix cost
• Explora tots els estats a una profunditat abans d'explorar els estats a profunditat
• Garanteix trobar la solució òptima
• Definim la frontera com una cua (FIFO)
• Els estats ja visitats es guarden en una llista o conjunt (per evitar cicles)

Implementació

def cerca_amplada(estat_inicial):
    """Cerca en amplada en un problema."""
    frontera = collections.deque([estat_inicial])
    visitats = set()

    while frontera:
        estat = frontera.popleft()
        if estat in visitats:
            continue
        visitats.add(estat)

        if es_solucio(estat):
            return estat

        for succesor in succesors(estat):
            if succesor not in visitats:
                frontera.append(succesor)

Exemple: Botelles d'aigua (I)

• Estat inicial: (0,0) - Estat final: (2,*) o (*, 2)
• Funcio de succesió: Operacions de buidar, omplir i trasvasar

1. Frontera: [(0,0)].
2. Després d’extraure (0,0): [(3,0), (0,4)].
3. Després d’extraure (3,0): [(0,4), (3,4), (0,3)].
4. Després d’extraure (0,4): [(3,4), (0,3), (3,4), (3,1)].
5. El segon (3,4) es descartarà si ja s’ha visitat.
6. ...

Exemple: Botelles d'aigua (II)

• Representació de l'arbre de cerca
  • Cada node és un parell de valors (a,b) que representen l'estat de les botelles
  • La busca en amplitud explora l'arbre per nivells
  • Podem observar que solament s'explora un nombre molt reduït de tots els possibles estats

Propietats

Problemes

• La complexitat espacial és un problema real.
  • Per exemple, suposem que cada estat ocupa 1KB i que el factor de ramificació és 10.
  • Si la solució es troba a una profunditat de 10, l’últim nivell pot ocupar fins a 10 TB.
  • A profunditat 100, l’últim nivell pot contindre 10¹⁰⁰ estats.
  • A profunditat 1000, l’últim nivell pot contindre 10¹⁰⁰⁰ estats.
• Típicament, ens quedarem sense espai abans de quedar-nos sense temps.

Búsqueda en profunditat

• L'estratègia de cerca en profunditat és similar a la de cerca en amplitud
• Utilitza una pila (LIFO) en lloc d'una cua
• Aquesta estratègia no garanteix trobar la solució òptima
• L'algorisme arriva fins a una profunditat màxima i després retrocedeix fins a trobar un camí alternatiu

Implementació

def cerca_profunditat(estat_inicial):
    frontera = [(estat_inicial, (estat_inicial,))]
    while frontera:
        estat, cami = frontera.pop()
        if es_solucio(estat):
            return estat
        for succesor in succesors(estat):
            if succesor not in cami:
                frontera.append((succesor, cami + (succesor,)))
    return None

Exemple: Botelles d'aigua (I)

• Estat inicial: (0,0) - Estat final: (2,*) o (*, 2)
• Funcio de succesió: Operacions de buidar, omplir i trasvasar

1. Pila inicial: [(0,0)].
2. Després d’afegir (3,0) i (0,4), s’extrau (0,4) perquè la pila és LIFO.
3. Des d’aquest estat s’exploren successors que no estiguen ja en el camí actual.

Exemple: Botelles d'aigua (II)

• Representació de l'arbre de cerca
  • Cada node és un parell de valors (a,b) que representen l'estat de les botelles
  • La busca en profunditat explora l'arbre fins a trobar una solució
  • Si no troba una solució, torna enrere fins a trobar un camí alternatiu
  • Si hi ha branques infinites, l'algorisme pot no acabar mai

Propietats

Quan utilitzar-la?

• El temps de la cerca en profunditat depén de l’ordre dels successors i de la posició de la solució
• En cerca en arbre, la profunditat sol necessitar menys memòria que l’amplitud
• La cerca en profunditat és molt útil quan:
  • El factor de ramificació és molt gran
  • La solució es troba a una profunditat molt baixa
  • No ens importa trobar la solució òptima
  • Verifiquem que no es creen cicles

Búsqueda en profundidad limitada

• La cerca en profunditat limitada és una variant de la cerca en profunditat
• En aquest cas, la cerca s'atura quan s'arriba a una profunditat màxima
• Si la solució es troba a una profunditat , no es trobarà
• La cerca en profunditat limitada és completa si és suficientment gran
• Retorna un indicador de tall: si no hi ha més camins, la cerca iterativa pot acabar sense solució.
• Ens permet evitar el problema de la cerca en profunditat quan hi ha branques infinites

Implementació

def cerca_profunditat_limitada(estat_inicial, limit):
    frontera = [(estat_inicial, (estat_inicial,))]
    tall = False
    while frontera:
        estat, cami = frontera.pop()
        if es_solucio(estat):
            return estat, tall
        for succesor in succesors(estat):
            if succesor not in cami:
                if len(cami) - 1 < limit:
                    frontera.append((succesor, cami + (succesor,)))
                else:
                    tall = True
    return None, tall

Búsqueda en profundidad iterativa

• Solució al problema de la cerca en amplitud y la cerca en profunditat utilitzant una única estratègia
• La cerca en profunditat iterativa és una cerca en profunditat limitada amb creixent
• Comença amb i va incrementant fins a trobar la solució

Traçat de l'algorisme (I)

Traçat de l'algorisme (II)

Traçat de l'algorisme (III)

Implementació

def cerca_profunditat_iterativa(estat_inicial):
    limit = 0
    while True:
        solucio, tall = cerca_profunditat_limitada(
            estat_inicial, limit)
        if solucio is not None or not tall:
            return solucio
        limit += 1

Propietats

Búsqueda de cost uniforme

• En els exemples amb costos, succesors(estat) retorna parells (successor, cost).

• La cerca de cost uniforme és una variant de la cerca en amplitud

• En aquest cas, la frontera s'ordena segons el cost del camí a cada estat (cua de prioritat)

• Estats visitats: de manera iterativa, es van visitant tots els que tenen un cost menor que l'actual

• Sí totes les accions tenen el mateix cost, la cerca de cost uniforme és equivalent a la cerca en amplitud

Exemple: Viatjar per Romania (I)

• Estat inicial: Arad
• Funcio de succesió: Carreteres.
• Cost: Distància entre ciutats (en Km)
• Comprovar si un estat és final: Estat = Bucharest
• Solució: Seqüència de ciutats que ens porten d'Arad a Bucharest

Exemple: Viatjar per Romania (II)

• Representació de l'arbre de cerca
  • Cada node és un parell de valors (a,b) que representen l'estat de les botelles
  • La busca en amplitud explora l'arbre per nivells
  • Podem observar que solament s'explora un nombre molt reduït de tots els possibles estats

Implementació

import heapq

def cerca_cost_uniforme(estat_inicial):
    """Cerca de cost uniforme en un problema."""
    frontera = [(0, estat_inicial)]
    visitats = set()

    while frontera:
        cost_actual, estat = heapq.heappop(frontera)

        # La frontera pot contenir el mateix estat més d'una vegada.
        if estat in visitats:
            continue

        visitats.add(estat)

        if es_solucio(estat):
            return estat

        for succesor, cost_accio in succesors(estat):
            if succesor not in visitats:
                heapq.heappush(frontera, (cost_actual + cost_accio, succesor))

Propietats

Gestió de fronteres

• La gestió de fronteres és un problema important en els algorismes de cerca
• Els algorismes que hem vist son tots molt semblants, la diferència està en com gestionen la frontera
  • Conceptualment sempre es tracta d'una cua amb prioritat
  • En la pràctica, per a les busquedes en profunditat i amplada podem utilitzar una cua o una pila
    • Per estalviar-nos el sobrecost d' de la cua de prioritat
  • Podriem, fins i tot, programar una implementació on pugam variar l'objecte frontera.

Definició

• L'algorisme de búsqueda de cost uniforme és un algoritme molt eficient, té, però alguns problemes
  • Busca en totes les direccions, sense tenir en compte la direcció cap a la solució
  • Per tant, analitza més estats dels que seria estrictament necessari
• En aquesta part de la unitat veurem técniques per solucionar aquestos problemes

Heurístiques

• Una heurística és:
  • Una funció que ens permet estimar el cost d'arribar a la solució des d'un estat
  • Dissenyada per un problema concret
• Heurístiques per rutes:
  • Distància en línia recta (euclidiana)
  • Distància manhattan

Exemple: Viatjar per Romania

• Heurística: Distància en línia recta (euclidiana)

Búsqueda voraç

• Si solament utilitzem la heurística per decidir quin estat de la frontera seguim:
  • Búsqueda voraç
  • Més eficient que la búsqueda de cost uniforme
  • No garanteix trobar la solució òptima
    height:330px
    

Búsqueda voraç

• En verd la ruta correcta i en roig la nostra
• Que podem fer perqué el nostre algorisme trobi la solució correcta?

Implementació

import heapq

def cerca_voraç(estat_inicial):
    """Cerca voraç en un problema."""
    frontera = [(0, estat_inicial)]
    visitats = set()

    while frontera:
        cost_actual, estat = heapq.heappop(frontera)
        visitats.add(estat)

        if es_solucio(estat):
            return estat

        for succesor, cost in succesors(estat):
            if succesor not in visitats:
                heapq.heappush(frontera, (heuristica(succesor), succesor))

Propietats

A*

• L'algorisme A* és una combinació de la búsqueda de cost uniforme i la búsqueda voraç
  • La búsqueda de cost uniforme ordena pel cost del camí o cost cap enrere:
  • La búsqueda voraç ordena pel cost de la heurística o cost endavant:
  • L'algorisme A* ordena per la suma dels dos:
  • El cost real recorregut sempre és ; només serveix per ordenar la frontera

Amb heurística consistent i costos no negatius, aquesta implementació troba una solució òptima.

Exemple: Viatjar per Romania (I)

Exemple: Viatjar per Romania (II)

Exemple: Viatjar per Romania (III)

Implementació

import heapq

def cerca_a_estrella(estat_inicial):
    """Cerca A* en un problema."""
    frontera = [(h(estat_inicial), 0, estat_inicial)]
    visitats = set()

    while frontera:
        _, cost_actual, estat = heapq.heappop(frontera)

        if estat in visitats:
            continue

        visitats.add(estat)

        if es_solucio(estat):
            return estat, cost_actual

        for succesor, cost_accio in succesors(estat):
            if succesor not in visitats:
                nou_cost = cost_actual + cost_accio
                prioritat = nou_cost + h(succesor)
                heapq.heappush(frontera, (prioritat, nou_cost, succesor))

Propietats

Condició: Aquestes propietats es compleixen si la heurística és consistent (com la distància en línia recta de Romania).

Connexió amb l'exercici de Romania

• Podem ponderar la heurística amb
  • : cerca de cost uniforme
  • : A* amb heurística admissible
  • : A* ponderat; explora menys estats, però pot perdre optimalitat i apropar-se a la cerca voraç
• Prova-ho a l'exercici de Romania comparant els pesos 0, 1, 2 i 100.

Heurístiques admissibles (I)

• Una heurística és admissible si:
  • No sobreestima el cost de la solució
  • És a dir, si el cost real de la solució és , la heurística és admissible si
• Si la heurística NO és admissible:
  • L'algorisme A* és equivalent a la búsqueda voraç
• Trobar una heurística admissible és un problema difícil.

Exemple: Puzzle 8 (I)

• Técnica útil redüir el problema a un problema més senzill
• Relaxació de les regles del joc
  1. Permetre que les peces s'intercanviïn entre elles
  2. Permetre que les peces es moguin a qualsevol posició, si està buida
  3. Permetre que les peces es moguin a qualsevol posició, sense restriccions (1+2)

Exemple: Puzzle 8 (II)

• La primera opció ens porta la heurística distància manhattan
  • Equival a un problema on hem de lliscar les peces fins a la seva posició.
  • Suma de les distàncies horitzontals i verticals de cada peça a la seva posició final
  • És admissible perquè no sobreestima el cost de la solució
• La tercera opció ens porta la heurística nombre de peces fora de lloc
  • Equival a un problema on hem de deixar directament en la seva posició.
  • Suma de les peces que no estan a la seva posició final
  • És admissible perquè no sobreestima el cost de la solució

Propietat Óptima de les heurístiques admissibles (I)

• Si és una ruta óptima fins a amb cost .
  • serà una ruta subòptima fins a amb cost , sent > .
  • serà una subpart de la ruta òptima desde la frontera
• Es possible que agafem abans d'?.
  • No, perquè > i > , perquè la heurística és admissible
  • Així, > >
• Les subrutes en la ruta òptima sempre seran més barates que en la ruta subòptima

Propietat Óptima de les heurístiques admissibles (II)

• A* explora els nodes en ordre creixent de
• Va agregant, de forma gradual, corves de nivell de grau
• Cada corba de nivell representa un conjunt de nodes amb un valor d' inferior a un valor concret

Propietat Óptima de les heurístiques admissibles (III)

• Si tenim dues heurístiques admissibles i , amb per a tots els estats
• Llavors, és més informativa que
• Per tant, serà més eficient que
• Es per això que, preferirem l'heurística Manhattan a l'heurística de peces fora de lloc

Limitacions de l'algorisme A*

• Amb una heurística adequada, A* pot explorar menys estats que la cerca de cost uniforme
• Però, l'algorisme A* té dues limitacions:
  • Espai de memòria: L'espai de memòria necessari pot ser molt gran
  • Temps d'execució: El temps d'execució pot ser molt gran
• Per això, s'han desenvolupat variants de l'algorisme A* que intenten millorar aquestes limitacions
• En aquesta unitat veurem dues:
  • A* de profunditat iterativa
  • A* ponderat

A* de profunditat iterativa

• L'algorisme A* de profunditat iterativa és una variant de l'algorisme A*
• Molt semblant a l'algorisme de profunditat iterativa
  • Utilitza la funció per tallar, en compte de la profunditat
• Ens permet reduir l'espai de memòria necessari
  • A costa de tindre que visitar alguns nodes més d'una vegada

Implementació (I)

def cerca_a_limitada(estat, g, limit, cami):
    f = g + h(estat)
    if f > limit:
        return None, f
    if es_solucio(estat):
        return cami[:], f
    proxim_limit = float("inf")
    for succesor, cost in succesors(estat):
        if succesor in cami:
            continue
        cami.append(succesor)
        solucio, valor = cerca_a_limitada(
            succesor, g + cost, limit, cami)
        cami.pop()
        if solucio is not None:
            return solucio, valor
        proxim_limit = min(proxim_limit, valor)
    return None, proxim_limit

Implementació (II)

def cerca_a_iterativa(estat_inicial):
    limit = h(estat_inicial)
    while limit < float("inf"):
        solucio, seguent = cerca_a_limitada(
            estat_inicial, 0, limit, [estat_inicial])
        if solucio is not None:
            return solucio
        limit = seguent
    return None

A* Ponderat

Definició

• L'algorisme A* ponderat és una variant de l'algorisme A*
• Es defineix un factor de ponderació que determina el pes de la heurística
• L'algorisme A* ponderat ordena per
• Si , l'algorisme A* ponderat és equivalent a l'algorisme A*
• Si , l'algorisme A* ponderat és s'apropa a la búsqueda voraç

Utilitat

• L'algorisme A* ponderat és útil per:
  • Reduir el cost de l'espai de memòria
  • Reduir el cost de l'espai de temps
  • A costa d'una solució no tan òptima
• En l'exemple de la dreta en una (la b)
  • S'estudien 7 vegades menys estats
  • Per una solució un menys eficient

Implementació

import heapq

def cerca_a_ponderat(estat_inicial, epsilon):
    frontera = [(epsilon * h(estat_inicial), 0, estat_inicial)]
    costos = {estat_inicial: 0}
    while frontera:
        _, cost_actual, estat = heapq.heappop(frontera)
        if cost_actual != costos[estat]:
            continue
        if es_solucio(estat):
            return estat, cost_actual
        for succesor, cost in succesors(estat):
            nou_cost = cost_actual + cost
            if nou_cost < costos.get(succesor, float("inf")):
                costos[succesor] = nou_cost
                prioritat = nou_cost + epsilon * h(succesor)
                heapq.heappush(frontera, (prioritat, nou_cost, succesor))
    return None

Anytime A*

• Podem aprofitar l'algorisme A* ponderat per construir un algorisme Anytime A*
  • Busquem una primera solució amb un gran, que pot no ser òptima
  • Anem reduint fins a que
  • Així, obtenim una bona solució en un temps raonable
    • Si tenim temps, podem seguir buscant una solució millor, fins arribar a la solució òptima

Implementació

def cerca_anytime_a(estat_inicial):
    millor_cost = float("inf")
    for epsilon in (8, 4, 2, 1):
        solucio = cerca_a_ponderat(estat_inicial, epsilon)
        if solucio is not None and solucio[1] < millor_cost:
            millor_cost = solucio[1]
            yield solucio

Demostració de búsquedes

Pac-Man

https://www.youtube.com/watch?v=2XjzjAfGWzY