TITRE : Procédé pour déterminer des positions optimisées d'un objet pour le suivi d'une trajectoire dans un environnement simulé.

La présente invention concerne un procédé pour déterminer des positions optimisées d'au moins un objet doté d'un champ de vision pour le suivi d'une trajectoire dans un environnement simulé comprenant des obstacles, le champ de vision pouvant être défini par une source, une portée et un angle d'ouverture.

L'invention s'applique notamment dans le domaine de géolocalisation précise dans des zones non couvertes par les systèmes classiques (GPS, signaux radio, amers visuels...) telles que les intérieurs de bâtiments, les mines, mais aussi les autres planètes, qui posent des difficultés majeures pour les tâches d'exploration et/ou de surveillance/maintenance.

D'une façon générale, un modèle de l'environnement est disponible ou conçu de façon à faire apparaître des passages et des éléments fixes comme par exemple des parois, murs, poteaux, .... Il peut s'agir d'un modèle fini ou encore à élaborer. Une trajectoire peut être prédéfinie dans l'environnement pour une mission d'exploration à travers des passages en évitant tout obstacle. Pour ce faire, il est prévu de positionner l'objet sur différents emplacements dans l'environnement pour un suivi efficace d'un élément mobile se déplaçant sur la trajectoire.

La présente invention a pour but de déterminer des emplacements optimisés pour positionner l'objet.

Un autre but de l'invention est de minimiser le temps de calcul pour déterminer ces emplacements.

L'invention a encore pour but la détermination d'un nombre minimum d'emplacements permettant de couvrir l'ensemble de la trajectoire.

On atteint au moins l'un des objectifs précités avec un procédé pour déterminer des positions optimisées d'au moins un objet doté d'un champ de vision pour le suivi d'une trajectoire dans un environnement simulé comprenant des obstacles, le champ de vision comprenant une source, une portée et un angle d'ouverture. Selon l'invention, le procédé est mis en œuvre par un ordinateur et comprend les étapes suivantes : a) sélection d'un ensemble de positions candidates, b) pour chaque position candidate, construction d'un champ de vision local placé à cette position candidate et orienté suivant les étapes suivantes : bl) définition de deux vecteurs positionnés à la position candidate et orientés vers un premier point d'un segment de la trajectoire principale, ce premier point étant à la portée de l'objet lorsque l'objet est placé à la position candidate, b2) balayage point par point du segment ; à chaque nouveau point balayé du segment, les vecteurs pointent vers deux points balayés les plus écartés vis-à-vis de la position candidate, b3) fin de balayage lorsqu'un nouveau point balayé est considéré non valide ; un point balayé étant considéré non valide lorsque ce point balayé se trouve hors de portée ou l'angle formé par les deux vecteurs est supérieur à l'angle d'ouverture du champ de vision ou un obstacle se trouve dans le triangle formé par la position candidate, le précédent point balayé et le nouveau point balayé; le champ de vision local étant défini par la portée du champ de vision et un angle d'ouverture formé par les deux vecteurs pour le dernier point balayé valide, c) affectation d'un score à chaque position candidate, d) construction globale des positions optimisées en réalisant les étapes suivantes : dl) à partir d'une extrémité de la trajectoire principale, détermination d'une position candidate ayant le score le plus élevé parmi un ensemble de positions candidates ayant un champ de vision local couvrant ledit point de départ ; le champ de vision local de la position candidate ainsi déterminée couvrant un segment de la trajectoire principale, d2) application successive de l'étape précédente sur le reste de la trajectoire principale jusqu'à ce qu'un champ de vision local couvre une autre extrémité de la trajectoire principale, d3) sauvegarde de l'ensemble des positions candidates ainsi déterminées comme étant les positions optimisées pour le placement dudit objet. Le procédé selon l'invention permet, pour des positions candidates, d'orienter des champs de vision locaux de façon efficace. La construction globale permet de retenir un minimum de position pour couvrir l'ensemble de la trajectoire. De ce fait, un mobile se déplaçant le long de la trajectoire principale peut totalement être suivi depuis les positions optimisées. Selon l'invention, il est prévu d'avoir plusieurs objets, chacun disposé à une position optimisée, ou bien d'avoir au moins un objet apte à se déplacer sur plusieurs positions optimisées en fonction du déplacement dudit mobile sur la trajectoire.

