Algorithmes pour les chemins orthogonaux non croisés avec obstacles

Ce document est une traduction de l’article de référence « Non-crossing Rectilinear Shortest Minimum Bend Paths in the Presence of Rectilinear Obstacles » sur la méthode de calcul des chemins orthogonaux non croisés à nombre minimal de virages dans des grilles 2D avec obstacles. Il a été publié dans « Journal of Telecommunications and Information Technology » en 2018. Je l’ai traduit car il m’a aidé dans mes recherches. Je l’ai expérimenté et je l’utilise dans mes projets. Je me suis permis cependant d’augmenter l’article par des explications, des exemples supplémentaires à des fins pédagogiques pour que chacun puisse en tirer parti. Il y a en effet de nombreuses abréviations et sigles qui paraissent ésotériques dans l’article et sont perturbants pour le lecteur qui n’est pas accoutumé aux habitudes littérales de l’américain et de notations spécifiques de langages de programmation. Vous trouverez donc un petit glossaire à la fin du document.

L’article présente un nouvel algorithme pour tracer les chemins les plus courts, non croisés et rectilignes (orientation angulaire de 90°) dans un graphique de grille dimensionnelle. Les chemins les plus courts sont déterminés en veillant à ce qu’ils ne se croisent pas et contournent les obstacles présents. Ces chemins les plus courts sont appliqués dans la conception de nombreuses applications… Lorsque plus d’un passage entre la source et la destination est possible, l’algorithme proposé sélectionne le chemin qui a le moins de virages le long du chemin. Je ne peux développer à la suite de la présentation de l’auteur dans le présent document, les adaptations pratiques en programmation que j’ai faites dans certains de mes projets. Ces dernières feront l’objet de publications à venir.

Les obstacles sont contournés par les chemins solutions de l’algorithme de Floyd-Warshall. Cependant l’auteur présente ici une version améliorée qui calcule toutes les paires des chemins possibles pour identifier les chemins les plus courts qui ne se croisent pas. Pour obtenir ce minimum de courbes (changements de direction) dans un chemin, l’article propose une modification à l’algorithme Floyd-Warshall, qui est la principale contribution de l’auteur présentée ici.

Notes typographiques :
- Les références entre crochets « [xx] » dans le texte, renvoient aux références de l’auteur mises à la fin de ce document. Certains articles cependant ne sont accessibles qu’avec un abonnement ou via une institution académique, mais les liens sont bien fonctionnels. Les chiffres entre parenthèses « (xx) », sont quant à eux, des références d’équations. - Les premières occurrences des mots en Gras Violet renvoient au glossaire.

Le problème des chemins les plus courts (MBSP signifie « Minimum Bend Shortest Path » qui se traduit par « Chemin le plus court avec un minimum de virages ») qui ne se croisent pas fait l’objet de plusieurs recherches et algorithmes décrits dans la littérature [1]-[3]. En général, les trajets les plus courts réduisent le temps et le coût de la communication. Les voies non croisées sont essentielles dans les tracés de puce VLSI, les cartes de circuit imprimé, le routage, les commandes de mouvements robotisés [4],[5], etc.

Les obstacles sont naturels et communs dans les graphiques représentant des scénarios géométriques ou géographiques. Dans la disposition d’un circuit imprimé, les composants constituent des obstacles pour le routage des chemins. De même, dans les plans de transport, les obstacles et les zones interdites sont très fréquents. Dans une telle situation, il est nécessaire de trouver des chemins optimaux qui évitent les obstacles et les contournent afin d’atteindre la destination.

Plusieurs algorithmes ont été proposés pour déterminer les chemins les plus courts en présence d’obstacles, lesquels sont modélisés sous forme de rectangles, de polygones rectilignes ou de polygones généraux [6]-[11]. Dans ce document, une nouvelle méthode pour contourner les obstacles sans les toucher est présentée. Les courbures ou les angles sont inévitables dans les graphiques qui ont des contraintes physiques ou lorsqu’un lien direct échoue. La présence de virages le long des chemins réduit la mobilité des objets et augmente la consommation d’énergie. En mise en œuvre physique, le coût de ces chemins est également plus élevé.

Par conséquent, l’auteur vise à assurer un minimum de courbures. Considérons un scénario où plusieurs chemins les plus courts de longueur égale existent entre une paire de nœuds dans un graphe rectiligne. Parmi ces chemins les plus courts et de même longueur, le chemin qui a le plus petit nombre de courbures est appelé « chemin rectiligne le plus court avec un minimum de virages » MBSP (« Minimum Bend Shortest Path ») [6]. D’abord, nous devons trouver le MBSP entre une paire source-destination donnée. S’il existe plusieurs MBSP pour cette paire, nous prenons l’un d’eux. L’objectif est de trouver des MBSP entre K paires source-destination distinctes.

Cela donne K MBSPs distincts, un pour chaque paire source-destination. De plus, les chemins doivent être distincts, disjoints et non croisés. Dans la méthode proposée, chaque paire source-destination attribue un seul chemin optimal. Nous avons K tels chemins correspondant à K telles paires. Ce n’est pas la même chose que K-chemins les plus courts pour une seule paire source-destination. Lorsque des obstacles sont présents dans le graphique, les chemins ne devraient pas toucher les obstacles, mais les éviter et les contourner. La région donnée où les chemins doivent être déterminés est discrétisée par une grille carrée uniforme de taille appropriée. Ensuite, les chemins contraints sont déterminés sur le graphe non dirigé en utilisant les algorithmes bien connus de Floyd-Warshall de la théorie des graphes. Même si les méthodes d’optimisation multicritère [12],[13] peuvent être utilisées pour résoudre ce problème MBSP, elles sont plus complexes et rencontrent des difficultés à déterminer les meilleurs poids pour combiner plusieurs critères en un seul. Les pondérations dépendent de la taille et de la disposition du graphique. L’article propose une comparaison entre la méthode proposée et la méthode d’optimisation bi-critère.

