|
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
-
Les transparents (seront mis en ligne en fonction du
déroulement du cours) (voir dans l'emploi du temps ci dessus).
- Les examens passés de 2018 à 2020
(et aussi des DEA Aravis, SIC, IV et masters IGMMV, IFI et IPAC de
1995 à 2018, mais le contenu des cours a évolué au fil
du temps) :
1995-1996,
1996-1997,
1997-1998,
1998-1999,
1999-2000,
2000-2001,
2001-2002 (et corrigé),
2002-2003 (et corrigé),
2003-2004 (et corrigé),
2004-2005 (et corrigé),
2005-2006 (et corrigé),
2006-2007 (et corrigé),
2008-2009 (et corrigé),
2009-2010 (et corrigé),
2010-2011 (et corrigé),
2011-2012 (et corrigé),
2012-2013 (et corrigé),
2014-2015 (et corrigé),
2015-2016 (et corrigé),
2016-2017 (et corrigé partiel),
2017-2018 (et corrigé),
2018-2019 (et corrigé),
2019-2020 (et corrigé),
2020-2021 (et corrigé),
2021-2022 (et corrigé),
2022-2023 (et corrigé),
- Bibliographie
- 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
|