Concurso de laberinto de ratón de computadora IEEE

Jaja~ ¿Alguna vez has participado en el Concurso Internacional de Laberinto de Ratón de Computadora Estándar Internacional IEEE?

¿Puedo preguntar de qué división es el póster original?

Introducción al mouse de la computadora (copio este párrafo): el mouse de la computadora (el nombre en inglés es Micromouse) está controlado por un microprocesador, que integra funciones de detección, juicio y caminata, y puede encontrar automáticamente Micro robots que encuentran el mejor camino hacia su destino. Puede percibir y memorizar automáticamente el mapa del laberinto en el "laberinto", encontrar un camino óptimo a través de un determinado algoritmo y llegar al destino lo más rápido posible. ?

1? ¿Reglas para que el mouse de la computadora corra por el laberinto?

Para conocer las reglas de la competencia internacional para que el mouse de la computadora corra por el laberinto, consulte el sitio web oficial de Instituto Internacional de Ingenieros Eléctricos y Electrónicos (IEEE):

http://www.eece.maine.edu/sc2006/2006MicromouseRules.pdf. ?

1.1 Especificaciones del laberinto? El laberinto consta de 256 cuadrados (unidades), cada cuadrado mide 18 cm cuadrados y está organizado en 16 filas × 16 columnas. Las paredes divisorias del laberinto están dispuestas a lo largo del perímetro del bloque para formar un pasaje del laberinto. Los dos lados del tablero divisorio son blancos y la parte superior es roja. El suelo del laberinto está fabricado con materiales de madera y pintado con pintura negra no reflectante. Los lados y la parte superior de los paneles divisorios tienen propiedades reflectantes para los rayos infrarrojos, mientras que el piso tiene propiedades absorbentes para los rayos infrarrojos. ?

¿Fotos del laberinto?

1.2? ¿Especificaciones del ratón de ordenador?

Los ratones de ordenador deben ser fabricados por los concursantes. Un ordenador completo. El mouse debe incluir un cuerpo, una fuente de alimentación, un sensor, un microprocesador, un motor y una unidad, entre otras partes. Los sensores del ratón de la computadora se pueden dividir en 3 grupos, que se utilizan para detectar si la pared uterina está cerca de las direcciones frontal, izquierda y derecha. Bajo el control del motor, el ratón de la computadora puede realizar acciones como ir derecho, girar, dar la vuelta y acelerar y desacelerar. ?

¿Fotos de muestra del ratón de la computadora?

1.3?¿Reglas de la competencia?

La función básica del mouse de la computadora es comenzar desde el punto de partida y caminar hasta el final. El tiempo se llama "tiempo de ejecución". El tiempo que tarda un ratón de computadora en ejecutarse desde la primera activación hasta el inicio de su ejecución se denomina "tiempo de laberinto". Los movimientos asistidos manualmente del ratón de la computadora durante la competición se denominan "toques". La competición utiliza estos 3 parámetros para puntuar.

Las puntuaciones del ratón de computadora se miden calculando el "tiempo de resolución de problemas" para cada ejecución, que es el tiempo del laberinto más 1/30 del tiempo de una ejecución. Si se ha tocado, reste 10 segundos y el resultado será el tiempo de resolución del problema. El tiempo total que el ratón de la computadora puede permanecer o correr en el laberinto no puede exceder los 15 minutos y se le permite ejecutarlo varias veces dentro del límite de tiempo.

Si entrar al laberinto es para detección y memoria, esta carrera se llama "carrera de prueba"; si ingresar al laberinto se basa en la memoria y la experiencia previas, el mejor camino se determina de acuerdo con un algoritmo inteligente; y si llegas a tu destino lo más rápido posible, la carrera se llama "sprint". ?

---------------------------------Hermosa línea divisoria---- - -------------------------

Texto: ¿El algoritmo del ratón de mi ordenador para navegar por el laberinto?

(Este artículo fue publicado por mí en el "Sitio web oficial del 3er Concurso por invitación de aplicaciones de innovación de sistemas integrados de Shanghai (Concurso internacional estándar de laberinto de ratas de computadora IEEE)", y lo siguiente está ligeramente modificado) 1. Estrategia de detección