La région géométrique considérée est représentée par une grille à mailles carrées qui couvre toute la région comme c’est montré Fig. 1. Un graphe planaire G (V,E) est construit :

En anglais, « A planar graph G(V,E) » signifie un graphe planaire, c’est-à-dire un graphe qui peut être dessiné sur un plan sans que ses arêtes se croisent.

Les variables V et E représentent respectivement les vertices (sommets) et les edges (arêtes) du graphe. V est l’ensemble des points ou nœuds du graphe, tandis que E est l’ensemble des lignes ou connexions entre ces points. G(V,E) désigne un graphe qui peut être représenté sur un plan sans que ses arêtes se croisent.

Sur le schéma ci-dessus de la grille exemple, la largeur en nombre de points est W = 10 et la hauteur en termes de points de la grille est H = 8. Les points de la grille sont les sommets (nœuds) du graphique et les lignes de la grille sont les arêtes du graphique. Ainsi, le nombre total de sommets (points de la grille) représenté par n est n = W x H. Le total nombre de liens (chemins théoriques) serait donc nL = (W-1) x H + (H-1) x W.

III-A. NUMÉROTATION DES NŒUDS▲

III-B. CONNECTIVITÉ DES NŒUDS ET POIDS DES ARÊTES▲

III-C. MATRICE DE CONTIGUÏTÉ▲

La matrice d’adjacence (connectivité) du graphe est représentée par A. La taille de la matrice A est n x n. L’élément A(i, j) de la matrice d’adjacence donne le poids du bord (lien) entre le nœud i et le nœud j. Les éléments diagonaux de A sont pris comme infini (∞), pour éviter les boucles automatiques sur elles-mêmes. Le graphique est un graphe non orienté. Par conséquent, A(i, j) = A(j, i) et A est symétrique. Une arête peut permettre la direction dans les deux sens. Lorsque i et j sont connectés A(i, j) = 1, sinon, A(i, j) = ∞.

Le nombre de 1s (** voir signification de 1s plus bas) dans la Ligne i de A est l’ensemble des valeurs 1 attribuées à chaque arête qui part du nœud i vers un voisin. Le nombre total de 1 sur cette ligne correspond donc au nombre d’arêtes sortantes de i (son degré sortant). Pour la Colonne i – chaque 1 de la colonne signale une arête qui arrive sur le nœud i ; leur total donne le nombre d’arêtes entrantes (son degré entrant).

Comme le graphe est non orienté et 4-connecté (chaque nœud intérieur est relié à ses quatre voisins nord, sud, est et ouest), le nombre maximal de 1 dans une même ligne ou colonne est 4.

** "1s" signifie simplement "des uns" (le chiffre 1, au pluriel) dans une matrice composée de 0 et de 1. C’est une abréviation anglaise pour "ones " (uns). Exemple : Si la ligne 3 (nœud 3) de la matrice est [∞ 1 ∞ ∞ 1 ∞], il y a 2 « 1 », l’article écrit "1s" (2 uns), donc le nœud 3 a 2 voisins directs.

• A est la matrice d’adjacence du graphe (ici, la grille).
• A (i, j) = 1 signifie qu’il existe une arête (un lien direct) entre le nœud i et le nœud j.
• Ligne i de A : chaque « 1 » sur cette ligne indique un voisin accessible directement depuis le nœud i (donc une arête qui « part » de i).
• Colonne i de A : chaque « 1 » sur cette colonne indique un voisin qui peut accéder directement à i (donc une arête qui « arrive » sur i).

Dans un graphe non orienté (comme la grille de l’article), chaque arête est comptée dans les deux sens, donc le nombre de 1 sur la ligne i ou sur la colonne i donne le degré du nœud : le nombre de voisins immédiats. Cela signifie que si les nœuds i et j sont connectés, on peut aller de i vers j ET de j vers 1 (A(i,j) = A(j,i)).

Puisque notre graphe est un graphe de grille à 4 connectivités, le nombre maximum de 1s dans une ligne ou une colonne est 4. Par exemple, considérez une grille de 3 x 3 graphe de neuf nœuds représentés par G, comme suit :

La matrice de contiguïté (adjacency) A correspondante sera :

En général, dans A, les rangées, ainsi que les colonnes des nœuds d’angle, ont 2 ones (uns), celles des nœuds de bordure non-angulaires ont 3 ones et celles des nœuds intérieurs ont 4 ones. Ainsi, les nœuds sont caractérisés par une connectivité directe, immédiatement le long des axes nord-sud et est-ouest. Les nœuds n’ont pas de connexion diagonale immédiate. C’est une exigence importante pour assurer la propriété de non-croisement des chemins les plus courts. En raison de cette connectivité à 4, tous les chemins connectés du nœud source au nœud de destination doivent être rectilignes.

III-D. OBJECTIF▲

Un chemin simple du nœud source s à la destination du nœud t est une série d’arêtes connectées de s à t passant par des nœuds intermédiaires sans boucles. Par la suite, pour des raisons de brièveté et de commodité, nous désignons le(s) chemin(s). Soit la séquence des nœuds intermédiaires le long d’un chemin spécifique de s à t, v1,v2, ...,vm. Ensuite, le chemin entier incluant s et t est représenté par P(s, t), tel que :

P(s, t) = [ s, v1, v2,…, vm, t] (1)

P(s,t) est un tableau de nœuds. Avec m nœuds intermédiaires, la taille du tableau est m + 2, qui est le même que le nombre de nœuds dans P(s, t). La longueur du chemin est la somme des poids des arêtes le long du chemin de s à t. D’après l’Équation (1), on observe que le nombre d’arêtes connectant s à t est m+1, soit un de moins que la taille du tableau P(s, t).

