Microscopic Management and Control of a Fleet of Cybercars

Back. 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 final report is here [2007mehani_cybercars_crossroads].

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é.

Les trajectoires sont actuellement approximées par des clothoïdes [1] et des 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,…).

• 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₀>0, les vitesses atteignables [v_min, v_max] (>0) et les accélérations [a_min, a_max] (0<,>0) et la distance à parcourir Dx, on a, à condition que le véhicule ne dépasse pas ses vitesses maximum atteignables durant le parcours,

Dx = v₀Dt + a (Dt)²,
Delta = v₀² + 4 a Dx₀, >0 si pas d'arrêt,
Dt = (-v₀+sqrt(Delta))/(2a),

insérant les valeurs (resp.) min et max de a, on obtient les valeurs (resp.) max et min de Dt, l'instant d'arrivé à une distance Dx 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 = (Dx - v₀(Dt))/(Dt)²

• Constraint Satisfaction Problems.
• Une meilleure (?) Formalisation du problème ;
• 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).

Après point du 12/07/2006.

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.

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.

On va utiliser l'idée de réservations¹⁾ pour ces points critiques.

[1] Rapport de stage d'Hayet AIT MEBAREK, Mirroir (bourrin) sur fylvestre

Wikipedia: STRIPS, Automated_planning

Steven M. LaValle, Planning Algorithms

• 15-19 juin : découverte d'IMARA et des divers projets/plateformes ;
• 20 juin - 12 juillet : bibliographie ;
• 13 juillet - 29 juillet : développement du Simulateur/environnement de test ;
  • 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 dans le SCM.
• 21-31 août :
  • algorithme “classique” de polling.
    • implémentation dans l'environnement de test ⇒ tag basic-polling dans dans le SCM ;
  • prise en compte de l'accélération des véhicules ;
  • SensibleVehicle adaptant sa vitesse aux obstacles.
• 1^er-12 septembre :
  • Algorithme de réservation de points critiques.
    • implémentation dans l'environnement de test ⇒ tag basic-reservations dans dans le SCM ;

• 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 :
  • Eurocast 2007 paper ;
• 16-19 octobre :
  • Générateur de trajectoires utilisant des 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 dans le SCM .
• 5-15 décembre :
  • Introduction Poissonienne des véhicules ;
  • Debug.

• Évitement de collision _avant_ le carrefour.
• 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.