Enrutamiento
Inteligente

Descripción General

Nuestra solución de enrutamiento de última generación soporta campos arbitrariamente complejos, navegación de cabeceras y muchas otras opciones configurables. En esta página encontrarás ejemplos y explicaciones de las diversas funcionalidades de enrutamiento, además de prototipos experimentales nuevos y emocionantes.

Modelado de Giros

Soportamos varios tipos de giro que se eligen automáticamente según una combinación de la geometría del campo y las características de los equipos. Si dos pasadas están a menos de 3 anchos de pasada entre sí, intentaremos conectarlas directamente con un giro. Si las pasadas están más separadas o no cabe ningún giro, realizaremos lo que llamamos un recorrido de cabecera, explicado con más detalle a continuación.

Conectores Pasada-Pasada

Para conexiones directas de pasada a pasada, soportamos los siguientes tipos de giro:

Giro en U

Cuando el radio de giro es inferior al 50% del ancho de pasada, se generarán giros en U como este para pasadas adyacentes. Hay una opción para extender el segmento recto hasta la cabecera, dando más espacio para girar y minimizando el pisoteo.

Giro en U Perfecto

Cuando el radio de giro es exactamente el 50% del ancho de pasada, se generarán giros en U perfectos como este para pasadas adyacentes, sin segmento recto intermedio.

Giro en Bulbo

Cuando el radio de giro es superior al 50% del ancho de pasada, se usa un giro en bulbo para conectar dos pasadas adyacentes. Solo se usaría si no cabe un giro en U.

Giro en P

Si la cabecera está en un ángulo agudo respecto al giro y el radio de giro es suficientemente grande, soportamos giros en P para minimizar la cantidad de dirección necesaria.

Conectores Pasada-Cabecera

Cuando no es posible una conexión directa, nos conectamos a una cabecera cercana realizando uno o más recorridos de cabecera para unir dos pasadas. Esto nos permite crear trayectorias entre casi cualquier par de pasadas del campo entero sin cruzar inválidamente el campo fuera de una zona de cabecera.

Conectores de Arco

Por defecto, intentamos usar conectores de arco, que tienen curvatura constante y un radio de giro al menos tan grande como el radio mínimo de giro. Esto permite una transición suave de la pasada a la cabecera sin movimientos bruscos. El giro puede acortarse automáticamente si no hay espacio suficiente para completarlo sin que el vehículo cruce el límite del campo.

Conectores Dubins

Si un conector de arco falla, se realiza una búsqueda para intentar conectar un conector Dubins a varios puntos de la cabecera en la dirección de viaje deseada, hasta encontrar uno válido que minimice el cambio total de ángulo.

Conector de Respaldo

Como último recurso, creamos un conector de respaldo que une directamente los dos puntos (ya sea entre dos pasadas o pasada-cabecera) y aparece en la interfaz como una gran línea roja. El usuario debe realizar ese giro manualmente antes de continuar la ruta.

Acortamiento de Giros

Si un giro no cabe desde una pasada hacia otra pasada o hacia una cabecera sin que ninguna parte del vehículo cruce el límite del campo, y si la configuración "Acortar Pasadas" está habilitada, el giro se acortará, es decir, girará antes del final de la pasada para poder realizarlo. Lamentablemente esto provoca una zona no cubierta, a menos que el vehículo pueda retroceder antes de hacer el giro (trabajos futuros darán soporte a esta funcionalidad si hay demanda). Si notas que se pierde mucha área, probablemente no tienes suficientes cabeceras para el radio de giro de tu vehículo y puede ser necesario replantear con más cabeceras. En el roadmap está la sugerencia automática del número de cabeceras según tu campo y equipo.

Extensión de Giros

En algunas situaciones, puede ser conveniente extender los giros más adentro de la cabecera. Esto puede habilitarse con la configuración "Extender Giros en Cabeceras". Si el giro cabe, se extenderá hasta tocar la cabecera más externa. Esto proporciona más espacio para girar y enderezar, minimizando el pisoteo. Los trabajos futuros incluyen engancharse siempre a las cabeceras cuando sea posible para minimizar aún más el pisoteo.

