Drone et PgRouting : utilisations et perspectives

L’objectif de cet article est de présenter une piste de réflexion sur l’utilisation de drone et PgRouting pour programmer des vols automatiques. L’idée est surtout d’associer les drones et les Systèmes d’Informations Géographiques (SIG). Ainsi, on élabore une chaîne de traitements de la prise en charge de données OpenStreetMap jusqu’à la programmation de vols automatiques. Pour commencer, on vous explique comment est apparue l’idée d’associer le drone et PgRouting. Ensuite, tous les matériels utilisés sont présentés : les données OpenStreetMap, PgRouting, le géocodage, le drone et les applications mobiles pour le télépilotage de l’aéronef. Puis, on montre comment utiliser ces différentes technologies afin de calculer les itinéraires de vols par drone.

Pour illustrer cet article, on a choisi la thématique de livraison par aéronef télépiloté. Il est évident que cette problématique requiert des moyens et des outils bien plus complexes que ceux mis en œuvre dans ce texte. La livraison par drone nécessite des ressources financières, techniques et humaines conséquentes comme le prouvent les projets Wing d’Alphabet, de Prime Air d’Amazon, etc. De plus, on ne discute pas des législations françaises sur les vols de drone. Pour cela, vous pouvez vous référer au site du Ministère de la Transition écologique et solidaire (MTES) qui présente toutes les informations sur les usages professionnels de drone.

• I. Drone et PgRountig : naissance d’une idée « farfelue »
• I.1. Création d’un business de livraison par drone
• I.2. Livraison par drone
• II. Vol automatique du drone : matériels utilisés
• II.1. Données OpenStreetMap, PgRouting / PostgreSQL et géocodage
• II.1.1. Le projet OpenStreetMap
• II.1.2. Le projet PgRouting
• II.1.3. Le géocodage
• II.2. Le drone ou aéronef télépiloté
• II.3. L’application DJI Pilot
• III. Drone et PgRouting : méthodologies pour le calcul des itinéraires et implémentation
• III.1. Import des données routières d’OpenStreetMap dans PostgreSQL
• III.2. PgRouting : calcul de l’itinéraire de livraison par drone
• III.2.1. Fonctions PgRouting Dijkstra
• III.2.2. Utilisation du Géocodage
• III.3. Import du fichier KML dans DJI Pilot
• III.3.1. Création du fichier KML
• III.3.2. DJI Pilot et KML
• IV. Discussions et perspectives sur l’utilisation du drone et PgRouting
• IV.1. Apports des outils SIG Open Sources et de PgRouting pour la livraison par drone
• IV.2. Limites contemporaines de la livraison par drone
• IV.2.1. Limites réglementaires
• IV.2.2. Limites techniques
• IV.2.3. Limites sociologiques

I. Drone et PgRouting : naissance d’une idée « farfelue »

I.1. Création d’un business de livraison par drone

En 2017, par l’initiative d’Alexandre, un très bon ami, on décide de créer un petit business de livraison de petits déjeuners. Comme les mastodontes de ce secteur d’activité, le principe de base est de réaliser des partenariats avec des restaurants. Pour notre business, il s’agit surtout de cibler des boulangeries et hôtels. Ces derniers proposent des menus publiés sur notre site internet dédié. Sur l’interface, le client saisit une adresse et par matching géographique, les fournisseurs localisés dans un rayon de quelques kilomètres apparaissent. Le client choisit alors un ou plusieurs menus et il peut ensuite passer la commande.

Alerté, le livreur récupère le menu à la boulangerie ou à l’hôtel à vélo. Ce moyen de locomotion léger et propre est important pour défendre les valeurs écologiques du procédé. Enfin, il livre le repas à l’adresse du client. Rien de très compliqué sur le principe et surtout peu d’investissement de départ est nécessaire.

I.2. Livraison par drone

