Resolución de problemas a través de búsqueda

Agentes 

Los agentes más sencillos son los agentes reflejos, que basan sus acciones en un mapeo directo de estados a acciones.

Los agentes reflejos no pueden operar bien en ambientes en los cuales el mapeo de relaciones estado->acción es demasiado grande y toma demasiado tiempo aprender las relaciones.

Los agentes basados en metas consideran acciones futuras y el nivel en que los resultados de esas acciones resultan deseables.

Los agentes resolvedores de problemas usan representaciones atómicas - esto significa que los estados del mundo son considerados unidades enteras, cajas negras que no tienen estructura interna visible para los algoritmos resolvedores de problemas.

Para discutir la resolución de problemas es necesario definir con precisión a los problemas y sus soluciones. Existen varios algoritmos de búsqueda de propósito general que pueden ser usados para resolver problemas.

Algoritmos de Búsqueda Informados y No Informados

Los algoritmos de búsqueda no informados son aquellos que sólo reciben como información del problema su definición. Los algoritmos de búsqueda no informados pueden resolver cualquier problema que sea resoluble, pero ninguno de ellos puede hacerlo eficientemente, operan a manera de la fuerza bruta. Los algoritmos de búsqueda en profundidad (DFS - depth first search) y búsqueda en anchura (BFS - breadth first search) son algoritmos de búsqueda no informados, al igual que la búsqueda de costo uniforme (UCS - uniform cost search). Un algoritmo no informado sólo es capaz de distinguir entre un estado que sea meta y aquellos que no lo son. Un algoritmo no informado genera sucesiones de estados sin distinguir cuál de los siguientes estados es más prometedor para alcanzar la solución final.

Los algoritmos de búsqueda informada reciben cierta guía para saber dónde empezar a buscar soluciones, lo que, en muchos casos, aumenta la eficiencia en tiempo de cómputo. Estas guías son a menudo heurísticas que son derivadas de la observación cuidadosa del problema y tienden a ser específicas a él. El algoritmo A* ("A star" o "A estrella") es un algoritmo de búsqueda informada de caminos que comúnmente se implementa usando la heurística de Distancia Manhattan. Un algoritmo informado genera sucesiones a los estados en base a un criterio que determina cuales estados son más prometedores para alcanzar la solución final.

Fuente: AIMA, Capítulo 3.