Conexiones de Cabecera Acortadas

Los giros adyacentes acortados para caber en la cabecera se convertirán en recorridos de cabecera cuando sea posible. Esto puede habilitarse con la configuración "Preferir Conexiones de Cabecera Acortadas". Los trabajos futuros incluyen habilitar esto para todas las conexiones pasada-pasada.

Sin Configuración

El giro se acorta para apenas tocar la cabecera, pero no recorre a lo largo de ella.

Con Configuración

Las conexiones se realizan a lo largo de la cabecera entre conectores adyacentes, minimizando el pisoteo.

Navegación de Cabeceras

Cuando no es posible un giro directo de pasada a pasada, la solución de enrutamiento cambia al modo de navegación de cabeceras. Se crean conectores de las pasadas a las cabeceras, seguidos de una serie de recorridos de cabecera y conectores entre cabeceras.

Recorridos Completos de Cabecera

Trabaja automáticamente todas las cabeceras de tu campo con planificación adicional: encontramos eficientemente un camino de ida y vuelta para cada cabecera de un grupo, minimizando la distancia no trabajada recorrida y preservando el tráfico de ruedas. Nuestro algoritmo puede partir de cualquier pasada inicial o final en la cabecera. El algoritmo evita giros que puedan colisionar con el obstáculo, garantizando la seguridad.

Preferir Cabecera Más Externa

Al realizar recorridos de cabecera, el algoritmo por defecto se conecta a la cabecera exterior más central, ya que ofrece un buen equilibrio entre espacio para girar y enderezar. Activar "Preferir Cabecera Más Externa" hará que se conecte a la cabecera más externa.

Comportamiento Predeterminado

Los recorridos de cabecera se conectan naturalmente a la cabecera más central.

Giros Conectados a la Cabecera Más Externa

Con "Preferir Cabecera Más Externa" activado, todos los recorridos de cabecera se conectan a la cabecera exterior más externa cuando es posible.

Enrutamiento de Múltiples Pasadas Internas

Ejemplo de una situación compleja donde el solver de ruta encuentra un camino a través de múltiples cabeceras, trabajándolas, así como todas las pasadas internas.

Cruces de Cabecera

Si un ángulo es demasiado agudo en una cabecera o pasada curva y se desea minimizar el área no cubierta, soportamos un flujo de trabajo de cruce: extendemos las líneas y las conectamos con un arco que respeta el radio de giro del vehículo. Los trabajos futuros incluyen extender aún más el giro para que el vehículo entero se enderece antes de retroceder.

Cabeceras Dirigibles

Si un cambio de ángulo supera cierto umbral en una cabecera o pasada curva, lo marcamos como necesitado de suavizado. A continuación, insertamos inteligentemente círculos con el radio de giro del vehículo de forma que minimice el área no cubierta entre pasadas. Tras el suavizado, obtenemos una pasada de cabecera que respeta las restricciones de curvatura del vehículo y minimiza el área no cubierta. Los trabajos futuros incluyen una decisión más inteligente entre suavizar o usar cruces en una esquina.

Antes del Suavizado

Resultados de ejemplo de un algoritmo de desplazamiento estándar. Si bien hay mayor cobertura, el vehículo no puede físicamente realizar giros tan cerrados.

Después del Suavizado

Tras aplicar el suavizado. Los giros que el algoritmo no pudo suavizar se convierten en cruces. Todos los giros suavizados respetan el radio mínimo de giro.

Algoritmos / Patrones

Algoritmo Predeterminado

Por defecto, modelamos el problema como una instancia del Problema de Enrutamiento Agrícola (ARP), que es la versión agrícola del bien conocido Problema de Enrutamiento de Vehículos. Es lo que se conoce como NP-difícil, es decir, no existen algoritmos que puedan resolver eficientemente todas las instancias posibles del problema de forma perfecta. Por ello hemos desarrollado un solver meta-heurístico personalizado para resolver el ARP, codificando los estándares del agricultor en la propia matriz de costes, generando una ruta capaz de navegar incluso por los campos más complejos en cuestión de minutos o incluso segundos.