En ce qui concerne le marketing, on réalise des partenariats avec des blogueurs locaux qui testent le service. Et là, comme fait la majorité des marketeurs, il faut créer un buzz dans les médias pour faire connaître le service. Alors que faire pour être relayé dans les journaux? Annoncer une polémique, montrer quelque chose d’orignal voir d’illégal. Et la lumière fût : livrer un petit déjeuner par drone! Mais comment faire pour que le drone parte de notre siège d’entreprise jusqu’au fournisseur et enfin jusqu’au client? En plus, tout le trajet doit s’effectuer en agglomération, c’est-à-dire avec des hauteurs d’obstacles très aléatoires constitués de bâti, de réseaux aériens et de végétation principalement.

Alors si on réfléchit, on pourrait s’inspirer des voies routières afin de tracer le vol du drone d’un point A à un point B. C’est déjà un principe étudié dans le Nord de la France dans le cadre d’un accord entre la région Hauts-de-France et la société Survey Copter-Airbus en juin 2019. Cette société se servira surtout des réseaux ferroviaires et fluviaux denses dans la région pour livrer des marchandises par drone autonome à partir du futur plus grand site d’e-commerce d’Europe. L’objectif est de desservir 78 millions de consommateurs dans un rayon de 300 km. Si le drone suit un maillage de différents réseaux, cela évite bien évidemment certains problèmes en cas de crash de l’appareil. Ainsi, en SIG, l’extension PgRouting de PostgreSQL permet de réaliser ce routage. Une fois l’itinéraire calculé et cartographié, on l’implémente dans l’aéronef pour paramétrer le vol automatique.

II. Vol automatique du drone : matériels utilisés

Cette section présente l’ensemble des données géographiques et les logiciels SIG utilisés. Le drone considéré ici ainsi que les logiciels de télépilotage associés proviennent du constructeur DJI. Ainsi, on réalise les tests sur le drone DJI Phantom 4.

II.1. Données OpenStreetMap, PgRouting / PostgreSQL et géocodage

II.1.1. Le projet OpenStreetMap

Le projet OpenStreetMap a pour objectif de délivrer des informations géographiques à l’échelle internationale de manière libre et gratuite. La communauté d’OSM garantit la production et la mise à jour des données dans les différentes catégories retenues. Ainsi, quiconque peut participer à l’ajout de données de son territoire après un procédé de validation. D’autre part, il est facile de se procurer et d’utiliser les données géographiques sous différents formats numériques. Plus d’informations sont disponibles sur le Wiki du projet OSM.

II.1.2. Le projet PgRouting

PgRouting implémente des fonctionnalités de routage dans le SGBD PostgreSQL associé à l’extension spatiale PostGIS. Le projet est OpenSource, développé et maintenu par une communauté dynamique. La documentation de PgRouting est disponible en ligne. On y trouve l’ensemble des explications et des références des différentes fonctions de routage de la librairie réparties selon les catégories suivantes :

• All Pairs Shortest Path, Johnson’s Algorithm
• All Pairs Shortest Path, Floyd-Warshall Algorithm
• Shortest Path A*
• Bi-directional Dijkstra Shortest Path
• Bi-directional A* Shortest Path
• Shortest Path Dijkstra
• Driving Distance
• K-Shortest Path, Multiple Alternative Paths
• K-Dijkstra, One to Many Shortest Path
• Traveling Sales Person
• Turn Restriction Shortest Path (TRSP)

II.1.3. Le géocodage

Par définition, le géocodage est la transformation d’une adresse en une coordonnée géographique avec une longitude X et une latitude Y. Pour passer de ce point géographique à une adresse, on parle de géocodage inversé. En France, Etalab met à disposition une API de géocodage en s’appuyant sur les données de la Base Adresse Nationale (BAN).

II.2. Le drone ou aéronef télépiloté

Le drone ou aéronef télépiloté est constitué au minimum des instruments suivants :

1. Les hélices ou rotors;
2. Les moteurs et contrôleurs;
3. Le compas électronique;
4. Le GPS;
5. Les gyroscopes.