Le champ de vision peut être formalisé sous la forme d'un secteur circulaire, c'est-à-dire un secteur de disque défini par un angle d'ouverture et un rayon égal à la portée de l'objet.

Selon une caractéristique avantageuse de l'invention, l'étape a) de sélection d'un ensemble de positions candidates peut comprendre les étapes suivantes :

- détermination d'une zone de détection optimisée le long de la trajectoire principale, cette zone étant délimitée par une trajectoire virtuelle gauche, dite sentier gauche, et une trajectoire virtuelle droite, dite sentier droit, les deux trajectoires virtuelles étant à une distance fixe de la trajectoire principale,

- pour tout point de la trajectoire principale, détermination d'une position candidate disposée perpendiculairement à la trajectoire principale et située sur le sentier gauche ou à une distance minimale de sécurité d'un obstacle si cet obstacle se trouve entre le sentier gauche et le point de la trajectoire principale,

- pour tout point de la trajectoire principale, détermination d'une position candidate disposée perpendiculairement à la trajectoire principale et située sur le sentier droit ou à une distance minimale de sécurité d'un obstacle si cet obstacle se trouve entre le sentier droit et le point de la trajectoire principale.

Par distance minimale de sécurité, on entend une distance minimale déterminée en fonction de la taille de l'élément qui doit suivre la trajectoire. De préférence, les sentiers gauche et droit sont ainsi contraints non pas directement par les obstacles mais par des zones de sécurité autour des obstacles.

La perpendiculaire à la trajectoire est déduite de la tangente approchée de la trajectoire principale, et correspond à la normale à la trajectoire au point considéré. Avec l'invention, l'ensemble des positions candidates peut être positionné sur des sentiers gauche et droite adaptés. Ces sentiers permettent de garantir le fait que l'objet sera placé majoritairement à une même distance optimisée pour le suivi d'un mobile sur la trajectoire.

En complément notamment de tout ce qui précède, la distance entre la trajectoire principale et le sentier gauche ou le sentier droit peut être déterminée en réalisant les étapes suivantes :

- détermination d'une corde C du champ de vision comme étant la distance maximum d'un segment inscrit dans le champ de vision,

- détermination d'une bande de tolérance comprenant la corde C, la distance entre la trajectoire principale et le sentier gauche ou droit est définie comme étant égale à une hauteur entre la source et le milieu de la bande de tolérance.

Le procédé selon l'invention permet donc de prévoir une distance optimisée entre l'objet et la trajectoire de façon à couvrir un maximum de longueur de la trajectoire à chaque position. La bande de tolérance est une marge de tolérance de la distance entre l'objet et la trajectoire. C'est-à-dire que, pour un objet positionné et orienté face à la trajectoire, tant que les variations de la trajectoire restent dans cette marge, l'on considère que le champ de vision couvre un segment de la trajectoire acceptable.

En complément notamment de tout ce qui précède, l'étape a) de sélection d'un ensemble de positions candidates peut en outre comprendre les étapes suivantes :

- détermination d'une zone réservée autour de la trajectoire principale, cette zone réservée étant moins large que la zone de détection optimisée ; des espaces obtenus entre la zone de détection optimisée et la zone réservée constituant des zones différentielles, et

- sélection de tout ou partie des points des zones différentielles comme des positions candidates.

Ladite zone réservée correspond à une zone réservée à l'élément mobile à suivre.

Il s'agit là d'un moyen pour obtenir plus de positions candidates non pas sur les sentiers mais également sur des surfaces qui sont plus proches de la trajectoire tout en conservant une distance minimum de sécurité représentée par la zone réservée. En complément notamment de ce qui précède, la sélection d'une partie des points des zones différentielles est obtenue lors de chaque étape dl) de détermination d'une position candidate ayant le score le plus élevé ; ledit ensemble de positions candidates comprenant en outre des positions candidates obtenues selon les étapes suivantes : dll) identification de parties des zones différentielles se trouvant à portée de la dite extrémité de la trajectoire principale ; pour chaque partie identifiée, réalisation des étapes suivantes : d 12) échantillonnage à une résolution, dl3) évaluation en calculant un score pour chaque point obtenu après échantillonnage, dl4) sélection du meilleur point, dl5) détermination d'une zone limitée autour du meilleur point sélectionné, dl6) répétition des étapes dl2) à dl5) avec augmentation de ladite résolution à chaque répétition jusqu'à atteindre un niveau de résolution prédéterminé, puis sélection du dernier meilleur point comme position candidate.