Dans ce cas, les poids de toutes les arêtes de connexion sont de 1. Par conséquent, le poids total du chemin est m+1 lui-même. Ce poids total est aussi appelé longueur du chemin. Lorsque cette longueur est courte, le coût de déplacement associé est également réduit.

IV-A. CHEMIN LE PLUS COURT▲

IV-B. PROPRIÉTÉ RECTILIGNE DES CHEMINS▲

IV-C. PROPRIÉTÉ DE NON-CROISEMENT DES CHEMINS▲

IV-D. REPRÉSENTATION DES OBSTACLES DANS LE GRAPHIQUE▲

Les obstacles correspondent aux zones du graphe que les chemins doivent éviter. Les chemins ne doivent pas entrer en contact avec ces obstacles et doivent les contourner si nécessaire pour atteindre la destination. Dans ce graphe en grille, les limites des obstacles sont définies par des points de la grille (nœuds du graphe), comme illustré dans la Fig. 3. Étant donné que les contours des obstacles sont représentés par les points d’une grille carrée, ces obstacles forment des polygones rectilignes. Ils peuvent également prendre la forme de polylignes, comme montré par la ligne dans la Fig. 3. Certains points de la grille peuvent aussi être spécifiés comme obstacles. Dans ce cas, tous les points le long de la ligne et les points isolés sont exclus ou rendus inaccessibles lors de la recherche des chemins les plus courts.

IV-D-1. Exclusion (ou marquage) d’un nœud spécifique▲

L’exclusion d’un nœud spécifique se fait en attribuant aux poids (distances) de toutes les arêtes incidentes à ce nœud la valeur infinie. Ainsi, les arêtes entrant ou sortant de ce nœud auront pour poids ∞ (infini). Par conséquent, l’algorithme de plus court chemin exclura ce nœud, car, s’il était inclus, la longueur totale (le poids) deviendrait ∞. Soit J le nœud à exclure, où J ∈ {1, ..., n}. Alors, les poids de toutes les arêtes sortant de J sont donnés par les éléments de la ligne J de la matrice d’adjacence A. De même, les poids des arêtes entrant dans J sont donnés par les éléments de la colonne J de A. Par conséquent, les éléments de la ligne J et de la colonne J doivent être mis à ∞. Avant de modifier ces éléments, la matrice A est sauvegardée dans une matrice temporaire « Atemp », qui pourra être utilisée pour restaurer J comme expliqué plus loin. Ainsi, l’opération d’exclusion s’effectue comme suit :

Atemp = A ; (2)

A(J, :) = ∞ ; (3)

Ici, la notation deux-points (:) est utilisée pour représenter tous les éléments de la ligne J. De même, les poids des arêtes entrant dans J sont mis à ∞ comme suit :

A(:, J) = ∞ ; (4)

Ici, A(:, J) représente tous les éléments de la colonne J. Ainsi, l’utilisation des équations (3) et (4) modifie la matrice d’adjacence A de sorte que le nœud J est exclu ou marqué lors de la recherche du plus court chemin. Les nœuds appartenant aux obstacles sont marqués de façon permanente. Mais dans notre méthode, certains nœuds sont marqués temporairement lors de l’itération en cours, pour être restaurés lors des itérations suivantes, comme cela sera expliqué plus loin.

IV-D-2. Inclusion ou réintégration d’un nœud précédemment exclu▲

L’inclusion ou la réintégration du nœud J, qui avait été précédemment exclu, se fait en restaurant les éléments de la ligne J et de la colonne J à partir de la matrice Atemp, selon :

A(J, :) = Atemp(J, :) ; (5)

A(:, J) = Atemp(:, J) ; (6)

IV-E. K PLUS COURTS CHEMINS NOEUD-DISJOINTS▲

IV-F. VIRAGES (BENDS) DANS UN CHEMIN▲

Considérons un chemin P(i,j) allant de la source i à la destination j. Soit k un nœud intermédiaire situé sur ce chemin, comme illustré à la Fig. 4. Le symbole k (en minuscule) est utilisé pour désigner les nœuds intermédiaires dans l’algorithme de Floyd-Warshall. Ce k est différent du K majuscule qui représente le nombre de plus courts chemins recherchés.

Maintenant, P(i,k) et P(k,j) sont les deux segments du chemin P(i,j) reliés au niveau du nœud k. Ces deux segments peuvent être perpendiculaires, comme dans la Fig. 4a, ou colinéaires (sans virage), comme dans la Fig. 4b.

IV-F-1. Vérification de l’existence d’un virage en k▲

Pour qu’il y ait un virage dans un chemin, il faut qu’un des segments soit horizontal et l’autre vertical, et inversement. Comme expliqué précédemment, la condition pour que le segment P(i,k) soit horizontal est que la différence des indices de nœuds ∣i−k∣ soit supérieure ou égale à H (la hauteur du graphe). C’est-à-dire, la valeur absolue ∣i−k∣ ≥ H. La condition pour que le segment P(k,j) soit vertical est ∣k−j∣ < H. Ces deux conditions peuvent s’exprimer ainsi :

Abs(i−k) ≥ H si P(i,k) est horizontal (7)

Abs(k−j) < H si P(k,j) est vertical

La contrainte (7) donne la condition pour que P(i,k) et P(k,j) soient perpendiculaires. Ils peuvent aussi être perpendiculaires lorsque P(i,k) est vertical et P(k,j) est horizontal. Cette condition s’écrit :

Abs(i−k) < H si P(i,k) est vertical (8)

Abs(k−j) ≥ H si P(k,j) est horizontal

Si l’une ou l’autre des contraintes (7) ou (8) est vérifiée, alors P(i,k) et P(k,j) sont perpendiculaires. Les contraintes (7) et (8) sont combinées par un OU logique, et la contrainte logique combinée s’écrit :

