Routage
Intelligent

Aperçu

Notre solution de routage de pointe prend en charge des champs arbitrairement complexes, la navigation en tournière et de nombreuses autres options configurables. Sur cette page vous trouverez des exemples et des explications des différentes fonctionnalités de routage, ainsi que des prototypes expérimentaux nouveaux et passionnants.

Modélisation des virages

Nous prenons en charge différents types de virage, choisis automatiquement en fonction d'une combinaison de la géométrie du champ et des caractéristiques des équipements. Si deux voies sont à moins de 3 largeurs de passage l'une de l'autre, nous tenterons de les connecter directement par un virage. Si les voies sont plus éloignées, ou s'il n'existe aucun virage pouvant s'y adapter, nous effectuerons ce que nous appelons une traversée de tournière, expliquée plus en détail ci-dessous.

Connecteurs voie-voie

Pour une connexion directe de voie à voie, nous prenons en charge les types de virage suivants :

Demi-tour en U

Lorsque le rayon de braquage est inférieur à 50 % de la largeur de passage, des demi-tours en U comme celui-ci seront générés pour les voies adjacentes. Il existe une option pour prolonger le segment droit jusqu'à la tournière afin de donner plus de place pour virer et minimiser le compactage.

Demi-tour en U parfait

Lorsque le rayon de braquage est exactement 50 % de la largeur de passage, des demi-tours en U parfaits comme celui-ci seront générés pour les voies adjacentes, sans segment droit entre les deux.

Virage en ampoule

Lorsque le rayon de braquage est supérieur à 50 % de la largeur de passage, un virage en ampoule est utilisé pour connecter deux voies adjacentes. Ce type ne serait utilisé que si un demi-tour en U ne peut pas s'y adapter.

Virage en P

Si la tournière est à un angle aigu par rapport au virage et que le rayon de braquage est suffisamment grand, nous prenons en charge les virages en P pour minimiser la quantité de braquage nécessaire.

Connecteurs voie-tournière

Si une connexion directe n'est pas possible, nous nous connecterons à une tournière proche en effectuant une ou plusieurs traversées de tournière pour relier deux voies. Cela nous permet de créer des chemins entre presque toutes les deux voies du champ entier sans traverser invalablement le champ en dehors d'une zone de tournière.

Connecteurs en arc

Par défaut, nous essayons d'utiliser des connecteurs en arc, qui ont une courbure constante et un rayon de braquage au moins aussi grand que le rayon de braquage minimum. Cela permet une transition douce de la voie vers la tournière sans mouvements brusques. Le virage peut être automatiquement raccourci s'il n'y a pas suffisamment de place pour le compléter sans que le véhicule ne quitte la limite.

Connecteurs Dubins

Si un connecteur en arc échoue, une recherche est effectuée pour connecter un connecteur Dubins à divers points de la tournière dans la direction de déplacement souhaitée, jusqu'à en trouver un valide qui minimise le changement d'angle total.

Connecteur de secours

En dernier recours, nous créons un connecteur de secours qui relie directement les deux points (soit entre deux voies soit voie-tournière) et apparaît dans l'interface comme une grande ligne rouge. L'utilisateur doit effectuer ce virage manuellement avant de continuer l'itinéraire.

Raccourcissement des virages

Si un virage ne peut pas s'adapter d'une voie à une autre ou vers une tournière sans qu'une partie du véhicule quitte la limite, et si le paramètre "Raccourcir les voies" est activé, le virage sera raccourci, c'est-à-dire qu'il amorcera plus tôt que la fin de la voie pour pouvoir le réaliser. Malheureusement, cela cause une zone manquée, à moins que votre véhicule puisse faire marche arrière avant d'effectuer le virage (les travaux futurs prendront en charge cette fonctionnalité si la demande existe). Si vous remarquez qu'une grande superficie est manquée, vous n'avez probablement pas suffisamment de tournières par rapport au rayon de braquage de votre véhicule et vous devrez peut-être relancer le plan avec davantage de tournières. La feuille de route prévoit de suggérer automatiquement le nombre de tournières en fonction de votre champ et de votre équipement.

Extension des virages

