Microscopic Management and Control of a Fleet of Cybercars

Back. 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 final report is here [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 clothoïdes [1] et des segments.

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 v0>0, les vitesses atteignables [vmin, vmax] (>0) et les accélérations [amin, amax] (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 = v0Dt + a (Dt)2,
Delta = v02 + 4 a Dx0, >0 si pas d'arrêt,
Dt = (-v0+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 - v0(Dt))/(Dt)2

  • 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).

Points critiques et réservation

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.

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.

La ressource à partager.

On va utiliser l'idée de réservations1) pour ces points critiques.

Références

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 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.
  • 1er-12 septembre :

The target acceleration to apply to the vehicle should depend on the target speed and the distance by which it should have been achieved. 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 :
  • 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.

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.
 
users/oliviermehani/2006internship.txt · Last modified: 2011/02/10 14:08 (external edit)
Recent changes · Show pagesource · Login