- Nous proposons deux méthodes de découpage automatique basées sur la notion de direction de travail. - La méthode complète, très coûteuse en temps de calcul, peut être couplée à une méthode heuristique qui permet de déterminer une solution sous- optimale de bonne qualité pouvant être réalisée en un temps beaucoup plus court.. - Direction de travail et côtés d’un champ convexe polygonal. - Détermination de la direction de travail optimale. - Complexité de l’algorithme exhaustif. - Champ, direction de travail et zones. - Direction de travail optimale. - Comme nous venons de l’expliquer, l’objectif recherché est de parcourir un champ pour effectuer un type de travail agricole tel que : le labour, l’épandage, ou la moisson, en minimisant un critère de coût qui sera défini plus loin. - Pour travailler un champ convexe, on choisit une direction de travail. - La trace : Segment de travail entre deux extrémités du champ.. - La direction de travail : direction destinée à guider les traces parallèles du tracteur.. - La zone de travail : La zone dans laquelle le tracteur effectue son travail en exécutant des traces rectilignes et parallèles à la direction de travail.. - La zone de fourrière doit également être travaillée, mais l’ordre de travail n’est pas toujours le même. - Par exemple, pour le labour, elle n’est travaillée qu’après que la zone de travail ait été travaillée. - zone de travail zone de fourrière direction de travail. - Dans le cas des champs non convexes, cependant, le suivi d’une seule direction de travail peut induire un nombre manœuvres très élevé et donc un effort et un temps d’exécution plus grands. - Par exemple, le champ représenté à la figure suivante peut être découpé en deux sous-champs, chacun ayant sa propre direction de travail.. - Chaque tracteur déplace un outil de travail. - La largeur de l’outil est déterminée en fonction du type de travail. - Les paramètres pratiques du tracteur reliés à chaque type de travail peuvent être retrouvés dans [11].. - Nous avons considéré le cas d’une tâche de type labour/semis dans laquelle la zone de travail est travaillée avant la zone de fourrière. - Cependant, seul un petit nombre d’entre elles étudient le problème de recouvrement par des mouvements de type back- forth (avancer-reculer) selon une direction de travail fixée, et prenant en compte l’existence d’une zone de fourrière devant également être travaillée.. - La direction de travail dans chaque cellule n’est pas définie.. - De plus la formule de calcul d’altitude semble complexe, et l’auteur ne présente pas une planification de trajectoire complète.. - Il a introduit des relations paramétriques sur les différents types de travail agricole, les caractéristiques de l’engin, la cinématique du tracteur, et la formule de calcul de la zone de fourrière.En second lieu, il a proposé une méthode de couverture de surface dans un champ sans obstacles. - Cet algorithme suppose que la direction de travail soit à priori déterminée. - Notons que l’exigence de la direction de travail à l’avance semble gênante.. - Sur la base de ces différentes contributions, rappelons que notre travail a pour but de rechercher un algorithme de découpage automatique d’un champ non convexe en sous- champs, en déterminant la direction de travail dans chaque sous-champ. - Le choix d’une direction de travail induit un nombre de traces et par suite un nombre de demi-tours aux extrémités des traces. - Pour un champ polygonal convexe, nous appellerons donc direction de travail optimale, la direction selon laquelle le nombre de demi-tours est minimisé. - Dans un champ polygonal convexe, la direction de travail optimale est toujours parallèle à l’un des côtés du champ. - Autrement dit, il suffit d’effectuer un test sur les directions parallèles à chacun des côtés du champ pour déterminer la direction de travail optimale.. - Démonstration : Si la direction de travail optimale d est parallèle à l’un des côtés du champ, la démonstration est alors triviale. - En résumé, nous avons démontré qu’il est toujours possible de minimiser le nombre de traces et donc de manœuvres en considérant une direction de travail parallèle à l’un des côtés du champ.. - De plus, ce mode de travail est conforme aux habitudes des agriculteurs.. - A partir de la démonstration que nous venons d’établir, l’algorithme de calcul de la direction de travail optimale est évident. - Dans la figure au-dessus, la direction de travail optimale correspond au côté 1-2, parce que la distance maximale entre ce côté et les différents sommets est L 12 , qui est la plus petite parmi L 12 , L 23 , L 34 , L 41. - Comme nous l’avons précédemment montré, dans un champ polygonal convexe la direction de travail optimale est toujours parallèle à l’un des côtés du champ. - Chaque sous-champ ainsi obtenu aura donc un certain côté du champ comme direction de travail. - Le coût d’un sous-champ (région convexe) étant déterminé par le nombre de manœuvres que l’on doit effectuer pour travailler cette région selon la direction de travail optimale.. - Ce qui diffère selon la direction de travail est le nombre de manœuvres effectuées. - Coût de région convexe R i = nombre de manœuvres selon la direction de travail optimale dans R i. - L’algorithme exhaustif de calcul de découpage optimal est détaillé en pseudo-code dans l’annexe 1.. - dans une région convexe), on détermine d’abord les points topologiques qui sont des extrémités de chaque trace dans la zone de travail ainsi que dans la zone de fourrière.. - Ensuite, depuis le point d’entrée du champ, on passe au point le plus proche parmi les points topologiques correspondants à la première et à la dernière trace dans la zone de travail. - Puis on travaille en suivant les traces dans la zone de travail. - Lorsque la zone de travail est entièrement travaillée, on passe au point topologique le plus proche dans la zone de fourrière et on effectue le travail dans la zone de fourrière. - Parfois, la fusion de régions adjacentes peut réduire le coût de travail. - Ici nous proposons de fusionner 2 régions si elles ont la même direction de travail et la région résultat doit être convexe selon cette direction de travail, càd que tout segment parallèle à la direction de travail reliant deux points de cette région sera inclus dans la région.. - Voici un exemple de calcul et le contenu du résultat enregistré. - Resultat de calcul. - Superficie : 353236.18 mettre carre Direction de travail optimale : -63.23 Nombre de manoeuvres : 29.50. - Superficie : 249261.49 mettre carre Direction de travail optimale : 872.77 Nombre de manoeuvres : 28.60. - Superficie : 246040.33 mettre carre Direction de travail optimale : 27.00 Nombre de manoeuvres : 27.50. - temps de calcul : 2.716445 secondes. - Totalité de manoeuvres = 122 Temps de calcul = 0.52 s. - Totalité de manoeuvres = 125 (2.6% d’erreur) Temps de calcul = 0.30 s. - Totalité de manoeuvres = 128 Temps de calcul = 0.73 s. - Totalité de manoeuvres = 128 (0.0% d’erreur) Temps de calcul = 0.41 s. - Totalité de manoeuvres = 117 Temps de calcul = 0.52 s. - Totalité de manoeuvres = 126 (7.7% d’erreur) Temps de calcul = 0.36 s. - Temps de calcul = 1.42 s Totalité de manoeuvres = 120 (0.0% d’erreur) Temps de calcul = 0.49 s. - Si le temps de calcul dans le cas de champs simples (tableaux précédents) semble peu variable, les différences sont considérables pour les champs normaux. - Totalité de manoeuvres = 107 Temps de calcul = 2.00 s. - Totalité de manoeuvres = 107 (0.0% d’erreur) Temps de calcul = 0.58 s. - Totalité de manoeuvres = 110 Temps de calcul = 2.36 s. - Totalité de manoeuvres = 112 (1.8% d’erreur) Temps de calcul = 0.47 s. - Totalité de manoeuvres = 132 Temps de calcul = 11.81 s. - Totalité de manoeuvres = 132 (0.0% d’erreur) Temps de calcul = 0.70 s. - Totalité de manoeuvres = 143 Temps de calcul = 3.70 s. - Totalité de manoeuvres = 146 (2.1% d’erreur) Temps de calcul = 0.50 s. - Totalité de manoeuvres = 138 Temps de calcul = 20.27 s. - Totalité de manoeuvres = 138 (0.0% d’erreur) Temps de calcul = 0.83 s. - Totalité de manoeuvres = 134 Temps de calcul = 49.27 s. - Temps de calcul = 0.81 s. - Totalité de manoeuvres = 164 Temps de calcul = 15.50 s. - Totalité de manoeuvres = 164 (0.0% d’erreur) Temps de calcul = 0.53 s. - Totalité de manoeuvres = 118 Temps de calcul = 95.61 s. - Temps de calcul = 0.94 s. - Totalité de manoeuvres = 106 Temps de calcul = 10.19 s. - Temps de calcul = 0.66 s. - Totalité de manoeuvres = 140 Temps de calcul = 229.83 s. - Totalité de manoeuvres = 141 (0.7% d’erreur) Temps de calcul = 0.80 s. - Totalité de manoeuvres = 178 Temps de calcul = 11.89 s. - Totalité de manoeuvres = 190 (6.7% d’erreur) Temps de calcul = 0.72 s. - Sur les champs complexes, la méthode exhaustive exige énormément de temps de calcul alors que la méthode heuristique en demande beaucoup moins.. - Totalité de manoeuvres = 131 Temps de calcul = 550.60 s. - Totalité de manoeuvres = 134 (2.3% d’erreur) Temps de calcul = 0.83 s. - Totalité de manoeuvres = 148 Temps de calcul = 216.46 s. - Temps de calcul = 1.17 s. - Totalité de manoeuvres = 186 Temps de calcul = 1359.07 s. - Totalité de manoeuvres = 192 (3.2% d’erreur) Temps de calcul = 1.16 s. - La méthode heuristique fournit une bonne approximation en un faible temps de calcul. - Influence de la largeur de l’outil. - Temps de travail total = 10.08 h Longueur parcourue = 53.44 km. - Temps de travail total = 10.06 h Longueur parcourue = 53.20 km En fait, le temps total est un bon critère à ajouter pour juger de la meilleure trajectoire.. - En se basant sur le résultat que la direction de travail permettant de minimiser le nombre de manœuvres est toujours parallèle à l’un des côtés du champ, nous avons introduit différentes stratégies de coupes et développé deux méthodes de calcul de découpage optimal. - Néanmoins, la résolution du problème dans sa globalité nécessite un temps de travail supérieur à un stage de 5 mois. - cout_optimal = cout_optimal + cout de travail de région_eff_max1 . - cout_optimal = cout_optimal + cout de travail de région_eff_max2;