Differences

This shows you the differences between two versions of the page.

users:oliviermehani:2006internship [2010/04/15 02:33]
Olivier Mehani
users:oliviermehani:2006internship [2011/02/10 14:08] (current)
Line 1: Line 1:
 +====== Microscopic Management and Control of a Fleet of Cybercars ======
 +[[users:oliviermehani|Back.]]
 +{{users:oliviermehani:2006internship:deadlock.jpg?200  |This is what we try to avoid (thanks Mitose (; )}}
 +The internship deals with trajectories generation for several cooperative vehicles in a given area (road, crossroad or district). The map of this area is supposed to be given.
 +More precisely, the 2D traces of the paths on the ground are given, the origin and destination of the vehicles are given, and we want to calculate the speed profile of each cybercar: such a routine is called a strategy. A strategy can be decomposed between the priority (the order of passage of the cybercars) and the speed optimization if the priority is given. The internships deals with the exploration of feasible strategy, i.e. strategies that are non-blocking (no dead-lock) and collision free. A first approach using classical polling models should give "natural" solutions, e.g. a traffic light like strategy. More advanced optimization methods using e.g. neural networks could be used to propose new strategies. This can be also necessary to explore solution in a complex area (district).
 +The strategy will be implemented and interfaced with the existing software. The result of the internship is a software (source, executable and documentation) and possibly a publication. A demonstration with cybercars would be a nice achievement (INRIA possesses a dozen of cybercars).
 +
 +The following tracks the progression of the work. The {{:users:oliviermehani:publications:mehani_olivier_cas_thesis.pdf|final report is here}} {[oliviermehani:2007mehani_cybercars_crossroads]}.
 +
 +===== Idée de base =====
 +On connait déjà les profils des trajectoires pour aller d'une entrée à une sortie d'un carrefour. On cherche à **calculer et optimiser les profils de vitesse** de plusieurs Cycabs arrivant dans la même période de temps sur ce carrefour.
 +
 +Le carrefour est l'embranchement de deux routes à angle droit, ainsi que les 100 mètres arrivant à cet embranchement, dans les 4 directions. Le carrefour contrôle les vitesses de //toutes// les Cycabs dans cette zone, et **connait toutes les informations** (particulièrement, leur destination).
 +
 +La performance du système est mesurable au temps moyen passé sur le carrefour, qui doit être minimisé.
 +
 +===== Embryons de solution =====
 +Les trajectoires sont actuellement **approximées par des [[wp>clothoid|clothoïdes]] [1] et des segments**.
 +
 +{{:users:oliviermehani:2006internship:segments_and_clothoids.png |Un exemple (très approximatif) de trajectoire à base de clothoides et de segments}}
 +
 +À chaque instant, un seul Cycab peut être sur un segment. Pour aller de l'entrée à la sortie voulue du carrefour, un **parcours du graphe** peut être (relativement rapidement) effectué afin de trouver les tronçons à emprunter.
 +
 +Lorsqu'un Cycab est sur un des tronçons, il occupe une place plus large que ce dernier. Il existe donc des **incompatibilités entre les tronçons**. Si un Cycab est sur un tronçon, les tronçons proches (concept à définir) ne pourront pas recevoir un autre Cycab au même instant.
 +
 +Au final, on dispose, à chaque instant, des informations suivantes pour **dynamiquement définir des vitesses** pour chaque Cycab (ou une date d'entrée et une date de sortie pour chaque couple (Cycab, tronçon)):
 +  * un graphe //orienté// de connexion des tronçons ;
 +  * une matrice d'incompatibilités ;
 +  * la liste des Cycabs présents, leurs position, vitesse courant et destination.
 +
 +À chaque pas de temps, l'algorithme est réexécuté pour adapter la plannification en fonction des nouvelles informations (arrivée d'un nouveau Cycab,...).
 +
 +==== Idées en vrac ====
 +  * Les tronçons doivent être découpés dynamiquement en fonction des Cycabs en présence et des trajectoires qu'ils vont emprunter.
 +  * On a peut calculer une fourchette de temps durant lesquels un Cycab peut arriver à un point de la trajectoire. Connaissant la vitesse actuelle //v//<sub>0</sub>>0, les vitesses atteignables [//v//<sub>min</sub>, //v//<sub>max</sub>] (>0) et les accélérations [//a<sub>min</sub>//, //a<sub>max</sub>//] (0<,>0) et la distance à parcourir D//x//, on a, //à condition que le véhicule ne dépasse pas ses vitesses maximum atteignables durant le parcours//,
 +
 +D//x// = //v//<sub>0</sub>D//t// + a (D//t//)<sup>2</sup>, \\
 +Delta = //v//<sub>0</sub><sup>2</sup> + 4 //a// D//x//<sub>0</sub>, >0 si pas d'arrêt, \\
 +D//t// = (-//v//<sub>0</sub>+sqrt(Delta))/(2//a//),
 +
 +insérant les valeurs (resp.) min et max de //a//, on obtient les valeurs (resp.) max et min de D//t//, l'instant d'arrivé à une distance D//x// du point actuel.
 +
 +De même, sachant l'instant d'arrivée désiré, on peut, //dans le cas général//, dériver l'accélération à donner au véhicule pour qu'il arrive à temps.
 +
 +//a// = (D//x// - //v//<sub>0</sub>(D//t//))/(D//t//)<sup>2</sup>
 +
 +  * [[users:oliviermehani:2006internship:ConstraintProgramming]].
 +  * Une meilleure (?) [[:users:oliviermehani:2006internship:FormalisationDuProbleme]] ;
 +  * Trouver les platoons potentiels (véhicules contigus de mêmes source et destination), les former, puis les gérer comme un seul véhicule ;
 +  * Utiliser des Inevitable Collision States ;
 +  * Privilégier les véhicules attendant depuis le plus longtemps, puis les plus gros groupes (trouver une hiérarchie quantitative).
 +
 +===== Points critiques et réservation =====
 +Après [[:users:oliviermehani:2006internship:20061207|point du 12/07/2006]].
 +
 +==== Principe ====
 +Il existe certains points //critiques// sur les trajectoires. Ceux ci se trouvent quand deux trajectoires se croisent ou se rejoignent. Autour de ces points se retrouvent donc les segments critiques vus plus haut. Ils sont la ressource à distribuer dans le temps.
 +
 +{{users:oliviermehani:2006internship:critical_points.png |Les points critiques.}}
 +
 +En fonction de la zone de chevauchement, il est possible que seules deux trajectoires soient mises en cause (1) ou plus (2).
 +
 +Une fois l'ordre de passage aux points critiques établi, il faut déterminer les horaires de passages. Cela doit cependant pouvoir se faire au cas par cas.
 +
 +{{users:oliviermehani:2006internship:curviligne.png |La ressource à partager. }}
 +
 +On va utiliser l'idée de réservations((Kurt Dresner and Peter Stone. //[[http://citeseer.ist.psu.edu/dresner04multiagent.html|Multiagent Traffic Management: A Reservation-Based Intersection Control]]//)) pour ces points critiques.
 +
 +===== Références =====
 +
 +[1] {{users:oliviermehani:2006internship:rapport_ait_mebarek_hayet.pdf|Rapport de stage d'Hayet AIT MEBAREK}}, [[\\fylvestre.inria.fr\data\ait_mebarek|Mirroir (bourrin) sur fylvestre]]
 +
 +Wikipedia: [[wp>STRIPS]], [[wp>Automated_planning]]
 +
 +Steven M. LaValle,  //[[http://msl.cs.uiuc.edu/planning/|Planning Algorithms]]//
 +
 +===== Organisation du stage =====
 +  * **15-19 juin** : découverte d'IMARA et des divers projets/plateformes ;
 +  * **20 juin - 12 juillet** : bibliographie ;
 +  * **13 juillet - 29 juillet** : développement du [[:users:oliviermehani:2006internship:simulateur]] ;
 +    * détection des points critiques ;
 +    * //produit attendu// : Simulateur avec modules basiques (trajectoires simples par segments,...) et documentation pour la prise en main => tag ''basic-modules'' [[https://gforge.inria.fr/plugins/scmsvn/viewcvs.php/simulator/tags/basic-modules/?root=mehani|dans le SCM]].
 +  * **21-31 août** :
 +    * algorithme "classique" de polling.
 +      * implémentation dans l'environnement de test => tag ''basic-polling'' dans [[https://gforge.inria.fr/plugins/scmsvn/viewcvs.php/simulator/tags/basic-polling/?root=mehani|dans le SCM]] ;
 +    * prise en compte de l'accélération des véhicules ;
 +    * SensibleVehicle adaptant sa vitesse aux obstacles.
 +  * **1<sup>er</sup>-12 septembre** :
 +    * [[#points_critiques_et_reservation|Algorithme de réservation de points critiques]].
 +      * implémentation dans l'environnement de test => tag ''basic-reservations'' dans [[https://gforge.inria.fr/plugins/scmsvn/viewcvs.php/simulator/tags/basic-reservations/?root=mehani|dans le SCM]] ;
 +{{users:oliviermehani:2006internship:acceleration_profile.png?200|The target acceleration to apply to the vehicle should depend on the target speed and the distance by which it should have been achieved.}}
 +{{users:oliviermehani:2006internship:collision_foresee.png?200|A collision foreseeing scheme that should be implemented}}
 +  * **13-26 septembre** :
 +    * Affinage des modèles/classes.
 +      * SensibleVehicle ;
 +        * gestion des vitesses en fonction de la distance où il faut l'atteindre ;
 +        * gestion/prévention des collisions.
 +      * SimulationManager.
 +        * statistiques de collisions.
 +  * **27 septembre - 13 octobre** :
 +    * Implémentation de base de l'algorithme de réservation ;
 +    * Amélioration du rendu graphique des informations et des classes responsables.
 +  * ** 1-31 octobre **:
 +    * [[:wiki:old:users:oliviermehani:papers:eurocast2007]] ;
 +  * **16-19 octobre** :
 +    * Générateur de trajectoires utilisant des [[#embryons_de_solution|clothoïdes]].
 +  * ** 13-16 novembre **:
 +    * IPv6 summit.
 +  * ** 20 octobre - 4 décembre **:
 +    * Refactoring des SpeedsManager et des Vehicles ;
 +    * Étendre les réservations aux critical points trop proches ;
 +    * Sauvegarde des images générées ;
 +    * Nouvelle implémentation réellement multiagent des réservations => tag ''reservations'' dans [[https://gforge.inria.fr/plugins/scmsvn/viewcvs.php/simulator/tags/reservations/?root=mehani|dans le SCM]] .
 +  * ** 5-15 décembre **:
 +    * Introduction Poissonienne des véhicules ;
 +    * Debug.
 +
 +==== Travaux futurs ====
 +  * FIXME Évitement de collision _avant_ le carrefour.
 +  * FIXME Tests et comparaisons ;
 +  * Nouvelle approche d'attribution des trajectoires à l'arrivée du véhicule ;
 +    * Algos génétiques ;
 +    * Recherche "classique".
 +  * Améliorations éventuelles des réservations ;
 +    * :?: Gestion des priorités en logique floue ;
 +  * Autres algos.