Le procédé selon l'invention permet de rechercher des positions candidates dans des parties des zones différentielles. Pour ce faire, en même temps que l'on parcourt la trajectoire lors de la phase de construction globale, on augmente le nombre de positions candidates en considérant les points à la portée du premier de chaque segment de trajectoire. La position candidate qui sera retenue est celle qui présentera le meilleur score.

Par zone limitée on entend une zone de dimension inférieure à la dimension de la partie identifiée, par exemple cette zone limitée peut être délimitée par les plus proches voisins du point sélectionné.

Selon un mode de réalisation de l'invention, la sélection d'une partie des points dans une zone différentielle peut comprendre les étapes suivantes : dl2) échantillonnage à une résolution, dl3) évaluation en calculant un score pour chaque point obtenu après échantillonnage, dl4) sélection du meilleur point, dl5) détermination d'une zone limitée autour du meilleur point sélectionné, dl6) répétition des étapes dl2) à dl5) avec augmentation de ladite résolution à chaque répétition jusqu'à atteindre un niveau de résolution prédéterminé, puis sélection du dernier meilleur point comme position candidate.

En complément notamment de ce qui précède, chaque zone différentielle peut être découpée en plusieurs sous-zones différentielles comprenant plusieurs points échantillonnés. Par ailleurs, les étapes dl2) à dl5) peuvent alors être réalisées sur chacune des sous-zones différentielles ainsi découpées.

Dans ce mode de réalisation, les positions candidates sur les zones différentielles peuvent être obtenues indépendamment et en amont de la phase de construction globale.

L'avantage de réaliser des multi-échantillonnages sur de petites surfaces est de diminuer le coût des calculs par rapport à un échantillonnage haute résolution sur toutes les zones différentielles.

Selon une caractéristique avantageuse de l'invention, les points de la trajectoire principale peuvent être déterminés par échantillonnage aléatoire, systématique, notamment à intervalle régulier, ou selon une règle prédéterminée.

Selon l'invention, le score peut être une longueur du segment balayé ou le nombre de points balayés.

Selon un mode de réalisation préféré, l'objet est un dispositif électronique de détection. Il peut s'agir d'un laser, une caméra, une tribune à disposer le long d'un circuit automobile, etc.

Il est également prévu un système de traitement de données comprenant des moyens pour mettre en œuvre les étapes du procédé tel que défini ci-dessus.

L'invention concerne également un produit programme d'ordinateur comprenant des instructions qui, lorsque le programme est exécuté par un ordinateur, conduisent celui-ci à mettre en œuvre les étapes du procédé tel que défini ci-dessus. D'autres avantages et caractéristiques de l'invention apparaîtront à l'examen de la description détaillée d'un mode de mise en œuvre nullement limitatif, et des dessins annexés, sur lesquels :

[Fig. 1] La figure 1 est une vue schématique d'un modèle de l'environnement, [Fig. 2] La figure 2 est une vue schématique de plusieurs modèles représentant le champ de vision d'un phare, avec 6 variant,

[Fig. 3] La figure 3 est une schématique illustrant un principe de détermination d'une bande de tolérance,

[Fig. 4] La figure 4 est une vue schématique permettant de comparer des largeurs de bandes comme définies sur la figure 3,

[Fig. 5] La figure 5 est une vue schématique illustrant des sentiers idéaux, représentés dans l'environnement,

[Fig. 6] La figure 6 est une vue schématique illustrant des sentiers adaptés à l'environnement, trajectoire sous-échantillonnée,

[Fig. 7] La figure 7 est une vue schématique illustrant des sentiers adaptés calculés en utilisant tous les points,

[Fig. 8] La figure 8 est une vue schématique illustrant un processus pour déterminer le champ de vision local,

[Fig. 9] La figure 9 est une vue schématique illustrant une succession d'étapes d'optimisations locales constituant une solution globale,

[Fig. 10] La figure 10 est une vue schématique illustrant une solution globale obtenue à partir des sentiers,

[Fig. 11] La figure 11 est une vue schématique illustrant une zone réservée autour de deux segments de la trajectoire et la génération d'une surface de solutions autour de deux points distincts,

[Fig. 12] La figure 12 est une vue schématique illustrant un échantillonnage régulier et une optimisation locale,

[Fig. 13] La figure 13 est une vue schématique illustrant un échantillonnage progressif,

