Brevet FR3044127A1 — publié le 20170526

Domaine de l'invention La présente invention a pour objet un procédé et un dis- positif pour déterminer la probabilité de présence (probabilité de séjour) d'un objet sur un réseau de trajets. L'invention a également pour objet un programme d'ordinateur pour la mise en oeuvre de ce procédé. Les objets peuvent par exemple se localiser à l'aide d'une carte numérique. Exposé et avantages de l'invention Dans ce contexte, l'invention a pour objet un procédé pour déterminer une probabilité de présence d'un objet dans un réseau de trajets comportant au moins un point de bifurcation d'où partent au moins un premier trajet partiel et un second trajet partiel, le procédé consistant à déterminer au moins une première probabilité représen- tant la probabilité de présence de l'objet sur le premier trajet partiel et au moins une seconde probabilité représentant la probabilité de présence de l'objet sur le second trajet partiel et, mettre à l'échelle au moins la première et la seconde probabilité pour que la somme de la première probabilité mise à l'échelle et de la seconde probabilité mise à l'échelle soit supérieure à la probabilité de l'objet sur un trajet partiel en amont du point de bifurcation, pour déterminer la probabilité de présence de l'objet dans le réseau de trajet. Le procédé selon l'invention permet de déterminer la pro- babilité de présence, encore appelé probabilité de séjour d'un objet sur un réseau de trajets ou de chemins. L'invention à également pour objet un appareil de commande appliquant le procédé et un programme d'ordinateur pour la mise en oeuvre du procédé. La probabilité de présence est la probabilité qu'un objet séjourne à un endroit déterminé dans un réseau de trajets. Un réseau de trajets est un réseau de chemins utilisés par l'objet. Un point de bi- furcation est un point du réseau de trajets où le trajet se divise en deux. Un objet selon l'invention est par exemple un véhicule, un téléphone mobile, une caisse, une valise, un paquet de données ou tout autre objet de ce type. 3044127 2 La probabilité selon l'invention est, par exemple, la probabilité de séjour représentée par un coefficient. Selon l'invention telle que décrite, l'utilisation d'un algo- rithme multivers permet de localiser des objets dans un réseau de tra- c jets, par exemple sur une carte numérique. L'avantage d'un tel procédé de localisation est que les probabilités de présence calculées à l'aide de l'algorithme multivers pour les objets, permet de fournir des valeurs très précises conformes à la réalité. Cela garantit la fiabilité de la localisation au cas où seulement quelques données de capteur ou de mau- 10 vaises données de capteur sont disponibles pour plausibiliser ou corriger la probabilité de présence. Selon un développement avantageux, l'étape de mise à l'échelle de la plus grande parmi la première et la deuxième probabilité contiennent une probabilité mise à l'échelle qui correspond à la proba- 15 bilité qu'un objet se trouve sur une partie de trajet en amont de la bi- furcation. Cela permet de mieux déterminer la probabilité de présence de l'objet dans le réseau de trajet. Selon un autre développement de l'invention, l'étape de mise à l'échelle consiste à mettre à l'échelle, la première et la seconde 20 probabilité si la somme de la première et de la seconde probabilités re- présente une probabilité supérieure à 100% et/ou pour que la somme de première et la seconde probabilités représente une probabilité égale à 100%. Cela permet également de mieux déterminer la probabilité de présence de l'objet sur un réseau de trajets. 25 L'invention a également pour objet un procédé pour dé- terminer la probabilité de présence d'un objet sur un réseau de trajets avec au moins un premier point de bifurcation d'où partent un premier trajet partiel et un second trajet partiel et d'au moins un second point de bifurcation qui se trouve sur le premier trajet partiel d'où partent au 30 moins un troisième et un quatrième trajets partiels. Le procédé consiste à : déterminer au moins une première probabilité représentant la probabilité de présence de l'objet sur le troisième trajet partiel si l'objet se trouve sur le premier trajet partiel, au moins une second probabilité représentant la probabilité de présence de l'objet sur 3044127 3 le quatrième trajet partiel si l'objet se trouve sur le premier trajet partiel et au moins une troisième probabilité représentant la probabilité de présence de l'objet sur le second trajet partiel ou sur un autre trajet partiel partant d'un autre point de bifurcation que 5 l'on atteint par le second trajet partiel, additionner au moins la première, la seconde et la troisième probabilités pour obtenir une valeur auxiliaire, et mettre à l'échelle au moins la première, la seconde et la troisième probabilités en utilisant la valeur auxiliaire pour déterminer la 10 probabilité de présence de l'objet dans le réseau de trajets. La valeur auxiliaire selon l'invention est une valeur qui a une probabilité supérieure à 100%. A titre d'exemple, les trois probabilités peuvent être mises à l'échelle dans l'étape de mise à l'échelle par rapport à une probabilité 15 de référence de 100% (ou de 1) de sorte que la somme des trois probabi- lités de mise à l'échelle correspond à une probabilité de 100% (ou de 1). Selon un développement, la valeur auxiliaire représente une probabilité supérieure à 100%. Dans l'étape de mise à l'échelle des troisième, quatrième et seconde probabilités, on opère de façon qu'après 20 la mise à l'échelle, la somme de la troisième, de la quatrième et de la seconde probabilités représente une probabilité de 100%. Cela permet une détermination aussi proche que possible de la réalité pour les probabilités de présence associées aux différents trajets partiels. Il est en outre avantageux que dans l'étape de détermina- 25 tion en utilisant la quatrième probabilité et la seconde probabilité, on détermine une probabilité de présence de l'objet sur un cinquième trajet partiel accessible à partir du premier et du second trajets partiels, si l'objet se trouve sur le premier trajet partiel ou le quatrième trajet partiel ou le second trajet partiel ou l'autre trajet partiel. Ainsi, par 30 exemple, le cinquième trajet partiel pourra être accessible par un pre- mier trajet d'accès comprenant le premier trajet partiel et le quatrième trajet partiel ou par un second trajet d'accès comprenant le second trajet partiel et l'autre trajet partiel. En outre, le quatrième trajet partiel ou l'autre trajet partiel peuvent aboutir au cinquième trajet partiel. Cette 35 forme de réalisation permet de localiser l'objet ou le véhicule sur des 3044127 4 trajets qui résultent de la jonction de deux ou plusieurs trajets partiels. Cela permet d'augmenter d'autant la précision de la localisation de l'objet du véhicule sur le réseau de trajets. Selon un autre développement, dans l'étape de détermi- 5 nation, la probabilité de présence de l'objet ou du véhicule sur le cin- quième trajet partiel correspond à la quatrième probabilité si la seconde probabilité représente une moindre probabilité de présence que la quatrième probabilité. En variante, la probabilité de présence correspond à la seconde probabilité si la quatrième probabilité représente une proba- 10 bilité de présence inférieure à la seconde probabilité. Cela permet de déterminer la probabilité de présence associée au cinquième trajet, de manière très simple en effaçant la probabilité représentée par la moindre probabilité de présence respective. Cela permet de réduire les capacités de calcul pour déterminer la probabilité de présence. 15 Le procédé peut également comporter une étape de cor- rection consistant à corriger la troisième, la quatrième ou la seconde probabilité en utilisant les données de capteur fournies par au moins un capteur de l'objet ou du véhicule. Le capteur est par exemple un capteur d'environnement de l'objet ou du véhicule. En plus ou en va- 20 riante, la probabilité concernée peut se corriger par l'étape de correction en utilisant les données de navigation. Suivant une autre caractéristique avantageuse, dans l'étape de détermination on détermine au moins une probabilité supplémentaire qui représente une probabilité de présence de l'objet ou du 25 véhicule sur au moins un trajet partiel supplémentaire partant de l'autre point de bifurcation, si l'objet ou le véhicule se trouve sur le second trajet partiel. De façon correspondante, dans l'étape d'addition, on peut additionner au moins la troisième, la quatrième et la seconde probabilités ainsi que la probabilité supplémentaire pour obtenir la valeur 30 auxiliaire et dans l'étape de mise à l'échelle, on met à l'échelle au moins la troisième, la quatrième, la seconde et la probabilité supplémentaire en utilisant la valeur auxiliaire. Cela permet de déterminer d'une manière très fiable et précise la probabilité de présence de l'objet ou du véhicule dans un ensemble de trajets partiels du réseau de trajets, 35 différents indépendamment, notamment les uns des autres. 3044127 5 Ce procédé peut s'implémenter par exemple sous la forme de programmes ou de circuits ou d'une forme mélangée composée de programmes et de circuits, par exemple dans un appareil de commande. L'invention a en outre pour objet un appareil de com- 5 mande pour exécuter les étapes du procédé dans une installation ap- propriée. Cette variante de réalisation de l'invention, sous la forme d'un appareil de commande, permet de résoudre de manière très rapide et efficace le problème auquel doit répondre l'invention. Un appareil de commande selon l'invention est un appa- 10 reil électrique qui traite des signaux de capteur et en fonction de ceux- ci, génère des signaux de commande et/ou des signaux de données. L'appareil de commande comporte une interface sous la forme d'un circuit et/ou d'un programme. Dans le cas d'une réalisation en forme de circuit, l'interface fait par exemple partie d'un système ASIC qui com- 15 porte différentes fonctions de l'appareil de commande. Mais il est éga- lement possible que les interfaces comportent leur propre circuit intégré ou soient au moins partiellement formées de composants discrets. Dans le cas d'une réalisation sous forme de programme, les interfaces peuvent être des modules de programme qui existent, par exemple, sur le 20 microprocesseur, à côté d'autres modules de programme. Suivant une autre caractéristique avantageuse, l'invention a pour objet un produit programme d'ordinateur ou un programme d'ordinateur avec un code programme enregistré sur un support ou élément de mémoire lisible par une machine telle qu'une 25 mémoire de semi-conducteurs, un disque dur ou une mémoire optique pour la mise en oeuvre, l'application et la commande selon les étapes du procédé, en particulier lorsque le produit-programme ou le programme sont exécutés sur un ordinateur ou par un dispositif. Dessins 30 La présente invention sera décrite ci-après, de manière plus détaillée à l'aide d'exemples de réalisation représentés dans les dessins annexés dans lesquels : la figure 1 est une représentation schématique d'un véhicule équi- pé d'un appareil de commande selon un exemple de réalisation, 3044127 6 - la figure 2 est une représentation schématique d'un segment d'un réseau de trajets appliqué à un appareil de commande selon un exemple de réalisation, - la figure 3 est une schéma d'un segment d'un réseau de trajets uti- 5 lisé avec un appareil de commande selon un exemple de réalisa- tion, - la figure 4A est une représentation schématique d'un segment d'un réseau de trajets utilisé avec un appareil de commande selon un exemple de réalisation, 10 - la figure 4B est une représentation schématique d'un segment d'un réseau de trajets utilisé dans un exemple de réalisation, - la figure 4C est une représentation schématique d'un segment d'un réseau de trajets utilisé dans un exemple de réalisation, - la figure 4D est une représentation schématique d'un segment d'un 15 réseau de trajets utilisé dans un exemple de réalisation, - la figure 4E une représentation schématique d'un segment d'un réseau de trajets utilisé dans un exemple de réalisation, - la figure 5 est un schéma d'un segment d'un réseau de trajets appliqué à un appareil de commande selon l'invention, 20 - la figure 6 montre un ordinogramme du procédé selon un exemple de réalisation de l'invention, et - la figure 7 est un schéma par blocs d'un exemple de réalisation de, l'invention sous la forme d'un appareil de commande. Description de modes de réalisation 25 La figure 1 est une représentation schématique d'un vé- hicule 100 équipé d'un appareil de commande 102 selon un exemple de réalisation. Le véhicule 100 circule sur une route 104 qui fait partie d'un réseau de trajets 106 et se divise en plusieurs trajets partiels aux points de bifurcation. L'appareil de commande 102 détermine la proba- 30 bilité selon laquelle le véhicule 100 séjourne à un endroit déterminé du réseau de trajets 106 en utilisant un algorithme multivers décrit ensuite de manière plus détaillée selon lequel on détermine la probabilité de présence du véhicule sur deux trajets partiels partant d'un même point de bifurcation en utilisant la probabilité de présence selon laquelle le 35 véhicule 100 se trouve sur l'un des deux trajets partiels indépendam- 3044127 7 ment. En option, l'appareil de commande 102 est couplé à un capteur d'environnement 108 du véhicule 100 pour saisir la position du véhi- 5 cule sur la route 104 et l'envoyer à l'appareil de commande 102 qui uti- lise les données des capteurs d'environnement 108 pour contrôler la plausibilité ou corriger les résultats de l'algorithme multivers. On peut localiser les objets, par exemple à l'aide d'un « filtre à particules » dans une carte numérique. A cet, un ensemble de 10 points, encore appelés particules, est donné dans la carte numérique. Chaque particule représente, avec une certaine probabilité, l'emplacement de séjour vrai de l'objet. Les particules se trouvent sur la carte dans certaines zones prédéfinies telles que par exemple sur des routes. 15 Dans une étape de mouvement d'un procédé de localisa- tion correspondant, on mesure le mouvement respectif de l'objet, par exemple à l'aide d'un algorithme de navigation à l'estime. La mesure des mouvements se fait, par exemple, en utilisant le système de navigation par satellites (en abrégé GNSS), l'odométrie, les compteurs de pas, les 20 gyroscopes, les capteurs d'accélération ou des WLAN-Fingerprints. Le résultat de la mesure donne un vecteur de déplacement correspondant au mouvement de l'objet. Comme les capteurs fonctionnent avec des erreurs, le vecteur de déplacement correspond à une distribution de probabilités. Généralement, on utilise une distribu- 25 tion normale. Le vecteur de déplacement est alors ajouté à chaque particule. Comme, de façon précise, il ne s'agit pas d'un vecteur, mais d'une distribution, on clone les particules et on additionne le vecteur de déplacement à chaque élément d'échantillon différent résultant de la 30 distribution. A partir des particules, on obtient ainsi un ensemble de particules filles. La probabilité de la particule-père est répartie aux particules enfant en fonction des probabilités. Ensuite, on efface la particule père. Les particules se déplacent dans une carte numérique. 35 On peut rejeter de nombreuses nouvelles particules générées si, au 3044127 8 cours de leurs mouvements, elles ont traversé des zones interdites de la carte numérique. C'est ainsi que les particules peuvent avoir traversé des murs ou, dans le cas d'un véhicule, être tombées de la chaussée. Toutes ces particules pourront être effacées au cours d'une étape de 5 nettoyage du procédé de localisation car de tels mouvements sont inter- dits. On peut prédéfinir également d'autres conditions aux limites pour vérifier la plausibilité des particules. C'est ainsi que, par exemple, l'algorithme de navigation à l'estime évoqué, fournit en plus du vecteur de déplacement, également une zone globale dans laquelle les objets 10 peuvent se trouver, c'est-à-dire dans une ellipse de séjour calculée par le système de navigation par satellite, et à l'extérieur de cette zone on effacera toutes les particules. Ce nettoyage se fait sensiblement par multiplication avec une probabilité dite d'émission. Ainsi, très rapidement, seules quelques 15 particules subsisteront qui permettent de déterminer approximative- ment la position réelle de l'objet sur la carte numérique. En multipliant avec la probabilité d'émission et en effa- çant les particules improbables, la somme des probabilités concernant toutes les particules ne dépassera plus le nombre 1. Au cours d'un 20 étape renormalisation, on met à l'échelle la probabilité de toutes les par- ticules qui subsistent pour obtenir de nouveau la somme 1. Il peut arriver qu'un tel filtre à particules possède une zone d'erreur, globale, relativement grande dans laquelle peuvent séjourner les particules, notamment du fait des zones d'ombre du système 25 de navigation par satellite ou de l'interruption d'une liaison WLAN. De plus, le vecteur de déplacement peut être très faible, c'est-à-dire qu'il indique uniquement la distance de décalage, mais pas de direction comme, par exemple, un compteur de pas. En outre, le réseau numérique dans lequel l'objet peut se placer se compose souvent uniquement 30 que de traits. La figure 2 montre une représentation schématique d'un segment de réseau de trajets 106 utilisable avec un appareil de commande selon un exemple de réalisation. Le réseau de trajets 106 est, par exemple le réseau de trajets décrit à l'aide de la figure 1. La figure 35 montre le trajet 104 qui arrive à un premier point de bifurcation 200 et 3044127 9 se divise en un premier trajet partiel 202, un second trajet partiel 204 et un troisième trajet partiel 206. La direction de circulation du véhicule dans le réseau de trajets 106 est indiqué par une flèche. La figure 3 est une représentation schématique d'un 5 segment d'un réseau de trajets 106 utilisé avec un appareil de com- mande correspondant à un exemple de réalisation. A la différence de la figure 2, sur le premier trajet partiel 202 on a une seconde bifurcation 300 d'où partent un troisième trajet partiel 206 et un quatrième trajet partiel 302. 10 La figure 4A montre schématiquement un segment d'un réseau de trajets 106 utilisables avec un appareil de commande selon un exemple de réalisation de l'invention. A la différence de la figure 3, le réseau de trajets 106 comporte sur le second trajet partiel 204, un autre point de bifurcation 400 d'où sont issus, selon cet exemple de réa- 15 lisation, un autre trajet partiel 402 et un autre trajet partiel 404. Les quatre trajets partiels 302 et les autres trajets partiels 402 rejoignent un cinquième trajet partiel 406 commun qui se trouve, par exemple entre le troisième trajet partiel 206 et le trajet partiel supplémentaire 404. 20 La figure 5 montre schématiquement un segment d'un réseau de trajets 106 utilisable avec l'appareil de commande selon l'exemple de réalisation. A la différence du réseau de trajets décrit à l'aide des figures 2-4A-4E, le réseau de trajets 106 de la figure 5 est sous la forme d'un peigne. Au premier point de bifurcation 200, la route 25 104 se divise en un premier trajet partiel 202 et en un second trajet partiel 204. Au niveau du second point de bifurcation 300 qui se trouve sur le premier trajet partiel 202, la chaussée 104 se divise en un troisième trajet partiel 206 et en un quatrième trajet partiel 302. Comme le montre la figure 5, la chaussée 104 se divise en un troisième point de 30 bifurcation 500 sur le troisième trajet partiel 206, en outre, en un sixième trajet partiel 502 et un septième trajet partiel 504. Au quatrième point de bifurcation 505 sur le sixième trajet partiel 502, la chaussée 104 se divise de nouveau en un huitième trajet partiel 506 et un neuvième trajet partiel 508. Le huitième trajet partiel 506 a un cin- 35 quième point de bifurcation 510. A partir du cinquième point de bifur- 3044127 10 cation 510, partent un dixième trajet partiel 512 et un onzième trajet partiel 514. Les trajets partiels 204, 302, 504, 508, 514 sont, par exemple, des sorties partant d'une chaussée principale de la voie de circulation 104 sous la forme de trajets partiels 202, 206, 502, 506, 512. 5 Les figures 2 et 3 représentent des exemples de croise- ments de trois voies, c'est-à-dire chaque fois d'un croisement avec trois sorties ayant les mêmes droits. La figure 2 montre qu'en passant par le croisement, chaque route, sous la forme de trajet partiel 202, 204, 206 est emprunté avec une probabilité de 33%, c'est-à-dire que la probabili- 10 té se répartit régulièrement entre toutes les sorties. La figure 3 montre un croisement analogue à celui de la figure 2 avec toutefois la différence que le croisement est quelque peu déformé et se compose de deux séquences de croisements. En utilisant le filtre à particules évoqué ci-dessus, pour déterminer la distribution 15 de probabilité, on distingue plus nettement la distribution des probabi- lités de la figure 3 selon la distribution de probabilité de la figure 2. A ce premier croisement sous la forme d'une première fourche 200, la moitié des particules ira à droite, l'autre moitié des particules ira à gauche. Les particules à droites, selon le sens de circulation, rencontrent alors le 20 croisement suivant sous la forme de la seconde bifurcation 300 et il se divise de nouveau des mêmes parties. Ainsi, il en résulte à la figure 2, une distribution de probabilités 1/3, 1/3, 1/3, une distribution de probabilités de 1/4, 1/4, 1/2 et cela selon de la faiblesse de la distance entre les deux croisements. 25 Dans le cas de l'exemple de réalisation de la figure 4A du réseau de trajets 106, on a une bande ou couloir de circulation 104 qui se divise en deux bandes de circulation 202, 204 qui se diviseront ensuite et se rejoignent dans une bande médiane 406. Le véhicule peut ainsi décider deux fois de la direction qu'il va utiliser. En résultat, les 30 trois bandes de circulation 206, 404, 406 ont la même probabilité. On a ainsi, en d'autres termes, une distribution de probabilités de 1/3, 1/3, 1/3. Du point de vue du filtre à particules, la moitié des particules passe sur le point de bifurcation à gauche, 200 fois vers la gauche, l'autre moitié des particules se divisant de nouveau pour être regrou- 3044127 11 pées sur la bande moyenne 406. On obtient ainsi, selon le filtre à particules, une distribution de 1/4, 1/2, 1/4. La figure 5 montre, à titre d'exemple, une forme de peigne. Des éléments bifurquant à gauche, partant à intervalles régu- 5 liers d'une ligne droite et chaque fois, on a une probabilité de bifurca- tion de 50%. Pour le véhicule, toutes les routes ou dérivations ont finalement la même probabilité. Du point de vue du filtre à particules, en revanche, le véhicule ne circule finalement en ligne droite qu'avec une probabilité de 1/32 car à chaque point de bifurcation, la moitié des 10 particules passe dans une dérivation. On pourrait compenser ces erreurs de détermination de la distribution des probabilités à l'aide d'un algorithme de navigation à l'estime qui assurerait une surcompensation. A l'aide de l'algorithme multivers décrit ci-après qui correspond à l'invention on peut, en re- 15 vanche, répondre aux exigences de précision. Le principe du filtre à particules repose sur le fait que parallèlement on suit un nombre élevé de positionnements possibles. Ainsi, on ne détecte pas précisément un objet, mais un ensemble d'objets ou de particules que l'on localise, par exemple, un ensemble de véhi- 20 cules qui arrivent de façon autonome et indépendante les unes des autres sur les croisements ; chaque conducteur décide lui-même, indépendamment des autres, uniquement selon le principe aléatoire dans quelle route il va bifurquer. De ce point de vue, les distributions telles que calculées avec le filtre à particules semblent correctes. 25 On veut maintenant déterminer toutefois, la position la plus probable d'un unique objet. Pour cela, on saura qu'un unique objet ne peut se décider en même temps pour aller à gauche et à droite. L'idée de base consiste alors à ce qu'à chaque croisement, l'objet ne peut se décider que pour un trajet. Contrairement, au point de vue du 30 filtre à particules, un unique objet ne peut pas se diviser à un croise- ment. En réalité, il ne peut décider que pour la gauche ou pour la droite. Ces deux réalités ne peuvent coexister simultanément. Il s'agit en quelque sorte d'une alternative universelle. Dans un univers, l'objet bifurque à droite et dans un autre univers, il bifurque à gauche. Il est 35 important qu'à la différence du filtre à particules, au moment de la divi- 3044127 12 sion, l'objet ne se divise pas, mais il y a formation de nouveaux univers alternatifs. Ces univers alternatifs ne sont pas à considérer comme des enfants d'un univers initial régnant avant la bifurcation. Bien plus, 5 il s'agit, par rapport à l'univers d'origine, de nouveaux univers paral- lèles, complètement équivalents en droit. Dès que ces univers sont créés, il n'y a plus d'alternance entre les univers. Les nouveaux univers résultent du clonage de l'univers d'origine. Ensuite, l'objet, dans un univers, bifurque vers la droite et 10 dans l'autre univers vers la gauche, ces univers étant générés en plus, c'est-à-dire qu'un père n'est pas divisé en plusieurs filles. Bien plus, on aura de nouveaux univers parents et chacun de ces univers parents aura une probabilité qui se déduit de la probabilité de transition après le croisement et de la probabilité avant le croisement. 15 Par le clonage, on aura la somme des probabilités jusqu'à la remise en norme pour tous les univers présents et non seulement pour les univers parents supérieurs à un. Pour déterminer la position la plus probable de l'objet, on utilise non seulement les probabilités des particules, mais également les 20 probabilités des univers. S'il y a différents univers dans lesquels se trouve l'objet à un seul et même endroit, la probabilité de présence est le maximum de tous les univers où l'objet se trouve à cet endroit. A la place d'univers parallèles, on peut également se re- présenter des chemins alternatifs partant de l'origine de l'objet vers la 25 position actuelle. Si un tel chemin rencontre une bifurcation, on le dé- crira de manière imagée en ce qu'un chemin supplémentaire va du point d'origine vers la bifurcation. Puis, un chemin bifurque dans une bifurcation et l'autre chemin utilise l'alternative. L'algorithme multivers peut être analogue au filtre de 30 particules. La différence est que dans le cas d'un filtre à particules, une particule se divise en particules filles ou particules enfants alors que dans un algorithme multivers, à la place d'enfants, on génère des parents. L'algorithme multivers peut, comme le filtre à particules, comporter des étapes de vérification de la plausibilité et une remise aux normes 35 des probabilités. 3044127 13 Pour l'algorithme multivers, il y a, par exemple les exi- gences suivantes concernant un procédé pour générer des univers parents. Lors du clonage et de la redistribution des probabilités 5 entre les parents, aucun parent ne doit avoir plus de probabilités que l'univers avant le clonage. Dans le cas contraire, on aurait une probabilité de transition de « avant le croisement » et « après le croisement » supérieure à 100%. En clonant on peut, jusqu'à la remise en norme, avoir 10 plus de probabilités. Toutefois, en clonant aucune probabilité ne peut disparaître, c'est-à-dire que la somme des probabilités des univers parents doit au moins être égale à la probabilité avant la bifurcation. En outre, le rapport des probabilités entre les univers pa- rents directement après le clonage doit correspondre au rapport qui 15 prédéfinit les probabilités au niveau du croisement, par exemple : « suivre avec une probabilité de 90% la chaussée principale et bifurquer avec seulement une probabilité de 10% dans une impasse ». De façon correspondante, les univers parents doivent avoir un rapport des probabilités de 90/10. 20 Le filtre à particules forme un cas limite dans lequel l'ancienne probabilité est complètement répartie aux parents sans générer de nouvelles probabilités au clonage. Cela correspond à la comparaison imagée selon laquelle la probabilité du père est répartie complètement entre les enfants et le père lui-même disparaît. 25 L'autre cas limite est celui pour lequel on génère le maximum de nouvelles probabilités. Dans ce cas, l'un des parents passerait sans modification de sa probabilité (naturellement jusqu'à la remise en norme) par la bifurcation. Tous les autres parents auraient, selon le rapport de distribution au niveau de la bifurcation, une proba- 30 bilité identique ou diminuée. L'algorithme multivers correspond à un cas limite. Entre les deux cas limites, il existe en théorie un nombre quelconque d'algorithme. Ces deux cas limites peuvent se résumer comme suit : le filtre à particules décrit la distribution d'un ensemble d'objets dans un 35 univers ; l'algorithme multivers décrit la distribution d'un unique objet 3044127 14 dans un ensemble d'univers parallèles. Entre deux cas limites, il existe un continu d'étapes intermédiaires possibles des algorithmes. L'algorithme multivers peut se formuler comme suit : On prend un croisement avec n sorties et des probabilités 5 de sortie pi...p.. La somme des probabilités est égale à 1. Sans limiter la généralité on a pip2...p.. Dans le cas du filtre à particules, la probabilité de la par- ticule père est transmise aux enfants, la probabilité du père étant multipliée par pi, p2...p.. Ensuite, la particule père disparaît. 10 Dans le cas de l'algorithme multivers, la situation est que la particule père considérée ci-dessus continue bien plus sous la forme d'une particule parent et reste inchangée. Elle se déplace à l'endroit du successeur le plus probable pl. En plus, on a de nouveaux parents qui multiplient la probabilité supplémentaire de la probabilité d'origine par 15 le coefficient pk/pi. Cela constitue le procédé de génération des univers parallèles ou des chemins parallèles. On génère ainsi une probabilité supplémentaire en multipliant la probabilité d'origine par (p2+...+p.)/pi. Si les particules arrivent à la même position dans différentes univers, l'univers le plus probable subsiste. L'univers le moins 20 probable sera effacé. Ce procédé peut également être appelé fusion des univers. Dans une étape de remise en norme, pour tous les uni- vers parallèles existant, à la fin d'une mise à jour de filtre on met en norme la somme des probabilités de toutes les particules ou univers sur 25 un. Le fonctionnement de l'algorithme multivers sera décrit ci-après, de manière plus détaillée à l'aide de l'exemple des figures 2-5 décrites ci-dessus. Selon la figure 2, une particule caractérisée par un point 30 se déplace vers le premier point de bifurcation 200 et doit décider entre les trois sorties 202, 204, 206. On aura deux parents supplémentaires ayant chacun une probabilité de 1. Après remise aux normes, on obtient une distribution des probabilités de 1/3, 1/3, 1/3. A la figure 3, après le premier point de bifurcation 200, 35 on a deux univers avec à chaque fois 50% de probabilités après la re- 3044127 15 mise en norme. Dans l'un des univers, la particule va vers le second point de bifurcation 300 de sorte qu'il en résulte de nouveaux univers. Dans l'un de ces univers, la particule bifurque au second point de bifurcation 300 vers la gauche alors que dans l'autre univers, la particule 5 bifurque au second point de bifurcation 300 vers la droite. Comme le passage à la même probabilité, les deux univers parents ont chaque fois une probabilité de 50%. On a ainsi trois univers ayant chaque fois une probabilité de 50%. Après remise en norme, on obtient finalement le résultat indiqué, à savoir 1/3, 1/3, 1/3. 10 A la figure 4A, après le premier point de bifurcation 200, on a deux univers avec une probabilité chacun de 50%. Après le second point de bifurcation 300, chacun des univers se subdivise en deux sous-univers avec chacun une probabilité de 50%. Après la remise en norme, on aura quatre univers ayant une probabilité chacun de 25%. 15 Dans deux des quatre univers, les particules se superposent directe- ment dans la poursuite du mouvement et peuvent ainsi être combinées. Comme les deux univers ont la même probabilité, on efface l'un des univers. Après remise en norme, on obtient trois univers ayant chaque fois une probabilité de 33%. 20 La figure 4B montre schématiquement un segment d'un réseau de trajets avec des probabilités associées aux trajets pour être utilisées dans un exemple de réalisations. Dans un filtre à particules il peut arriver qu'après une étape de mouvement, on aura des particules à la fois sur le segment en 25 amont de la bifurcation et sur le segment en aval de celle-ci. Grâce à la topologie, on obtient des probabilités de transition différentes sur le segment derrière la bifurcation, par exemple l'utilisateur suit la route principale avec une probabilité de 66% et la route auxiliaire avec seulement 33% de probabilité. Il en résulte alors que les particules en 30 avant de la bifurcation sera de 100%, les particules sur la route princi- pale en aval de la bifurcation auront 66% et les particules sur la route secondaire derrière la bifurcation correspondra à 33%. Toutes ces probabilités sont ensuite mises en norme à l'échelle en fonction de la proposition. Dans ce cas, les particules en 35 amont de la fourche ont toujours une plus grande probabilité qu'en 3044127 16 aval. Dans le cas extrême, on applique un algorithme de coïncidence à la position en amont de la bifurcation jusqu'à ce que toutes les particules soient passées par-dessus la bifurcation. Selon la représentation de la figure 4B, avant le point de 5 bifurcation, les particules ont toujours une probabilité plus grande que les particules après la bifurcation. La figure 4C est un schéma d'un segment d'un réseau de trajets avec des probabilités mises à l'échelle ou mises en norme associées aux parties de trajets pour servir dans l'exemple de réalisation de 10 l'invention : certaines particules après le point de bifurcation ont la même probabilité qu'avant la bifurcation. Dans l'exemple de l'invention tel que présenté ici, après la bifurcation, sur le segment avec la plus grande probabilité relative de transition, les particules ont la même probabilité que celles en amont de 15 la bifurcation. Ainsi, la position déterminée par un algorithme de con- cordance dans le réseau correspondra plus à la position réelle. Dans le cas où à une bifurcation simple, toutes les parti- cules sont déplacées au-delà de la bifurcation, il n'y a pas de différence par rapport à l'utilisation usuelle d'un filtre à particules. Ce n'est que si 20 l'étape de déplacement dépasse plus d'une bifurcation ou si les parti- cules se trouvent à la fois devant et derrière le point de bifurcation, que la solution présentée ici est avantageuse. La figure 4D montre schématiquement un segment d'un réseau de trajets avec des probabilités associées aux parties de segment 25 pour servir dans un exemple de réalisation dans lequel on a un second point de bifurcation. On aura trois chemins possibles et la dérivation vers la droite dans cet exemple aura toujours 2/3 de la probabilité et la dérivation vers la gauche aura 1/3. Selon les procédés usuels, on a ici les probabilités de présence absolues, indiquées. 30 La figure 4E est une représentation schématique d'un segment d'un réseau de trajets avec des probabilités mises à l'échelle ou mises en norme associées aux parties de trajets pour servir dans un exemple de réalisation. Selon le procédé présenté ici, on aura, par exemple, les probabilités de présence, absolues, indiquées, présentées à 35 la figure 4E. 3044127 17 A la figure 5 on a associé, à chaque point de bifurcation, un nouvel univers avec la probabilité du parent. Après le premier point de bifurcation 200, on a deux parents ayant une probabilité chacun de 50%. Après le second point de bifurcation 300, l'un des deux univers 5 génère un autre univers avec une probabilité de 50%. Ainsi, après la remise en norme des trois univers, on aura une probabilité à chaque fois de 33%. L'autre univers génère au point de bifurcation suivant un nouvel univers avec une probabilité de 33% etc. En conclusion, tous les trajets auront une probabilité équivalente. 10 La figure 6 montre un ordinogramme d'un procédé 600 selon un exemple de réalisation. Le procédé 600 est, par exemple, appliqué par l'appareil de commande décrit ci-dessus à l'aide des figures 1 à 5. Le procédé 600 permet de déterminer une probabilité de présence d'un objet dans un réseau de trajets avec au moins un point de bifurca- 15 tion dont sont issus au moins un premier trajet partiel et un second trajet partiel. Dans une étape 610 on détermine au moins une première probabilité représentant la probabilité de présence de l'objet 100 sur le premier trajet partiel 202 et on détermine au moins une seconde proba- 20 bilité représentant la probabilité de présence de l'objet 100 sur le deu- xième trajet partiel 204. Enfin, on peut mettre à l'échelle au moins les première et seconde probabilités dans l'étape 630 de mise à l'échelle de façon que la somme de la première et de la seconde probabilités mises à l'échelle soit 25 supérieure à la probabilité de l'objet sur un trajet partiel en amont du point de bifurcation, pour déterminer la probabilité de présence de l'objet dans le réseau de trajets. On peut également envisager un exemple de réalisation de l'invention dans lequel, en outre, dans le réseau de trajets, on a au 30 moins un second point de bifurcation sur la première partie de trajet d'où sont issus au moins un troisième trajet partiel et un quatrième trajet partiel. Dans l'étape 610 consistant à déterminer, on détermine au moins une troisième probabilité représentant la probabilité de présence de l'objet si l'objet se trouve sur le troisième trajet partiel et au moins 35 une quatrième probabilité représentant la probabilité de présence de 3044127 18 l'objet sur le quatrième objet partiel si l'objet se trouve sur ce quatrième objet partiel. Dans l'étape d'addition 620 on additionne au moins la seconde, la troisième et la quatrième probabilités pour obtenir une valeur auxiliaire. Enfin, dans l'étape 630 de la mise à l'échelle, on met à 5 l'échelle au moins la seconde, la troisième, la quatrième probabilités en utilisant la valeur auxiliaire pour déterminer la probabilité de présence de l'objet dans le réseau de trajets. Selon un exemple de réalisation, on peut mettre à l'échelle les trois probabilités pour que la somme des trois probabilités, 10 après la mise à l'échelle, représente une probabilité de 100% (ou une probabilité égale à 1). Selon un autre exemple de réalisation, dans l'étape 620 on détermine la probabilité du cinquième trajet partiel réunissant le premier et le second trajets partiels, c'est-à-dire une bande médiane en 15 ce que l'on efface la probabilité du premier ou du second trajet partiel qui a la plus faible probabilité de présence, de sorte que la probabilité qui reste est attribuée au cinquième trajet partiel. Les étapes 610, 620, 630 peuvent être exécutées en per- manence. 20 La figure 7 montre un schéma par blocs d'un appareil de commande 104 selon un exemple de réalisation de l'invention. L'appareil de commande 104 comporte une installation 710 pour déterminer au moins une première probabilité d'une probabilité de présence de l'objet sur le premier trajet partiel et au moins une seconde 25 probabilité représentant la probabilité de présence de l'objet sur le se- cond trajet partiel. En outre, l'appareil de commande comporte une installation 730 pour mettre à l'échelle au moins la première et la seconde probabilités pour que la somme de la première et de la seconde probabilités mises à l'échelle, soit supérieure à la probabilité de l'objet sur un 30 trajet partiel en amont du point de bifurcation, pour déterminer la pro- babilité de présence de l'objet dans le réseau de trajets. On peut également envisager un exemple de réalisation de l'invention dans lequel l'installation 710 servant à déterminer est conçu pour déterminer au moins une troisième probabilité représentant 35 la probabilité de présence de l'objet si celui-ci se trouve sur le troisième 3044127 19 trajet partiel et au moins une quatrième probabilité représentant la probabilité de présence de l'objet sur le quatrième trajet partiel, si l'objet se trouve sur le quatrième trajet partiel. Dans l'installation d'addition 720 on additionne au moins la seconde, la troisième et la 5 quatrième probabilités pour obtenir une valeur auxiliaire. Enfin, dans l'installation de mise à l'échelle 730 on met à l'échelle au moins la seconde, la troisième et la quatrième probabilités en utilisant la valeur auxiliaire, pour déterminer la probabilité de présence de l'objet dans le réseau de trajets. 10 3044127 20 NOMENCLATURE DES ELEMENTS PRINCIPAUX 100 Véhicule 102 Appareil de commande 5 104 Chaussée / route 106 Réseau de trajets 108 Capteur d'environnement 200 Point de bifurcation 202 Premier trajet partiel 10 204 Second trajet partiel 206 Troisième trajet partiel 300 Point de bifurcation 302 Quatrième trajet partiel 400 Point de bifurcation 15 402 Autre trajet partiel 404 Trajet partiel supplémentaire 406 Cinquième trajet partiel 500 Troisième point de bifurcation 502 Sixième trajet partiel 20 505 Quatrième point de bifurcation 506 Huitième trajet partiel 508 Neuvième trajet partiel 510 Cinquième point de bifurcation 512 Dixième trajet partiel 25 514 Onzième trajet partiel 600 Procédé 610-630 Etapes du procédé. 30 REVENDICATIONS1°) Procédé (600) pour déterminer la probabilité de présence d'un objet (100) dans un réseau de trajets (106) comportant au moins un point de bifurcation (200) d'où partent au moins un premier trajet partiel (202) et un second trajet partiel (204), procédé (600) comprenant les étapes suivantes consistant à : déterminer (610) au moins une première probabilité représentant la probabilité de présence de l'objet (100) sur le premier trajet partiel (202) et au moins une seconde probabilité représentant la pro- babilité de présence de l'objet (100) sur le second trajet partiel (204), et mettre à l'échelle (630) au moins la première et la seconde probabilité pour que la somme de la première et de la seconde probabilité mises à l'échelle soit supérieure à la probabilité de l'objet (100) sur un trajet partiel en amont du point de bifurcation (200), pour dé- terminer la probabilité de présence de l'objet (100) dans le réseau de trajet (106). 2°) Procédé (600) selon la revendication 1, caractérisé en ce que dans l'étape (630) de mise à l'échelle, la plus grande des première et seconde probabilités a une valeur mise à l'échelle qui correspond à la probabilité que l'objet (100) se trouve sur un trajet partiel en amont du point de bifurcation (200). 3°) Procédé (600) selon l'une des revendications 1 et 2, caractérisé en ce que la somme de la première et de la seconde probabilités représente une probabilité supérieure à 100 pourcent et/ou la première et la seconde probabilités représentent une probabilité égale à 100%. 4°) Procédé (600) selon l'une des revendications 1 à 3, caractérisé en ce que dans un réseau de trajets (106) on a au moins un second point de bi- furcation (300) se trouvant sur le premier trajet partiel (202) d'où par- 3044127 22 tent au moins un troisième trajet partiel (206) et un quatrième trajet partiel (302), procédé caractérisé en ce que dans l'étape de détermination (610) on détermine au moins une troi- 5 sième probabilité représentant la probabilité de présence de l'objet (100) si l'objet (100) se trouve sur le troisième trajet partiel (202) et au moins une quatrième probabilité représentant la probabilité de présence de l'objet (100) sur le quatrième trajet partiel (302) si l'objet (100) se trouve sur le quatrième trajet partiel (302), 10 une étape d'addition (620) additionnant au moins la seconde, la troisième et la quatrième probabilités pour obtenir une valeur auxiliaire, et l'étape de mise à l'échelle (630) mettant à l'échelle au moins la seconde, la troisième, la quatrième probabilités en utilisant la valeur 15 auxiliaire pour déterminer la probabilité de présence de l'objet (100) dans le réseau de trajet (106). 5°) Procédé (600) selon la revendication 4, caractérisé en ce que 20 l'étape d'admission fournit une valeur auxiliaire qui représente une probabilité supérieure à 100% et dans l'étape de mise à l'échelle (630) on met à l'échelle la troisième, la quatrième et la seconde probabilités pour qu'après cette mise à l'échelle, la somme de la troisième, de la quatrième et de la seconde probabilités représente une probabilité de 100%. 25 6°) Procédé (600) selon la revendication 4 ou 5, caractérisé en ce que dans l'étape de détermination (610), en utilisant la quatrième probabilité et la seconde probabilités, on détermine une probabilité de présence 30 de l'objet (100) sur un cinquième trajet partiel (406) accessible par le premier trajet partiel (202) et le second trajet partiel (204), si l'objet (100) se trouve sur le premier trajet partiel (202) ou le quatrième trajet partiel (302) ou sur le second trajet partiel (204) ou l'autre trajet partiel (402). 35 3044127 23 7°) Procédé (600) selon la revendication 6, caractérisé en ce que dans l'étape de détermination (610), la probabilité de présence de l'objet (100) sur le cinquième trajet partiel (406) correspond à la quatrième 5 probabilité si la seconde probabilité représente une probabilité de pré- sence inférieure à la quatrième probabilité ou correspond à la seconde probabilité si la quatrième probabilité représente une probabilité de présence inférieure à la seconde probabilité. 10 8°) Procédé (600) selon l'une des revendications 4 à 7, caractérisé par une étape de correction de la troisième, quatrième et/ou seconde probabilités en utilisant les données de capteur fournies par au moins un capteur (108) de l'objet (100). 15 9°) Procédé (600) selon l'une des revendications 4 à 8, caractérisé en ce que dans l'étape de détermination (610) on détermine au moins une probabilité supplémentaire qui représente la probabilité de présence de l'objet 20 (100) sur au moins un trajet partiel (404) partant de l'autre point de bi- furcation (400) si l'objet (100) se trouve sur le second trajet partiel (204), * et dans l'étape d'addition (620) on additionne au moins la troisième, la quatrième, la seconde et la probabilité supplémentaire pour obte- 25 nir la valeur auxiliaire, dans l'étape de mise à l'échelle (630) on met à l'échelle au moins la troisième, la quatrième, la seconde probabilité et la probabilité supplémentaire en utilisant la valeur auxiliaire. 30 10°) Appareil de commande (102) comportant des unités (710, 720, 730) pour exécuter et/ou commander les étapes du procédé (600) selon l'une des revendications 1 à 9. 3044127 24 11°) Programme d'ordinateur pour la mise en oeuvre du procédé (600) selon l'une des revendications 1 à 9 et support de mémoire lisible par une machine comportant le programme d'ordinateur. 5