G= [ (abs(i−k) ≥ H) ET (abs(k−j) < H) ] OU [ (abs(i−k) < H) ET (abs(k−j) ≥ H ) ] (9)

G est une variable logique. Les segments P(i,k) et P(k,j) sont perpendiculaires si G, donné par l’équation (9), est vraie, sinon ils sont colinéaires. Dans la Fig. 4, G = vrai pour le chemin de la Fig. 4a et G = faux pour celui de la Fig. 4b.

La principale contribution de cet article est la modification de l’algorithme de Floyd-Warshall pour les plus courts chemins entre toutes les paires, afin de prendre en compte les virages à 90° (angles) le long des chemins.

V-A. PRINCIPE DE BASE▲

Considérons deux chemins différents P(s,a,t) et Q(s,b,c,d,e,f,t) allant de la source s à la destination t, comme illustré à la Fig. 5. Ici, P(s,a,t) comporte un virage en a, tandis que Q(s,b,c,d,e,f,t) en comporte cinq, respectivement en b,c,d,e,f.

Dans le graphe en grille carrée de la Fig. 5, chaque arête a un poids de 1 et les chemins sont rectilignes. Par conséquent, les longueurs des deux chemins sont identiques et valent 8, même si le nombre de virages diffère pour chaque chemin. Dans ce cas, l’algorithme de plus court chemin peut choisir indifféremment le chemin P ou le chemin Q, avec la même préférence.

Mais notre objectif est de sélectionner P plutôt que Q, car P présente un nombre inférieur de virages. Pour atteindre cet objectif, on introduit des poids de virage en plus des poids des arêtes.

V-A-1. Poids de virage▲

On attribue un poids très faible (comparé au poids d’une arête) ε à chaque virage (ou angle). Ainsi, le poids de virage est représenté par ε. Désormais, lors du calcul de la longueur totale d’un chemin, on additionne à la fois les poids des arêtes et les poids des virages. Cette longueur totale est appelée longueur augmentée du chemin (augmented length). Un poids de virage très faible est choisi, de sorte que, lors de la comparaison de deux chemins ayant des longueurs d’arêtes totales différentes, ce poids n’ait pas d’influence significative. En revanche, lors de la comparaison de deux chemins de même longueur totale d’arêtes, les poids de virage jouent un rôle décisif.

V-A-2. Sélection du poids de virage ε▲

Soit le nombre maximal possible estimé de virages (angles) le long d’un chemin long dans le graphe, noté mnb. Alors, le poids total des virages serait mnb × ε. Cette valeur doit être inférieure au poids d’un saut (hop) unique, afin que l’ajout du poids des virages n’affecte pas les poids relatifs des chemins comparés.

Par conséquent, ε doit être choisi de sorte que : mnb × ε < 1.

C’est-à-dire, choisir :

Ainsi, ε dépend de la taille et de la disposition du graphe.

V-A-3. Longueur augmentée du chemin▲

La longueur totale d’un chemin prenant en compte à la fois les poids des arêtes et les poids des virages est définie comme la longueur augmentée du chemin APL (Augmented Path Length). Ainsi, pour un chemin donné :

APL = « somme des poids des arêtes le long du chemin » + « somme des poids des virages le long du chemin ».

Par conséquent, un chemin rectiligne avec un nombre plus faible de virages aura une APL plus faible. Par exemple, dans la Fig. 5, l’APL du chemin P(s, a, t) est 8 + ε, car il possède un virage, tandis que celle du chemin Q(s, b, c, d, e, f, t) est 8 + 5.ε, car il possède 5 virages.

VI-A. Algorithme 1 : FW toutes les paires de chemin le plus court (Floyd Warshall All Pair Shortest Path).▲

VI-B. ALGORITHME DE FLOYD-WARSHALL AVEC POIDS DE VIRAGE▲

L’algorithme de Floyd-Warshall modifié est donné sous la forme de l’Algorithme 1. En entrée, il prend la matrice d’adjacence A, la hauteur du graphe H, le nombre de nœuds n et la valeur du poids de virage ε. En sortie, il fournit la matrice D des longueurs (distances) des plus courts chemins et la matrice Next. L’Algorithme 1 est nommé « Floyd-Warshall All Pair Shortest Path » (FWAPSP1) et il est écrit sous forme de fonction.

La matrice D fournit les chemins connectés de longueur augmentée minimale (APL) entre toutes les paires de nœuds. Dans l’Algorithme 1, on observe que la mise à jour de D[i][j] et Next[i][j] (étapes 8a et 8b) intervient avant l’ajout du poids de virage ε à D[i][j]. Par conséquent, les matrices D et Next ne reflètent pas complètement et fidèlement la connectivité globale des chemins en tenant compte des longueurs augmentées (APL). Ainsi, il est nécessaire de recalculer de nouvelles matrices D et Next, cette fois en se basant sur les valeurs de D[i][j] plutôt que sur celles de A[i][j]. Même si, dans la suite, la matrice Next calculée à partir de FWAPSP1 n’est pas utilisée directement, elle est conservée par formalité. Le recalcul des matrices D et Next est réalisé dans l’Algorithme 2. En entrée, il prend la matrice de connectivité D, la hauteur du graphe H et n. En sortie, il fournit la matrice F des longueurs minimales mises à jour et la matrice Next.

La vérification de l’existence d’un virage sur le chemin en k, c’est-à-dire la recherche d’un nœud intermédiaire entre i et j, est plus simple dans l’algorithme de Floyd-Warshall que dans celui de Dijkstra, car les deux termes du membre droit de l’étape 8a (mise à jour pour la minimisation) de FWAPSP1 ou FWAPSP2 correspondent à l’addition de deux sous-chemins P(i, k) et P(k, j). Ainsi, le terme de contrainte G, comme donné par l’équation (9), peut être facilement construit, ce qui n’est pas le cas avec l’algorithme de Dijkstra.

