Búsqueda

• Pasos en el proceso de búsqueda
  • transformación de objetivo: un objetivo como un conjunto de estados
  • formulación del problema: elegir operadores y espacio de estado
  • búsqueda
  • ejecución
• Tipos de problemas
  • problemas de estado único: el estado siempre se conoce con certeza
  • problemas de estado múltiple: se sabe en que estados puede estar
  • problemas de contingencia: se construyen planes con partes condicionales, basadas en sensores
  • probemas de exploración: el agente debe aprender el efecto de las acciones
• Definición formal de problema
  • estados inicial (o conjunto de estados)
  • conjunto de operadores
  • test del objetivo
  • coste del camino
• Problemas ejemplo
  • Dominios juguete
    • 8-puzzle
    • 8-reinas, n-reinas
    • criptoaritmética
    • vacuum world
    • misioneros y caníbales
  • Dominios reales
    • el problema del viajante
    • VLSI layout
    • navegación de robots
    • secuencias de ensamblaje
• Problema ejemplo: torre de Hanoi
  • estado inicial: los tres discos están en la clavija 1 con el mayor abajo y el más pequeño arriba
  • conjunto de operadores: el disco de arriba de una clavija se coloca en una clavija que no contenga un disco más pequeño
  • test del objetivo: función que chequea si el estado es el final (los tres discos están en la clavija 3 con el mayor abajo y el más pequeño arriba
  • coste del camino: cada operados coste cte. 1

• Medida de rendimiento
  • ¿encuentra una solución?
  • ¿cual es el coste de la búsqueda
  • ¿cual es el coste total (coste camino + coste búsqueda)?
  • quitar detalles innecesarios de la representación para que sea mas barato encontrar una solución
• Búsqueda de soluciones
  • expansión del estado actual (con un operador)
  • estrategia de búsqueda: ¿próximo estado a expandir?
  • árbol de búsqueda
    • estructuras de datos
    • frontera: encontrar los estados a expandir (cola)
• Estrategias de búsqueda
  • no informadas, ciegas
  • informadas, heurísticas
• En cualquier caso se necesitan restricciones que mantengan la búsqueda en un tamaño manejable