Séminaire Francilien de Géométrie Algorithmique et Combinatoire

Le Séminaire de Géométrie Algorithmique et Combinatoire vise à regrouper des exposés dans ce domaine au sens le plus large, et dans les disciplines connexes en mathématiques et informatique. Il est ouvert à tous les chercheurs et étudiants intéressés. Les exposés sont destinés à un public large.

Il se tient un jeudi par mois, de 14h à 17h, à l'Institut Henri Poincaré à Paris (plan d'accès), en salle 201.

Pour recevoir les annonces de ce séminaire, envoyer un message à vincent [dot-sign] pilaud [the-funny-at-sign] lix [dot-sign] polytechnique [dot-sign] fr.

La liste des exposés passés est disponible ici.


21 décembre 2017
14h Karim Bouyarmane LORIA, Nancy
The humanoid robot motion planning problem
The ability of an intelligent agent endowed with a physical (mechanical) body, to act and interact with its environment through physical motion, is a key ability to qualify the agent as intelligent. Humanoid robots are such agents. They are computers with physical embodiment, or « algorithms » that can act on the real world. A key component of their intelligence is thereby their ability to reason about their environment and their own body (both at geometrical level and physics level), and understand how they can move within this environment and interact with it (planning problem), as well as their ability to actually execute the motion, i.e. to perform a physical realization of the plan (control problem) confronting any idealized model used at planning time to the physical reality. We label both the motion planning and motion control problems as motion intelligence. Through humanoid robots, we try to emulate the human's self motion intelligence. The applications of this endeavor are multiple, from creating autonomous humanoid robots capable of executing high-level commands (physical motion-inducing tasks, which is their added value over other computers tasks), to understanding human motion and motor control, and efficiently assisting the humans in their motions through physical wearable devices or through physical collaboration with robots. The motion planning problem takes different levels of complexity when considering the different kinds of robotic embodiments (fixed-base industrial manipulator arms, wheeled mobile robots, four-legged or six-legged robots, flying drones, bipedal humanoids), each category having its own specificity, constraints, dimensionality, and proposed methods of resolution that proved more or less efficient over the years. We will give an overview of the motion planning problem and control for robots in general and focus on the case of humanoid robots, presenting both the early approaches and the recent advances and open problems on the topic.
15h30 Éric Colin de Verdière LIGM, CNRS & Univ. Marne-la-Vallée
Deciding contractibility of curves on the boundary of a $3$-manifold
In $3$-dimensional computational topology, one of the most important problems is the unknot problem: Is an input simple closed curve in $R^3$ unknotted? The seminal result by Hass, Lagarias, and Pippenger [JACM 1999] shows that the problem is in NP. Very recently, Lackenby proved that the problem is also in coNP. However, no subexponential-time algorithm is known.
I will briefly describe Hass et al.'s method, based on normal surface theory, and will explain why it provides an exponential-time algorithm for the following problem: Given a simple closed curve $c$ on the boundary of a $3$-manifold $M$, is $c$ contractible in $M$? Then, I will describe an exponential-time algorithm to solve the same problem, removing the restriction for $c$ to be simple. The main tool for this result, obtained together with Salman Parsa, is the loop theorem, a fundamental tool in the study of $3$-manifolds, which I will also explain.
18 janvier 2018
14h Marie Albenque LIX, École Polytechnique
TBA
15h30 Philippe Chassaing IEC, Université de Lorraine
TBA
8 février 2018
14h TBA
15h30 TBA
15 mars 2018
14h Xavier Allamigeon CMAP, École Polytechnique
TBA
15h30 TBA
12 avril 2018
14h TBA
15h30 TBA
17 mai 2018
14h TBA
15h30 TBA
28 juin 2018
14h TBA
15h30 TBA

Le séminaire bénéficie du soutien de l'Institut Henri Poincaré.

Le comité scientifique est constitué de:

Le comité d'organisation est constitué de Steve Oudot, Arnau Padrol et Vincent Pilaud.