Mejorar A* y que el robot aproveche cintas transportadoras

[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

[tamat]

La unica solucion que se me ocurre es que en lugar de computar el camino a la salida computes tambien el camino a la casilla mas cercana de la cinta, y repitas la busqueda a la salida, si da un camino mas rapido sumado al coste de llegar hasta la cinta pues ya está.

El problema es cuando haya más de una cinta.

Tal vez A* no sea lo mas apropiado para este caso. O quiza debas marcar las zonas cercanas a una cinta con un peso ligeramente menor.

[Warchief]

Es perfecto. Simplemente disminuye el coste de recorrer una casilla con cinta. Si el coste de recorrer una casilla normal es 1, el de una con cinta 0.5 o algo así (las funciones de coste y de heurística dependen del dominio). O si pasar por una cinta no consume electricidad del robot y eso es bueno, entonces el coste es 0. Verás como las usa.

Prueba en http://www.vision.ee.ethz.ch/~cvcourse/astar/AStar.html . Pon las casillas normales como "Tough", y las de cinta como "Easy". Pon los puntos de entrada y salida, y dale a ver.

[Diodo]

Hola de nuevo

La unica solucion que se me ocurre es que en lugar de computar el camino a la salida computes tambien el camino a la casilla mas cercana de la cinta, y repitas la busqueda a la salida, si da un camino mas rapido sumado al coste de llegar hasta la cinta pues ya está.

El problema es cuando haya más de una cinta.

Tal vez A* no sea lo mas apropiado para este caso. O quiza debas marcar las zonas cercanas a una cinta con un peso ligeramente menor.

Gracias tamat
Creo que lo que comentas de ampliar la zona de influencia de la cinta sera la mejor solucion
Que otros algoritmos podria aplicar ademas del a*? las busquedas en profundidad y anchura consumen mucho tiempo no?

Es perfecto. Simplemente disminuye el coste de recorrer una casilla con cinta. Si el coste de recorrer una casilla normal es 1, el de una con cinta 0.5 o algo así (las funciones de coste y de heurística dependen del dominio). O si pasar por una cinta no consume electricidad del robot y eso es bueno, entonces el coste es 0. Verás como las usa.

Prueba en http://www.vision.ee.ethz.ch/~cvcourse/astar/AStar.html. Pon las casillas normales como "Tough", y las de cinta como "Easy". Pon los puntos de entrada y salida, y dale a ver.

Gracias Warchief

El problema que tengo es que tambien tengo en cuenta la direccion del robot por ese motivo pasa de la cinta, ya que girar hacia abajo cuesta 2 turnos, mientras que avanzar solo 1 y el coste de h (distancia manhattana la meta) es el mismo para los 2.
La direccion la tengo en cuenta por que hay cintas que ademas de trasladar al robot, lo hacen rotar.

El ejemplo de la pagina esta curioso. Lo que no entiendo es por que analiza todas las casillas ??

De nuevo gracias a los 2 por la ayuda

saludos

[Zaelsius]

Repasando la teoría.. para que A* devuelva siempre el camino óptimo, h() debería devolver el coste del camino de coste mínimo desde el nodo actual a la meta. h() es la heurística.

h() debe ser siempre optimista( devuelve la menor distancia posible, o una menor a ésta) para que A* halle el resultado óptimo.

Si usas Manhattan como heurística(distancia del camino mínimo sin obstáculos), no estás teniendo en cuenta las casillas cintas transportadoras, y h() deja de ser optimista.

Creo que deberías cambiar tu función h() por una más compleja. Se me ocurre que podrías devolver el coste del camino en zig-zag mínimo, examinando cada celda, claro.

[Esgaroth]

Si el robot vé solo las celdas adyacentes, entonces convendría que se mueva en diagonal (alternando entre bajar e ir a la derecha en el ejemplo visual). Y cuando encuentre una flecha que tenga sentido favorable que se dirija a ella.

[Diodo]

Hola a todos

Gracias por las respuestas

Creo que me he explicado mal. Realmente no me interesa el camino mas corto, si no el que requiera menos movimientos (turnos) . Cada turno se puede hacer un movimiento (girar izquierda, girar derecha o avanzar).
Es por esto que tomo la distancia manhattan en la heuristica ya que los caminos diagonales son muy costosos (en cuanto a turnos se refiere).

Un saludo

[Esgaroth]

Entonces descarta por completo mi sugerencia.

¿Qué distribución probabilística tienen las cintas? Es decir, ¿siempre están verticalmente? ¿Pueden tener sentido no favorable? ¿Existe tendencia a que se presenten en cierto lugar del mapa?

Y también: ¿El mapa siempre es cuadrado? ¿Hay algún obstáculo?

Saber esos aspectos nos ayudaría a responderte.