VI-C. ALGORITHME PRINCIPAL▲

L’objectif est de déterminer K chemins rectilignes, non croisés, les plus courts et avec un nombre minimal de virages (RNMBP) en présence d’obstacles rectilignes. L’algorithme principal utilise les Algorithmes 1 et 2 pour mettre en œuvre le RNMBP. Initialement, les obstacles donnés sont marqués dans la matrice d’adjacence A.

VI-C-1. Ordre de traitement▲

Dans un graphe, un chemin plus long crée plus d’obstacles pour les chemins suivants qu’un chemin plus court. Considérons l’exemple de deux chemins illustrés à la Fig. 6.

La ligne la plus longue relie les nœuds 3 à 38 et la plus courte relie les nœuds 24 à 22. Si la ligne la plus longue est tracée en premier, comme dans la Fig. 6a, elle couvre tout le graphe horizontalement. Par conséquent, la seconde ligne, plus courte, ne peut pas être tracée sans croiser la première. Ainsi, la propriété de non-croisement ne peut pas être satisfaite. En revanche, si la ligne la plus courte est tracée en premier, l’obstacle créé est petit et la seconde ligne, plus longue, peut être tracée en respectant la propriété de non-croisement, comme montré en Fig. 6b.

Par conséquent, parmi les K plus courts chemins à déterminer, on les traite dans l’ordre croissant de leur longueur. Initialement, les longueurs minimales de tous les K chemins sont déterminées en tenant compte de la propriété de non-croisement (chemins nœud-disjoints). Ensuite, les paires (s, t) correspondantes sont triées par ordre croissant de leur longueur. Puis, la liste triée des paires (s, t) est traitée l’une après l’autre, comme décrit dans la sous-section III.E.

Ainsi, P(s_i, t_i) pour i = 1 à K donne les K plus courts chemins non croisés avec un nombre minimal de virages. Puisque l’algorithme RNMB utilise l’algorithme de Floyd-Warshall modifié, la complexité temporelle est O(n³). La fonction de reconstruction du chemin a une complexité de O(n).

VI-D. RÉSULTATS EXPÉRIMENTAUX ▲

Plusieurs exemples sont résolus en utilisant l’algorithme RNMBP. En raison du manque de place, tous les résultats ne sont pas présentés.

Exemple 1. Ici, W = 17, H = 13 et K = 7.

Le nombre total de nœuds est n = 17 × 13 = 221 et ε = 0,001, ce qui correspond à mnb = 1000. L’ensemble des paires (s-t) est le suivant :

(s-t) = { (78-187), (189-56), (127-152), (195-18), (82-25), (154-138), (1-100) }.

Cet exemple ne comporte pas d’obstacles.

Les plus courts chemins sont trouvés en utilisant RNMBP. Les 7 chemins non croisés sont illustrés à la Fig. 7. Les chemins complets et leurs longueurs sont donnés dans le Tableau 1.

Exemple 2. Il s’agit d’un exemple avec obstacles rectilignes. Ici, W = 17, H = 13 et K = 2. Le nombre total de nœuds est n = 17 × 13 = 221 et ε = 0,001. L’ensemble des paires (s-t) est :

(s-t) = { (1-73), (164-196) }.

Les deux plus courts chemins évitant les obstacles sont trouvés en utilisant RNMBP et sont présentés à la Fig. 8.

Dans la Fig. 8, les chemins ne touchent pas les obstacles. L’algorithme RNMBP peut être modifié de telle façon que les chemins puissent toucher les bords des obstacles, mais sans les traverser.

Dans l’algorithme RNMBP proposé, la minimisation du nombre de virages ainsi que la longueur d’un chemin sont réalisées simultanément à l’aide de la version modifiée et bien connue de l’algorithme de Floyd-Warshall. À l’inverse, dans [6], les auteurs déterminent d’abord le plus court chemin en escalier, puis utilisent la méthode « push-and-drag » (pousser et tirer) pour réduire le nombre de virages. L’algorithme décrit dans [6] est relativement plus complexe que la méthode présentée ici, dans laquelle il n’est pas nécessaire d’effectuer des opérations de poussée ou de traction.

Dans l’algorithme proposé, la gestion des obstacles se fait simplement en marquant (excluant) les nœuds de frontière correspondants. Dans [6], un graphe supplémentaire appelé « graphe de frontière » est créé, ce qui augmente inutilement la complexité. Dans [7], des graphes de pistes (« track graphs ») sont construits pour gérer les obstacles. Dans [8], des points induits et plusieurs chemins sont générés avant d’obtenir le chemin final. Dans [9], les points extrêmes et les arêtes des obstacles sont d’abord déterminés. Dans ce cas, un traitement supplémentaire des obstacles n’est pas nécessaire. Dans l’algorithme de Lee [10],[10 autre], la propagation de front d’onde est utilisée dans tout le graphe jusqu’à atteindre le nœud cible, ce qui est un processus fastidieux. Dans [11] un graphe de visibilité est créé pour gérer les obstacles. Ici, il n’est pas nécessaire de créer des graphes supplémentaires.

Dans l’étape suivante, une comparaison de la complexité temporelle avec l’optimisation bi-objectif est réalisée. Considérons un exemple où K = 7 et ε = 0,001. La largeur W = 10 et la hauteur H varie de 20 à 60 par pas de 5. Ainsi, n = W × H varie de 200 à 500 par pas de 50. Le problème est résolu à la fois par la méthode d’optimisation bi-objectif (BiOO) [13] et par RNMBP. La longueur du chemin et le nombre de virages le long du chemin sont exprimés par les fonctions L(x) et B(x), respectivement, où x est le vecteur binaire de décision [13]. La fonction objectif scalarisée F(x) est définie comme :

F(x) = λ ⋅ L(x) + (1−λ) ⋅ B(x) F(x) (11)

