SoloCodigo

Programación Específica => Inteligencia Artificial => Mensaje iniciado por: Diodo en Domingo 9 de Diciembre de 2007, 12:22

Título: Mejorar Algoritmo A*
Publicado por: Diodo en Domingo 9 de Diciembre de 2007, 12:22
Hola a todos

Tengo el siguiente problema. Estoy intentando implementar un A* en un mapa tablero donde un robot debe llegar a una meta. En el mapa existen cintas transportadoras que te avanzan 1 casilla mas en cada ciclo.
La duda que tengo es que no se como hacer que el robot aproveche las cintas, ya que solo las ve si pasa por un nodo vecino. Ejemplo:

En este caso si las ve y hace el siguiente camino:

(http://es.geocities.com/soyminero1980/c1.JPG)

En este caso no las ve y hace el siguiente camino

(http://es.geocities.com/soyminero1980/c2.JPG)

Habia pensado en prolongar de alguna manera el posible camino beneficioso de las cintas. Pero no se que manera seria la correcta

Alguien sabe alguna buena manera de que el robot aproveche las cintas ??

Muchas gracias ¡¡¡

Un saludo
Título: Re: Mejorar Algoritmo A*
Publicado por: hano en Domingo 9 de Diciembre de 2007, 13:56
Supongo que estarás usando alguna heurística como la distancia Manhattan... ¿Has probado a cambiar la heurística de tal forma que recoja la existencia de las cintas? De alguna forma, que las cintas que acerquen al destino resten distancia total, y las cintas que alejen del destino incremente aún más la distancia.
Título: Re: Mejorar Algoritmo A*
Publicado por: Diodo en Domingo 9 de Diciembre de 2007, 14:33
Hola

Si estoy usando la distancia manhattan pero el problema no es de heuristica.

El problema es que el robot nunca ve (o explorara) la casilla de la cinta si no esta al lado( a 1 casilla de distancia) que es donde se cogen los nodos vecinos

gracias
Título: Re: Mejorar Algoritmo A*
Publicado por: dannyv en Jueves 20 de Diciembre de 2007, 22:12
y si en lugar de utilizar la distancia manhattan utilizas la distancia euclidiana desde el origen al destino. En ese caso tal vez el robot podria moverse hacia las cintas?
Título: Re: Mejorar Algoritmo A*
Publicado por: Nebire en Miércoles 23 de Abril de 2008, 00:04
Evidentemente si no ve las cintas más que aun paso de distancia la cosa no promete.

En ese caso lo que se debe hacer es buscar un algoritmo que garantice el mayor éxito posible para encontrar cintas en el camino. Esto es debes garantizar una trayectoria en línea recta desde el origen hacia el destino, en el caso que presentas, describiría una diagonal y además encontraría la cinta. Si no encuentra una cinta seguirá tardando el mismo costo que el otro camino que te describe, la línea recta lo que verifica es la posibilidad de que en su camino directo esté una cinta.

el algoritmo sería un avance vertical y un avance horizontal mientra no vea cinta así :

Código: Text
  1.  
  2.  
  3. funcion determinar_ruta
  4.     pasosV= (y.destino - Y.origen) 'pasos verticales hacia destino
  5.     pasosH= (X.destino - X.origen) ' pasos horizontales hasta destino.
  6.  
  7.     si pasosV > pasosH luego
  8.        avH=1' avance horizontal= 1
  9.        avV= pasosV / pasosH  ' avance vertical
  10.     en otro caso
  11.        avV=1                       ' avance vertical = 1
  12.        avH= pasosH / pasosV
  13.     fin si
  14. fin determinar_ruta
  15.  
  16. funcion avanzar_ficha
  17.   meta=false
  18.   cinta=false
  19. hacer
  20.     si avH = 1 luego
  21.          iterar  1 hasta avV
  22.              avanzar vertical ' 1 unidad
  23.              cinta= comprobar_Haycinta  ' se hace una llamada a esa función
  24.              meta= comprobar_Meta  ' comprueba si llegó a la meta  
  25.              si (cinta=true)  o (meta = true) salir de iterar
  26.          fin iterar
  27.          si meta= false luego
  28.              avanzar horizontal ' 1 unidad  
  29.              llamada a comprobar_Haycinta  
  30.              meta= comprobar_Meta  ' comprueba si llegó a la meta  
  31.          fin si
  32.     en otro caso
  33.          iterar  1 hasta avH
  34.              avanzar horizontal ' 1 unidad
  35.              cinta= comprobar_Haycinta  ' se hace una llamada a esa función
  36.              meta= comprobar_Meta  ' comprueba si llegó a la meta  
  37.              si (cinta=true)  o (meta = true) salir de iterar
  38.          fin iterar
  39.          si meta= false luego
  40.               avanzar vertical ' 1 unidad  
  41.               llamada a comprobar_Haycinta  
  42.              meta= comprobar_Meta  ' comprueba si llegó a la meta  
  43.          fin si
  44.     fin si
  45.     
  46. repetir mientras meta=false  ' (no encuentre final )
  47.  fin avanzar_ficha
  48.  
  49. funcion comprobar_Haycinta
  50.     si se detecta cinta
  51.            llamada a avanzar_desdeCinta
  52.            llamada a determinar_ruta  ' actualiza según nueva posición
  53.            devolver true
  54.      fin si
  55. fin funcion
  56.  
  57. funcion comprobar_Meta
  58.     si llegó a la meta luego
  59.         devolver true
  60.     fin si
  61. fin funcion
  62.  
  63.  

Naturalmente avanzar horizontal y vertical será si puede avanzar, puesto que es posible que alcance un tope antes de lograr la meta... eso ya lo dejo a tu entretenimiento

Para hacer un algorimo más eficiente sería necesarios saber más detalles ¿ las cintas se colocan aleatoriamente ?, ¿ existen más cintas de solo 1 ?, ¿ se pueden mover ?, también si una cinta retrocede... o te aleja más que donde estabas y como comentas si es posible variar su tamaño.

El algortimo presentado se basa en la estadística del problema matemático si lanzamos una aguja al aire y tenemos 1 línea trazada en el suelo que posiblidad hay que quede atravesando la línea...