Computadora El mouse solo puede usar la estrategia de exploración parcial del laberinto, es decir, bajo un tiempo o número de detecciones limitado, solo se explora una parte del laberinto para encontrar el mejor camino. El ratón de la computadora camina por el callejón. Si al final no hay camino por donde ir, el callejón es un "callejón muerto"; el ratón de la computadora solo puede caminar en 3 direcciones como máximo (frente, izquierda, derecha). 2 o 2 Puedes caminar en las direcciones anteriores, lo que se llama "cruzar". Al encontrar una intersección, existen varias reglas de selección para elegir la dirección a pie, de la siguiente manera. ?

◆?Regla de la mano derecha:?La dirección derecha es la prioridad, seguida de la dirección lineal y la dirección izquierda. ?

◆?La regla de la mano izquierda:?La izquierda es la dirección prioritaria de viaje, seguida de la dirección lineal y la dirección derecha. ?

◆?La regla del centro-izquierda:?La línea recta es la dirección prioritaria hacia adelante, luego la dirección izquierda y la dirección derecha. Similar a esto es la regla del centro-derecha.

?

◆?La ley de los números aleatorios:?Tome valores aleatorios como dirección de viaje. ?

◆? Ley centrípeta: dado que el punto final se establece en el centro del laberinto, cuando hay una intersección, la dirección que apunta al centro del laberinto es la dirección prioritaria.

2. ¿Marcar?

Para recordar la información detallada del laberinto, es necesario marcar las ubicaciones de las unidades del laberinto. El laberinto tiene 16 × 16 unidades, las cuales se pueden marcar en coordenadas bidimensionales, es decir, representadas por las coordenadas XY de cada unidad. Por ejemplo, el punto inicial se puede marcar como (0, 0), el punto final como (7, 7), etc. Además, también es necesario marcar la posible dirección de desplazamiento de la unidad del laberinto, que puede ser en orientación absoluta o relativa.

Orientación absoluta: Un método de marcado que no tiene nada que ver con la dirección de desplazamiento del mouse de la computadora. Utiliza un número binario de 4 dígitos para representar las cuatro direcciones: este, oeste, sur y norte. . "1" significa que se permite viajar (sin paredes), "0" significa que no se permite viajar (paredes).

Orientación relativa: método de marcado relacionado con la dirección de desplazamiento del mouse de la computadora. Se puede marcar con un número binario de 3 dígitos, que representa el frente, la izquierda y la derecha respectivamente. "1" significa permitido (sin paredes), "0" significa no permitido (paredes presentes). ?

Tres. ¿Bloquear?

Durante la ejecución de prueba del mouse de la computadora o durante el sprint final, es necesario "bloquear" parte del camino, es decir, cuando se descubre que un determinado camino es un callejón sin salida. (solo una entrada pero no una salida), establezca una marca en la entrada del camino (generalmente la intersección), es decir, cambie la marca de línea de la entrada de 1 a 0. ?

Cuatro: ¿Prueba?

La prueba es la única forma de obtener el mapa del laberinto (marcadores de ruta para cada unidad), por lo que debes obtener tantos como sea posible según las reglas. permitir que la información del Laberinto se prepare para el sprint final. Durante la prueba, además de marcar las líneas de unidades que pasan, también se debe seleccionar una estrategia de detección adecuada. ?

Cinco. ¿Completación de datos?

Dado que es imposible detectar todas las unidades, la "completación de datos" se puede lograr en función de ciertos datos. La finalización de datos es un método para complementar unidades no detectadas con datos de fase existentes a su alrededor. Primero, busque la unidad cuyos datos de unidad sean FFH. Si las cuatro unidades adyacentes de la unidad en el este, oeste, sur y norte no son 00H o FFH, analice "este", "oeste" y "sur. ", y "norte". "Dos conjuntos de datos de 4 unidades para ver si hay una dirección factible que apunte a la unidad. De ser así, es coherente en esa dirección y se pueden hacer suposiciones audaces sobre los datos. ?

Seis. ¿Tabla de contornos?