λ est fixé à 0,5 pour donner le même poids aux deux critères. La BiOO (minimisation de F(x)) est réalisée par programmation entière binaire. Le temps nécessaire pour BiOO ainsi que pour RNMBP, pour différentes valeurs de n (nombre total de nœuds dans le graphe), est présenté à la Fig. 9.

D’après la Fig. 9, on constate que la méthode RNMBP nécessite beaucoup moins de temps que la méthode BiOO. Bien entendu, les temps mesurés dépendent de la machine utilisée et ne sont donc que relatifs.

Un nouvel algorithme est présenté pour déterminer K plus courts chemins non croisés et à nombre minimal de virages en présence d’obstacles, dans un graphe en grille carrée. Une technique simple et originale est adoptée pour minimiser le nombre de virages dans le plus court chemin en introduisant des poids de virage et des longueurs de chemin augmentées dans l’algorithme de Floyd-Warshall modifié. Les obstacles et la contrainte de non-croisement sont gérés en excluant les nœuds correspondants. Notre algorithme RNMBP a une complexité temporelle de O(n³) et est simple à mettre en œuvre. Malgré cela, son temps d’exécution est nettement inférieur à celui de la méthode BiOO.

Établi pour la compréhension et traduction des abréviations et sigles anglo-saxons présents dans l’article mais aussi dans la littérature spécialisée qui traite des recherches des chemins les plus courts. Je les ai accompagnés normalement dans le texte d’exemples contextuels lorsqu’ils sont utilisés dans l’article ci-dessus.

APL (Augmented Path Length)

C’est la longueur totale intégrant les poids des arêtes et des virages. Par exemple un chemin avec 3 virages a une APL = longueur + 3ε, où ε = 0,001. Cela permet de prioriser les chemins avec moins de virages quand les longueurs sont égales.

BiOO (Bi-Objective Optimization)

C’est une méthode d’optimisation combinant deux critères (longueur et virages).

Par exemple 𝐹(𝑥)=0.5 .𝐿(𝑥)+0.5 .𝐵(𝑥) compare RNMBP et BiOO. RNMBP surpasse BiOO en temps d’exécution pour n > 300. n représente le nombre total de nœuds dans le graphe rectiligne.

Comparaisons algorithmiques

Dijkstra vs Floyd-Warshall

• Dijkstra : O((V+E)log V) pour une seule source, optimal pour graphes peu denses réf.
• Floyd-Warshall : O(V³) pour toutes paires, optimal pour graphes denses réf.
• Seuil empirique : Floyd-Warshall préférable si E > V²/log V

Bellman-Ford vs Floyd-Warshall

• Bellman-Ford : gère les poids négatifs, O(VE) par source
• Floyd-Warshall : poids positifs uniquement, O(V³) toutes paires
• Application : Bellman-Ford pour détection de cycles négatifs dans les taux de change

Complexité temporelle O(n³)

Temps d'exécution cubique où n est le nombre de nœuds. Pour n=100, l'algorithme effectue environ 1 million d'opérations (100³). Floyd-Warshall met à jour une matrice n×n pour tous les triplets (i,j,k) de nœuds.

FWAPSP1/2 (Floyd-Warshall All Pairs Shortest Path)

Variantes modifiées de l’algorithme Floyd-Warshall. FWAPSP1/2 intègre un poids ε pour chaque virage détecté via la condition a𝑏𝑠(𝑖−𝑘) ≥ 𝐻. Utilisé pour calculer les distances en évitant les nœuds marqués comme obstacles.

Graphe rectiligne et planaire

Tout graphe rectiligne est planaire, car ses arêtes suivent une grille et ne se croisent jamais, sauf éventuellement aux sommets. Mais l’inverse n’est pas vrai : un graphe planaire peut avoir des arêtes dans toutes les directions, du moment qu’il n’y a pas de croisement, alors qu’un graphe rectiligne impose des arêtes strictement parallèles aux axes.

Un graphe rectiligne est un graphe dont toutes les arêtes sont des segments de droites parallèles aux axes x ou y du plan, c’est-à-dire uniquement horizontales ou verticales. Ce type de graphe est typiquement construit à partir d’une grille régulière (maillage carré), où chaque sommet (nœud) représente un point de la grille et chaque arête relie deux nœuds adjacents sur une même ligne ou colonne. Dans une grille 8×10, 8 lignes (H = 8) et 10 colonnes (W = 10), les nœuds sont numérotés colonne par colonne, du bas vers le haut puis colonne suivante, comme décrit dans l’article.

• Le nœud 2 se connecte horizontalement au nœud 10 (différence = 8 = H), ce qui correspond à un déplacement d’une colonne vers la droite.
• Le nœud 2 se connecte verticalement au nœud 3 (différence = 1), ce qui correspond à un déplacement d’une ligne vers le haut.

Applications du Graphe rectiligne :

Routage de pistes sur un circuit imprimé (PCB), planification de trajets pour robots mobiles dans un environnement quadrillé, réseaux de capteurs sans fil disposés sur une grille…

Un Graphe planaire est un graphe qui peut être représenté dans le plan sans que deux arêtes ne se croisent (autrement qu’aux sommets). Cela signifie qu’il existe une disposition des sommets et des arêtes sur une feuille de papier (ou un écran) où aucun segment reliant deux sommets ne coupe un autre segment, sauf éventuellement à une extrémité commune.

• Un carré, un triangle, ou un graphe en forme de grille sont planaires car on peut les dessiner sans croisement d’arêtes.
• Le graphe complet à 4 sommets (K4) est planaire : il suffit de placer un sommet à l’intérieur du triangle formé par les trois autres pour éviter tout croisement.
• À l’inverse, le graphe complet à 5 sommets (K5) ne l’est pas : il est impossible de le dessiner dans le plan sans croisement d’arêtes.

Applications du Graphe planaire :