[Fig. 14] La figure 14 est une vue schématique illustrant une succession d'étapes locales en passant de segment en segment de la trajectoire avec un échantillonnage progressif de chaque surface couverte par le champ de vision local.

Les modes de réalisation qui seront décrits dans la suite ne sont nullement limitatifs; on pourra notamment mettre en œuvre des variantes de l'invention ne comprenant qu'une sélection de caractéristiques décrites par la suite isolées des autres caractéristiques décrites, si cette sélection de caractéristiques est suffisante pour conférer un avantage technique ou pour différencier l'invention par rapport à l'état de la technique antérieur. Cette sélection comprend au moins une caractéristique de préférence fonctionnelle sans détails structurels, ou avec seulement une partie des détails structurels si cette partie uniquement est suffisante pour conférer un avantage technique ou pour différencier l'invention par rapport à l'état de la technique antérieur.

En particulier toutes les variantes et tous les modes de réalisation décrits sont prévus pour être combinés entre eux dans toutes les combinaisons où rien ne s'y oppose sur le plan technique.

Les différents modes de réalisation de la présente invention comprennent diverses étapes. Ces étapes peuvent être mises en œuvre par des instructions d'une machine exécutable au moyen d'un microprocesseur par exemple.

Alternativement, ces étapes peuvent être réalisées par des circuits intégrés spécifiques comprenant une logique câblée pour exécuter les étapes, ou par toute combinaison de composants programmable et composants personnalisés.

La présente invention peut également être fournie sous forme d'un produit programme d'ordinateur qui peut comprendre un support mémoire informatique non-transitoire contenant des instructions exécutables sur une machine informatique, ces instructions pouvant être utilisées pour programmer un ordinateur (ou tout autre dispositif électronique) pour exécuter le procédé.

Bien que l'invention n'y soit pas limitée, nous allons maintenant décrire un procédé selon l'invention pour déterminer les positions d'un détecteur laser pour le suivi de la trajectoire d'un robot dans un environnement simulé. Ce détecteur laser est par la suite nommé phare. Il peut s'agir de tout type de dispositif auquel un champ de vision peut être associé. On peut par ailleurs citer un drone équipé d'un moyen de détection et/ou de visualisation.

La figure 1 est une vue schématique d'un modèle d'environnement représentant des parois 1 et des poteaux 2. Les espaces vides sont des passages par lesquels une ou plusieurs trajectoires peuvent être envisagées.

La présente invention concerne une stratégie de placement des phares, de manière à optimiser, ici minimiser, le nombre de positions des phares nécessaire à la réalisation d'une mission donnée. La mission peut être l'exploration de l'environnement par deux robots ou drones, l'un servant de phare placé successivement dans des positions optimisées pour visualiser le parcours du second.

L'objectif de l'invention est de déterminer les positions des phares dans un environnement simulé pour ensuite en déduire un positionnement desdits phares dans l'environnement réel. Les positions qui seront déterminées ont un effet technique dans le suivi d'un mobile sur une trajectoire dans l'environnement réel.

Une solution au problème global est une liste de couples (placement, section) décrivant comment positionner le phare et quelle section de la trajectoire est couverte par le phare ainsi positionné :

Solution = [ placemento, sectiono) , . . . placement,,, section,,)

L'optimisation au niveau global consiste donc à minimiser le nombre n de couples nécessaires à la réalisation de la mission. Cependant, chaque étape est dépendante de la précédente, le point de départ de la sectionk+i étant le dernier point de la section/,.

L'optimal global peut être obtenu en sélectionnant successivement les meilleures solutions locales. C'est-à-dire choisir le placement du phare qui permet de maximiser la section de trajectoire couverte, puis boucler sur le reste de la trajectoire.

La présente invention permet notamment de déterminer l'espace de solutions locales, qui est en réalité un ensemble de placements possibles du phare, de calculer la pertinence de chacune de ces solutions sous la forme d'un score déterminé analytiquement de façon à sélectionner le meilleur placement, puis de construire la solution globale couvrant toute la trajectoire.

Pour un phare émettant un laser dans l'environnement, la zone couverte peut être définie par divers éléments :

- la portée p : distance en mètres à laquelle les récepteurs sont encore capables de capter et d'exploiter les informations encodées dans les lasers,

- angle 6 : angle délimitant le champ de vision, exprimé en degrés où en radians

Ainsi, la zone de couverture d'un phare est un secteur circulaire, défini par les inéquations suivantes : x ² + y ² < p ² -tan (0/2) < x/y < tan 6/2) y > 0