Después de un número limitado de detecciones, bloqueos y finalización, se puede obtener una tabla bidimensional que describe el circuito del laberinto. Aunque no todo, es parte o la mayor parte del mismo, que puede contener varios caminos hasta el final. Para encontrar el camino hasta el punto final, es necesario crear una tabla de contornos. La tabla de contorno se refiere al número de pasos (una unidad es un paso) desde el punto inicial de cada unidad detectada, y el número de pasos desde el punto inicial es 0. ?

2.7? ¿Camino factible?

En la tabla de contorno, se conoce el número de pasos desde cualquier unidad en el camino factible hasta el punto inicial, en orden de mayor a menor, Podrás regresar al punto de partida. En orden de pequeño a grande, se puede alcanzar el punto final. Puede haber no solo un camino factible, sino varios. La búsqueda de un camino factible comienza desde el punto inicial y continúa en la dirección permitida para avanzar en una dirección 1 mayor que el valor del contorno actual hasta el punto final. A veces puede encontrarse con una situación en la que el valor del contorno de la siguiente unidad es menor que el valor actual, como (6, 2) puntos, o es más de 1 mayor que el valor actual. Si la unidad actual no es un punto de intersección, puede ignorarla, ingresar la siguiente unidad y buscar en la dirección en la que aumenta el valor del contorno; si es un punto de intersección, realizar un análisis de tendencia para descubrir la dirección en la que se encuentra; el valor del contorno aumenta y descarta los contornos La dirección en la que el valor disminuye. ?

2.8?¿El número de pasos en un camino factible?

El número de pasos en un camino factible se refiere al número de unidades pasadas desde el punto inicial hasta el punto final, que se puede calcular a partir de la tabla de contornos. Línea A: 19 pasos de (0,0) a (7,4), 1 paso de (7,4) a (7,5), 1 paso de (7,5) a (7,6), (7 , 6) Vaya al paso (7,7) 28-27=1. Total=19+1+1+1=22 pasos. Línea B: 24 pasos de (0,0) a (6,2), 1 paso de (6,2) a (7,2), 19-17=2 pasos de (7,2) a (7,4 ), (7,4) a (7,5) 1 paso, (7,5) a (7,6) 1 paso.

(7,6) a (7,7) 28-27=1 paso, total =24+1+2+1+1+1=30 pasos. De la misma forma, podemos obtener: Línea C, 22+1+1=24 pasos; Línea D, 28 pasos. ?

7.?¿La mejor ruta?

Para completar el ataque en el menor tiempo, la elección de la ruta es crucial para el ratón del ordenador. Elegir un camino con menos pasos es una de las condiciones para determinar el mejor camino, pero no es la única. Teniendo en cuenta que el mouse de la computadora también toma tiempo al girar, se debe ponderar el número de vueltas y luego agregarlo al número de pasos para determinar el número ponderado de pasos. Número de pasos ponderados = Número de pasos + Número de giros × Peso de giro Número de giros: Un giro de 90° cuenta como 1 vez y un giro de 180° cuenta como 2 veces. Peso de giro: este es un parámetro que tiene un impacto importante en los resultados y debe determinarse en función de la estructura del mouse de la computadora y la ejecución de prueba. Si el mouse de la computadora no tiene función de aceleración, es decir, avanza a una velocidad constante, su valor se puede seleccionar de 0,4 a 1,0 si el mouse de la computadora tiene una función de velocidad variable, su valor se puede aumentar adecuadamente de acuerdo con la rango de velocidad variable. ?

Conclusión final: Presentaré en detalle un algoritmo para que un mouse de computadora navegue por un laberinto. La práctica demuestra que este algoritmo básicamente puede cumplir con los requisitos de la competencia del laberinto del mouse de computadora.

Existen muchos algoritmos para que los ratones de computadora naveguen por laberintos, y están surgiendo nuevos algoritmos uno tras otro. Este artículo es solo un punto de partida para la referencia del cartel. Espero que pueda ser útil para el cartel.

Además, la siguiente QQ: 258979684?, si hay algo que no entiendes, podemos comunicarnos en línea.