💾 Archived View for ploum.net › 2023-11-03-logiciels-de-navigation.gmi captured on 2024-07-08 at 23:59:22. Gemini links have been rewritten to link to archived content
⬅️ Previous capture (2024-05-10)
-=-=-=-=-=-=-
2023-11-03
S’il y’a bien un logiciel propriétaire difficile à lâcher, c’est Google Maps. Ou Waze, qui appartient également à Google. Pourquoi est-ce si compliqué de produire un logiciel de navigation libre ? Ayant passé quelques années dans cette industrie, je vais vous expliquer les différents composants d’un logiciel de navigation.
Les briques de base d’un logiciel de navigation sont la position, les données, le mapmatching, le routing, la recherche et les données temps réel. Pour chaque composant, je propose une explication et une analyse des solutions libres.
Le premier composant est un système de positionnement qui va fournir une coordonnée géographique avec, parfois, un degré de précision. Une longitude et une latitude, tout simplement.
Il existe plusieurs manières d’estimer une position. Le plus connu est le GPS qui capte des ondes émises par les satellites du même nom. Contrairement à une idée tenace, votre téléphone n’émet rien lorsqu’il utilise le GPS, il se contente d’écouter les signaux GPS tout comme une radio FM écoute les ondes déjà présentes. Votre téléphone n’a de toute façon pas la puissance d’émettre jusqu’à un satellite. Les satellites GPS sont, au plus près, à 20.000 km de vous. Vous croyez que votre téléphone puisse envoyer un signal à 20.000 km ?
Pour simplifier à outrance, le principe d’un satellite GPS est d’émettre en permanence un signal avec l’heure qu’il est à son bord. Votre téléphone, en captant ce signal, compare cette heure avec sa propre horloge interne. Le décalage entre les deux permet de mesurer la distance entre le téléphone et le satellite, sachant que l’onde se déplace à la vitesse de la lumière, une onde radio n’étant que de la lumière dans un spectre invisible à l’œil humain. En refaisant cette opération pour trois satellites dont la position est connue, le téléphone peut, par triangulation, connaître sa position exacte.
Fait intéressant: ce calcul n’est possible qu’en connaissant la position des satellites GPS. Ces positions étant changeantes et difficilement prévisibles à long terme, elles sont envoyées par les satellites eux-mêmes, en plus de l’heure. On parle des « éphémérides ». Cependant, attendre l’envoi des éphémérides complètes peut prendre plusieurs minutes, le signal GPS ne pouvant envoyer que très peu de données.
C’est la raison pour laquelle un GPS éteint depuis longtemps mettra un long moment avant d’afficher sa position. Un GPS éteint depuis quelques heures seulement pourra réutiliser les éphémérides précédentes. Et pour votre smartphone, c’est encore plus facile : il profite de sa connexion 4G ou Wifi pour télécharger les éphémérides sur Internet et vous offrir un positionnement (un « fix ») quasi instantané.
Le système GPS appartient à l’armée américaine. Le concurrent russe s’appelle GLONASS et la version civile européenne Galileo. La plupart des appareils récents supportent les trois réseaux, mais ce n’est pas universel.
Même sans satellite, votre smartphone vous positionnera assez facilement en utilisant les bornes wifi et les appareils Bluetooth à proximité. De quelle manière ? C’est très simple : les appareils Google et Apple envoient, en permanence, à leur propriétaires respectifs (les deux entreprises susnommées) votre position GPS ainsi que la liste des wifi, appareils Bluetooth et NFC dans le voisinage. Le simple fait d’avoir cet engin nous transforme un espion au service de ces entreprises. En fait, de nombreux engins espionnent en permanence notre position pour revendre ces données.
Si on coupe le GPS d’un appareil Android Google, celui-ci se contentera d’envoyer une requête à Google sous la forme : « Dis, je ne connais pas ma position, mais je capte le wifi grandmaman64 et superpotes89 ainsi qu’une télé Samsung compatible Bluetooth, t’aurais pas une idée d’où je suis ? ». Réponse : « Ben justement, j’ai trois utilisateurs qui sont passés hier près de ces wifis et de cette télé, ils étaient dans la rue Machinchose. Donc tu es probablement dans la rue Machinchose. » Apple fait exactement pareil.
Quelle que soit la solution utilisée, GPS ou autre, la position d’un smartphone est fournie par le système d’exploitation et ne pose donc aucun problème au développeur d’application. C’est complètement transparent, mais l’obtention d’une position sera parfois légèrement plus longue sans les services Google ou Apple propriétaires décrits ci-dessus.
Ce n’est pas tout d’avoir une position, encore faut-il savoir à quoi elle correspond. C’est le rôle des données cartographiques, souvent appelées "data" dans l’industrie.
Obtenir des données cartographiques est un boulot inimaginable qui, historiquement, impliquait de faire rouler des voitures sur toutes les routes d’un pays, croisant les données avec la cartographie officielle puis mêlant cela aux données satellites. Dans les années 2000, deux fournisseurs se partageaient un duopole (Navteq, acquis par Nokia en 2007 et TeleAtlas, acquis par Tomtom en 2008). Google Maps utilisait d’ailleurs souvent des données issues de ces fournisseurs (ainsi que tous les GPS de l’époque). Dans certaines régions, le logo Navteq était même visible sur la cartographie Google Maps. Mais plutôt que de payer une fortune à ces entreprises, Google a décidé de lancer sa propre base de données, envoyant ses propres voitures sur les routes (et profitant de l’occasion pour lancer Google Street View).
La toute grande difficulté des data, c’est qu’elles changent tout le temps. Les sentiers et les chemins se modifient. Des routes sont ouvertes. D’autres, fermées. Des constructions se font, des quartiers entiers apparaissent alors qu’une voie se retrouve à sens unique. Parcourir la campagne à vélo m’a appris que chaque jour peut être complètement différent. Des itinéraires deviennent soudainement impraticables pour cause de ronces, de fortes pluies ou de chutes d’arbres. D’autres apparaissent comme par magie. C’est un peu moins rapide pour les automobilistes, mais tentez de traverser l’Europe avec une carte d’une dizaine d’années et vous comprendrez votre douleur.
En parallèle de ces fournisseurs commerciaux est apparu le projet OpenStreetMap que personne ne voulait prendre au sérieux dans l’industrie. On m’a plusieurs fois ri au nez lorsque j’ai suggéré que cette solution était l’avenir. Tout comme Universalis ne prenait pas Wikipédia au sérieux.
Le résultat, nous le connaissons : OpenStreetMap est aujourd’hui la meilleure base de données cartographiques pour la plupart des cas d’usage courant. À tel point que les géants comme Waze n’hésitent pas à les repomper illégalement. Sebsauvage signale le cas d’un contributeur OSM qui a sciemment inventé un parc de toutes pièces. Ce parc s’est retrouvé sur Waze…
Sebsauvage: j’ai un problème avec Waze
Mais les applications utilisant OpenStreetMap doivent faire face à un gros défi : soit demander à l’utilisateur de charger les cartes à l’avance et de les mettre à jour régulièrement, soit de les télécharger au fur et à mesure, ce qui rend l’utilisation peu pratique (comment calculer un itinéraire ou trouver une adresse dans une zone dont on n’a pas la carte ?). Le projet OpenStreetMaps est en effet financé essentiellement par les dons et ne peut offrir une infrastructure de serveurs répondant immédiatement à chaque requête, chose que Google peut confortablement se permettre.
Une fois qu’on a la carte et la position, il suffit d’afficher la position sur la carte, non ? Et bien ce n’est pas aussi simple. Tout d’abord parce que la planète est loin de correspondre à une surface plane. Il faut donc considérer la courbure de la terre et le relief. Mais, surtout, le GPS tout comme les données cartographiques peuvent avoir plusieurs mètres d’imprécision.
Le mapmatching consiste à tenter de faire coïncider les deux informations : si un GPS se déplace à 120km/h sur une ligne parallèle située à quelques mètres de l’autoroute, il est probablement sur l’autoroute ! Il faut donc corriger la position en fonction des données.
En ville, des hauts bâtiments peuvent parfois refléter le signal GPS et donc allonger le temps de parcours de celui-ci. Le téléphone croira alors être plus loin du satellite que ce n’est réellement le cas. Dans ce genre de situation, le mapmatching vous mettra dans une rue parallèle. Cela vous est peut-être déjà arrivé et c’est assez perturbant.
Une autre application du mapmatching, c’est de tenter de prédire la position future, par exemple dans un tunnel. La position GPS, de par son fonctionnement, introduit en effet une latence de quelques secondes. Dans une longue ligne droite, ce n’est pas dramatique. Mais quand il s’agit de savoir à quel embranchement d’un rond-point tourner, chaque seconde est importante.
Le logiciel peut alors tenter de prédire, en fonction de votre vitesse, votre position réelle. Parfois, ça foire. Comme lorsqu’il vous dit que vous avez déjà dépassé l’embranchement que vous devez prendre alors que ce n’est pas le cas. Ou qu’il vous dit de tourner dans trente mètres alors que vous êtes déjà passé.
On a la position sur la carte qui est, le plus souvent, notre point de départ. Il manque un truc important: le point d’arrivée. Et pour trouver le point d’arrivée, il faut que l’utilisateur l’indique.
Les recherches géographiques sont très compliquées, car la manière dont nous écrivons les adresses n’a pas beaucoup de sens : on donne le nom de la rue avant de donner la ville avant de donner le pays ! Dans les voitures, la solution a été de forcer les utilisateurs à entrer leurs adresses à l’envers: pays, ville, rue, numéro. C’est plus logique, mais nous sommes tellement habitués à l’inverse que c’est contre-intuitif.
Le problème de la recherche dans une base de données est un problème très complexe. Avec les applications OpenStreetMap, la base de données est sur votre téléphone et votre recherche est calculée par le minuscule processeur de ce dernier.
Ici, Google possède un avantage concurrentiel incommensurable. Ce n’est pas votre téléphone qui fait la recherche, mais bien les gigantesques serveurs de Google. Tapez "rue Machinchose" et la requête est immédiatement envoyée à Google (qui en profite pour prendre note dans un coin, histoire de pouvoir utiliser ces informations pour mieux vous cibler avec des publicités). Les ordinateurs de Google étant tellement rapide, ils peuvent même tenter d’être intelligent: il y’a 12 rue Machinchose dans tout le pays, mais une MachinChause, avec une orthographe différente, dans un rayon de 10km, on va donc lui proposer celle-là . Surtout que, tient, nous avons en mémoire qu’il s’est rendu 7 fois dans cette rue au cours des trois dernières années, même sans utiliser le GPS.
Force est de constater que les applications libres qui font la recherche sur votre téléphone ne peuvent rivaliser en termes de rapidité et d’aisance. Pour les utiliser, il faut s’adapter, accepter de refaire la recherche avec des orthographes différentes et d’attendre les résultats.
On a le départ, on a l’arrivée. Maintenant il s’agit de calculer la route, une opération appelée « routing ». Pour faire du routing, chaque tronçon de route va se voir attribuer différentes valeurs : longueur, temps estimé pour le parcourir, mais aussi potentiellement le prix (routes payantes), la beauté (si on veut proposer un trajet plus agréable), le type de revêtement, etc.
L’algorithme de routing va donc aligner tous les tronçons de route entre le départ et l’arrivée, traçant des centaines ou des milliers d’itinéraires possibles, calculant pour chaque itinéraire la valeur totale en additionnant les valeurs de chaque tronçon.
Il va ensuite sélectionner l’itinéraire avec la meilleure valeur totale. Si on veut le plus rapide, c’est le temps total estimé le plus court. Si on veut la distance, c’est la distance la plus courte, etc.
À mon époque, l’algorithme utilisé était le plus souvent de type « Bidirectionnal weighted A-star ». Cela signifie qu’on commence à la fois du départ et de l’arrivée, en explorant jusqu’au moment où les chemins se rencontrent et en abandonnant les chemins qui sont déjà de toute façon disqualifiés, car un plus court existe (oui, on peut aller de Bruxelles à Paris en passant par Amsterdam, mais ce n’est pas le plus efficace).
Une fois encore, le problème est particulièrement complexe et votre téléphone va prendre un temps énorme à calculer l’itinéraire. Alors que les serveurs de Google vont le faire pour vous. Google Maps ne fait donc aucun calcul sur votre téléphone : l’application se contente de demander aux serveurs Google de les faire à votre place. Ceux-ci centralisent les milliers d’itinéraires demandés par les utilisateurs et les réutilisent parfois sans tout recalculer. Quand on est un monopole, il n’y a pas de petits profits.
Mais si on veut le trajet le plus rapide en voiture, une évidence saute aux yeux: il faut éviter les embouteillages. Et les données concernant les embouteillages sont très difficiles à obtenir en temps réel.
Sauf si vous êtes un monopole qui se permet d’espionner une immense majorité de la population en temps réel. Il vous suffit alors, pour chaque tronçon de route, de prendre la vitesse moyenne des téléphones qui sont actuellement sur ce tronçon.
L’artiste Simon Weckert avait d’ailleurs illustré ce principe en promenant 99 smartphones connectés sur Google maps dans un chariot. Le résultat ? Une rue déserte est devenue un embouteillage sur Google Maps.
La performance Google Maps de Simon Weckert
Là , force est de constater qu’il est difficile, voire impossible, de fournir ces données sans espionner massivement toute la population. À ce petit jeu, les alternatives libres ne pourront donc jamais égaler un monopole de surveillance comme celui de Google.
Mais tout n’est pas noir, car, contrairement à ce qu’on pourrait croire, les infos trafic ne nous permettent pas d’aller plus vite. Elles donnent une illusion d’optimalité qui empire le trafic sur les itinéraires alternatifs et, au final, le temps perdu reste identique. Le seul avantage est que la prévision du temps de trajet est grandement améliorée.
Une expérience du routing sur Organic Maps
Une étude démontrant que les infotrafics ne font que modifier le problème sans le résoudre.
Ce résultat résulte de ce que j’appelle le paradoxe de l’embouteillage. C’est un fait bien connu des scientifiques et ignoré à dessein des politiciens que le trafic automobile est contre-intuitif. Au plus la route est large et permet à de nombreux véhicules de passer, au plus les embouteillages seront importants et la circulation chaotique. Si votre politicien propose de rajouter une bande sur le périphérique pour fluidifier la circulation, changez de politicien !
L’explication de ce phénomène tient au fait que lorsqu’il y’a un embouteillage sur le périphérique, ce n’est pas le périphérique qui bouche. C’est qu’il y’a plus de voitures qui rentrent sur le périphérique que de voitures qui en sortent. Or, les sorties restent et resteront toujours limitées par la taille des rues dans les villes.
En bref, un embouteillage est causé par le goulot d’étranglement, les parties les plus étroites qui sont, le plus souvent, les rues et ruelles des différentes destinations finales. Élargir le périphérique revient à élargir le large bout d’un entonnoir en espérant qu’il se vide plus vite. Et, de fait, cela rend les choses encore pires, car cela augmente le volume total de l’entonnoir, ce qui fait qu’il contient plus d’eau et mettra donc plus longtemps à se vider.
99 smartphones dans un bac à roulette: c’est tout ce que nous sommes pour Google
Les infotrafics et les itinéraires alternatifs proposés par Google Maps ne font pas autre chose que de rajouter une bande de trafic virtuelle (sous forme d’un itinéraire alternatif) et donc élargissent le haut de l’entonnoir. Les infos trafic restent utiles dans les cas particuliers où votre destination est complètement différente du reste de la circulation. Où si la congestion apparait brusquement, comme un accident : dans ce cas, vous pourriez avoir le bénéfice rare, mais enviable d’emprunter l’itinéraire de secours juste avant sa congestion.
La plupart du temps, les infotrafics sont globalement contre-productifs par le simple fait que tout le monde les utilise. Elles seraient parfaites si vous étiez la seule personne à en bénéficier. Mais comme tout le monde les utilise, vous êtes également obligé de les utiliser. Tout le monde y perd.
Leur impact premier est surtout psychologique: en jouant avec les itinéraires alternatifs, vous pouvez vous convaincre que vous n’avez pas d’autre choix que prendre votre mal en patience. Alors que, sans eux, vous serez persuadés qu’il y’a forcément une autre solution.
Alors, se passer de Google Maps ? Comme nous l’avons vu, ce n’est pas évident. Le service Google Maps/Waze se base sur l’espionnage permanent et instantané de milliards d’utilisateurs, offrant une précision et une rapidité insurpassable. Quand on y pense, le coût de ce confort est particulièrement élevé. Et pourtant, Google Maps n’est pas la panacée.
J’ai personnellement un faible pour Organic Maps, que je trouve bien meilleur que Google Maps pour tout à l’exception du trafic routier : les itinéraires à pieds, en vélo et même en voiture hors des grands axes sont bien plus intéressants. Certes, il nécessite de télécharger les cartes. Inconvénient, selon moi, mineur, car permettant une utilisation même sans connexion. La recherche est, par contre, souvent frustrante et lente.
Mais le mieux est peut-être d’explorer les alternatives libres à Google Maps dans cet excellent article de Louis Derrac.
5 alternatives Ă Google Maps, par Louis Derrac
Et puis, pourquoi ne pas lutter contre la privatisation du bien commun qu’est la cartographie en apprenant à contribuer à OpenStreetMap ?
La photo d’illustration est de Al Soot, sur Unsplash
----
Email:
permalinks:
