Programación Específica > Inteligencia Artificial

 Mejorar Algoritmo A*

(1/1)

Diodo:
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:



En este caso no las ve y hace el siguiente camino



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

hano:
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.

Diodo:
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

dannyv:
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?

Nebire:
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 ---  funcion determinar_ruta    pasosV= (y.destino - Y.origen) 'pasos verticales hacia destino    pasosH= (X.destino - X.origen) ' pasos horizontales hasta destino.     si pasosV > pasosH luego       avH=1' avance horizontal= 1       avV= pasosV / pasosH  ' avance vertical     en otro caso       avV=1                       ' avance vertical = 1       avH= pasosH / pasosV    fin sifin determinar_ruta funcion avanzar_ficha  meta=false  cinta=falsehacer    si avH = 1 luego         iterar  1 hasta avV             avanzar vertical ' 1 unidad             cinta= comprobar_Haycinta  ' se hace una llamada a esa función             meta= comprobar_Meta  ' comprueba si llegó a la meta               si (cinta=true)  o (meta = true) salir de iterar         fin iterar         si meta= false luego             avanzar horizontal ' 1 unidad               llamada a comprobar_Haycinta                meta= comprobar_Meta  ' comprueba si llegó a la meta            fin si    en otro caso         iterar  1 hasta avH             avanzar horizontal ' 1 unidad             cinta= comprobar_Haycinta  ' se hace una llamada a esa función             meta= comprobar_Meta  ' comprueba si llegó a la meta               si (cinta=true)  o (meta = true) salir de iterar         fin iterar         si meta= false luego              avanzar vertical ' 1 unidad                llamada a comprobar_Haycinta                meta= comprobar_Meta  ' comprueba si llegó a la meta            fin si    fin si    repetir mientras meta=false  ' (no encuentre final )  fin avanzar_ficha funcion comprobar_Haycinta    si se detecta cinta           llamada a avanzar_desdeCinta           llamada a determinar_ruta  ' actualiza según nueva posición           devolver true     fin sifin funcion funcion comprobar_Meta    si llegó a la meta luego        devolver true    fin sifin funcion  
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...

Navegación

[0] Índice de Mensajes