Please enable JavaScript.
Coggle requires JavaScript to display documents.
FUNDAMENTO DE LOS SITEMAS INTELIGENTES - Coggle Diagram
FUNDAMENTO DE LOS SITEMAS INTELIGENTES
Representación y control
Proceso de Resolución de Problemas
Especificación de problema
Análisis el Problema
Aislamiento y Representación del Conocimiento
Representación
Corresponde con una posible configuración o situación del problema durante el proceso de resolución del mismo
Transformaciones
Convertir la situación actual del problema en otra
Control
Que secuencias de transformaciones aplicar y como efectuar la elección para alcanzar la resolución del problema
Maneras de realizar Resolución de Problemas mediante Exploración de Alternativas
Representación en Espacio de Estados
Procedimiento de resolución de problema
Tres estados
Inicial
Intermedio
Final u objetivo
Operador
Proceso o acción que aplicada sobre un estado lo convierte en otro
Espacio de Estados
Espacio que recoge todos los estados posibles de un problema
Procedimiento de Resolución de Problemas en el Espacio de estados
Aquel que determina una secuencia de aplicación de operadores tal en el espacio de estados que, partiendo del estado inicial consigue alcanzar el estado final, es decir, aquel que es capaz de determinar una trayectoria entre ambos estados
Solución al Problema
Trayectoria de estados que ligan el estado inicial con el final
Reducción de problemas
Búsqueda no Informada
Búsqueda Aleatoria
Búsqueda por Niveles (Anchura)
BFS
Visitar y expandir primero los nodos al mismo nivel
Características
Se usa la lista ABIERTA como cola FIFO
Uniformidad de la exploración
Interesante cuando el objetivo se prevé en un nivel próximo al la raíz
Completitud
Es completa. Garantiza que se encuentra la solución si esta existe
Optimalidad
Es óptimo. Siempre encuentra la solución más optima
Búsqueda en Profundiad
DFS
Visita hacia el nivel más profundo del árbol de búsqueda. En este caso, los nodos terminales que no son objetivo se descartan de memoria
Características
Se usa la lista ABIERTA como cola LIFO
En ciertos casos no hay vuelta atrás (backtracking)
Resultado muy dependiente del orden de aplicación de operadores
Completitud
No es completa. Puede no acabar nunca si encuentra una rama sin fin en el espacio de estados
Optimalidad
No es óptima
Búsqueda en Profundidad Acotada
Fija un límite máximo de profundidad o cota de profundidad
Completitud
Es completa
Optimalidad
No es óptima
Complejidad
Espacial: O(b*c)
Temporal O(b^c)
Búsqueda en Profundidad Iterativa
Secuencia de búsquedas sucesivas acotadas en profundidad, con cota
Completitud
Es completa
Optimalidad
Es óptima
Búsqueda Hacia Atrás
Partir de un estado objetivo y aplicar los operadores en orden inverso hasta alcanzar el estado inicial
Búsqueda Bidireccional
Búsquedas simultáneas por el estado inicial y por el estado objetivo
Búsqueda con Islas
Realizar búsquedas parciales de las trayectorias entre estados intermedios
EVALUACIÓN DE LAS ESTRATEGIAS DE BÚSQUEDA
Completitud
Se garantiza o no que se encuentra la solución si existe
Optimalidad
Caso de que existan diversas soluciones, se encuentra la óptima o no
Complejidad
Se estiman en el peor caso en función de algún parámetro del problema. En notación "Big O"
Espacial
(Cantidad de memoria necesaria)
Temporal
(Tiempo necesario)
Factor de Ramificación (b)
Número constante que indica la cantidad promedio de nodos b que se expanden a partir de uno padre dado
Ramificación y Acotación
(Branch-and-Bound)
Utilizar la información suministrada por una función de coste de cada trayectoria parcial
Completitud
Completo sobre árboles finitos
Optimalidad
si b es finito, coste >= exponencial
Ramificación y Acotación con Programación Dinámica
Trayectoria óptima, todas las subtrayectorias también lo son
Si en la lista de trayectorias recorridas existen varias que tienen el último nodo común, sólo la de menor coste podrá formar parte del a trayectoria óptima
Usa lista Abierta y Cerrada
Búsquedas Informadas
HEURÍSTICA
Criterios, métodos o principios para decidir cuál de entre diversos cursos de acción alternativos "promete" ser el más efectivo para alcanzar algún objetivo
Objetivo
Guiar al proceso de búsqueda visitando algunos nodos seleccionados según las siguientes estrategias:
Exploración ordenada
Ordenar las preferencias sobre los nodos en base a expectativas heurísticas de éxito
Poda
Eliminación de ciertas ramas heurísticamente poco adecuadas para la exploración
Características
Se basa en la experiencia y el sentido común
Es un principio y aproximadamente correcto
No garantiza que se vaya a encontrar la solución
Si la encuentra no asegura que sea óptima
En casos puede encontrar una buena solución en tiempo aceptable
Clasificación
Generales
De propósito Especial
Estrategia en Escalada
Ordenar los hijos en base a evidencias heurísticas y elegir en cada paso a uno de los descendientes del estado actual que mejore el valor heurístico de su padre
Sentido de la Escalada
El mejor el valor más alto
El mejor el valor más bajo
Variantes
Escalada Simple
Se generan los hijos uno a uno calculando su valor heurístico
El primer hijo que sea mejor que el estado actual se elige como sucesor y se convierte en el nuevo estado actual
Escalada por Máxima Pendiente
Se generan todos los hijos y se calcula su valor heurístico
Se escoge al mejor de los hijos
si es mejor o igual que estado actual, pasa a ser el nuevo estado actual
Si no, se detiene el proceso
No es óptimo ni Completo
Problemas
Máximos locales
Todos los hijos son peores que el padre
Mesetas
Todos los hijos tienen el mismo valor que el padre
Crestas
Mezcla de los dos anteriores
Estrategia Primero el Mejor (Best-First)
Combina anchura y profundidad guiándose por la heurística
Compleitud
Es completo
Optimalidad
No es óptimo
Estrategia por Haces (Beam-Search)
Exploración por Niveles (Anchura) pero en vez de explorar todas las ramas, explora un subconjunto podando el resto
Completitud
No es completo
Ramificación y Acotación con Subestimación
Mejorar Branch-and-Bound añadiendo una estima del coste hasta el nodo objetivo
Se combina conocimiento Determinista y conocimiento Heurístico
Estrategia A*
Mejorar Primero el Mejor introduciendo evaluación del camino recorrido junto a predicción del camino por recorrer como Ramificación y Acotación con subestimación y eliminando repeticiones como en Programación Dinámica
Es óptimo y completo si
Todo nodo tiene un número finito de sucesores
El coste de aplicación de cada operador es no negativo
La función h(e) es una heurística admisible
Exploración en juegos
Formalización
Estado
Inicial
Intermedio
Final
Gana (g)
Pierde (p)
Tablas (t)
Operador
Prueba de Finalización
Indica el final del juego
Función de Evaluación
Asigna un valor numérico a cada posición del juego
Función de utilidad
Evaluación sobre resultados del juego (posiciones finales)
Técnica de representación
Árbol alternado
Niveles
Nodos
Sucesores
Procedimientos
MINIMAX
Realizar una simulación limitada del juego con Estrategia basada en considerar un adversario hipotético
Combina
Exploración Restringida con una frontera de evaluación
Evaluación estática
Retropropagación de la evaluación
Seleccionar el mejor movimiento desde la raiz
Extensión Max^n
MINIMAX para múltiples jugadores
Para cada nodo se construye un vector de evaluaciones con dimensión igual al número de jugadores
Extensión para juegos con Azar
Incorporar un jugador ficticio, "el dado"
Los nodos asociados a "el dado" tienen por valor esperado los nodos sucesores
Propiedades
Completo
Sí, cuando el juego es finito
Óptimo
Sí, cuando el adversario juega perfectamente, en otro caso subóptimo
Complejidad temporal
O(b^m)
Complejidad espacial
O(b.m)
Poda Alfa-Beta
Modificar el MINIMAX intentado evitar la generación de todas las alternativas
Generar y evaluar simultáneamente
Arrastrando información adicional sobre el proceso
En los nodos MIN
Examinar primero los sucesores con Menor valor
En los nodos MAX
Examinar primero los sucesores con Mayor valor
Mejoras a ambos procedimientos
Efecto Horizonte
No se puede ver más allá del Horizonte, problema a largo plazo
Solución, búsqueda en profundidad variable
Uso de biblioteca de Movimientos
Consultar posición actual en un catálogo y recuperando el movimiento guardado
Profundización Iterativa
Expandir hasta profundidad p
Seleccionar el mejor movimiento
Si hay tiempo, estudiar k movimientos más
Al final del tiempo ejecutar el movimiento identificado en la búsqueda completa más profunda
Aumento de Podas en Alfa-Beta
Resolución de problemas mediante reducción
Árboles And/Or
Cada nodo representa un problema
Un nodo que no se puede descomponer es un nodo terminal
Un nodo terminal con solución es un Problema Primitivo o PRIMITIVA
Dado un nodo descomponible, si cada operador genera un conjunto de nodos de solución alternativa es un nodo OR
Si por el contrario, la resolución de todos es necesaria para resolver el padre, es un nodo AND
Agentes Inteligentes
Sistema que interactúa con su entorno
Percibe
Actúa
Realiza
Objetivos
Externos
Cambiar el estado del entorno
Internos
Estructura del estado del agente
Elementos Básicos para el Análisis basado en Agentes
PAOE (PAGE)
Percepciones
Acciones
Objetivos (Goals)
Entorno
Tipos de entorno
Accesible/Inaccesible
Determinista/No determinista
Episódico/No Episódico
Estático/Dinámico
Discreto/Contínuo
Función del Agente
Conducta
Historio o memoria
Agente Ideal
Agente Racional
Hace lo correcto
Es efectivo
La racionalidad depende de
La medida de rendimiento que define el grado de éxito
Lo que el agente ha percibido antes
Lo que el agente conoce del entorno
Las acciones que puede realizar el agente
Agente Racional Ideal
Agente que realiza las acciones que maximizan su medida de rendimiento
Agente Autónomo
Sentido Débil
Su comportamiento está dictado en base a su propia experiencia
Sentido Fuerte
Es capaz de interactuar con su entorno de manera independiente
Agente Inteligente
Agente capaz de acción autónomo flexible
Características
Reactividad
Capacidad para percibir y responder al entorno
Proactividad
Capacidad para exhibir conducta dirigida a objetivos
Habilidad social
Capacidad para interactuar con otros agentes
Tipos Básicos de Agentes
Agente Controlado por tabla
Mantiene en memoria una tabla con todas las secuencias perceptuales posibles
Ventajas
Puede parecer inteligente
Podemos conseguir agentes que hagan lo que queramos
Desventajas
Para cualquier cosa sencilla se requerirá una tabla grande
Resultaría muy costosa
El agente no sería totalmente autónomo
Agente Reflejo Simple
Se pueden resumir las tablas representando ciertas porciones de asociaciones entrada-salida mediante reglas
Agente Reflejo con estado (memoria)
A partir de un estado del mundo utiliza reglas para crear un estado nuevo que actualiza
Agente con Objetivos
Conocer los objetivos del sistema con información acerca del resultado de posibles acciones
Agentes Basados en Utilidad
Conseguir valorar las vías necesarias para poder alcanzar el objetivo