Avance 15-21 octubre

Guillermo encontró las bases para unos algoritmos de Value Iteration, Policy Iteration y Passive ADP Agent, los cuales se implementaron en Ruby y se subieron a la plataforma (Webtec) como avance de la semana. Estamos trabajando en determinar la manera en la que utilizaremos estos algoritmos para avanzar en nuestro proyecto y ver cómo direccionar las decisiones que necesite tomar nuestro agente en su búsqueda del objetivo.

Algoritmos, la primera prioridad

El principal contratiempo del equipo actualmente es la definición de un algoritmo que cumpla con todos los requisitos del viajero cognitivo. Existen múltiples áreas dentro de la misma inteligencia artificial que ofrecen soluciones potenciales, como el aprendizaje maquinal, la minería de datos y el reconocimienot de patrones. No obstante, la cantidad de información a investigar es vasta y es difícil discriminar aquella que no es relevante, ya que no se cuenta con bases sólidas en esta área del conocimiento.
Habiendo definido los algoritmos necesarios, el proceso de implementación será mucho más fluido y ameno. Mientras tanto, seguiremos invirtiendo tiempo en investigación, de modo que se eviten contratiempos en el futuro por una mala elección de técnica o un diseño precario.

Minuta octubre 10

Lluvia de ideas de lo discutido el día de hoy...

• Cada elemento va a tener un banco de propiedades
• El agente intentará guardar en un banco de conocimiento las propiedades y las intentará conectar.
• Necesitamos investigar sobre minería de datos y necesitamos establecer ciertas relaciones.
• Data mining y pattern recognition.

-> Hay que buscar algoritmos de minería de datos, luego buscar sobre que estructura de datos opera ese algoritmo y buscar al final qué lenguaje nos facilita el manejo de esas estructuras.

Investigación: Algoritmo A*

Investigación: Algoritmo A* Pathfinding

El algoritmo de búsqueda A* se usa para encontrar un camino desde un nodo inicial a un nodo meta, utilizando un conjunto de soluciones parciales, de las cuales se elige la mejor mediante una comparación de costos estimados.

El área de búsqueda

El usar una cuadrícula para representar relaciones espaciales facilita el desarrollo del algoritmo, pues los movimientos se limitan a verticales, horizontales y diagonales, es decir, el área de búsqueda se limita a una matriz bidimensional. Además, se podrá diferenciar entre aquellos cuadrados que representan “camino transitable” y los que representan “camino intransitable”, por ejemplo, agua o edificios.

Se almacena siempre el “cuadrado padre” de cada uno de los cuadrados que se van identificando como posibles alternativas a seguir, pues al final esto permitirá conocer los cuadrados que forman la ruta seleccionada.

La búsqueda

Se manejan los conceptos de “lista abierta” y “lista cerrada”.
La lista abierta contiene a los cuadrados que son considerados en cada uno de los movimientos.
La lista cerrada contiene a los cuadrados que no serán considerados en cada uno de los movimientos.

La búsqueda inicia con tres acciones:

1. El punto inicial se agrega a la lista abierta.
2. Se identifican todos los cuadrados adyacentes al punto inicial que sean transitables y se agregan a la lista abierta, con el punto de inicial como “cuadrado padre”.
3. El punto inicial se quita de la lista abierta y se agrega a la lista cerrada, pues ya no será considerado (ya que se está “pisando” actualmente).

La clave para determinar qué cuadrados deben recorrerse consiste en una ecuación: F = G + H.

• “G” representa el costo mínimo de movimiento para ir desde el cuadrado actual hacia uno de los cuadrados adyacentes. Una manera de fijar un costo para los movimientos verticales y horizontales, y un costo mayor para los movimientos diagonales (matemáticamente, la raíz cuadrada de la suma de dos cuadrados del costo vertical u horizontal).
• “H” representa una suposición simplificada del costo estimado para ir desde el cuadrado adyacente seleccionado hacia el punto meta. Se puede calcular de distintas maneras, una es el método Manhattan: se ignora si los cuadrados son transitables o no, y se cuentan los costos de ir desde el cuadrado seleccionado hacia el meta, pero sólo moviéndose vertical u horizontalmente.

Para continuar la búsqueda, se elige el cuadrado cuyo valor “F” sea menor y se realiza lo siguiente:

4. Se quita el cuadrado seleccionado de la lista abierta y se agrega a la lista cerrada.
5. Todos los cuadrados adyacentes que sean transitables y que no estén en la lista cerrada ni en la lista abierta, se agregan a la lista abierta y el cuadrado actual se vuelve su “padre”.
6. De los cuadrados adyacentes que ya estaban en lista abierta, se verifica si el nuevo camino (aquél que pasa por el cuadrado seleccionado) tiene un costo “G” menor que el que tenía anteriormente. Si lo tiene, se cambia su “cuadrado padre” al cuadrado actual, recalculando su costo “F”.

Este proceso se repite hasta que:

Se agregue a la lista cerrada el cuadrado del punto meta, en cuyo caso se ha logrado el objetivo.
No se encuentre el cuadrado del punto meta y la lista abierta está vacía (no hay más cuadrados a los que se pueda mover), en cuyo caso no existe un camino al punto meta.