Un aéronef télépiloté doit être utilisé en conformité avec les limitations associées à sa navigabilité, les exigences définies par le constructeur et dans les limites du scénario opérationnel autorisé et de la réglementation applicable. Le télépilote doit s’assurer que le vol de l’aéronef reste à l’intérieur du volume maximal défini par les limites horizontales et verticales. Les limites verticales correspondent à la position géographique définie par les coordonnées X et Y. Les limites verticales correspond à la hauteur de vol de l’appareil.

Plusieurs types de vols du drone existent :

• le vol manuel : un télépilote contrôle en temps réel la trajectoire du drone ;
• le vol automatique : le vol du drone a été programmé à priori et le télépilote n’intervient pas sur la trajectoire. Toutefois, ce dernier peut reprendre le contrôle à tout moment ;
• et, le vol autonome : le drone évolue de manière automatique sans la possibilité d’intervention d’un télépilote.

II.3. L’application DJI Pilot

Les applications mobiles DJI Pilot et DJI Go sont disponibles sur IOS et Androïd. DJI Go est une application ayant connue plusieurs versions et possède une documentation. Les deux applications permettent de paramétrer le drone (hauteur de vol, vitesse de vol maximale, etc). DJI GO possède plusieurs modes de vol dits intelligents mais pour la préparation de la mission du vol, DJI Pilot est préférable. Cette dernière permet ainsi de cartographier la mission du vol (Mission Flight) par drone avec de nombreux paramètres. Il est à noter que de nombreuses fonctionnalités de DJI Pilot ont été intégrés dans le logiciel de télépilotage utilisé pour le drone DJI Phantom 4 RTK.

III. Drone et PgRouting : méthodologies pour le calcul des itinéraires et implémentation

Dans cette section, les différentes méthodologies sont décrites pour calculer les itinéraires de vols de drone en s’appuyant sur les données du réseau routier. Ensuite, le fichier sous format KML produit est implémenté dans l’application mobile DJI Pilot programmant le vol du drone.

III.1. Import des données routières d’OpenStreetMap dans PostgreSQL

Comme évoqué précédemment, la programmation du vol du drone s’appuie sur des réseaux existants tels le réseau routier et le réseau navigable. Ici, on prend en charge les données du réseau routier français issu du projet OpenStreetMap. Plusieurs solutions s’offrent aux utilisateurs afin d’importer les données dans le SGBD PostgreSQL. Ces dernières sont mises à disposition sur plusieurs sites : GeoFrabrik, OverTurboPass, etc.

Dans un premier temps, on installe les extensions PostGIS, PgRouting et HSTORE sur PostgreSQL.

CREATE EXTENSION PostGIS;
CREATE EXTENSION PgRouting;
CREATE EXTENSION HSTORE;

Après le téléchargement de la donnée OSM compressé, le logiciel Osmconvert permet de diminuer les temps de traitement. Ensuite, l’import du fichier dans PostgreSQL est possible grâce à différents outils comme osmosis, Imposm et osm2pgrouting. Ce dernier utilitaire est le plus utilisé pour l’import des données OSM dans une base PgRouting. L’exemple de la ligne de commande suivante prend en charge le format osm afin d’importer les données OSM dans PostgreSQL:

osm2pgrouting -f [données OSM].osm -h [hôte] -p [port] -d [nom de la base de données] --schema [nom du schema] -U [utilisateur] -W [mot de passe] -c [fichier de configuration].xml

Le fichier de configuration global mapconfig.xml prend en charge les différents éléments des tags highway, cycleway, tracktype, junction correspondant respectivement aux données OSM du réseau routier, cyclable, du type de revêtement et les jonctions de types carrefours giratoires. Ici, on prend le fichier mapconfig_for_cars.xml prenant en compte seulement le réseau routier.

Le logiciel SIG QGIS nous montre ainsi le réseau linéaire pris en charge par exemple en Bretagne (figure 1).

III.2. PgRouting : calcul de l’itinéraire de livraison par drone

III.2.1. Fonctions PgRouting Dijkstra

