FLASH INFORMATIQUE FI



plan.epfl.ch : dessine-moi un chemin




Pierre CREVOISIER


JPEG - 8.4 ko
La recherche d’itinéraire permet de définir le chemin entre deux points sur le campus. Le point de départ et d’arrivée peuvent être le nom d’une personne, un local ou une unité. Il est également possible de demander le parcours adapté à une personne à mobilité réduite

Vous ne vous en étiez pas aperçu ? Depuis le mois de septembre, plan.epfl.ch a opéré sa mue. Une entrée discrète pour des changements importants : une simplification de l’interface, une ergonomie repensée, de meilleures performances, des outils de personnalisation des plans et, surtout, le calcul d’itinéraire. Visite guidée.
La troisième version de l’application plan.epfl.ch est en ligne. Face au succès croissant de ce service depuis sa mise en ligne, il y a 3 ans déjà [1], l’ancienne version commençait à s’essouffler un peu et une optimisation du moteur du cartoserveur était nécessaire. Sur ce point, nous avons eu tout à gagner des développements entrepris par Camptocamp pour d’autres clients de CartoWeb [2], en particulier Swisstopo. Investir dans un projet open source y trouve son intérêt : pouvoir bénéficier des expériences accumulées par d’autres partenaires...
En plus des gains de performance et d’une ergonomie retravaillée, des fonctionnalités de personnalisation sont disponibles. Ainsi, si vous souhaitez générer un fichier PDF en ajoutant graphiquement des informations - comme le lieu d’une conférence et le chemin d’accès depuis l’arrêt du métro - vous pouvez utiliser des outils de dessin simples et passer ensuite à la création du PDF.

Chacun cherche son chat

Mais c’est sans doute le calcul d’itinéraire qui marque aujourd’hui une étape majeure de plan.epfl.ch, autant par sa genèse que par les fonctionnalités nouvelles qu’il propose.
Il est fort probable que le projet n’aurait pas vu le jour sans une conjonction de différents facteurs, en particulier l’intérêt du Laboratoire de Topométrie. Il y a deux ans environ, une étudiante nous demande un accès aux données de plan.epfl.ch pour réaliser un premier travail de semestre sur le calcul d’itinéraire. Un travail de diplôme suivra [3]. Tant le KIS que Camptocamp suivent cette démarche avec intérêt. Le travail est de qualité et il nous incite en tous les cas à associer le Domaine Immobilier et Infrastructures (DII) de l’EPFL et lui proposer d’en lancer la réalisation. Les règles du jeu sont clairement établies : le Laboratoire de Topométrie assume le rôle de conseil scientifique, la DII prend en charge le dessin du réseau sur ces plans, le KIS gère les interfaces utilisateurs et Camptocamp le développement du moteur de calcul.

Les mailles du filet

Pour tracer le chemin d’un lieu à un autre, il faut connaître l’ensemble des éléments qui composent ce chemin : les portes, les escaliers, les couloirs. Au-delà, il faut aussi associer certaines caractéristiques permettant d’optimiser un parcours (un chemin qui traverse les couloirs d’un bâtiment n’est a priori pas aussi simple que celui qui contourne ce bâtiment...).
Dans les plans Autocad utilisés par nos collègues de la DII pour gérer les locaux de l’EPFL, ces données n’existaient pas. Il a donc fallu les générer. L’un de leurs collaborateurs a donc passé le campus à la loupe pour créer une sémantique réseau. Le résultat est impressionnant : 29’413 points et 35’432 arêtes composent les mailles de ce filet géant. Chaque point et arête du réseau contient donc des attributs spécifiques :

  • passage principal (les grands couloirs, la diagonale, etc.) ou mineur (l’entrée d’un laboratoire par exemple) ;
  • porte libre d’accès, contrôlée par un lecteur Camipro, ou simplement fermée à clé ;
  • type d’obstacle (rampe, escalier, ascenseur)...

La principale difficulté a été de trouver des passerelles entre les contraintes imposées par les plans Autocad - où chaque unité est un réseau en soi, sans référence particulière aux autres réseaux - et le modèle géographique. Prenons par exemple un escalier : dans le plan Autocad, la liaison entre deux étages n’est pas prise en compte. Il a donc fallu ruser et choisir une convention de description d’attribut sur les plans pour créer une sorte d’arête virtuelle (vers l’étage inférieur ou supérieur, voire les deux).
Cette stratégie a d’ailleurs permis un contrôle fin de la cohérence des données : si un point indiquant un sens ascendant était marqué un plan, il était nécessaire que son équivalent descendant soit référencé à l’étage supérieur.
Au-delà de la création initiale de ce réseau, nous nous sommes attachés à définir des règles simples qui seront appliquées par nos collègues de la DII pour tous leurs futurs plans et, plus important encore, pour la mise à jour des données existantes.

