Brevet FR2677756A1 — publié le 19921218

La présente invention concerne un procédé et un dispositif de calcul d'un itinéraire de navigation notamment pour véhicule automobile, dans une région donnée. On connait déjà dans l'état de la technique différents procédés et dispositifs de ce type pour le calcul d'un itinéraire de navigation d'un véhicule automobile dans une région donnée entre un point de départ et un point d'arrivée, à l'aide d'un calculateur d'itinéraire dans lequel sont chargés des algorithmes de calcul. Dans l'état de la technique, les calculateurs et les algorithmes travaillent à partir d'une mémoire de masse dans laquelle sont stockés différents paramètres de noeuds correspondant à des carrefours et d'arcs correspondant à des voies aboutissant à ces carrefours. Ces paramètres permettent de définir par exemple la présence de feux de signalisation à un carrefour, différentes contraintes de circulation liées à celui-ci, la longueur des voies aboutissant à ces carrefours, etc.. Ces différents paramètres permettent aux algorithmes de calcul de déterminer le meilleur itinéraire possible pour aller d'un point de départ à un point d'arrivée, entrés par un utilisateur dans le calculateur et différentes informations d'aide à la navigation du véhicule qui sont ensuite transférées par ce calculateur à des moyens d'affichage pour informer l'utilisateur de l'itinéraire optimal calculé. Cependant, ces procédés et ces dispositifs présentent un certain nombre d'inconvénients car ils nécessitent des moyens de mémorisation très importants et un temps de calcul relativement long. En effet, les calculateurs sont obligés de travailler sur l'ensemble des informations relatives aux noeuds et aux arcs de la région donnée, et on conçoit que ceci se traduit par un temps de réponse très long de l'ensemble d'aide à la navigation. Le but de l'invention est donc de résoudre ces problèmes en proposant un procédé et un dispositif de calcul d'un itinéraire de navigation, qui soient simples, fiables et qui permettent d'obtenir un itinéraire le plus rapidement possible. A cet effet, l'invention a pour objet un procédé de calcul d'un itinéraire de navigation notamment pour véhicule automobile, dans une région donnée entre un point de départ et un point d'arrivée, à l'aide d'un calculateur d'itinéraire dans lequel sont chargés des algorithmes de calcul, caractérisé en ce que - on découpe la région en zones, - dans chaque zone, on définit différents paramètres de noeuds correspondant à des carrefours et d'arcs correspondant à des voies aboutissant à ces carrefours, utilisables par les algorithmes de calcul du calculateur d'itinéraire, - on stocke par blocs de zone, ces différentes informations dans une mémoire de masse, - on sélectionne parmi les blocs de zone, des blocs utiles au calcul d'un itinéraire en fonction des données de point de départ et d'arrivée, entrées par un utilisateur dans le calculateur, - on transfère ces blocs utiles de la mémoire de masse dans la mémoire de travail du calculateur d'itinéraire, et - on calcule l'itinéraire à partir des informations contenues dans ces blocs utiles. Selon un autre aspect, l'invention a également pour objet un dispositif de calcul d'un itinéraire de navigation notamment pour véhicule automobile, dans une région donnée, entre un point de départ et un point d'arrivée, du type comportant un calculateur d'itinéraire dans lequel sont chargés des algorithmes de calcul, caractérisé en ce qu'il comporte des moyens de découpage en zones, des moyens de définition dans chaque zone, de différents paramètres de noeuds correspondant à des carrefours et d'arcs correspondant à des voies aboutissant à ces carrefours, utilisables par les algorithmes de calcul du calculateur d'itinéraire, des moyens de stockage de masse par blocs de zone de ces différentes informations, des moyens de sélection parmi les blocs de zone, des blocs utiles au calcul d'un itinéraire en fonction des données de points de départ et d'arrivée entrées par l'utilisateur dans le calculateur, des moyens de transfert des blocs utiles de la mémoire de masse dans la mémoire de travail du calculateur d'itinéraire et des moyens de calcul d'itinéraire à partir des informations contenues dans ces blocs utiles. L'invention sera mieux comprise à l'aide de la description qui va suivre, donnée uniquement à titre d'exemple et faite en se référant aux dessins annexés, sur lesquels - la Fig.1 illustre une première étape d'un procédé selon l'invention au cours de laquelle on découpe une région donnée, en zones; - la Fig.2 illustre une seconde étape d'un procédé selon l'invention au cours de laquelle on définit, pour chaque zone, différents paramètres de noeuds correspondant à des carrefours et d'arcs correspondant à des voies d'accès à ces carrefours; - la Fig.3 illustre une troisième étape d'un procédé selon l'invention, au cours de laquelle on stocke les différents paramètres définis dans la seconde étape dans une mémoire de masse;; - les Fig.4 et 5 illustrent des étapes de sélection parmi les blocs d'informations stockés dans la mémoire de masse, des blocs utiles au calcul d'un itinéraire de navigation en fonction des points de départ et d'arrivée entrés par un utilisateur dans le calculateur; et - la Fig.6 représente un schéma synoptique d'une partie d'un dispositif selon l'invention. Ainsi qu'on peut le voir sur la Fig.1, la première étape d'un procédé de calcul d'un itinéraire de navigation selon l'invention, consiste à découper une région donnée, en zones. Sur cette figure, la région illustrée est celle de Paris et celle-ci est découpée en zones élémentaires, par exemple de 1 km de côté. Ce découpage est réalisé par tout moyen de traitement d'informations approprié comme par exemple par un ordinateur ou autre, à partir d'une base de données reprenant sous forme numérique, les différentes informations cartographiques relatives à la région. On notera que ces différentes informations peuvent être fournies par les différentes institutions géographiques nationales et que ces bases numériques existent déjà dans l'état de la technique. Comme on peut le voir sur la Fig.2, on définit ensuite dans chaque zone, après l'opération de découpage réalisée précédemment, différents paramètres de noeuds correspondant à des carrefours et d'arcs correspondant à des voies aboutissant à ces carrefours. Ces différents paramètres concernent des critères de confort et de rapidité permettant aux algorithmes de calcul intégrés dans le calculateur d'itinéraire de déterminer un itinéraire conseillé, de manière connue en soi. C'est ainsi par exemple que sur cette figure 2, les différents carrefours sont désignés par les références générales S, tandis que les arcs sont désignés par les références générales a. Les différents paramètres caractérisant ces noeuds et ces arcs, sont par exemple la présence de feux de signalisation, l'existence de travaux ou de limitations de circulation, la longueur des arcs reliant les noeuds, etc. Par ailleurs, à chaque noeud sont également associées ses coordonnées dans un système d'axes de la région numérisée et chaque arc peut être décomposé en une succession de points physiques décrivant sa courbure. On notera que ces noeuds et ces arcs peuvent également être liés à des informations interprétables par l'utilisateur, telles que par exemple le nom des routes, des rues ou encore des carrefours, ces informations pouvant être visualisées sur un écran d'aide à la navigation de manière connue en soi. On conçoit donc que la région, qu'elle concerne une ville ou de manière générale un réseau routier, est représentée par un ensemble de voies, de rues ou de routes et de carrefours, et s'identifie très bien à un graphe orienté dans lequel chaque carrefour est un noeud et toute partie de rue ou de voie entre deux carrefours, est un arc. L'efficacité des algorithmes de calcul d'itinéraire demande une organisation de fichiers de base de données de stockage, telle que de tout noeud il soit possible de connaître rapidement tout autre noeud accessible de celui-ci. Ainsi, à chaque noeud de base, qui sera appelé par la suite noeud de référence, on associe outre des informations locales le concernant, la liste de tous les noeuds auxquels il donne accès, ces noeuds étant appelés par la suite noeuds successeurs, ainsi que des informations concernant le lien entre ces noeuds, comme par exemple un numéro ou un nom d'arc, des informations caractérisant cet arc telles que sa longueur, la largeur de la voie représentée, l'angle de cet arc par rapport à un axe choisi, etc. . La différenciation des noeuds réellement accessibles sur le terrain de ceux numérisés dans la base de données et dont les liens n'ont pas de réalité physique, du fait par exemple de la présence de sens uniques ou d'impasses, peut être faite soit par une information ajoutée dans la liste des informations concernant les noeuds, soit par l'affectation d'un signe moins au noeud successeur par exemple. L'intérêt de la conservation de tous les noeuds successeurs existant dans la base de données numérisées, même si ceux-ci ne sont pas accessibles directement sur le terrain, est suscité par une volonté de correction ou de modification ultérieures simplifiées. En effet, on peut être amené à interdire l'accès d'une voie ou bien à l'autoriser à nouveau selon les besoins et ceci doit pouvoir se faire de façon quasi instantanée. On est donc tenu de conserver une trame complète de la carte numérisée de la région et de superposer une notion de sens de circulation à celle-ci. Chaque enregistrement élémentaire de la base de données est caractérisé par un numéro de noeud de référence et le nombre de noeuds auxquels il donne accès dans la base, suivi de la liste des numéros des noeuds successeurs qui sont liés et des paramètres utiles aux algorithmes de calcul d'itinéraire et caractérisant l'arc liant les noeuds concernés. Bien entendu, d'autres organisations peuvent etre envisagées. Ainsi, le numéro d'arc au sein d'un enregistrement successeur dans la base n'est pas utile lors du calcul d'itinéraire, mais il peut quand même être précisé pour deux raisons - la possibilité de délivrer une-liste d'arcs plutôt qu'une liste de noeuds pour définir le chemin calculé semble plus correspondre à la finalité de la fonction d'aide à la navigation (délivrance des informations par fourniture d'une succession de voies, plutôt que de croisements).La présence de ces informations permet par exemple un gain de temps important, lors de la présentation de l'itinéraire optimal calculé, - la liste des paramètres caractérisant les arcs d'enregistrements successeurs peut également être séparée du fichier contenant ceux-ci et associée aux arcs concernés dans un fichier supplémentaire (par exemple le fichier dans lequel on trouve une correspondance entre numéros d'arcs et noms de voies) afin de réduire la taille du fichier. En effet, chaque liste est présente deux fois dans le fichier de calcul d'itinéraire (un arc est défini entre deux noeuds) avec de nombreux paramètres modifiables. On constate donc que les enregistrements complets décrivant les noeuds dans le fichier de calcul d'itinéraire ne sont pas de taille fixe et que leur taille dépend du nombre de noeuds successeurs. L'avantage de cette méthode de stockage est d'obtenir un fichier final sans perte d'espace mémoire mais la contrepartie est une impossibilité de retrouver un enregistrement rapidement. En effet, tout enregistrement dans la base ne peut être lu que si le précédent a été lu. Cependant, cet inconvénient peut être efficacement éliminé grâce à une organisation par bloc de la base, telle que celle utilisée dans le procédé et le dispositif selon l'invention et l'emploi d'un fichier d'index comme cela est illustré sur la Fig.3. Ce fichier d'index permet de retrouver rapidement les différentes informations stockées par bloc dans le fichier d'enregistrements. On notera que ces différentes informations relatives à toutes les zones et donc à la région concer née, sont stockées dans une mémoire de masse du système d'aide à la navigation embarqué à bord du véhicule. Ainsi, cette mémoire de masse contient toutes les informations nécessaires à un calcul d'itinéraire dans toute la région concernée, mais ces informations sont stockées par blocs et les informations de chaque bloc sont donc relatives à une zone élémentaire de la région. On conçoit alors qu'il n'est pas nécessaire de calculer l'itinéraire sur la totalité des informations contenues dans cette mémoire de masse dans la mesure où il est possible de sélectionner parmi ces blocs de zone, des blocs utiles au calcul d'un itinéraire en fonction des données des points de départ et d'arrivée entrés par l'utilisateur dans le calculateur. Cette sélection peut être opérée suivant différentes stratégies. En effet, il y a lieu tout d'abord de restreindre le domaine cartographique à analyser à un domaine d'étude cohérent géographiquement et contenant les informations nécessaires pour la résolution de l'application, ces informations étant ensuite transférées dans la mémoire de travail du calculateur d'itinéraire. On cherche alors à se ramener à une notion d'ensemble d'éléments utiles, simples à gérer. Grâce au découpage précédent de la région, en zones élémentaires, tout domaine d'étude est constitué par un ensemble de blocs qui peuvent être considérés à ce niveau comme des cellules élémentaires facilement analysables par les algorithmes de calcul intégrés dans le calculateur d'itinéraire. Si l'on prend deux noeuds Sd et Sa comme point de départ et point d'arrivée, séparés par une distance L et que l'on cherche à calculer le plus court chemin reliant ces deux points dans la carte numérisée, il est évident que les blocs élémentaires utiles au calcul ne peuvent etre constitués que par des blocs de données contigüs géographiquement et par les blocs contenant les points de départ et d'arrivée. A partir de cette régle, plusieurs stratégies de calcul peuvent être imaginées pour répondre aux besoins. Intuitivement, il semble cohérent de choisir comme domaine d'étude, un domaine de forme elliptique incluant ces deux points en les considérant ou non comme foyers de l'ellipse. Le dimensionnement du grand axe et du petit axe de l'ellipse peuvent être laissés au libre choix de l'utilisateur et peuvent être modulés par exemple en fonction de l'éloignement des deux points ou de l'échelle des zones élémentaires. Ceci est illustré sur la Fig.4, où l'on voit apparaître que le domaine d'étude présente une forme générale elliptique incluant les points de départ et d'arrivée Sd et Sa respectivement. Ce domaine d'étude qui comporte donc des blocs utiles au calcul d'un itinéraire en fonction des données de points de départ et d'arrivée, est transféré de la mémoire de masse dans la mémoire du calculateur d'itinéraire. Cependant, cette sélection de blocs utiles peut s'avérer insuffisante dans certains cas particuliers. En effet, le domaine d'étude obtenu est efficace lors d'un calcul itinéraire dont le principe de base repose sur la détermination de la plus courte distance entre les points de départ et d'arrivée. Or, ceci ne permet pas toujours de répondre aux besoins de l'utilisateur. En effet, si dans le cas particulier, on dispose d'une carte de Paris numérisée et que l'on cherche le chemin le plus rapide reliant deux points opposés de cette ville, il est bien entendu que c'est la ceinture périphérique qui est le chemin le plus à même de répondre à une demande d'accès rapide de l'utilisateur. Or, si l'on sélectionne un domaine d'analyse elliptique tel que mentionné ci-dessus, il est impossible de prendre en compte le boulevard périphérique, celui-ci sortant largement du domaine d'étude envisagé. Cette difficulté peut être contournée en créant des ensembles de blocs présélectionnés toujours pris en compte quels que soit le point de départ et le point d'arrivée entrés par l'utilisateur, ces blocs étant organisés sous forme de fichiers qui seront appelés par la suite fichiers de contraintes, comme cela est illustré sur la Fig.5. Ces fichiers de contraintes sont alors systématiquement sélectionnés par le calculateur et inclus dans le domaine d'étude et ils sont donc pris en compte dans tout calcul d'itinéraire. Ces fichiers de contraintes peuvent comporter différentes informations relatives, suivant le cas, à des voies rapides traversant une ville, à des quais permettant d'accéder rapidement à différents endroits de celle-ci, etc.. Ces différentes informations relatives aux fichiers de contraintes sont également sélectionnées et transférées de la mémoire de masse dans la mémoire de travail du calculateur d'itinéraire pour permettre à celui-ci de calculer cet itinéraire de manière optimale à partir des informations contenues dans l'ensemble de ces blocs sélectionnés. Le dispositif permettant de mettre en oeuvre ce procédé est illustré sur la Fig.6. Ce dispositif comporte un ensemble à microprocesseur 1 de type connu en soi, relié à une mémoire de masse 2, à une mémoire de travail 3, à des moyens 4 d'entrée d'informations par exemple des points de départ et d'arrivée par un utilisateur et constitués par exemple par un clavier et à un dispositif d'affichage d'itinéraire calculé 5. On notera que les moyens d'entrée de données et le dispositif d'affichage peuvent par exemple être disposés sur la console centrale ou sur le tableau de bord du véhicule de manière connue en soi. La mémoire de masse 2 contient sous forme numérisée, toutes les informations relatives à la région donnée, ces informations étant stockées par blocs de zone, ce qui permet, en fonction des informations de points de départ et d'arrivée, entrées par l'utilisateur dans le microprocesseur 1 à l'aide du clavier 4, à ce microprocesseur 1 de sélectionner dans la mémoire de masse 2, les blocs utiles au calcul d'un itinéraire en fonction de ces informations de points de départ et d'arrivée et de les transférer dans sa mémoire de travail 3 pour accélérer le calcul de l'itinéraire. Bien entendu, d'autres modes de réalisation de ce dispositif peuvent être envisagés. La partie de numérisation de la région, de découpage de celle-ci en blocs, de définition dans ceux-ci des paramètres de noeuds et d'arcs et leur stockage dans la mémoire de masse 2, n'est pas représentée dans le détail car ces différentes opérations sont réalisées par un ordinateur connu programmé de manière adéquate. REVENDICATIONS 1. Procédé de calcul d'un itinéraire de navigation, notamment pour véhicule automobile, dans une région donnée, entre un point de départ et un point d'arrivée, à l'aide d'un calculateur (1) d'itinéraire, dans lequel sont chargés des algorithmes de calcul, caractérisé en ce que:: - on découpe la région en zones, - dans chaque zone, on définit différents paramètres de noeuds correspondant à des carrefours et d'arcs correspondant à des voies aboutissant à ces carrefours, utilisables par les algorithmes de calcul du calculateur d'itinéraire, - on stocke par blocs de zone, ces différentes informations dans une mémoire de masse, - on sélectionne parmi les blocs de zone, des blocs utiles au calcul d'un itinéraire en fonction des données de points de départ et d'arrivée, entrées par un utilisateur dans le calculateur, - on transfère ces blocs utiles de la mémoire de masse dans la mémoire de travail du calculateur d'itinéraire, et - on calcule l'itinéraire à partir des informations contenues dans ces blocs utiles. 2. Procédé selon la revendication 1, caractérisé en ce que les blocs utiles sont sélectionnés dans un domaine d'étude elliptique englobant les points de départ et d'arrivée entrés par l'utilisateur. 3. Procédé selon la revendication 2, caractérisé en ce qu'on sélectionne en outre des blocs de fichiers de contraintes de circulation contenant des informations relatives à des itinéraires présélectionnés. 4. Dispositif de calcul d'un itinéraire de navigation notamment pour véhicule automobile, dans une région donnée entre un point de départ et un point d'arrivée, à l'aide d'un calculateur (1) d'itinéraire dans lequel sont chargés des algorithmes de calcul, caractérisé en ce qu'il comporte des moyens de découpage de la région, en zones, des moyens de définition dans chaque zone, de différents paramètres de noeuds correspondant à des carrefours et d'arcs correspondant à des voies aboutissant à ces carrefours, utilisables par les algorithmes de calcul du calculateur d'itinéraire, des moyens (2) de stockage de masse par blocs de zone de ces différentes informations, des moyens (1) de sélection parmi les blocs de zone, de blocs utiles au calcul d'itinéraire en fonction des données de points de départ et d'arrivée entrées par l'utilisateur dans le calculateur, des moyens (1) de transfert des blocs utiles de la mémoire de masse (2) dans une mémoire de travail (3) du calculateur d'itinéraire et des moyens (1) de calcul de l'itinéraire à partir des informations contenues dans ces blocs utiles.