Dans certaines situations, il peut être souhaitable d'étendre vos virages davantage dans la tournière. Cela peut être activé en basculant le paramètre "Étendre les virages dans les tournières". Si un virage peut s'adapter, il sera étendu de sorte qu'il touche la tournière la plus extérieure. Cela offre plus de place pour virer et se redresser, tout en minimisant le compactage. Les travaux futurs prévoient de se raccrocher toujours aux tournières lorsque possible pour minimiser encore davantage le compactage.

Connexions de tournière raccourcies

Les virages adjacents raccourcis pour s'adapter à la tournière seront convertis en traversées de tournière si possible. Cela peut être activé en basculant "Préférer les connexions de tournière raccourcies". Les travaux futurs prévoient d'activer cela pour toutes les connexions voie-voie.

Sans paramètre

Le virage est raccourci pour toucher juste la tournière, mais ne la traverse pas.

Avec paramètre

Les connexions sont faites le long de la tournière entre des connecteurs adjacents, minimisant le compactage.

Navigation en tournière

Lorsqu'un virage direct de voie à voie n'est pas possible, la solution de routage passe en mode de navigation en tournière. Des connecteurs des voies vers les tournières sont créés, suivis d'une série de traversées de tournière et de connecteurs entre tournières.

Traversées complètes de tournière

Travaillez automatiquement toutes les tournières de votre champ avec une planification supplémentaire, en trouvant efficacement un chemin aller-retour pour chaque tournière d'un groupe, minimisant la distance non travaillée parcourue tout en préservant la circulation des roues. Notre algorithme peut partir de n'importe quelle voie de départ ou d'arrivée sur la tournière. L'algorithme empêche tout virage susceptible de heurter l'obstacle, garantissant ainsi la sécurité.

Préférer la tournière extérieure

Lors des traversées de tournière, l'algorithme se connecte par défaut à la tournière extérieure la plus centrale, car elle offre un bon compromis entre l'espace pour virer et se redresser. Activer "Préférer la tournière la plus extérieure" permettra de se connecter à la tournière la plus extérieure.

Comportement par défaut

Les traversées de tournière se connectent naturellement à la tournière la plus centrale.

Virages connectés à la tournière la plus extérieure

Lorsque "Préférer la tournière la plus extérieure" est activé, toutes les traversées de tournière se connectent à la tournière extérieure la plus extérieure si possible.

Routage multi-voies internes

Exemple d'une situation complexe où le solveur d'itinéraire trouve un chemin à travers plusieurs tournières, les travaillant ainsi que toutes les voies internes.

Croisillons de tournière

Si un angle est trop aigu sur une tournière ou une voie courbe et que l'objectif est de minimiser la superficie manquée, nous prenons en charge un flux de travail en croisillons : on prolonge les lignes et on les connecte avec un arc qui respecte le rayon de braquage du véhicule. Les travaux futurs prévoient d'étendre encore davantage le virage afin que l'ensemble du véhicule se redresse avant de reculer.

Tournières directrices

Si un changement d'angle dépasse un certain seuil dans une tournière ou une voie courbe, nous le marquons comme nécessitant un lissage. Nous intégrons ensuite intelligemment des cercles avec le rayon de braquage du véhicule de façon à minimiser la superficie manquée entre les passes. Après le lissage, nous obtenons une passe de tournière qui respecte les contraintes de courbure du véhicule et minimise la superficie manquée. Les travaux futurs prévoient une décision plus intelligente entre le lissage et l'utilisation de croisillons dans un coin.

Avant le lissage

Exemples de résultats d'un algorithme de décalage standard. Bien que la couverture soit plus grande, le véhicule ne peut physiquement pas effectuer des virages aussi serrés.

Après le lissage

Après l'application du lissage. Les virages que l'algorithme n'a pas pu lisser sont convertis en croisillons. Tous les virages lissés respectent le rayon de braquage minimum.

Algorithmes / Motifs

Algorithme par défaut

Par défaut, nous modélisons le problème comme une instance du Problème de routage agricole (ARP), qui est la version agricole du bien connu Problème de routage de véhicules. Il s'agit de ce que l'on appelle NP-difficile, ce qui signifie qu'il n'existe aucun algorithme pouvant résoudre efficacement toutes les instances possibles du problème de manière parfaite. C'est pourquoi nous avons développé un solveur méta-heuristique personnalisé pour résoudre l'ARP, en encodant les standards des producteurs dans la matrice de coûts elle-même, générant un itinéraire capable de naviguer dans les champs les plus complexes en quelques minutes voire secondes.