Nuestro solver de enrutamiento calcula las distancias desde y hacia cada par posible de pasadas en el campo, usando rutas exactas para pasadas en aproximadamente la misma área y estimaciones inteligentes para pasadas en el lado opuesto del campo. Esto crea lo que se conoce como una matriz de distancias, que se introduce en nuestro solver propietario para optimizar un camino que recorra cada pasada y cabecera, minimizando la distancia no trabajada. No se hacen suposiciones previas sobre el patrón de trabajo; los resultados se basan únicamente en las distancias calculadas entre ellas. Esto permite al solver tener una visión notable en ciertos momentos, saltando una o más pasadas que no son inmediatamente obvias para el usuario, solo para luego usarlas para salir eficientemente de una situación en la que un enfoque tradicional habría quedado atrapado.

Evitar Saltar Pasadas

Cuando está activado, el coste de desplazarse a una pasada adyacente se reduce a la mitad. Esto fomenta (pero no fuerza) un patrón más recto, al coste potencial de mayor distancia no trabajada o, en el caso siguiente, mayor área no cubierta. En el ejemplo siguiente, podría preferirse otra cabecera para que quepan los giros.

Pasadas Continuas (Boustrophedon)

Un patrón predefinido de ida y vuelta, comenzando en un lado del campo y avanzando hasta el otro. Ideal para campos simples y aquellos con pequeños obstáculos.

Si notas que hay demasiados recorridos de cabecera, recomendamos ejecutar nuestro algoritmo predeterminado y activar "Evitar Saltar Pasadas". Esto evitará casos extremos de recorridos de cabecera, a costa de perder uniformidad.

Espiral Agrupada

Un patrón predefinido que impone siempre al menos un salto de N pasadas en un patrón de avanzar y luego retroceder. Funciona mejor en campos simples y con pequeños obstáculos.

Serpiente

El patrón serpiente cubre el campo saltando una pasada en cada giro y luego regresando por las pasadas no cubiertas. Reduce el número de giros bruscos.

Enrutamiento por Capacidad

Si el usuario especifica capacidad y caudal para su vehículo, puede acceder a nuestras diversas funcionalidades de enrutamiento por capacidad. Actualmente tenemos dos flujos de trabajo separados para esto. El primero es Vehículo Único, que es el tipo de rutas mostrado anteriormente, sin área de preparación y con un solo vehículo trabajando. El otro es Múltiples Vehículos con Capacidad, donde uno o más vehículos parten de un área de preparación y pueden trabajar pasadas hasta alcanzar su capacidad, momento en el que regresarán al depósito de preparación por las cabeceras.

Múltiples Vehículos con Área de Preparación

Actualmente es una configuración experimental en desarrollo. Las rutas pueden no estar bien optimizadas y pueden comportarse de forma extraña o incluso fallar hasta que las desarrollemos más.

Si está activado, se determinará un área de preparación extendiendo primero la pasada mediana del campo y eligiendo un punto en el límite que la intersecte. La idea es tener un área de preparación aproximadamente central, pero los trabajos futuros incluyen la opción de definir una o más áreas de preparación posibles a las que regresar. Las áreas de preparación se definen actualmente como un único punto en el límite.

La ruta ahora comenzará y terminará en el área de preparación y, cuando sea necesario, el vehículo realizará un recorrido de cabecera de regreso para recargar/descargar. El propio optimizador tiene en cuenta el coste de ir y volver del área de preparación, lo que es diferente de los métodos anteriores, que se realizan como posprocesamiento de una ruta regular sin capacidad. En la literatura académica, esto se conoce como Problema de Enrutamiento de Vehículos con Capacidad, o CVRP.

Experimental