La figure 2 présente le modèle d'un phare, ou plutôt trois déclinaisons de ce modèle, avec une portée identique p = 5m mais avec différentes valeurs de l'angle d'ouverture 6. Lors d'une exploration typique, la trajectoire est majoritairement rectiligne, les variations de directions, c'est-à-dire les virages, n'étant que des cas particuliers entre deux sections rectilignes. En faisant l'hypothèse d'une trajectoire rectiligne, il devient alors aisé de déterminer comment placer le phare par rapport à la trajectoire. Ainsi, lorsque l'angle d'ouverture est petit : 6 < 60°, le plus grand segment inclus dans la zone de couverture est n'importe lequel des rayons du secteur circulaire, de longueur p, c'est le cas de l'exemple représenté avec 6 = 40°.

Dans le cas où 6 = 60°, la corde c et les deux rayons extrêmes délimitant le secteur circulaire forment un triangle équilatéral, donnant donc c = p. Enfin, dans le dernier cas, où 6 > 60° le plus grand segment inclus dans le secteur devient la corde c. Sa longueur est calculable en évaluant l'équation suivante c = 2p. si n (0/2)

Dans l'exemple de la figure 2, c atteint plus de 9.5m, alors que la portée du phare n'est que de 5m. Placer le phare de manière à superposer la corde c du secteur circulaire permet donc de maximiser la longueur de trajectoire rectiligne couverte par le phare. Et donc, par la même occasion, de minimiser le nombre de déplacements de phare nécessaires à la bonne conduite d'une mission. Afin d'effectuer cette superposition, il convient de placer le phare, orienté perpendiculairement à la direction de la trajectoire, à une distance d de cette dernière, calculée de la manière suivante : d = p.cos(0/2)