Le plus court chemin

Après ce travail de bénédictin, la deuxième phase a consisté à développer le moteur de calcul. Deux voies ont été explorées : GeoTools [4], une librairie Java GIS. Elle avait le mérite d’exister et a permis un prototypage assez rapide. Une autre voie était de créer un nouveau module PostGIS en C.
Camptocamp a choisi la deuxième option. Cette solution avait plusieurs avantages, dont une meilleure intégration à PostgreSQL/PostGIS. Pour Camptocamp, franchir ce pas impliquait aussi une contribution majeure puisque ce développement allait renforcer l’offre open source de CartoWeb [5].
Pour le calcul proprement dit, le choix s’est porté sur l’algorithme de Dijkstra[ [fr.wikipedia.org/wiki/Algorithme_de_Dijkstra ]], un outil classique de calcul du chemin le plus économique sur un graphe. Chaque attribut est multiplié par son poids et la combinaison permet de déterminer le parcours optimal. Ajoutez le critère d’une mobilité réduite par exemple (qui donne aux obstacles un poids infini) et vous orienterez ainsi différemment une personne handicapée, voire le transport d’un objet volumineux...
Pour compléter le tableau, ajoutons encore que plan.epfl.chest interfacé avec la base de données Camipro via un Web Service SOAP. Une fonctionnalité qui permet des réponses plus pertinentes pour des lieux dont les accès sont réservés (de manière permanente ou en fonction de l’horaire).

Un outil expérimental

Le résultat est là. Il n’est pas parfait et plusieurs personnes nous ont déjà signalé des parcours... surprenants. Avez-vous par exemple déjà essayé de passer par le monte-charge situé dans les locaux de la VPPL pour rejoindre le Copernic ? Le filet est percé par endroits. Il manque en particulier les espaces extérieurs : les routes, les parkings, les arrêts d’autobus ou de métro n’ont pas encore été intégrés au réseau. Ce travail est en cours.
De même, une grande partie des informations n’existent tout simplement pas : les portes dont le sésame est détenu par les seuls concierges ou les zones contrôlées par des systèmes d’accès spécifiques (les salles blanches p.ex.). Ces informations seront mises à jour de manière itérative, à partir de vos contributions et des erreurs que vous signalerez.
Maintenant, je vous propose une petite expérience : si vous ne l’avez encore jamais tenté, rendez-vous à l’adresse deplan.epfl.ch. Dans la recherche d’itinéraire, entrez votre nom (ou le nom d’un local quelconque) dans le champ Départ. Sous Arrivée, tapez Copernic. Le dernier arrivé paye la tournée...

[1] Lire le première article de Claude Philipona au sujet de l’origine du projet plan.epfl.ch : http://dit.epfl.ch/publications-spip/article.php3?id_article=36

[2] www.cartoWeb.org/

[3] Les références du travail de diplôme sont sur infoscience.epfl.ch/search.py ?recid=60103

[4] www.geotools.org/

[5] www.cartoWeb.org/contribs.html



Cherchez ...

- dans tous les Flash informatique
(entre 1986 et 2001: seulement sur les titres et auteurs)
- par mot-clé

Avertissement

Cette page est un article d'une publication de l'EPFL.
Le contenu et certains liens ne sont peut-être plus d'actualité.

Responsabilité

Les articles n'engagent que leurs auteurs, sauf ceux qui concernent de façon évidente des prestations officielles (sous la responsabilité du DIT ou d'autres entités). Toute reproduction, même partielle, n'est autorisée qu'avec l'accord de la rédaction et des auteurs.


Archives sur clé USB

Le Flash informatique ne paraîtra plus. Le dernier numéro est daté de décembre 2013.

Taguage des articles

Depuis 2010, pour aider le lecteur, les articles sont taggués:
  •   tout public
    que vous soyiez utilisateur occasionnel du PC familial, ou bien simplement propriétaire d'un iPhone, lisez l'article marqué tout public, vous y apprendrez plein de choses qui vous permettront de mieux appréhender ces technologies qui envahissent votre quotidien
  •   public averti
    l'article parle de concepts techniques, mais à la portée de toute personne intéressée par les dessous des nouvelles technologies
  •   expert
    le sujet abordé n'intéresse que peu de lecteurs, mais ceux-là seront ravis d'approfondir un thème, d'en savoir plus sur un nouveau langage.