Notre solveur de routage calcule les distances vers/depuis chaque paire possible de voies dans le champ, en utilisant des itinéraires exacts pour les voies dans à peu près la même zone, et des estimations intelligentes pour les voies du côté opposé du champ. Cela crée ce que l'on appelle une matrice de distances, qui est ensuite fournie à notre solveur propriétaire pour optimiser un chemin qui traverse chaque voie et tournière, tout en minimisant la distance non travaillée. Aucune hypothèse préalable n'est faite sur le motif de travail ; les résultats sont uniquement basés sur les distances calculées entre elles. Cela permet au solveur d'avoir parfois une remarquable prévoyance, en sautant une ou plusieurs voies qui ne sont pas immédiatement évidentes pour un utilisateur, pour ensuite les utiliser afin de sortir efficacement d'une situation dans laquelle une approche traditionnelle l'aurait piégé.

Éviter de sauter des passes

Lorsqu'activé, le coût de déplacement vers une voie adjacente est divisé par deux. Cela encourage (mais ne force en aucun cas) un motif plus rectiligne, au coût potentiel d'une distance non travaillée supplémentaire, ou dans le cas ci-dessous, d'une plus grande superficie manquée. Dans l'exemple ci-dessous, une autre tournière pourrait être préférable pour que les virages s'adaptent.

Voies continues (Boustrophedon)

Un motif aller-retour prédéfini, partant d'un côté du champ et allant jusqu'à l'autre. Idéal pour les champs simples et ceux avec de petits obstacles.

Si vous remarquez qu'il y a trop de traversées de tournière, nous recommandons d'exécuter notre algorithme par défaut et d'activer "Éviter de sauter des passes". Cela évitera les cas extrêmes de traversées de tournière, au coût de la perte d'uniformité.

Spirale groupée

Un motif prédéfini qui impose toujours au moins un saut de N voies dans un motif d'avancer puis reculer. Fonctionne mieux dans les champs simples et ceux avec de petits obstacles.

Serpent

Le motif serpent couvre le champ en sautant une voie à chaque virage, puis en revenant par les voies non couvertes. Réduit le nombre de virages serrés.

Routage par capacité

Si l'utilisateur spécifie une capacité et un débit pour son véhicule, il peut accéder à nos diverses fonctionnalités de routage par capacité. Actuellement nous avons deux flux de travail distincts pour cela. Le premier est Véhicule unique, qui correspond au type d'itinéraires présenté ci-dessus, sans zone de départ et avec un seul véhicule en activité. L'autre est Multi-véhicules avec capacité, où un ou plusieurs véhicules partent d'une zone de départ et peuvent travailler des voies jusqu'à ce qu'ils atteignent leur capacité, auquel point ils traverseront les tournières jusqu'au dépôt de départ.

Multi-véhicules avec zone de départ

Actuellement un paramètre expérimental en cours de développement. Les itinéraires peuvent ne pas être bien optimisés et peuvent se comporter de manière étrange voire planter complètement jusqu'à ce que nous les développions davantage.

Si activé, une zone de départ sera déterminée en étendant d'abord la voie médiane dans le champ et en choisissant un point sur la limite qui l'intersecte. L'idée est d'avoir une zone de départ approximativement centrale, mais les travaux futurs prévoient l'option de définir une ou plusieurs zones de départ possibles vers lesquelles revenir. Les zones de départ sont actuellement définies comme un seul point sur la limite.

L'itinéraire commencera et se terminera maintenant à la zone de départ, et lorsque nécessaire, le véhicule effectuera une traversée de tournière pour revenir à la zone de départ pour le remplissage/dépôt. L'optimiseur lui-même prend en compte le coût du retour vers et depuis la zone de départ, ce qui est différent des méthodes ci-dessus qui sont effectuées en post-traitement sur un itinéraire régulier sans capacité. Dans la littérature académique, cela est connu sous le nom de Problème de routage de véhicules avec capacité, ou CVRP.