Cependant, même en dehors des virages, les trajectoires sont rarement parfaitement rectilignes, mais plutôt contenues dans une bande réduite, dont la largeur varie selon le scénario et l'intensité du lissage. Ainsi, modéliser la trajectoire par une bande de largeur b permet de mieux prendre en compte les réalités du terrain. La figure 3 représente cette bande, inscrite dans le secteur circulaire. Elle est définie entre une bordure intérieure, la corde c (à distance d du phare) et une bordure extérieure, la corde c' (à une distance d' = d + b du phare).

Augmenter la largeur b de la bande aura pour conséquence de diminuer la longueur maximale de bande couverte, à l'avantage de la capacité à mieux couvrir les cas où la trajectoire ne serait pas totalement rectiligne, ainsi que les virages bruts de la trajectoire. Cette capacité de tolérance est proportionnelle à l'aire de la bande, qui est définie de la manière suivante :

Le choix de la largeur de bande b peut être un compromis entre longueur maximale couverte et aire maximale couverte. L'évaluation de ces grandeurs en fonction de la largeur de bande est présentée sur la figure 4, qui propose un compromis déterminé par l'intersection des courbes distance (décroissante) et aire (croissante) exprimées dans la même échelle. Sur la figure 4, l'intersection correspond à la valeur de b = 2.25m, ce qui donne un c' = 7.06m.

On prévoit de placer le phare orienté en direction de la trajectoire à une distance constante. Cette distance est déterminée en additionnant la distance d définie précédemment (entre le phare et la bordure intérieure) et la moitié de la largeur de bande. Ainsi : dphare = p.cos(0/2) +b/2

Dans le cas présent, pour Q =150°, b=2.25m et p=5m, on obtient une distance de dphare = 2.418m.

Sur la figure 5 est représentée une trajectoire principale 51. Les phares doivent être placés dans des positions optimisées pour couvrir l'ensemble de cette trajectoire principale 51. Cette trajectoire principale peut avoir notamment été déterminée lors d'un processus de génération de trajectoire faisant intervenir des allées en pointillées sur la figure 5.

Pour tenir compte de la distance dphare dans le positionnement du phare, on peut définir une nouvelle trajectoire de chaque côté de la trajectoire principale, que nous nommerons sentiers. Chaque sentier est une trajectoire virtuelle parallèle à la trajectoire principale, décalée d'une distance constante dphare vers la gauche ou vers la droite. Le côté gauche ou droit est une simple représentation pour spécifier que les sentiers sont disposés de part et d'autre de la trajectoire principale dans une représentation 2D de l'environnement simulé, vu de dessus.

Ainsi, un sentier est l'ensemble des solutions possibles au problème d'optimisation du placement des phares respectant le critère de distance défini ci-dessus.

Déterminer un sentier parallèle à la trajectoire principale nécessite quelques calculs géométriques, majoritairement situés dans la détermination des virages intérieurs de la courbe. Un module informatique tel que par exemple Shapely propose une fonction de commodité permettant de réaliser automatiquement ces calculs.

Les sentiers tels que définis ne tiennent pas compte de l'environnement.

Pour respecter les propriétés de visibilité et d'absence de collisions, on peut utiliser un algorithme de moulage par rayons, « Ray casting » en anglais. Cela consisterait en la construction d'un rayon partant de la trajectoire, à la normale de chacun des points de cette trajectoire.

La présente invention propose un nouvel algorithme permettant d'atteindre le même résultat en utilisant uniquement des opérations ensemblistes. Nous allons construire une médiatrice M pour chaque couple ti, t/’+l) de points consécutifs de la trajectoire principale. Les moitiés gauche M _g et droite Md de cette médiatrice jouerons le rôle de rayons. Les zones restreintes ainsi que les sentiers idéaux S _g (gauche) et Sd (droit) déterminés précédemment joueront quant à eux le rôle de limites sur lesquelles les rayons s'arrêteront.

Nous ne présenterons que la génération du sentier réel droit, la détermination du côté gauche étant en tous points similaire. L'idée générale de l'algorithme présenté ici est dans un premier temps de déterminer l'ensemble Id des intersections entre la demi-médiatrice droite et l'union de l'environnement (parois et poteaux) et du sentier idéal droit :

I _d = {m £ M _d Wz £ Z, m Cl (z U S _d ) 0} Il s'agit ensuite de déterminer, le point p inclus dans Id le plus proche de l'origine de la demi-médiatrice Md.

La figure 5 illustre l'algorithme avec deux exemples sur une trajectoire sous-échantillonnée, permettant ainsi de dessiner les rayons construits sans saturer l'image. L'ensemble Id peut ne contenir qu'un seul point, la médiatrice ne traversant pas d'obstacles, auquel cas ce point sera utilisé pour construire le sentier adapté. C'est le cas le plus simple, visible pour la demi-médiatrice droite entre t38 et t39.

Cet ensemble peut également contenir un point et un ensemble de segments issus de l'intersection entre les zones restreintes et la demi- médiatrice. Il faudra alors sélectionner le point le plus proche de l'origine de la demi-médiatrice parmi l'ensemble des points inclus dans ces segments d'intersection. C'est le cas pour la demi-médiatrice droite des points t36 et t37.

La figure 6 illustre un résultat lorsque l'algorithme est appliqué sur une trajectoire principale correctement échantillonnée.

Les sentiers adaptés gauche 71 et droit 72 sur la figure 7 constituent donc l'ensemble de positions candidates pour le phare. Il s'agit ensuite de déterminer l'orientation du phare en chaque position candidate en construisant un champ de vision local. La présente invention prévoit une détermination analytique de l'orientation du phare. Pour ce faire, cette détermination est réalisée lors d'une phase d'évaluation au cours de laquelle chaque position candidate est évaluée.

Afin d'évaluer la pertinence d'un point , il faut déterminer une méthode de calcul de l'orientation a du phare, permettant de transformer ce point en une solution p, cf). Nous allons construire une fonction qui parcourt l'ensemble des points de la section de trajectoire.

Lorsque l'on considère un seul point de l'un des sentiers adaptés, l'ensemble des points de la trajectoire est compris dans un secteur circulaire virtuel, défini par deux rayons et une portée. Nous allons modéliser ces rayons par deux vecteurs Umin et Umax. L i dée globale est d'agrandir le secteur circulaire virtuel pour qu'il inclue chacun des points de Tk, et ce tant que le secteur virtuel n'a pas atteint les dimensions maximales de la zone de diffusion du phare.

La figure 8 présente différentes étapes de l'agrandissement du secteur circulaire virtuel. Les vecteurs Umin et Umax sont mis à jour au besoin, à chaque ajout de point tk, si le point est à l'extérieur du secteur circulaire. Si mise à jour il y a, on vérifie que l'angle d'ouverture 6 du secteur virtuel est toujours inférieur à l'angle maximal permis par le phare. La distance entre le point à ajouter et la position candidate du phare est également calculée. Si les deux conditions 6 < Qmax et ll - tdl < portée sont respectées, il est possible de couvrir tk depuis p.

Bien que les vérifications précédentes garantissent la présence du point tk dans le secteur de diffusion du phare positionné en p, les occlusions potentielles dues à l'environnement ne garantissent pas la visibilité de l'ensemble des points de la trajectoire à suivre depuis la position candidate. En effet, un obstacle pourrait occulter la ligne de vue, rendant la solution inefficace en pratique. Le modèle de l'environnement comprend un ensemble O de polygones représentant les obstacles (parois, poteaux, ...).

Nous allons construire un test de visibilité. Afin d'accepter un nouveau point tk dans la section couverte, il faut non seulement que ce point soit visible depuis p, mais également que le segment allant de tk-i à tk soit intégralement visible pour que l'on puisse se rendre de l'un à l'autre sans perdre le lien visuel avec le phare. Pour garantir cette visibilité, il faut qu'aucun obstacle ne se trouve dans le triangle A défini par les points tk-i, tk et p. Nous pouvons pour cela utiliser l'opérateur d'intersection et ainsi vérifier la propriété de visibilité : vo e o,o n A= 0

L'évaluation à proprement parler consiste à calculer un score pour chaque champ de vision local déterminé. Le score est proportionnel au segment pris dans le champ de vision local. Nous pouvons calculer directement cette distance en sommant au fur et à mesure les distances lltk-i - t/dl, ou simplement en comptant le nombre de points couverts, ce qui est moins coûteux et aussi discriminant pour le choix de la solution optimale.

Pour la première solution, soit / l'indice du premier point ti non couvert depuis la position p, le score est donné par la somme suivante : La phase d'évaluation permet donc pour chaque position candidate de construire un champ de vision local et de lui associer un score.

On va maintenant décrire la construction d'une solution globale.

La construction d'une solution globale optimale consiste à résoudre le problème local de maximisation de trajectoire couverte en commençant par le début de la trajectoire. On retient la position candidate dont le champ de vision local intègre le premier point de la trajectoire principale et présente le score le plus élevé (parmi tous les champs de vision intégrant le premier point de la trajectoire principale). Il faut ensuite réduire la trajectoire à traiter en soustrayant la partie couverte précédemment. On boucle ainsi tant qu'il reste des points dans la trajectoire à traiter.

La figure 9 permet de visualiser les différentes étapes nécessaires au suivi de la trajectoire principale de bout en bout. Les points évalués localement ainsi que leurs scores associés sont dessinés sur chaque étape. La solution optimale est choisie parmi ces points permettant par la même occasion de déterminer la section couverte. Cette solution est représentée par le secteur circulaire de diffusion sur la figure 9. Ce processus est ensuite répété jusqu'au bout de la trajectoire.

Sur la figure 9, à l'étape 0, on distingue le champ de vision local 91 dont la source est située contre une paroi de l'environnement sur un sentier adapté. La source du champ de vision coïncide avec une position candidate 92 ayant eu le score le plus élevé parmi un ensemble de positions candidates dans la portée du point de départ 93. La position candidate 92 qui a été sélectionnée se trouve sur le sentier gauche. L'angle d'ouverture de ce champ de vision local est inférieur ou égal au champ de vision maximum du phare. Le segment ou la section couverte par le champ de vision est la plus grande possible.

A l'étape 1, on considère le reste de la trajectoire principale. Le point de départ est désormais le premier point du reste de la trajectoire non couverte par le premier segment. De la même manière, on considère la position ayant obtenu le meilleur score. Le champ de vision local de cette position permet de déterminer le segment couvert. L'algorithme est appliqué successivement sur le reste de la trajectoire jusqu'à atteindre le point d'arrivée, 94 à l'étape 4 sur la figure 9. La solution globale ainsi obtenue est résumée sur la figure 10, où les étapes successives sont superposées sur la carte, formant une solution optimale. La pertinence de cette solution s'évalue par le nombre d'étapes nécessaires à la réalisation de la mission.

La présente invention propose ainsi des solutions pour lesquelles les positions candidates sont sur les sentiers adaptés. Cela est optimal pour une trajectoire purement rectiligne. Cependant, dans de nombreux cas pratiques, la trajectoire à suivre est loin d'être rectiligne. Pour ce faire, la présente invention prévoit d'étendre l'espace de solutions à toute la surface entre les sentiers gauche et droit de façon à mieux couvrir les sections à forte courbure. Augmenter ainsi l'espace de solutions a évidemment un coût en calculs, mais peut permettre d'obtenir de meilleures solutions par rapport à des positions sur les sentiers.

Afin de déterminer la surface de solutions Pk, on détermine d'abord une surface Sk comme étant la surface de la zone de détection optimisée. Par ailleurs, le phare ne devant pas gêner le mobile dans le suivi de sa trajectoire principale, nous écartons les points trop proches de cette dernière. Notons Rk cette zone réservée, qui est définie par la contrainte de respect de la distance de sécurité ds de la manière suivante :

R _k = {q £ R ² V Vt £ T _k , || t — || < ds}

La figure 11 présente les surfaces et zones réservées 110 et 111 de deux sections distinctes de la trajectoire principale. Ainsi l'ensemble Pk des solutions pour une section k sera défini par la différence entre ces deux surfaces :

Pk = Sk - Rk

La surface Pk est un espace de solutions plus large que les précédents sentiers et offre probablement de meilleures solutions locales.

On prévoit également d'évaluer les solutions de Pk en calculant des scores. Or, la fonction d proposée ci-dessus ne permet de fournir un score que pour un point donné. Il nous faut donc échantillonner la surface Pk, nous allons pour cela utiliser une grille uniformément espacée, générant ainsi un sous- ensemble de points E _k c P _k . Ayant maintenant affaire à des points, il est possible d'évaluer leur pertinence respective. La figure 12 présente la grille de points évalués, ainsi que leur score. Une fois de plus, la discrétisation, ici la distance entre chaque échantillon testé, est volontairement choisie pour simplifier la compréhension et la visualisation des résultats. Il est toutefois possible de faire varier cette distance afin de tester plus de candidats, et ainsi ajuster le rapport coût/performance de l'algorithme d'optimisation locale.

La solution locale trouvée est meilleure, car le point choisi couvre une portion plus longue de la trajectoire principale. En contrepartie, le coût total de l'optimisation augmente linéairement avec le nombre de points testés.

Afin de diminuer le coût, une stratégie d'évaluation multi-échelle permettant de réduire drastiquement le nombre de points à évaluer a été mise en place. En effet, il est possible d'obtenir une résolution fine, sans tester l'ensemble de la grille à haute résolution. L'astuce consiste à faire un premier échantillonnage à faible résolution, procéder à l'évaluation des points, sélectionner le meilleur, puis répéter le processus avec une résolution plus fine, mais dans une zone limitée autour du meilleur point précédemment sélectionné.

Ainsi, pour obtenir une résolution de 1cm = 0.01m, dans une portée de 5m avec une seule échelle, il faudrait :

Card E) < (^) ² ~ 10 ⁵

