Modèles d'environnements, planification de trajectoires

Modèles d'environnements, planification de trajectoires



Emploi du temps 2019-2020, séances de 2h en général le jeudi matin ou le mardi aprés-midi)
  • jeudi 19 septembre [OD] (10h15, salle FST-VG-ST12) Introduction à la géométrie algorithmique,Enveloppe convexe: définition et algorithmes. [+exercices]
  • jeudi 26 septembre [OD] (08h00, salle FST-HP-E35) Triangulation de Delaunay, intro, définitions et premières propriétés. [+exercices]
  • jeudi 3 octobre [OD] (10h15, salle FST-HP-E34) Triangulation de Delaunay, algorithme incremental, un algorithme en O(n log n) dans le cas le pire. [+exercices]
  • jeudi 10 octobre [OD] (08h00, salle salle FST-HP-E34) Simplifier les algorithmes sans trop perdre en rapidité: la randomisation. [+exercices controle continu]
  • jeudi 17 octobre [OD] (08h00, salle FST-HP-E35) Que faire quand les erreurs numériques sont géométriquement insensées ?
  • jeudi 17 octobre [OD] (10h15, salle FST-VG-ST20) Le problème du voyageur de piano: arrangements de courbes et de surfaces. [+exercices controle continu]
  • jeudi 24 octobre [FC] (08h00, salle FST-HP-E35) Cartes en robotique
  • jeudi 7 novembre [FC] (10h15, salle FST-HP-E24) Espace de configuration
  • jeudi 14 novembre [OD] (08h00, salle FST-HP-E32) Application reconstruction: comment retrouver une surface à partir de points de données. Un peu de complexité sous des hypothèses probabilistes. [+exercices controle continu]
  • jeudi 21 novembre [OD] (10h15, salle FST-HP-E34) Présentation des stages dans l'équipe Gamble. [+exercices ] [+exercices ]
  • jeudi 5 décembre [FC] (08h00, salle ??) Planification stochastique
  • jeudi 5 décembre [FC] (10h15, salle ??) Planification déterministe [+exercices controle continu]
  • jeudi 16 janvier [exam] (9h00, salle ??)
Contrôle des connaissances
  • Controle continu (40%) pas de session de rattrapage
    • 4 exercices notés en fin de séance
  • Épreuve anticipée (60%)
    • un exam écrit 2h le 9 janvier. Documents et ordinateurs interdits. 2 pages de notes de cours manuscrites sont autorisées.
    • un exposé sur article
      • date sur rendez-vous à prendre le 7 janvier au plus tard pour un passage avant fin janvier)
      • présentation d'un article de recherche en binôme (ou monôme). Un seul bi(mo)nôme par article. Vous devez envoyer votre choix de sujet à Olivier Devillers ET Francis Colas, par courriel, entre le 1er et le 10 décembre.
      • Votre exposé sera de 20 mn et sera suivi 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/...?
      • Liste des articles: (si vous n'avez pas accés aux articles, demandez nous. Les résumés devraient suffire pour choisir.)
          (Alexis Barthelemy) (Damien Choffe)
        • Chew & Fortune, 1997: Sorting helps for Voronoi diagram lien (Steward Naoki)
        • Seidel, 1991: A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons lien
        • Seidel, 1991: Small-dimensional linear programming and convex hulls made easy. lien (Clément Charton et Nelson LEMERCIER)
        • Bose, Morin, 1999: Online routing in triangulations. lien (Quentin DUVERGER et Godefroy DELHAY)
        • Hershberger, 1989: Finding the upper envelope of n line segments in O (n log n) time lien
        • Bose, Devroye, Loffler, Snoeyink, & Verma, 2009: The spanning ratio of the Delaunay triangulation is greater than pi/2. lien
        • Hershberger, 2011: Stable Snap rounding lien (Pierre Cadart et Jad Abdul Rahman Obeid)
        • Erickson, 2001: Nice point sets can have nasty Delaunay triangulations lien
        • Avis, ElGindy, & Seidel, 1985: Simple on-line algorithms for convex polygons. lien
        • Dijkstra, 1959: A note on two problem in connexion with graphs lien (Guillaume Gaillard et William Vanhuffel)
        • Hart et al, 1968: A Formal Basis for the Heuristic Determination of Minimum Cost Paths lien (Maureen BOUDART et Walid HAFIANE)
        • Koenig & Likhachev, 2002: D*Lite lien (Valentin Collignon, Antonin Calba)
        • LaValle & Kuffner, 2001: Randomized Kinodymanic Planning lien (Henri LAMBERT et Matthieu HOCHLANDER)
        • Kavraki et al, 1996: Probabilistic roadmaps for path planning in high-dimensional configuration spaces lien (Paul Merlin)
        • Karaman and Frazzoli, 2011: Sampling-based algorithms for optimal motion planning lien (Maxime ROBINET, Julien LEICHTNAM)
        • Palmieri, Luigi, Sven Koenig, and Kai O. Arras. RRT-Based Nonholonomic Motion Planning Using Any-Angle Path Biasing. lien. (Gaëtan Pelte, Clément Bellanger)
        • Alex Nash, Kenny Daniel, Sven Koenig, Ariel Felner. Theta*: Any-Angle Path Planning on Grids. lien (Francesco Conforti et Lucas Schwab)
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