La livraison par drone doit suivre le chemin le plus court du réseau routier. Pour cela, le calcul de l’itinéraire du point de départ au point final s’appuie sur la famille des fonctions PgRouting Dijkstra.

Dans cet article, on ne détaille ni l’algorithme pgr_dijkstra utilisé ni les fonctions SQL implémentées ci-dessous. Ces dernières sont issues du Workshop FOSS4G mettant en application de manière approfondie PgRouting (v 2.6).

La première fonction wrk_dijkstra construite retourne le chemin le plus court entre deux points en prenant en compte les id d’OSM id_osm contenus dans la table ways.

--DROP FUNCTION wrk_dijkstra(regclass, bigint, bigint);

CREATE OR REPLACE FUNCTION wrk_dijkstra(
        IN edges_subset regclass,
        IN source BIGINT,
        IN target BIGINT,
        OUT seq INTEGER,
        OUT gid BIGINT,
        OUT name TEXT,
        OUT cost FLOAT,
        OUT azimuth FLOAT,
        OUT route_readable TEXT,
        OUT route_geom geometry
    )
    RETURNS SETOF record AS
$BODY$
    WITH
    dijkstra AS (
        SELECT * FROM pgr_dijkstra(
            -- using parameters instead of specific values
            'SELECT gid AS id, * FROM ' || $1,
            (SELECT id FROM ways_vertices_pgr WHERE osm_id = $2),
            (SELECT id FROM ways_vertices_pgr WHERE osm_id = $3))
    ),
    get_geom AS (
        SELECT dijkstra.*, ways.name,
            CASE
                WHEN dijkstra.node = ways.source THEN the_geom
                ELSE ST_Reverse(the_geom)
            END AS route_geom
        FROM dijkstra JOIN ways ON (edge = gid)
        ORDER BY seq)
    SELECT
        seq,
        edge,  -- will get the name "gid"
        name,
        cost,
        degrees(ST_azimuth(ST_StartPoint(route_geom), ST_EndPoint(route_geom))) AS azimuth,
        ST_AsText(route_geom),
        route_geom
    FROM get_geom
    ORDER BY seq;
$BODY$
LANGUAGE 'sql';

La seconde fonction wrk_fromAtoB, s’appuyant sur wrk_dijkstra, prend en entrée la table ways et les coordonnées géographiques des points de début et de fin du trajet le plus court.

-- DROP FUNCTION wrk_fromAtoB(varchar, numeric, numeric, numeric, numeric);

CREATE OR REPLACE FUNCTION wrk_fromAtoB(
    IN edges_subset regclass,
    IN x1 numeric, IN y1 numeric,
    IN x2 numeric, IN y2 numeric,
    OUT seq INTEGER,
    OUT gid BIGINT,
    OUT name TEXT,
    OUT length FLOAT,
    OUT the_time FLOAT,
    OUT azimuth FLOAT,
    OUT geom geometry
)
RETURNS SETOF record AS
$BODY$
DECLARE
    final_query TEXT;
BEGIN

    final_query :=
        FORMAT( $$
            WITH
            vertices AS (
                SELECT * FROM ways_vertices_pgr
                WHERE id IN (
                    SELECT source FROM %1$I
                    UNION
                    SELECT target FROM %1$I)
            ),
            dijkstra AS (
                SELECT *
                FROM wrk_dijkstra(
                    '%1$I',
                    -- source
                    (SELECT osm_id FROM vertices
                        ORDER BY the_geom <-> ST_SetSRID(ST_Point(%2$s, %3$s), 4326) LIMIT 1),
                    -- target
                    (SELECT osm_id FROM vertices
                        ORDER BY the_geom <-> ST_SetSRID(ST_Point(%4$s, %5$s), 4326) LIMIT 1))
            )
            SELECT
                seq,
                dijkstra.gid,
                dijkstra.name,
                ways.length_m/1000.0 AS length,
                dijkstra.cost AS the_time,
                azimuth,
                route_geom AS geom
            FROM dijkstra JOIN ways USING (gid);$$,
        edges_subset, x1,y1,x2,y2); -- %1 to %5 of the FORMAT function
    RAISE notice '%', final_query;
    RETURN QUERY EXECUTE final_query;
