Modèles d'environnements, planification de trajectoires

Modèles d'environnements, planification de trajectoires



Emploi du temps 2022-2023, séances de 2h, le jeudi matin à 10h15
  • jeudi 15 septembre [XG] Introduction à la géométrie algorithmique. Enveloppe convexe: définition et algorithmes. [+slides] [+exercices corrigés]
  • jeudi 22 septembre [XG] Triangulation de Delaunay, intro, définitions et premières propriétés. [+slides], [+exercices corrigés]
  • jeudi 29 septembre [XG] Triangulation de Delaunay, algorithme incremental, un algorithme en O(n log n) dans le cas le pire. [+slides], [+exercices corrigés]
  • jeudi 6 octobre [OD] Simplifier les algorithmes sans trop perdre en rapidité: la randomisation. [+slides], [+exercices notés corrigés]
  • jeudi 13 octobre [OD] Que faire quand les erreurs numériques sont géométriquement insensées ? [+slides], [+exercices corrigés]
  • jeudi 20 octobre [FC] Cartes en robotique [+slides],
  • jeudi 27 octobre [OD] Application reconstruction et maillages [+slides], [+exercices notés corrigés]
  • jeudi 10 novembre [XG] Le problème du déménageur de piano: arrangements de courbes et de surfaces.
    [+slides], [+exercices corrigés]
  • jeudi 24 novembre [XG] Subdivision spatiale et planification de trajectoires [+exercices corrigés]
  • jeudi 1 décembre [FC] Espace de configuration [+slides],
  • jeudi 8 décembre [FC] Planification déterministe [+slides],
  • jeudi 15 décembre [FC] Planification stochastique [+slides],
  • jeudi 19 janvier, 10:15 [exam] (durée 2h) examen corrigé]
  • semaine du 6 au 10 février [exposés sur article].
Contrôle des connaissances
  • Controle continu (40%) pas de session de rattrapage
    • 4 exercices notés à la fin de certaines séances
  • Épreuve anticipée (60%) Cette épreuve est en deux parties, un exposé sur article et une épreuve de connaissance du cours.
    • Épreuve de cours, sous reserves des contraintes sanitaires elle sera constituée d'un exam écrit 2h. Documents et ordinateurs interdits. 2 pages de notes de cours manuscrites sont autorisées.
    • un exposé sur article
      • date à fixer ultérieurement (janvier-février)
      • présentation d'un article de recherche en monôme. Un seul monôme par article. Vous devez envoyer votre choix de sujet à Francis Colas, Olivier Devillers ET Xavier Gaoc, par courriel, avant le 10 janvier (premier arrivé premier servi, la liste des sujets déjà choisis est maintenue sur cette page web).
      • Votre exposé sera de 15 mn et sera suivi de 15mn de questions, nous conseillons une structuration en
        • Contexte, état de l'art
        • La contribution de l'article (quel algorithme/étude de complexité/... est nouveau dans ce papier selon les auteurs)
        • Analyse: Qu'est ce qui est selon vous nouveau/intéressant/crucial/réutilisable/...?
      • quelques conseils
        • faites une répétition minutée,
        • pour la présentation ayez votre ordinateur prêt à brancher pour ne pas perdre de temps,
        • numérotez vos slides (pour que l'exminateur puisse s'y référer dans ses questions)
        • révisez le cours relatif à l'article que vous avez choisi.
      • Liste des articles: (si vous n'avez pas accés aux articles, demandez nous. Les résumés devraient suffire pour choisir.)
        • Erickson, 2001: Nice point sets can have nasty Delaunay triangulations lien (Raphaël BAGAT)
        • M. Otte and E. Frazzoli. RRTX: Real-Time Motion Planning/Replanning for Environments with Unpredictable Obstacles in Algorithmic Foundations of Robotics XI, Springer, 2015, pp. 461-478. lien (Axee COULON)
        • Dijkstra, 1959: A note on two problem in connexion with graphs lien (Victor DHEDIN)
        • Bose, Devroye, Loffler, Snoeyink, & Verma, 2009: The spanning ratio of the Delaunay triangulation is greater than pi/2. lien (Othmane ELKANOUNI)
        • LaValle & Kuffner, 2001: Randomized Kinodymanic Planning lien (Kevin ENGRAND)
        • Koenig & Likhachev, 2002: D*Lite lien (Yanis FERNANDEZ)
        • Kavraki et al, 1996: Probabilistic roadmaps for path planning in high-dimensional configuration spaces lien (Florian FRITZ)
        • Alex Nash, Kenny Daniel, Sven Koenig, Ariel Felner. Theta*: Any-Angle Path Planning on Grids. lien (Jérémy GRISÉ)
        • Hart et al, 1968: A Formal Basis for the Heuristic Determination of Minimum Cost Paths lien (Antonin GUYOT)
        • Palmieri, Luigi, Sven Koenig, and Kai O. Arras. RRT-Based Nonholonomic Motion Planning Using Any-Angle Path Biasing. lien. (Hugo LEBLOND)
        • Karaman and Frazzoli, 2011: Sampling-based algorithms for optimal motion planning lien (Dorian MARTINETTO)
        • Seidel, 1991: A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons lien (Morgan MELLINGER)
        • Avis, ElGindy, & Seidel, 1985: Simple on-line algorithms for convex polygons. lien (Guillaume SCHMIT)
        • Alvarez, Victor, and Raimund Seidel 2013. A simple aggregative algorithm for counting triangulations of planar point sets and related problems. lien (Justine SOMMERLATT)
        • Soutenance au LORIA en salle 006 (près de l'entrée, prévoir une pièce d'identité)
        • Vendredi 3 février
          • 14h00 Justine SOMMERLATT
          • 14h30 Hugo LEBLOND
          • 15h00 Dorian MARTINETTO
          • 15h30 Kevin ENGRAND
        • Mardi 7 février
          • 10h30 Guillaume SCHMIT
          • 11h00 Yanis FERNANDEZ
          • 11h30 Morgan MELLINGER
          • 12h00 Antonin GUYOT
          • 13h30 Jérémy GRISÉ
          • 14h00 Raphaël BAGAT
        • Jeudi 9 février
          • 11h30 Victor DHEDIN
          • 12h00 Othmane ELKANOUNI
        • Mardi 14 février
          • 15h00 Axel COULON
          • 15h30 Florian FRITZ
      Documents

      Prérequis du cours

      • Il serait souhaitable de connaître un peu d'algorithmique. En particulier quelques algorithmes de tri (tri fusion, quick sort) et les arbres binaires équilibrés.

      Contacter le responsable : Olivier.Devillers(at)inria.fr