Fuentes:
Lester, Patrick. A* pathfinding for beginners. Julio, 2005. http://www.policyalmanac.org/games/aStarTutorial.htm
A* search algorithm. Wikipedia. http://en.wikipedia.org/wiki/A*_search_algorithm

Modelo espiral en el proyecto

Identificación del Modelo Espiral en el proyecto “Viajero Cognitivo”

Iteraciones:

1. Representación de la información
Objetivos: Determinar una estructura de datos que permita representar relaciones espaciales.
Restricciones: En esta iteración no se busca optimizar rutas, sólo tener la estructura de datos que las represente.

2. Procesamiento de la información
Objetivos: Lograr cambios de representación interna de la información detonados por modificaciones directas que una persona haga, es decir, por datos ingresados como entrada.
Restricciones: No hay interacción del agente inteligente con el contexto, se busca que el cálculo de la ruta se vaya modificando a partir de datos entrada directos.

3. Interacción del agente inteligente con su ambiente
Objetivos: Lograr cambios de representación interna de la información detonados por el ambiente propio en el que se encuentra el agente inteligente, su contexto.
Restricciones: Ya hay interacción del ambiente con el contexto, pero éste aún no se guía por metas, sino por datos entrada directos.

4. Metas y toma de decisiones
Objetivos: El agente inteligente debe actuar de acuerdo a la meta que le haya sido planteada.
Restricciones: No se cuenta con interfaz gráfica.

5. Interfaz gráfica
Objetivos: Funcionamiento del agente inteligente en el contexto, con una interfaz gráfica que permita percibir visualmente los procesos de toma de decisiones, exploración y actuación.
Restricciones: N/A

Fases del Modelo Espiral

Las fases en el Modelo Espiral

El Modelo Espiral es iterativo: las cuatro fases son repetidas un número específico de veces.

En cada iteración se busca agregar algo más al proyecto, además de eliminar problemas, identificar riesgos y planear estrategias a seguir.

Para cada iteración habrá cuatro fases:

• Determinar objetivos

En la primera iteración: los objetivos, alternativas y restricciones del proyecto son determinados.
En las siguientes iteraciones: las especificaciones pueden sufrir ciertas modificaciones al momento de decidir qué estrategias utilizar durante la iteración actual.

• Análisis de riesgos

En esta fase todas las alternativas disponibles para desarrollar el proyecto son analizadas y se crean estrategias para utilizar la o las que se hayan seleccionado para reducir o eliminar los riesgos.

• Desarrollo

El desarrollo del proyecto se lleva a cabo en esta fase, así como las pruebas.

• Evaluación y planificación

En esta fase el producto desarrollado es evaluado por el cliente o usuarios finales.
Con la retroalimentación obtenida, se procede a planificar la siguiente iteración, si es necesaria.

Slides del libro de Inteligencia Artificial

Aquí va un enlace a la página con las presentaciones de Power Point del libro de:
Artificial Intelligence: A Modern Approach.

Para la entrega del lunes...

Plan de trabajo para el lunes antes de las 8 de la manana

PEAS Memo
SPIRAL Oscar
Entradas del BLOG Arturo
Resumen de Minutas Memo
Documentos de objetivos Memo
Documento de problemas de aprendizaje Oscar
Fuentes de informacion Arturo
Avance de investigacion Oscar
proyectos relacionados Arturo
Pseudocodigo Memo
Conceptos del capitulo 2 relacionados al proyecto Oscar
Compilacion Arturo

Definición del proyecto

Hola, el día de hoy empieza este blog en el que el Equipo 1 de la clase Ciencia cognitiva con la Dra. Ma. Elena Morín y el Dr. José Ignacio Icaza, comentará acerca del desarrollo del proyecto Viajero Cognitivo. Esperamos poder actualizarlo constantemente para mostrar nuestros avances, logros y problemas.

A continuación pongo un resumen de nuestro proyecto.

Equipo:
Arturo Garza
Guillermo Garza
Oscar Mendoza

Planteamiento del problema:
El proyecto a desarrollar consiste en la generación de rutas óptimas con base en experiencia previa. Se pretende programar un agente inteligente que sea capaz de almacenar relaciones espaciales del contexto en el que se encuentra. Cuando sea necesario encontrar un camino eficiente, éste utilizará su banco de representaciones y las combinará para obtener una solución.
Esto es una alternativa a uno de los problemas clásicos en ciencias computacionales, donde normalmente se recalculan las diferentes opciones en un determinado momento y después se elige el mejor postor. Se espera igualar o mejorar el rendimiento del algoritmo tradicional a través de esta aproximación cognitiva.
Con lo anterior, es posible plantear el problema a resolver como la obtención de una alternativa creativa al problema de la ruta más óptima. Se quiere hacer uso de los conceptos de memoria y experiencia para permitir a un agente ser más eficiente cada vez, con base en las búsquedas que ha hecho previamente y los elementos que conoce en un determinado momento.

Saludos,

Arturo