Fundamentos de Inteligencia Artificial: Búsqueda, Lógica y Algoritmos Genéticos

1. Fundamentos de la Búsqueda en Espacios de Estados

Un Estado (S) contiene la información necesaria para generar sucesores, comprobar la meta y calcular el coste. Para definirlo, debemos responder: ¿Qué cambia durante el problema? ¿Qué necesito para saber si puedo aplicar una acción? ¿Qué necesito para saber si he terminado? ¿Qué necesito para calcular el coste?

Ejemplo (Cajas): S = vector orden(i). Si orden(i) = -1, la caja no está colocada; si orden(i) = k, la caja está en la posición k.

Operadores (O)

Definidos por parámetros, precondiciones (cuándo aplicar), efectos (qué cambia) y coste. Ejemplo (Cajas): Apilar(i). Precondición: orden(i) = -1. Efecto: orden(i) <- t + 1. Coste: 1.

Factor de Ramificación (b)

Es el número de operadores instanciados aplicables desde un estado. b(s) depende de las restricciones del dominio. En una rejilla 4-conexa, el valor varía según la posición (esquinas 2, bordes 3, interior 4).

Tamaño del Espacio

Número de configuraciones posibles. Ejemplos: Permutaciones (N!), combinaciones (C(N,k)), binario (2^N) o asignación (M^N).

2. Algoritmos de Búsqueda

• No informados: BFS o IDDFS (costes unitarios), Coste Uniforme/Dijkstra (costes variables positivos).
• Optimalidad: BFS es óptimo en costes unitarios al explorar por niveles. DFS no garantiza optimalidad. El Coste Uniforme es óptimo al expandir siempre el nodo con menor g(n).
• IDDFS: Combina la optimalidad de BFS con el bajo consumo de memoria de DFS, aunque reexpande nodos.

3. Heurísticas y A*

Una heurística admisible no sobreestima el coste mínimo real restante (h(n) <= coste real). Se obtiene relajando restricciones del problema.

• A*: Utiliza f(n) = g(n) + h(n). Es óptimo si h es admisible. Se detiene cuando la meta sale de la lista ABIERTA.
• IDA*: Versión de DFS con umbral sobre f(n). Menor uso de memoria, pero mayor número de reexpansiones.

4. Lógica y Representación del Conocimiento

Lógica Proposicional

Representa hechos concretos mediante literales. No utiliza variables, lo que limita su escalabilidad en dominios complejos.

Lógica de Predicados

Utiliza variables y relaciones generales. Permite definir reglas reutilizables para cualquier objeto, depósito o tubería, facilitando la escalabilidad.

Marcos (Frames)

Estructuras basadas en clases, atributos, valores y herencia (ej. ROBOT es-un OBJETO).

5. Algoritmos Genéticos (AG)

Trabajan con una población de soluciones candidatas. Ciclo: Población → Fitness → Selección → Cruce → Mutación → Nueva población.

• Individuo: Codificación de la solución (binaria, permutación, etc.).
• Fitness: Función que evalúa la calidad (maximizar utilidad o minimizar coste).
• Cruce y Mutación: Operadores que deben preservar la validez de la solución.

6. Planificación con PDDL

Representa dominios mediante predicados, estado inicial, objetivo y acciones con precondiciones y efectos. Es fundamental gestionar correctamente los efectos negativos (ej. al mover un robot, eliminar su posición anterior).

7. Errores Comunes a Evitar

• No usar variables en lógica proposicional.
• No confundir DFS con algoritmos óptimos.
• No aplicar BFS en problemas con costes variables.
• No sobreestimar el coste en heurísticas de minimización.
• No olvidar los efectos negativos en PDDL.
• No detener A* al generar la meta, sino al extraerla de ABIERTA.