Cartographie, conception de réseaux routiers ou ferroviaires, routage sur PCB (où l’on souhaite éviter les croisements de pistes), théorie des couleurs (théorème des quatre couleurs) …
Graphe non orienté : Dans un graphe non orienté, cela signifie qu’une arête peut permettre le flux dans les deux directions.

• Si les nœuds i et j sont connectés, on peut aller de i vers j ET de j vers i
• La connexion est bidirectionnelle
• La matrice A est symétrique : A(i,j) = A(j,i)
• Connexions du nœud 5 (centre)
• Nœud 5 ↔ Nœud 2 (vers la gauche)
• Nœud 5 ↔ Nœud 8 (vers la droite)
• Nœud 5 ↔ Nœud 4 (vers le bas)
• Nœud 5 ↔ Nœud 6 (vers le haut)
• Dans la matrice d'adjacence :
• A(5,2) = 1 ET A(2,5) = 1 (connexion gauche)
• A(5,8) = 1 ET A(8,5) = 1 (connexion droite)
• A(5,4) = 1 ET A(4,5) = 1 (connexion bas)
• A(5,6) = 1 ET A(6,5) = 1 (connexion haut)
  

La terminologie "arête qui part" et "arête qui arrive" est utilisée pour expliquer comment interpréter la matrice d'adjacence, non pas pour indiquer une orientation, mais la symétrie.

Exemple de preuve de graphe non-orienté :

Si le graphe était orienté, nous aurions des situations comme :

• A(1,2) = 1 mais A(2,1) = ∞ (connexion unidirectionnelle)
• Ou A(5,8) = 1 mais A(8,5) = ∞ (flux dans une seule direction)

Heuristique

Une heuristique est une méthode pratique (non nécessairement optimale) pour résoudre un problème complexe en un temps raisonnable. Dans l’article, on parlera d’heuristique en O(n³). La complexité O(n³) est celle de l’algorithme modifié de Floyd-Warshall utilisé ici. La complexité est cubique, l’algorithme met à jour une matrice n×n pour tous les triplets de nœuds. Pour n=200, l’algorithme effectue environ 200⁶ = 8 millions opérations (8×10⁶).

IEEE (Institute of Electrical and Electronics Engineers)

Organisation professionnelle pour les normes technologiques. Par exemple, les références et certains articles spécialisés sont cités et publiés dans des revues IEEE. Ce sont des sources académiques dans le domaine de l’ingénierie.

Itération de Yen

Méthode itérative pour trouver K chemins disjoints. Premier chemin calculé → ses nœuds marqués comme obstacles → deuxième chemin calculé → etc. Évite la complexité exponentielle du problème NP-complet.

Layouts

Les layouts de puces VLSI (Very Large Scale Integration) désignent l’agencement des composants électroniques (transistors, interconnexions) sur un circuit intégré complexe. Dans l’article, les obstacles (composants physiques) sont modélisés comme des polygones rectilignes dans un graphe. Les chemins de routage doivent contourner ces obstacles pour éviter les courts-circuits. Dans un layout VLSI, les pistes entre transistors doivent éviter les zones occupées par les mémoires ou les blocs logiques…

Marquer/Démarquer (Mark-out/Mark-in)

Technique d'exclusion temporaire de nœuds en mettant leurs arêtes à ∞. Code type :

A_temp := A; // Sauvegarde

A[J,:] := ∞; // Exclusion du nœud J

A[:,J] := ∞;

// ... calcul ...

A[J,:] := A_temp[J,:]; // Restauration

Matrice d'adjacence

Structure de données n×n où A[i][j] = 1. « 1 » représente une unité de distance dans la grille. Chaque ligne représente un nœud de départ. Chaque colonne représente un nœud d’arrivée. On met « 1 » si les nœuds i et j sont connectés directement (arrête existante) comme pour les nœuds voisins d’une grille, sinon, on met ∞.

Pour reconnaître si un segment est horizontal ou vertical, il faut appliquer la règle des numérotations. Par exemple dans une grille 8×10 (H = 8, W = 10) :
Segment 2→10 est horizontal dans la grille car |10 - 2| = 8 = H. Puisque 8 ≥ H, c'est un segment horizontal.
Les éléments diagonaux valent ∞ pour éviter les auto-boucles.
Le graphe est un graphe non orienté. Par conséquent, A(i,j) = A(j,i) et A est symétrique et mathématiquement correct. Les arêtes n'ont pas de direction privilégiée. Cela signifie que :

• L'arête entre le nœud i et le nœud j est identique à l'arête entre j et i
• Si A(i,j) représente le poids de l'arête de i vers j, alors A(i,j) = A(j,i)

MBSP (Minimum Bend Shortest Path)

Chemin le plus court avec le nombre minimal de virages à 90°. Parmi plusieurs chemins courts de même longueur, le MBSP est sélectionné pour réduire la consommation d’énergie. C’est un critère utilisé pour les véhicules autonomes où les virages ralentissent le mouvement.

Mémoïsation

Technique stockant les résultats intermédiaires pour éviter les recalculs.

NP-complet (Non-déterministe Polynomial)

Désigne une classe de problèmes difficiles à résoudre efficacement. Exemple : Trouver K chemins disjoints est NP-complet, mais l’article utilise une heuristique en O(n³) contre une approche combinatoire exponentielle pour BiOO. Justifie donc le choix d’une approche itérative plutôt qu’exacte. Par exemple, avec n=400, RNMBP résout le problème en quelques secondes, tandis que BiOO nécessite des heures.

Parallélisation Floyd-Warshall

Chaque itération k peut paralléliser les calculs (i,j). Pour n=1000, on peut utiliser 1000 threads calculant simultanément les lignes de la matrice. Gain théorique : réduction du temps de O(n³) à O(n³/p) où p est le nombre de processeurs.

