En esta recopilación pueden verse decenas de tomas de micro-ratones robóticos resolviendo laberintos cada vez más grandes y complicados – a velocidades de vértigo. Las tomas abarcan varios años de grabaciones en competiciones oficiales y todos los clips están en tiempo real. Así que aunque parezcan demasiado rápidos es simplemente que lo son. [vía microsiervos: http://www.microsiervos.com/archivo/robots/evolucion-micro-ratones-roboticos-laberintos.html ]
#27:
#6 En realidad aquí no existe "a la primera". Y tampoco es que se mencione que lo hagan así en ningún lado. Luego no existe ningún debate sobre ello y no deja de ser meritorio.
Lo que ocurre es que estamos acostumbrados a ver robots de ciencia ficción que hacen de todo maravillosamente bien. Y luego,cuando nos muestran avances robóticos (que son realmente increíbles) nos parece que no es nada del otro mundo.
Reconocer espacialmente un laberinto (parte física), resolver el camino más corto (parte lógica) y reproducir los desplazamientos exactos a la mayor velocidad posible (parte mecánica) es extremadamente dificil de conseguir.
#15:
#9 No, eso no es interesante, porque ante una bifurcación, el algoritmo de un ratón puede decir "si es la primera vez que llegas a este punto prueba primero a la derecha. Si es la segunda vez, prueba el camino de en frente", y el de otro ratón, justo lo contrario. El que ganase sería de chiripa, para ese laberinto en concreto, lo cual no nos da información de cuál es mejor.
#3:
#1 Según leo, son carreras en dos fases. La primera de reconocimiento del laberinto y la segunda, que es la que se muestra en el video, de resolución en base a los datos recogidos en el reconocimiento y a contrareloj.
Lo interesante sería verlos resolver el laberinto en una sola fase y que alguno destacase sobre los otros.
Al final, lo que vemos en el vídeo, son carreras de velocidad con un mapeado perfecto.
#9 No, eso no es interesante, porque ante una bifurcación, el algoritmo de un ratón puede decir "si es la primera vez que llegas a este punto prueba primero a la derecha. Si es la segunda vez, prueba el camino de en frente", y el de otro ratón, justo lo contrario. El que ganase sería de chiripa, para ese laberinto en concreto, lo cual no nos da información de cuál es mejor.
#15 O puede decir: si llevo tres giros a la derecha y estoy cerca del límite es más probable que el siguiente giro sea a la izquierda. Pequeñas variaciones en los algoritmos marcarían la diferencia a la larga.
#26 Si se sabe donde está el final del laberinto y se conocen las dimensiones, se puede usar un poco de IA para encontrar el camino de una manera algo mas eficiente que prueba y error, mapeando distancias y direcciones.
#9 Esta competición es de robótica, no de algorísmica. El tema es cómo hacer un raton que pueda moverse así de rápido, cosa que no es nada sencilla, en vez de "qué algoritmo usar para resolver el laberinto".
No tiene mucho sentido meter la parte algorísima en una competición como esta porque eso se puede estudiar en software (con simulaciones) lo cual es muchísimo más efectivo. Además, no parece un problema demasiado complicado (probablemente el algoritmo óptimo es un astar con una heurística que considere tanto distancia al objetivo como coste de saltar a un nodo previo) ni interesante (¿qué aplicación tendría esto?). No he buscado a fondo, pero es posible hasta que sepamos ya cuál es el algoritmo óptimo para laberintos realmente aleatorios.
Todo el mundo hablando de algoritmos, pero lo alucinante son las cubiertas que llevan, menudo agarre. Como apliquen esto a los taxis autónomos del futuro, va a ser pedir uno y escuchar ambulancias en menos de 10 segundos
#30 El algoritmo está en github: https://github.com/idt12312/MazeSolver2015
Los comentarios están todos en japonés, pero las variables están en inglés.
Allí utilizan un procesador STM32F407 (un ARM Cortex M4, de 32 bits, con convertidores ADC/DAC) a 167 MHZ.
Se puede usar el google translate para traducir...
Si, pero... Si es que primero se suelta un ratón en un laberinto y tiene que " reconocerlo " para luego elaborar un cálculo de cuál es el camino más corto ( no el único . O quizás sí.. según ) y en una fase posterior hacer la carrera y eso lo hace sin asistencia externa ... Así todo está miniaturizado en el mismo ratón... en ese caso, me quito el sombrero.!
#11 Bueno, realmente no es nada complicado. Para mapear un laberinto sólo te tienes que pegar a una pared (izquierda o derecha) y recorrerla. Acabarás llegando al punto de partida después de recorrer todo el laberinto (salvo las paredes sueltas, pero si el sonar es lo suficientemente amplio detectará la abertura igual. Otra opción es usar movimientos aleatorios, realmente hay muchas variantes para ello.
Luego, para encontrar el camino mínimo, se pueden usar técnicas de grafos como Dijkstra o A*. En mi caso, yo me decantaría por una llamada Fast Marching Method:
Cohen, L. D., & Kimmel, R. (1997). Global minimum for active contour models: A minimal path approach. International journal of computer vision, 24(1), 57-78.
Una vez creado el camino...a correr.
PD: si buscas 'fast marching method for path planning' en google, te salen mil ideas para esto, incluida una para robots en marte.
#13 Ese sistema sirve únicamente cuando la entrada y la salida están en el borde exterior del laberinto. Si la salida estuviera por ejemplo en el centro, tal vez no se llegara nunca recorriendo los bordes. Imagina un edificio (una biblioteca por ejemplo, jeje) al que se accede desde la calle, pero donde las escaleras están en el medio de la planta baja, cuyos pasillos forman el laberinto. Si te limitas a pegarte a una pared, volverías a la entrada y nunca recorrerías la parte interior ni encontrarías la salida.
#14 Por eso digo que los de pared libre pueden fallar. De todas maneras, existen mil métodos para mejorarlo. Uno sencillo es recorrerlo de esa manera hasta llegar a un punto que hayas visto, buscar en el mapa zonas donde no has encontrado pared e ir hacia ellas hasta encontrar una, y volver a empezar.
Como digo, hay mil técnicas distintas, unas más sofisticadas que otras.
Sensacionalista e incluso errónea por el empleo de la palabra resolver cuando lo mostrado no es el proceso o fase de resolución (y que es la que deberían mostrar realmente).
#c-12" class="content-link" style="color: rgb(227, 86, 20)" data-toggle="popover" data-popover-type="comment" data-popover-url="/tooltip/comment/2882480/order/12">#12#13# ... Gracias por comentar.
Un poco arriba ( #27 ) ya menciona que es un reto robótico; y por eso mismo asombroso.
Miniaturizar e integrar tanto la información como la ejecución de la tarea - de forma autónoma - es el mérito.
Yo supongo que hay " marcas de salida " ya que posicionar el ratón en el laberinto, me parece imposible de otra manera. O... Qué ?
A mi lo que me sorprende es lo poco que se habla de que algunos clips son del 2012
Años de ventaja. A saber qué competiciones hacen a día de hoy en los suburbios clandestinos.
"The runs are conducted in two phases. In the first, the robot methodically finds its way through the maze using sensors, and in the second one, which are the speed runs seen above and below, the tiny bot uses the map it created in the first run to complete the second as quickly as possible. If you only watch the first few minutes of this video you’ll think it’s a guarantee the mouse will always find its way every time, but there are plenty of failures as well."
#6 En realidad aquí no existe "a la primera". Y tampoco es que se mencione que lo hagan así en ningún lado. Luego no existe ningún debate sobre ello y no deja de ser meritorio.
Lo que ocurre es que estamos acostumbrados a ver robots de ciencia ficción que hacen de todo maravillosamente bien. Y luego,cuando nos muestran avances robóticos (que son realmente increíbles) nos parece que no es nada del otro mundo.
Reconocer espacialmente un laberinto (parte física), resolver el camino más corto (parte lógica) y reproducir los desplazamientos exactos a la mayor velocidad posible (parte mecánica) es extremadamente dificil de conseguir.
#5 No, pero no es que que les den el mapa para que los carguen de antemano... los mismos ratones recorren primero el laberinto para mapearlo. En el vídeo se ve además alguno que se queda atascado sin saber que hacer.
#1 Según leo, son carreras en dos fases. La primera de reconocimiento del laberinto y la segunda, que es la que se muestra en el video, de resolución en base a los datos recogidos en el reconocimiento y a contrareloj.
Comentarios
Entonces no es como lo ofrecen
Lo interesante sería verlos resolver el laberinto en una sola fase y que alguno destacase sobre los otros.
Al final, lo que vemos en el vídeo, son carreras de velocidad con un mapeado perfecto.
#9 No, eso no es interesante, porque ante una bifurcación, el algoritmo de un ratón puede decir "si es la primera vez que llegas a este punto prueba primero a la derecha. Si es la segunda vez, prueba el camino de en frente", y el de otro ratón, justo lo contrario. El que ganase sería de chiripa, para ese laberinto en concreto, lo cual no nos da información de cuál es mejor.
#15 Con el suficiente número de pruebas no sería chiripa. Acabarías con el mejor algoritmo para resolver estos puzzles.
#17 Cierto. El problema, en este caso, sería tener espacio suficiente para crear tantos laberintos
#15 O puede decir: si llevo tres giros a la derecha y estoy cerca del límite es más probable que el siguiente giro sea a la izquierda. Pequeñas variaciones en los algoritmos marcarían la diferencia a la larga.
#26 Si se sabe donde está el final del laberinto y se conocen las dimensiones, se puede usar un poco de IA para encontrar el camino de una manera algo mas eficiente que prueba y error, mapeando distancias y direcciones.
#9 Esta competición es de robótica, no de algorísmica. El tema es cómo hacer un raton que pueda moverse así de rápido, cosa que no es nada sencilla, en vez de "qué algoritmo usar para resolver el laberinto".
No tiene mucho sentido meter la parte algorísima en una competición como esta porque eso se puede estudiar en software (con simulaciones) lo cual es muchísimo más efectivo. Además, no parece un problema demasiado complicado (probablemente el algoritmo óptimo es un astar con una heurística que considere tanto distancia al objetivo como coste de saltar a un nodo previo) ni interesante (¿qué aplicación tendría esto?). No he buscado a fondo, pero es posible hasta que sepamos ya cuál es el algoritmo óptimo para laberintos realmente aleatorios.
#30 #9
minuto 5#32 Es una pasada.
Todo el mundo hablando de algoritmos, pero lo alucinante son las cubiertas que llevan, menudo agarre. Como apliquen esto a los taxis autónomos del futuro, va a ser pedir uno y escuchar ambulancias en menos de 10 segundos
#30 El algoritmo está en github:
https://github.com/idt12312/MazeSolver2015
Los comentarios están todos en japonés, pero las variables están en inglés.
Allí utilizan un procesador STM32F407 (un ARM Cortex M4, de 32 bits, con convertidores ADC/DAC) a 167 MHZ.
Se puede usar el google translate para traducir...
#31 Muy interesante.
Si, pero... Si es que primero se suelta un ratón en un laberinto y tiene que " reconocerlo " para luego elaborar un cálculo de cuál es el camino más corto ( no el único . O quizás sí.. según ) y en una fase posterior hacer la carrera y eso lo hace sin asistencia externa ... Así todo está miniaturizado en el mismo ratón... en ese caso, me quito el sombrero.!
#11 Bueno, realmente no es nada complicado. Para mapear un laberinto sólo te tienes que pegar a una pared (izquierda o derecha) y recorrerla. Acabarás llegando al punto de partida después de recorrer todo el laberinto (salvo las paredes sueltas, pero si el sonar es lo suficientemente amplio detectará la abertura igual. Otra opción es usar movimientos aleatorios, realmente hay muchas variantes para ello.
Luego, para encontrar el camino mínimo, se pueden usar técnicas de grafos como Dijkstra o A*. En mi caso, yo me decantaría por una llamada Fast Marching Method:
Cohen, L. D., & Kimmel, R. (1997). Global minimum for active contour models: A minimal path approach. International journal of computer vision, 24(1), 57-78.
Una vez creado el camino...a correr.
PD: si buscas 'fast marching method for path planning' en google, te salen mil ideas para esto, incluida una para robots en marte.
#13 Ese sistema sirve únicamente cuando la entrada y la salida están en el borde exterior del laberinto. Si la salida estuviera por ejemplo en el centro, tal vez no se llegara nunca recorriendo los bordes. Imagina un edificio (una biblioteca por ejemplo, jeje) al que se accede desde la calle, pero donde las escaleras están en el medio de la planta baja, cuyos pasillos forman el laberinto. Si te limitas a pegarte a una pared, volverías a la entrada y nunca recorrerías la parte interior ni encontrarías la salida.
#14 Por eso digo que los de pared libre pueden fallar. De todas maneras, existen mil métodos para mejorarlo. Uno sencillo es recorrerlo de esa manera hasta llegar a un punto que hayas visto, buscar en el mapa zonas donde no has encontrado pared e ir hacia ellas hasta encontrar una, y volver a empezar.
Como digo, hay mil técnicas distintas, unas más sofisticadas que otras.
Sensacionalista e incluso errónea por el empleo de la palabra resolver cuando lo mostrado no es el proceso o fase de resolución (y que es la que deberían mostrar realmente).
#18 Sensacionalista?... madre mia con meneame
Pues... Como un aspirador, no?
#c-12" class="content-link" style="color: rgb(227, 86, 20)" data-toggle="popover" data-popover-type="comment" data-popover-url="/tooltip/comment/2882480/order/12">#12#13# ... Gracias por comentar.
Un poco arriba ( #27 ) ya menciona que es un reto robótico; y por eso mismo asombroso.
Miniaturizar e integrar tanto la información como la ejecución de la tarea - de forma autónoma - es el mérito.
Yo supongo que hay " marcas de salida " ya que posicionar el ratón en el laberinto, me parece imposible de otra manera. O... Qué ?
Me lo apunto para Reyes, no sé donde lo voy a meter pero lo quiero ya.
Son poco eficientes y nulos a la hora de "pensar".
Todos sabemos como acaba esto..... (SPOILER ALERT) ... con un doctor adicto al dolor.
Espero que utilizarán algo diferente al LISP, el cual odio
pd: también odio el PROLOG
A mi lo que me sorprende es lo poco que se habla de que algunos clips son del 2012
Años de ventaja. A saber qué competiciones hacen a día de hoy en los suburbios clandestinos.
No resuelven el laberinto, sólo son carreras de velocidad, Ya llevan el recorrido grabado.
#1 No es verdad. Deberías ver el vídeo.
#2 Pero como van a hacer eso a la primera???
#4 Aquí hay más info: https://nerdist.com/robot-micro-mouse-maze-speed-trials/
"The runs are conducted in two phases. In the first, the robot methodically finds its way through the maze using sensors, and in the second one, which are the speed runs seen above and below, the tiny bot uses the map it created in the first run to complete the second as quickly as possible. If you only watch the first few minutes of this video you’ll think it’s a guarantee the mouse will always find its way every time, but there are plenty of failures as well."
#5 Pues eso, no es a la primera...
#6 En realidad aquí no existe "a la primera". Y tampoco es que se mencione que lo hagan así en ningún lado. Luego no existe ningún debate sobre ello y no deja de ser meritorio.
Lo que ocurre es que estamos acostumbrados a ver robots de ciencia ficción que hacen de todo maravillosamente bien. Y luego,cuando nos muestran avances robóticos (que son realmente increíbles) nos parece que no es nada del otro mundo.
Reconocer espacialmente un laberinto (parte física), resolver el camino más corto (parte lógica) y reproducir los desplazamientos exactos a la mayor velocidad posible (parte mecánica) es extremadamente dificil de conseguir.
#6 Eataría bien ver tambien la Primera fase.
#5 No, pero no es que que les den el mapa para que los carguen de antemano... los mismos ratones recorren primero el laberinto para mapearlo. En el vídeo se ve además alguno que se queda atascado sin saber que hacer.
#7 Mas que sin saber que hacer parece ser que se pegan tal tortazo que se quedan dados la vuelta...
#1 Según leo, son carreras en dos fases. La primera de reconocimiento del laberinto y la segunda, que es la que se muestra en el video, de resolución en base a los datos recogidos en el reconocimiento y a contrareloj.
#3 Tienes razón el vídeo es cuando tiene ya memorizado el camino.
Interesante es la parte de exploración.