Estoy calculando la ruta más corta de un robot en un avión con obstáculos poligonales. Todo funciona bien y rápido, no hay problemas allí. Pero, ¿cómo suavizar el camino para que se vuelva curvilíneo? A continuación se muestra una imagen de un camino que conecta vértices con una línea recta. P.S El robot es solo un círculo.Ruta de suavizado de un robot
This paper podría ser útil. Parece que es un problema no trivial. Resumen:
Los cajones de gráficos automáticos necesitan calcular trayectorias entre versiones de un polígono simple que además de permanecer en el interior necesita exhibir ciertas propiedades estéticas. Algunos de estos requieren la incorporación de cierta información sobre la forma poligonal sin estar demasiado lejos de la ruta real más corta. Presentamos un algoritmo para calcular una región localmente convexa que "contiene" la ruta Euclidiana más corta entre dos vértices de un polígono simple. La región tiene una forma de límite que "sigue" la forma del camino más corto. Una spline Bezier cúbica en la región interior proporciona una curva libre de colisiones "corta y suave" entre los dos vértices dados. Los resultados obtenidos parecen ser estéticamente agradables y los métodos utilizados pueden ser de interés independiente. Son elementales y aplicables. La Figura 7 es un resultado de muestra producido por nuestra implementación actual.
Solía jugar mucho con las técnicas de cálculo de rutas cuando trato de hacer secuencias de vuelo realistas para representar en Teragen. Inicialmente intenté usar Bézier Curves.
Pero descubrieron que (para volar por lo menos) que no son tan útiles. La razón es que la curvatura entre curvas es discontinua y, por lo tanto, no se puede usar para calcular un ángulo bancario correcto continuo para un vuelo en vuelo. Además, es difícil estar seguro de que la curva no se cruza con una montaña.
I digress. La forma en que eventualmente me decidí fue un camino simple basado en un resorte de masa, y lo relajé en sumisión.
Subdividir la ruta en muchos segmentos pequeños, cuanto más, mejor. Para cada punto, muévelo un poco en una dirección para reducir el ángulo entre él y sus vecinos, y lejos de los obstáculos. Repita muchas veces hasta que la ruta se haya establecido.
k = 0.01 // Adjust the values of k and j to your liking.
j = 0.01 // Small values take longer to settle. Larger values are unstable.
For each point P
normal_vector = vector_to_previous_point + vector_to_next_point
obstacle_vector = vector_to_nearest_obstacle
obstacle_distance = magnitude(obstacle_vector)
obstacle_vector *= obstacle_distance^2
P += (normal_vector * k) - (obstacle_vector * j)
La ventaja de este tipo de técnicas elemento de relajación finitos es que se puede programar todo tipo de limitaciones en él, y el camino va a instalarse en un cierto compromiso entre ellos, en función de los pesos (j, k en este caso).
Si usted está en la robótica, por qué no venir y unirse a la Robotics Proposal?
Gracias, su método se ve fantástico a primera vista, aunque todavía tendría que implementarlo y probarlo. Y, oh, sí, apoyaré la propuesta;) – nullpotent
¿No puede simplemente hacer el trazado curvo en la ejecución real del algoritmo de seguimiento de ruta? Si abandona el camino como está (es decir, líneas rectas conectadas), implementa una distancia de anticipación de ~ 1 metro (este valor dependerá de la velocidad de su robot y de la cantidad que haya rellenado el espacio de configuración para evitar obstáculos) en el el algoritmo de control que calcula la velocidad de cada rueda alisará automáticamente la ruta sin necesidad de preprocesamiento.
Aquí hay una imagen rápida de lo que quiero decir ...la línea punteada roja es la ruta que realmente ejecuta el robot cuando controlas a un punto en función de la distancia de anticipación. Una distancia de búsqueda anticipada simplemente calcula un punto más abajo en el camino por una distancia arbitraria.
Una vez más, lo único que tiene que preocuparse es la cantidad que está relleno obstáculos para asegurarse de que evitar chocar contra ellos. Normalmente creo que el área de un obstáculo está rellenada por la mitad del radio del robot, pero si controlas con una distancia de anticipación, es posible que tengas que hacerlo un poco más grande.
Al final opté por la misma solución que presentó aquí. Necesitaba un poco de ajuste pero funcionó. Gracias, no obstante;) – nullpotent
En el caso de un robot no podemos conocer el futuro. Tenemos que dibujar cada punto sabiendo solo la ubicación del robot y los obstáculos. El método habitual para hacer trayectos curvos de longitud mínima es modelar el robot con un círculo y mover el círculo para que permanezca en contacto con los obstáculos. Solo mantenga un radio y los giros serán curvas.
Si desea curvas y NO distancia mínima intente hacer que el radio anterior sea proporcional a la distancia desde un vértice de polígono.
La idea de las curvas de Bezier solo funciona para hacer que la trayectoria se curve en retrospectiva. Cambia donde ha estado el robot. Por lo general, los robots que cambian el pasado se llaman "trampas". Una forma de evitar tener que cambiar el camino que ya ha recorrido es mirar hacia adelante. ¿Pero puede el robot ver alrededor de las esquinas? Tienes que especificar las reglas mejor.
Primer paso: necesita definir el radio de giro de su robot. Si se puede activar un centavo de manera eficiente, ¿por qué querrías * tomar un camino curvilíneo? –
Tienes razón. Sabía que alguien me preguntaría eso. Mi robot tendrá un radio de giro completo, pero quería saber cómo se hace, aun así. "Cómo conectar puntos con una curva" era la verdadera pregunta. Me disculpo. – nullpotent
Creo que ese número es intrínseco a la respuesta a la pregunta. Pero podemos usar alguna variable, supongo, digamos 'TR' para representar el radio de giro. En ese caso, ya ha respondido su propia pregunta para el caso especial de 'TR = 0'. –