PCB (Printed Circuit Board)

Circuit électronique imprimé avec des pistes conductrices. Le routage sur PCB nécessite des chemins rectilignes évitant les composants. Dans ce contexte, les obstacles sont modélisés comme des polygones rectilignes dans le graphe.

Polygone rectiligne

Forme géométrique dont tous les côtés sont parallèles aux axes. Les obstacles dans l'article sont représentés comme des polygones rectilignes délimités par les points de grille.

Programmation dynamique

Technique divisant un problème en sous-problèmes optimaux. Floyd-Warshall calcule

Ou

en notation avec indices temporels

Signification des notations :

Pour k = 1 à n :
    Pour i = 1 à n :
        Pour j = 1 à n :
            distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])

Relaxation d'arête

Opération de mise à jour des distances. Si distance[i][j] > distance[i][k] + distance[k][j], alors distance[i][j] = distance[i][k] + distance[k][j]. Dans l'article, cette relaxation inclut le poids des virages ε.

RNMBP (Rectilinear Non-crossing Minimum Bend Paths)

Algorithme proposé pour trouver des chemins rectilignes non croisés avec virages minimaux. Le RNMBP utilise une version modifiée de Floyd-Warshall pour traiter les obstacles rectilignes. Il est appliqué dans les réseaux de capteurs sans fil et les layouts ferroviaires.

Routage PCB (Printed Circuit Board)

Problème de traçage de pistes électriques évitant les composants. Dans un PCB 10×8 cm avec résolution 1mm, on obtient une grille 100×80. Les composants (résistances, condensateurs) deviennent des obstacles polygonaux.

Matrice creuse (Sparse Matrix)

Optimisation pour graphes peu denses. Si un graphe 1000×1000 n'a que 5000 arêtes, utiliser une liste d'adjacence économise 99.5% de mémoire par rapport à une matrice complète.

SODA (Symposium on Discrete Algorithms)

Conférence annuelle sur les algorithmes discrets. Par exemple, le présent article compare les performances de RNMBP avec des méthodes présentées à SODA dans un contexte de Benchmarking des algorithmes géométriques.

Théorème des chemins non-croisés

Dans une grille carrée, les chemins disjoints en nœuds ne se croisent jamais. Preuve : deux arêtes rectilignes ne peuvent se croiser qu'en un nœud commun, donc des chemins sans nœuds communs ne se croisent pas.

Véhicule autonome - Navigation

Application où les virages consomment plus d'énergie. Un véhicule passant de 50 km/h à 30 km/h dans un virage consomme 15% d'énergie supplémentaire. L'algorithme RNMBP minimise ces virages.

VLSI (Very Large Scale Integration)

Technologie de fabrication de circuits intégrés complexes. Dans les layouts de puces VLSI, les composants agissent comme obstacles pour les chemins de routage. Ce concept technologique est utilisé dans les applications en conception de circuits intégrés où les chemins doivent contourner des obstacles. C’est un agencement de millions de transistors sur une puce. Un processeur moderne (5nm) peut contenir 50 milliards de transistors sur 1cm². L'algorithme route les interconnexions métalliques entre blocs fonctionnels.

Variables clés et notations

H : Hauteur du graphe en nœuds (H = 8 pour un graphe 8x10).

ε (epsilon) : Poids d’un virage (≈ 0,001). ε = 1mnb évite de fausser les distances. mnb : Nombre maximal estimé de virages dans un chemin. La condition mnb ε < 1 garantit que le poids total des virages n’altère pas la priorité donnée à la longueur du chemin. Si mnb =1000, alors ε=0,001, et un chemin avec 500 virages ajoute 0,5 à sa longueur.

K : Nombre de paires source-destination. K = 7 chemins calculés en parallèle signifient le calcul simultané de K chemins disjoints dans le même graphe, sans parallélisme informatique. Les nœuds utilisés par un chemin sont marqués comme obstacles pour les itérations suivantes. Les chemins sont traités séquentiellement, par ordre croissant de longueur. Le premier chemin (le plus court) est tracé, puis ses nœuds sont exclus pour le calcul du deuxième chemin, etc.

« → » Cette petite flèche indique dans la théorie des graphes pour indiquer une direction d'un nœud vers un autre.
« : » (deux-points) signifie « tous les éléments de la ligne » A(J,:) ou bien tous les éléments de la colonne A(:,J). Cette notation est utilisée en MATLAB ou Python/Numpy.
Exemple 1 : A(J, :) = ∞. Cette notation A(J, :) = ∞ dans l’article signifie que l’on attribue la valeur « infini » à tous les éléments de la ligne J de la matrice d’adjacence A, c’est-à-dire à tous les poids des arêtes sortant du nœud J. A est la matrice d’adjacence du graphe, où chaque élément A(i, j) représente le poids (ou la distance) de l’arête entre le nœud i et le nœud j.
Exemple 2 : Soit une matrice 3 x 3 identique à celle de l’exemple donné dans ce glossaire (Graphe non orienté). Si l’on veut exclure le nœud 5 (centre de la matrice), il faut écrire :
A(5,:) = ∞ (ligne 5) :

• Tous les éléments de la ligne 5 deviennent ∞
• Cela exclut toutes les arêtes sortant du nœud 5

A(:,5) = ∞ (colonne 5) :

• Tous les éléments de la colonne 5 deviennent ∞
• Cela exclut toutes les arêtes entrant vers le nœud 5

« || » : la double barre dans l’expression est un opérateur logique qui signifie OU (« OR » en anglais) dans la plupart des langages de programmation (C, C++, Java, Python…).

Exemple : G = (abs(i-k) >= H ET abs(k-j) < H) || (abs(i-k) < H ET abs(k-j) >= H);

{1 : n} signifie {1... n} que l’ensemble des sommets est constitué des entiers allant de 1 à n.

IX-A. Remerciements▲