Computed path does not go through Champs-Elysées

[tnguyenh]

[tnguyenh]

[agrignard]

Très bizarre ce bug, on a inspecté en long et en large le fichier OSM, y'a un problem de connexion à cet endroit la a priori donc pas grand monde ne veut prendre les champs (pas etonnant qu'il faille les redesigner ;-)!

[tnguyenh]

Temporairement résolu. Le calcul de general_map doit être affiné et il faut vérifier qu'il ne reste rien de bizarre dans le shapefile.

[ptaillandier]

vous avez modifié le(s) shapefile ?

Le mar. 28 janv. 2020 à 00:43, Tri Nguyen-Huu notifications@github.com a écrit :

Temporairement résolu. Le calcul de general_map doit être affiné et il faut vérifier qu'il ne reste rien de bizarre dans le shapefile.

[image: image] https://user-images.githubusercontent.com/18676913/73223688-3ed7fa00-4167-11ea-8cf9-4455e1125809.png

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/agrignard/ReChamp/issues/65?email_source=notifications&email_token=AALPWHPA73GTBKAALD5EPSDQ75WTRA5CNFSM4KMJN7IKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOEKBP3UQ#issuecomment-579010002, or unsubscribe https://github.com/notifications/unsubscribe-auth/AALPWHKDGQQTVEPHFRYQZYDQ75WTRANCNFSM4KMJN7IA .

[agrignard]

@tnguyenh bonne nouvelle!

C était quoi le soucis ??!

[agrignard]

J'ai pas tout compris ce que Tri a fait mais Patrick si tu veux voir le commit https://github.com/agrignard/ReChamp/commit/edc21918483757fe0c49f27af8bc80f3557c5e48

[agrignard]

ca passe encore pas des endrotis un peu bizarres non?

@tnguyenh tu peux enlever les afficahges de debugages aussi?

[tnguyenh]

Non ça ne marche pas. Après vérification les agents ne suivent pas le plus court chemin, je vais committer un fichier de test dans pas longtemps pour illustrer ça. Je vérifie déjà qu'il n'y a pas une erreur qui m'aurait échappée... Patrick, tu sais quel algo est utilisé dans le pathfinder ?

[tnguyenh]

Et après vérification, ce n'est pas un souci avec le shapefile... plus de détails dans pas longtemps.

[tnguyenh]

Un peu plus de détails: voici un essai avec l'affichage de plusieurs trajectoires. Etrangement il y a deux véhicules qui passent par des points en communs mais qui ne suivent pas le même chemin entre ces deux points.

[tnguyenh]

J'ai commité un fichier de test. Il affiche l'exemple de deux chemins, un court (en vert) et un long (en jaune). Par rapport aux exemples précédents, c'est le chemin jaune qui est choisi à la place du vert. Dans le fichier test, la voiture 0 prend un chemin entre les deux, mais plus long que le vert...

[tnguyenh]

update avec un essai avec shortest_path (chemin bleu). Le poids est plus important que celui du chemin vert...

[agrignard]

@ptaillandier qu est ce que tu en penses ?

[ptaillandier]

je regarde ça dans quelques heures (là, je suis en réunion).

Le mar. 28 janv. 2020 à 14:30, Arnaud Grignard notifications@github.com a écrit :

@ptaillandier https://github.com/ptaillandier qu est ce que tu en penses ?

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/agrignard/ReChamp/issues/65?email_source=notifications&email_token=AALPWHOFDDBHBD4MZDWKMRTRAAXOPA5CNFSM4KMJN7IKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOEKDJPXY#issuecomment-579246047, or unsubscribe https://github.com/notifications/unsubscribe-auth/AALPWHI3GYTPA7CQRO2MMA3RAAXOPANCNFSM4KMJN7IA .

[tnguyenh]

J'ai fait un test en réécrivant un pathfinder, qui celui-là donne bien la bonne trajectoire (en violet). Ca sent le bug ou le feature. Est-ce que l'algo utilisé est exact ou une heuristique ?

[ptaillandier]

exact et fiable a priori. Je vais regarder.

Le mar. 28 janv. 2020 à 14:49, Tri Nguyen-Huu notifications@github.com a écrit :