Expérimental

Une collection de fonctionnalités à venir et expérimentales sur lesquelles l'équipe Verge travaille. N'hésitez pas à nous contacter pour toute question ou recommandation sur ce que vous aimeriez voir ensuite.

Plan de trajectoire par données de journal

En utilisant les données de journal de votre machine, nous pouvons reconstituer le trajet de votre véhicule, permettant la relecture d'itinéraires, l'analyse et bientôt la planification à partir de données de journal. Cela vous permet de couvrir exactement la même zone qu'une opération précédente, ou des fonctionnalités plus complexes comme le semis entre les rangs ou la gestion des rangs manquants. Des algorithmes intelligents utilisent les données de journal pour reconstruire avec précision les voies même lorsque des données sont manquantes.
Nous expérimentons actuellement la prise en charge de John Deere et Trimble PTx FarmENGAGE, mais si vous utilisez un format particulier, nous serions plus que ravis de travailler ensemble pour l'accommoder.

Reconstitution de voies à partir de données de capteurs

En utilisant les données des capteurs, nous pouvons souvent récupérer la ligne centrale d'origine, même lorsque certains points sont manquants ou ont des lectures incorrectes.

Relecture d'itinéraire avec données réelles

Visualisez et analysez comment votre champ a été travaillé. Les travaux futurs pourraient inclure des analyses détaillées des opérations effectuées, par quelles machines, et des suggestions d'amélioration.

Outils tractés

Un véhicule peut avoir un ou plusieurs outils tractés attachés derrière lui. Nous modélisons actuellement le véhicule principal avec une géométrie de direction Ackermann, le point d'attelage étant à une distance fixe derrière l'essieu arrière de chaque véhicule et outil. Plusieurs outils peuvent être enchaînés, et nous supposons que tous les outils sont non motorisés. Nous exécutons des simulations cinématiques du véhicule parcourant nos virages pour montrer où se trouveront les limites de votre système d'équipement, vous alertant de toute situation dangereuse de sortie du champ. Les travaux futurs incluront l'amélioration des virages pour tenir compte de l'outil tracté, l'optimisation des virages afin de minimiser les contraintes sur l'attelage, et l'intégration de tout cela dans notre algorithme de recherche.

Représentation du champ en grille

Une approche prometteuse souvent utilisée en autonomie consiste à discrétiser la zone de travail sous forme de grille, où un type de recherche connu sous le nom de hybrid A* peut être utilisé pour trouver le chemin directeur le plus court entre deux points quelconques de la grille. Ci-dessous, un exemple d'une partie d'un champ discrétisé de cette manière. Les sections vertes sont des passes de tournière et sont considérées comme préférables pour se déplacer, le marron est un espace de tournière valide, et le rouge est une zone dangereuse qui pourrait faire sortir du champ.

Toutes les approches actuelles sont basées sur des méthodes géométriques et peuvent donc avoir du mal à trouver des raccourcis. Un exemple pourrait être la section du bas, où une approche traditionnelle "toujours suivre la tournière" pourrait amener l'utilisateur à contourner inutilement l'obstacle, causant un temps non productif supplémentaire. En exécutant un algorithme de recherche, on peut voir qu'il serait peut-être possible de traverser ici. Cette estimation approximative peut aider à guider une recherche plus fine, validant que votre véhicule ainsi que tous les outils peuvent effectivement emprunter ce raccourci.

Exemple d'un véhicule cherchant un chemin dans un système de grille plus simple. Remarquez comment le planificateur intègre les dimensions du véhicule. Les différents arcs verts et marrons correspondent à des trajectoires possibles que l'algorithme a explorées avant de trouver la solution finale. Les travaux futurs incluent une fonction de pénalisation qui évite de longer les murs de près comme dans cette vidéo, ainsi que diverses améliorations de performance, une préférence pour le déplacement le long des tournières, et l'intégration générale dans notre solution de routage complète.

Plus d'informations sur les cas d'utilisation potentiels et d'autres exemples à venir prochainement.

Options de configuration

Une liste d'options possibles à passer à l'algorithme de routage, avec une brève explication. Pour plus d'informations, veuillez consulter notre documentation API ou nous contacter.