END;
$BODY$
LANGUAGE 'plpgsql';

Par exemple, sur la figure, on retourne le chemin le plus court du réseau routier entre les points de coordonnées [longitudes;latitudes]: [1.6252165;48.0912605] et [-1.626354;48.0915774] grâce à la requête SQL suivante :

SELECT geom FROM wrk_fromAtoB( 'ways',-1.6252165,48.0912605,-1.626354,48.0915774);

La figure 2 montre un exemple de chemin le plus court calculé entre deux points sur Geometry Viewer de PostgreSQL.

III.2.2. Utilisation du Géocodage

Afin de déterminer les coordonnées géographiques du point de départ et d’arrivée, on utilise le géocodage à l’aide de l’API BAN et de l’API d’OpenLayers. Après avoir chargé les modules d’OpenLayers souhaités, les coordonnées géocodées des adresses saisies sont retournées à l’aide d’une opération asynchrone en JavaScript. Vous pouvez tester la saisie d’une adresse permettant le calcul d’un cercle d’un rayon de 100 km lors du déconfinement en France. On y reviendra dans un prochain tutoriel ReactJS / OpenLayers.

III.3. Import du fichier KML dans DJI Pilot

L’application DJI Pilot permet d’importer des fichiers KML contenant les coordonnées géographiques du chemin emprunté par le drone.

III.3.1. Création du fichier KML

Un fichier KML (Keyhole Markup Language) est un vecteur pouvant être créé sur différents logiciels SIG comme QGIS, Google Earth, etc. La structure du fichier KML se base sur du XML :

<?xml version="1.0" encoding="UTF-8"?><kml xmlns="http://www.opengis.net/kml/2.2" xmlns:gx="http://www.google.com/kml/ext/2.2" xmlns:kml="http://www.opengis.net/kml/2.2" xmlns:atom="http://www.w3.org/2005/Atom">
<Document>	
       <name>...</name>	
       <Placemark>          
         <coordinates>            
           .............           
         </coordinates>         
       </Placemark>
</Document>

L’objectif est de générer ce fichier KML de manière automatique en intégrant les coordonnées de l’itinéraire calculé dans les balises <coordinates> . Pour cela, la géométrie retourné par la fonction wrk_fromAtoB est transformée en format KML grâce à la fonction PostGIS ST_AsKML. On intègre également une troisième dimension Z aux coordonnées géographiques formant la ligne par la fonction PostGIS ST_Force3DZ. Par exemple, on obtient les coordonnées géographiques en 3D du chemin le plus court entre deux points par :

SELECT ST_AsKML(ST_Force3DZ(geom)) FROM wrk_fromAtoB( 'ways',-1.6252165,48.0912605,-1.626354,48.0915774)

Enfin, le résultat de cette requête est incorporé de manière automatique dans le fichier KML.

III.3.2. DJI Pilot et KML

Dans DJI Pilot, après avoir sélectionné Mission Flight (figure 3), on peut créer un vol ou importer un fichier KML (figure 4).

Pour importer le fichier KML, il suffit de placer le fichier sur la carte SD du mobile et de le charger dans l’application DJ Pilot depuis le chemin choisi.

Puis, on choisit le tracé Waypoint correspond à une géométrie linéaire. Enfin, le tracé de la mission de vol automatique est visible sur la cartographie de l’application comme le montre la figure 5 :

Enfin, il ne reste plus qu’à s’assurer des hauteurs du vol… Et c’est parti pour le vol automatique du drone!

IV. Discussions et perspectives sur l’utilisation du drone et PgRouting

La démonstration présentée dans cet article possède des intérêts, notamment pour les dronistes et les géomaticiens mais aussi quelques limites.

IV.1. Apports des outils SIG Open Sources et de PgRouting pour la livraison par drone

