Calcul d’itinéraires avec édition du graphe en ligne

Le plan d’orientation en ligne de l’Ecole polytechnique fédérale de Lausanne est un outil indispensable pour les étudiants, les collaborateurs et les visiteurs du campus universitaire. Avec ses 80 bâtiments totalisant près de 700’000 m2, ses quelque 10’000 bureaux, laboratoires, auditoires et salles de cours, l’EPFL est un véritable labyrinthe.

Une nouvelle version de la recherche d’itinéraires, dotée d’une édition simplifiée via le framework web Open Source GeoMapFish, sera mise en production d’ici quelques semaines.

Recherche d’itinéraires

L’application Plan d’orientation EPFL, ou “Plan”, fournit des informations précieuses sur le campus : bureaux, salles de cours, points d’intérêt, transports, restauration, etc.. Parmi les nombreuses fonctionnalités proposées, la recherche d’itinéraires est particulièrement utile. En partant d’un résultat de la recherche, il est possible de faire calculer puis d’afficher le plus court chemin vers une destination. L’utilisateur peut ensuite continuer à naviguer sur la carte en gardant le chemin calculé en surimpression. Une feuille de route permet la navigation directe vers les changements de niveau.

Si l’application Plan se base sur le framework GeoMapFish, le calcul lui-même est réalisé dans la base de données grâce à la librairie pgRouting. L’algorithme A* utilisé nécessite la mise en place d’un graphe composé d'arêtes et de sommets qui représente l’entier du réseau de couloirs, zones extérieures et locaux de l'École. Ce graphe mathématique contient également les géométries (lignes) qui permettent l’affichage du résultat.

Bien sûr, le graphe doit inclure le passage d’un étage à l’autre par les escaliers et les ascenseurs. Des poids différents sont par ailleurs attribués à quatre niveaux d'importance des arêtes : traversée de l’EPFL, passage d’un bâtiment à l’autre, couloir et intérieur d’un local. Ces niveaux permettent par exemple d’éviter la traversée d’un local alors qu’il serait plus logique de continuer dans le couloir adjacent.

On le comprend, la saisie d’un tel graphe pour un campus de cette taille constitue un réel défi. Il est donc important de fournir aux utilisateurs chargés de l’édition les outils les plus simples et les plus intuitifs possibles.

Versions actuelle et future

Jusque récemment, la saisie des chemins possibles pour les itinéraires était réalisée via des dessins AutoCAD. L’utilisateur affichait le réseau d’itinéraires avec en fond le plan d’architecte et pouvait ainsi appliquer des modifications. Cette manière de faire avait plusieurs inconvénients :

- Un plan AutoCAD par niveau, avec une jointure entre les étages difficile à dessiner

- Conversion nécessaire entre le dessin AutoCAD et le graphe dans la base de données.
Cette conversion était effectuée via des scripts FME complexes dont la maintenance était hasardeuse

- Impossibilité de tester le réseau dessiné sans lancer la mise à jour de la base de données

- Peu aisé de travailler à plusieurs sur la modification du graphe

Après une analyse approfondie, la décision a été prise de transférer vers une interface web la saisie du réseau d’itinéraires. La fonctionnalité a été ajoutée au Géoportail, l’application pour les collaborateurs de l’EPFL qui se base sur les mêmes données que Plan et qui fournit déjà des outils d’édition. L’édition du graphe se fait donc directement sur les tables de la base de données qui sont utilisées pour le calcul par la librairie pgRouting. A chaque modification, il est donc possible de tester directement comment réagit la recherche d’itinéraires.

Des règles claires définissent comment la jointure entre deux étages doit être réalisée. Par exemple, dans le cas d’un escalier, une arête de type “escalier” doit être dessinée dans le sens de la montée à l’étage inférieur et une autre à l’étage supérieur, en prenant soin de lier les deux.

Fonctionnalités avancées

Plusieurs fonctions avancées simplifient le travail d’édition du réseau :

Snapping

Tous les points et lignes du réseau sont aimantés (snapping). Il est ainsi possible d’atteindre une grande précision lorsqu’on ajoute une nouvelle ligne. Lorsqu’on snappe sur une ligne existante, celle-ci est automatiquement coupée en deux. En affichant les lignes de l’étage inférieur ou supérieur, le snapping garantit la connexion des escaliers et des ascenseurs.

Orthogonalité

Lors de l’ajout d’une ligne, la touche Ctrl permet d’activer la fonction d’orthogonalité. Celle-ci garantit que la nouvelle ligne sera verticale, horizontale ou diagonale. Au besoin, si le bâtiment n’est pas orienté parfaitement au nord, la carte peut être tournée avant l’utilisation de la fonction d’orthogonalité.

Détection d’erreurs

La fonction de détection d’erreurs permet d’afficher sur une couche spéciale des points rouges aux endroits où le réseau contient des erreurs. Un clic sur un point rouge donne des informations sur le problème rencontré. La version actuelle de cette fonction est assez basique et ne peut détecter que des erreurs simples telles qu’un escalier non connecté à l’étage inférieur ou supérieur. Des améliorations sont prévues.

Validation

Les modifications du réseau peuvent être relativement complexes, comme lorsqu’un nouveau bâtiment est ajouté. Il est donc important d’avoir deux versions du réseau, une version en production (ou validée) et une version en cours de modification (non validée). La version non validée peut être testée via la recherche d’itinéraires classique par l’ajout d’un paramètre spécial dans l’URL de l’application. Un bouton permet de passer la version non validée en production, lorsque les modifications sont terminées.

Evolutions

Plusieurs évolutions possibles ont été discutées et pourraient voir le jour prochainement :

Gestion avancée des erreurs

Afin d’aider encore plus l’utilisateur qui saisit le réseau d’itinéraires, on peut imaginer détecter de nombreux types d’erreurs supplémentaires. Un exemple qui sera certainement développé est la recherche de locaux ne contenant pas de point du réseau, et qui ne pourront donc jamais être atteints par un itinéraire.

Feuille de route avancée

Aujourd’hui, la feuille de route proposée à l’utilisateur final est assez simple. Elle permet uniquement de passer d’un changement de niveau à un autre. On peut imaginer de nombreuses améliorations, comme des indications sur les changements de direction importants, les entrées dans les bâtiments ou les passages à proximité de points d’intérêts marquants (œuvres d’art, par exemple).

Mobilité réduite

Le calcul d’itinéraires ne permet pas aujourd’hui d’éviter les escaliers et autres obstacles. L’ajout d’une option au niveau de l’interface pourrait indiquer au calcul qu’il doit ignorer les escaliers et, par exemple, privilégier les portes automatiques.

Position précise de l’utilisateur

La localisation des personnes à l’intérieur des bâtiments est toujours un problème délicat. Le signal GPS peut être réduit et n’est dans tous les cas pas suffisant pour déterminer à quel étage on se trouve. Il existe des solutions matérielles qui pourraient être mises en place et couplées au calcul d’itinéraires afin de connaître la position exacte de l’utilisateur. Cette position pourrait ensuite être utilisée comme point de départ ou pour déterminer si l’utilisateur s’écarte du chemin proposé.

Plan d'orientation EPFL : https://plan.epfl.ch