Una colección de funcionalidades futuras y experimentales en las que el equipo de Verge está trabajando. Contáctanos para cualquier pregunta o recomendación sobre lo que te gustaría ver a continuación.

Plan de Trayectoria por Datos de Registro

Usando datos de registro de tu máquina, podemos recrear el recorrido de tu vehículo, permitiendo la reproducción de rutas, análisis y, próximamente, planificación a partir de datos de registro. Esto te permite cubrir exactamente la misma área que una operación anterior, o funcionalidades más complejas como la siembra entre filas o el manejo de filas con huecos. Los algoritmos inteligentes usan datos de registro para reconstruir con precisión las pasadas incluso cuando hay datos ausentes.
Actualmente estamos experimentando con soporte para John Deere y Trimble PTx FarmENGAGE, pero si utilizas un formato particular, estaremos más que encantados de trabajar juntos para adaptarnos a él.

Recreación de Pasadas a Partir de Datos de Sensor

Usando los datos del sensor, a menudo podemos recuperar la línea central original, incluso cuando faltan algunos puntos o tienen lecturas incorrectas.

Reproducción de Ruta con Datos Reales

Visualiza y analiza cómo se trabajó tu campo. Los trabajos futuros pueden incluir análisis detallados de cuándo se realizaron las operaciones, con qué máquinas y sugerencias de cómo mejorarlas.

Implementos Remolcados

Un vehículo puede tener uno o más implementos remolcados acoplados detrás. Actualmente modelamos el vehículo principal con geometría de dirección Ackermann, con el punto de enganche a una distancia fija detrás del eje trasero de cada vehículo e implemento. Se pueden encadenar múltiples implementos y asumimos que todos son no motorizados. Ejecutamos simulaciones cinemáticas del vehículo recorriendo nuestros giros para mostrar dónde estarán los límites del sistema de equipos, alertando sobre situaciones peligrosas de salida del campo. Los trabajos futuros incluyen mejorar los giros teniendo en cuenta el implemento remolcado, optimizar los giros para minimizar el estrés en el enganche e incorporar esto a nuestro algoritmo de búsqueda.

Representación del Campo en Cuadrícula

Un enfoque prometedor usado en autonomía es discretizar el área de trabajo como una cuadrícula, donde un tipo de búsqueda conocido como A* híbrido puede usarse para encontrar el camino dirigible más corto entre cualquier par de puntos en la cuadrícula. A continuación se muestra un ejemplo de una parte de un campo discretizado de esta manera. Las secciones verdes son pasadas de cabecera y se consideran preferibles para el desplazamiento, el marrón es espacio de cabecera válido y el rojo es área peligrosa que podría llevar a salir del campo.

Todos los enfoques actuales se basan en métodos geométricos y, por tanto, pueden tener dificultades para encontrar atajos. Un ejemplo podría ser la sección inferior, donde un enfoque tradicional de "seguir siempre la cabecera" puede hacer que el usuario conduzca innecesariamente alrededor del obstáculo, causando tiempo no productivo adicional. Ejecutando un algoritmo de búsqueda, podemos ver que quizás sea posible cruzar por ahí. Esta estimación aproximada puede ayudar a guiar una búsqueda más refinada, validando que tu vehículo junto con cualquier implemento puede realmente tomar ese atajo.

Un ejemplo de un vehículo buscando un camino en un sistema de cuadrícula más sencillo. Observa cómo el planificador incorpora las dimensiones del vehículo. Los diversos arcos verdes y marrones corresponden a posibles trayectorias que el algoritmo ha explorado antes de encontrar la solución final. Los trabajos futuros incluyen una función de penalización que evite pegarse a las paredes como en este vídeo, así como diversas mejoras de rendimiento, preferencia por recorrer cabeceras y la integración general en nuestra solución completa de enrutamiento.

Próximamente más información sobre posibles casos de uso y más ejemplos.

Opciones de Configuración

Una lista de opciones posibles que se pueden pasar al algoritmo de enrutamiento, junto con una breve explicación. Para más información, consulta nuestra documentación de API o contáctanos.