De manière générale, les informations géographiques sont relativement présentes dans l’utilisation des drones. Dans cet article, on a démontré l’apport de la géomatique et des outils SIG Open Sources comme PgRouting pour calculer l’itinéraire de vols automatiques de drone. PgRouting a toute sa place pour aider à la conception d’un code aérien et la circulation automatisée des drones.

IV.2. Limites contemporaines de la livraison par drone

A l’opposé, on doit souligner que la livraison par drone rencontre encore de multiples limites d’ordre réglementaire, technique et sociologique.

IV.2.1. Limites réglementaires du vol de drone

D’un point de vue réglementaire, la France est l’un des pays les plus réglementés en ce qui concerne l’usage des drones professionnels -et de loisir-. Si bien que sa législation fait office de référence pour les textes européens dans le domaine. A travers l’exemple de Survey Copter-Airbus cité précédemment, on voit bien qu’obtenir l’aval de toutes les administrations gouvernementales françaises ayant le droit de regard sur les activités des aéronefs demande de nombreuses ressources. Cette situation est discutable lorsqu’on se rend compte que la livraison par drone prend son envol aux Etats-Unis, en Australie, en Finlande. En effet, ne doit-on pas laisser l’innovation se réguler d’elle-même et non l’orienter par des lois restrictives qui s’empilent les unes après les autres? Cette problématique de l’intervention de l’état sur le secteur privé est d’autant plus soumis à débat face aux enjeux techniques et sociologiques de la livraison par drone.

IV.2.2. Limites techniques

Les limites techniques de livraison par drone sont encore nombreuses. L’autonomie des batteries, le poids des colis livrés par rapport aux capacités de l’aéronef sont encore limitées à ce jour. Aussi, contrairement au système routier, il n’existe pas de réseau pour drone et encore moins un code aérien approfondi excepté quelques règles de priorité. En outre, pour des livraisons à grande échelle, une logistique importante serait mise en place avec des entrepôts de stockage et des « dronestations » en référence aux hélistations. Bref, toutes ces prérogatives sont limitées à quelques grands acteurs du marché comme Amazon par exemple.

En outre, les outils SIG pris en charge dans cet article et le drone utilisé ne permettent qu’un chaîne de traitements de l’information géographique semi-automatisés. En effet, la programmation des vols automatiques peut se faire sans intervention humaine. Puis, l’intégration de l’itinéraire du vol dans l’aéronef ainsi que son allumage et la recharge des batteries sont réalisés par l’Homme. Toutefois, cette limite dans la chaîne de traitements n’existe pas pour divers drones.

IV.2.3. Limites sociologiques

Enfin, les limites sociologiques sont évidentes. En effet, la population est-elle prête à se faire livrer son pain ou ses médicaments par drone? Hier, certainement que la majorité des personnes auraient rejeté cette idée pour des motifs de relations humaines, de robotisation et de connectivité de plus en plus prédominante. D’ailleurs, la problématique des pollutions sonores, visuelles et environnementales comme Starlink, la flotte de satellites du milliardaire Elon Musk (R. Lehoucq, F. Graner, 2020) est aussi à envisager. Mais, aujourd’hui, la crise du Coronavirus-Covid-19 remet beaucoup de certitudes et de valeurs sociologiques en question notamment avec une distanciation sociale imposée à ce stade. Dans un avenir proche, cette dernière sera adoptée de manière inconsciente par nous tous. En outre, la connectivité et la robotisation prendront une part toujours plus importante dans la vie des sociétés.

En conclusion, l’utilisation des drones pour la livraison de marchandises est bien lancée. Et l’apport des outils SIG dans ce domaine est prépondérant.

Si vous êtes intéressés par des formations Drone et SIG, de l’apprentissage du télépilotage pour l’acquisition de données aériennes jusqu’aux traitements des données raster sur des logiciels libres (QGIS, Grass, Python et PostgreSQL) et leur valorisation sur un WebSIG, n’hésitez pas à nous contacter : contact@geomatick.com .

D’autres articles sur le drone et SIG sont en préparation, vous pouvez vous abonner sur le site pour rester en veille – on ne vous polluera pas d’emails – .