J'ai fait un test en réécrivant un pathfinder, qui celui-là donne bien la bonne trajectoire (en violet). Ca sent le bug ou le feature. Est-ce que l'algo utilisé est exact ou une heuristique ?

[image: image] https://user-images.githubusercontent.com/18676913/73269549-518d1600-41dd-11ea-8d7f-d514efc9192a.png

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/agrignard/ReChamp/issues/65?email_source=notifications&email_token=AALPWHOS6ANYHS3EWSJDJEDRAAZVBA5CNFSM4KMJN7IKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOEKDLNXY#issuecomment-579253983, or unsubscribe https://github.com/notifications/unsubscribe-auth/AALPWHPYW6IWHI4E5CAGOGLRAAZVBANCNFSM4KMJN7IA .

[tnguyenh]

A priori en récrivant Dijstra on a les bons chemins, mais c'est horriblement lent. A mon avis c'est plutôt un A*, non ?

[ptaillandier]

Tu peux tester, tu as plusieurs algo dans GAMA (il y a model exemple qui dit comment changer l'algo), mais je serais étonné que le résultat soit mauvais. (dijkstra, bidirectional dijkstra, A, bi-directional A, Bellman, Floyd Warhsall).

Le mar. 28 janv. 2020 à 15:03, Tri Nguyen-Huu notifications@github.com a écrit :

A priori en récrivant Dijstra on a les bons chemins, mais c'est horriblement lent. A mon avis c'est plutôt un A*, non ?

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/agrignard/ReChamp/issues/65?email_source=notifications&email_token=AALPWHNSTLRF7VP2MU6UVILRAA3K3A5CNFSM4KMJN7IKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOEKDM54A#issuecomment-579260144, or unsubscribe https://github.com/notifications/unsubscribe-auth/AALPWHK76EYIDXSEPHKVEN3RAA3K3ANCNFSM4KMJN7IA .

[tnguyenh]

J'ai mis un nouveau fichier de test testNewPathFinder. Il affiche les chemins de 19 voitures en blancs avec le compute_path du driving skill, et en cyan celui d'une voiture avec Dijkstra. Le temps de calcul de Dijkstra écrit en gaml est très long (ça freeze quand ça recompute). Mais on voit bien que ce ne sont pas les mêmes chemins qui sont choisis.

Si compute_path n'est pas un algo exact (ce qui ne me semblerait pas absurde), il faudra soit vraiment forcer le passage de manière plus importante sur general_speed_map, soit faire circuler les véhicules avec une matrice Origine Destination sur un graphe plus réduit, soit précalculer les parcours avec Dijsktra (ce qui enlève la possibilité de réagir aux bouchons).

[tnguyenh]

Trouvé le modèle... mais bon y'a marqué dedans que A* assure de trouver le plus court chemin, ce qui est faux... je vais regarder.

(ca marche peut être si l'heuristique est basée sur une distance euclidienne, mais ce n'est pas notre cas avec l'utilisation de general_speed_map).

[ptaillandier]

Alors, si c'est vrai, la version de A* de GAMA (comme dans la plupart des libs de graphe) renvoie le plus court chemin exacte. Le problème ne vient pas de ça, mais juste des poids choisit pour le graphe et l'effet "je garde mon ppc tant que je n'ai pas fini mon chemin". J'ai amélioré les choses en laissant la possibilité aux agents de prendre un chemin alternatif quand la route d'après est embouteillée.

Le mar. 28 janv. 2020 à 15:33, Tri Nguyen-Huu notifications@github.com a écrit :

Trouvé le modèle... mais bon y'a marqué dedans que A* assure de trouver le plus court chemin, ce qui est faux... je vais regarder.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/agrignard/ReChamp/issues/65?email_source=notifications&email_token=AALPWHKHZSNKHZR7RSDSOZDRAA6Z3A5CNFSM4KMJN7IKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOEKDQHCA#issuecomment-579273608, or unsubscribe https://github.com/notifications/unsubscribe-auth/AALPWHNDIWMFBN3LXBMV4OLRAA6Z3ANCNFSM4KMJN7IA .

[ptaillandier]

En fait, après vérification, cela dépend du graphe. Ce que j'ai dit est généralement vrai (pour tous les autres graphes), mais pas forcément pour notre graphe de route :

Wikipedia:

Un algorithme de recherche qui garantit de toujours trouver le chemin le plus court à un but s'appelle « algorithme admissible ». Si A utilise une heuristique qui ne surestime jamais la distance (ou plus généralement le coût) du but, A peut être avéré admissible. Une heuristique qui rend A* admissible est elle-même appelée « heuristique admissible ».

Si l'évaluation renvoie simplement toujours zéro, qui n'est jamais une surestimation, alors, A* exécutera une implémentation possible de l'algorithme de Dijkstra et trouvera toujours la solution optimale. La meilleure heuristique, bien qu'habituellement impraticable pour calculer, est la distance minimale réelle (ou plus généralement le coût réel) au but. Un exemple d'une heuristique admissible pratique est la distance à vol d'oiseau du but sur la carte.

Dans notre cas, les poids des arcs est souvent inférieurs à la distance entre 2 points, donc, cela casse cette condition. quatre solutions : garder NBA et tant pis si c'est un peu faux par moment, prendre Dijkstra (un peu plus lent), modifier le poids des arcs pour qu'il soient toujours supérieur à la distance entre les 2 noeuds, ajouter la possibilité dans GAMA de ne pas utiliser l'heuristique de NBA. Dommage qu'on n'utilise pas GAMA 2.0 qui intègre la dernière version de jgrapht qui inclut l'algo Bidirectional-Dijkstra, pas beaucoup moins bon que NBA* et toujours exact.

Le mar. 28 janv. 2020 à 17:18, Patrick Taillandier < patrick.taillandier@gmail.com> a écrit :

Alors, si c'est vrai, la version de A* de GAMA (comme dans la plupart des libs de graphe) renvoie le plus court chemin exacte. Le problème ne vient pas de ça, mais juste des poids choisit pour le graphe et l'effet "je garde mon ppc tant que je n'ai pas fini mon chemin". J'ai amélioré les choses en laissant la possibilité aux agents de prendre un chemin alternatif quand la route d'après est embouteillée.

Le mar. 28 janv. 2020 à 15:33, Tri Nguyen-Huu notifications@github.com a écrit :

Trouvé le modèle... mais bon y'a marqué dedans que A* assure de trouver le plus court chemin, ce qui est faux... je vais regarder.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/agrignard/ReChamp/issues/65?email_source=notifications&email_token=AALPWHKHZSNKHZR7RSDSOZDRAA6Z3A5CNFSM4KMJN7IKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOEKDQHCA#issuecomment-579273608, or unsubscribe https://github.com/notifications/unsubscribe-auth/AALPWHNDIWMFBN3LXBMV4OLRAA6Z3ANCNFSM4KMJN7IA .

[tnguyenh]

Ca marche pas sur 1.8 ? Dommage... mais on va s'en sortir en siouxant un peu. En fait l'algo actuel convient très bien sauf pour les agents avec une origine/destination, mais comme c'est toujours les mêmes on peut les précalculer. Ca semble être fait dans le modèle de graphes, je vais regarder comment on fait, je reviendrai vers toi si je galère ;)

[tnguyenh]

@Patrick: est-ce qu'il y a moyen de sauvegarder uniquement quelques chemins ?

[ptaillandier]

non, mais si il n'y a quelques chemins, tu peux les calculer en début de simulation. Après, il y a une action du driving skill qui permet de reconstruire proprement un chemin à partir d'un ensemble d'intersection (path_from_nodes je crois).

Le mar. 28 janv. 2020 à 20:36, Tri Nguyen-Huu notifications@github.com a écrit :

@patrick https://github.com/patrick: est-ce qu'il y a moyen de sauvegarder uniquement quelques chemins ?

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/agrignard/ReChamp/issues/65?email_source=notifications&email_token=AALPWHJ4RS2GHDYN6CSXVBDRACCNFA5CNFSM4KMJN7IKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOEKETO5Y#issuecomment-579417975, or unsubscribe https://github.com/notifications/unsubscribe-auth/AALPWHMK6VCXR445ZIB6FTTRACCNFANCNFSM4KMJN7IA .

[tnguyenh]

Tout va bien les parisiens peuvent revenir en 4x4 sur les champs.