En Appliquant cette fois-ci une recherche avec une succession d'échelles (par exemple d = 1, 0.1, 0.01) le nombre d'échantillons à tester est déterminable de la manière suivante : 10 ²

Cette approche permet donc de limiter très fortement le nombre de calculs nécessaires pour obtenir une résolution fine. Toutefois, ne testant pas l'ensemble des points de la grille à résolution fine, il est possible de tomber dans un extremum local, dont la valeur peut être très éloignée de l'optimum global qui aurait été trouvé avec l'approche mono-résolution. Il est alors possible de sélectionner plus d'un point à chaque étape, limitant ainsi ce risque. Bien que ce garde-fou ait un coût en calculs, il reste très limité par rapport au coût de l'approche mono-résolution :

La figure 13 présente l'approche multi-échelle et les résultats obtenus à chaque résolution, ainsi que le résultat obtenu avec l'approche mono-résolution avec d = 0.1. Une rapide analyse quantitative et qualitative permet de valider l'approche, qui permet d'obtenir des résultats aussi précis. Il est même possible, au vu de la réduction du coût en calcul, de calculer à une résolution supérieure, ce qui prendrait trop de temps en pratique pour l'approche monoéchelle.

La succession d'optimisations locales obtenues avec l'approche par surface est présentée sur la figure 14. Bien que la discrétisation choisie soit volontairement grossière afin de faciliter la visualisation, on peut constater une amélioration des positions choisies, particulièrement autour des virages important de la courbe principale.

Bien entendu, l'invention n'est pas limitée aux exemples qui viennent d'être décrits. De nombreuses modifications peuvent être apportées à ces exemples sans sortir du cadre de la présente invention telle que décrite