Fecha de clase: 9 de Octubre 2014
INTRODUCCIÓN
Esta fue una de las primeras clases del semestre iniciando
con un tema muy interesante como son los agentes resolventes de problemas y
árboles de búsqueda para la resolución de problemas en la IA; esto nos muestra
que hay agentes artificiales capaces y aptos para actuar de acuerdo a su
entorno.
Como ya lo
sabemos el objetivo principal de la Inteligencia Artificial es que las máquinas
sean capaces de obtener un comportamiento automático es decir que tomen
decisiones por si mismos.
MARCO TEÓRICO
La comunidad de IA especializada en planificación se ha
preocupado del problema de diseño de agentes artificiales capaces de actuar en
un entorno.
La planificación se puede ver como una forma de programación automática.
Dentro de la comunidad de la IA simbólica, se ha asumido desde hace tiempo
que algún tipo de sistema debe formar parte de los componentes centrales de
cualquier agente artificial.
La idea básica es dotar al agente planificador:
- Representación del objetivo a alcanzar
- Representación de las acciones que puede realizar
- Representación del entorno
- Capacidad de generar un plan para alcanzar el objetivo
Un plan es una secuencia (lista) de acciones, que llevan de un estado
inicial a un estado final. La planificación se puede ver como un problema de
búsqueda en un espacio de estados. (Vazquez, J)
PROBLEMAS DEL MUNDO REAL
Hemos visto como el (roblona de busqueda de una ruta esta
definido en terminos de posiciones y transiciones a lo largo de ellas. Los
algoritmos de busqueda de rutas se han utilizado en una variedad de
aplicaciones, tales como rutas en redes de computadores, planificacion de
operaciones militares, y en sistemas de planificacion de viajes de lineas aereas.
Estos problemas son complejos de especificar. Consideremos un ejemplo simplificado
de un problema de viajes de lineas aereas que especificamos como:
• Estados: cada estado esta representado por una localizacion (por ejemplo, un
aeropuerto) y la hora actual.
• Estado uncial: especificado por el problema.
• Fumian sucesor: devuelve los estados que resultan de tomar cualquier vuelo programado (quiza
mas especificado por la clase de asiento y su posicion) desde el aeropuerto
actual a otro, que salgan a la hora actual mas el tiempo de transito del aeropuerto.
• Test objetivo: .tenemos nuestro destino para una cierta hora especificada?
• Costo del camino: esto depende del costo en dinero, tiempo de espera, tiempo del vuelo,
costumbres y procedimientos de la inmigracion, calidad del asiento, hora, tipo
de avion, kilometraje del aviador experto...(Russell, S y Norvig, P)
BUSQUEDA DE SOLUCIONES
Hemos formulado algunos problemas, ahora necesitamos
resolverlos. Esto se hace mediante busqueda a traves del espacio de estados.
Este capitulo se ocupa de las tecnicas de busqueda que utilizan un arbol de
busqueda explicito generado por el estado inicial y la funcion sucesor,
definiendo asi el espacio de estados.
MEDIR EL RENDIMIENTO DE LA RESOLUCIÓN DEL PROBLEMA
La salida del algoritmo de resolución de problemas es fallo o una solución.
Evaluaremos el rendimiento de un algoritmo de cuatro formas :
·
Completitud : ¿ está garantizado que el algoritmo encuentre una solución cuando esta
exista?
·
Optimización: ¿encuentra la estrategia la solución óptima , según lo definido en la
página 62 ?
·
Complejidad en tiempo: ¿cuánto tarda en encontrar una solución?
·
Complejidad en espacio: ¿cuánta memoria se necesita para el funcionamiento de la busqueda?
ESTRATEGIAS DE BUSQUEDA NO INFORMADA
El término significa que ellas no tienen información
adicional acerca de los estados más allá de la que proporciona la definición
del problema. Todo lo que ellas pueden hacer es generar los sucesores y distinguir
entre un estado objetivo. (Russell, S y
Norvig, P)
BUSQUEDA
PRIMERO EN ANCHURA
La búsqueda en anchura prioritaria intenta explorar el
espacio de búsqueda haciendo un recorrido por niveles, de manera que un nodo se
visita solamente cuando todos sus predecesores y sus hermanos anteriores en
orden de generación ya se han visitado.
Para obtener este algoritmo solo hemos de instanciar
la estructura que guarda los nodos abiertos a una cola, en el algoritmo general
de búsqueda que hemos visto en el capítulo anterior. Esta estructura nos
consigue que se visiten los nodos en el orden que hemos establecido.
BUSQUEDA
PRIMERO EN PROFUNDIDAD
Esta estrategia intenta seguir un camino hasta la mayor profundidad
posible, retrocediendo cuando acaba el camino y retomando la última posibilidad
de elección disponible.
El principal problema de este algoritmo es que no acaba si existe la
posibilidad de que hayan caminos infinitos. Una variante de este algoritmo que
evita este problema es el algoritmo de profundidad limitada (Búsqueda en
profundidad prioritaria), éste impone un límite máximo de profundidad que
determina la longitud máxima de los caminos recorridos. Esta limitación
garantiza que el algoritmo acaba, pero no garantiza encontrar la solución, ya
que ésta puede estar a mayor profundidad que el límite impuesto. (UNIVERSITAT
POLITÉCNICA DE CATALUNYA)
CONCLUSIÓN
Los agentes que planifican son muy importante ya que
por medio de la programación hace que las máquinas tengan comportamientos que
solucionen problemas de manera rápida a comparación al que lo hace un ser
humano, claro está que el equipo no va a resolver el problema al 100% como lo
solucionaría una persona pero si cumple algunas normas que el ser humano como
tal no tomaría en cuenta. Las estrategias de búsqueda para la búsqueda no
informada son de vital importancia para la solución de los problemas a
proponer.
BIBLIOGRAFÍA
Russell, S y Norvig, P. 2004. INTELIGENCIA ARTIFICIAL. UN ENFOQUE MODERNO. Segunda edición. PEARSON
EDUCATION, S.A. Impreso en España.
UNIVERSITAT
POLITÉCNICA DE CATALUNYA, 2013. Departament de Llenguatges i Sistemes
Informátics. APUNTS D’INTEL.LIGE`NCIA ARTIFICIAL. Formato (PDF). Disponible en:
http://www.lsi.upc.edu/~bejar/ia/material/teoria/ApuntesIA.pdf
Vazquez, J. 2011. Agentes
Planificadores. Formato PDF. (En línea). Consultado el 22 de oct. Disponible en
http://www.lsi.upc.edu/~jvazquez/teaching/iag/transpas/4-PL1
