\newcommand{\int}{\mathop{\rm int}\nolimits} \newcommand{\cl}{\mathop{\rm cl}\nolimits} \newcommand{\bu}{\bullet} \newcommand{\INT}{\mathop{\bf INTERSECT}\nolimits} \newcommand{\INTp}{\mathop{\bf INTERSECT'}\nolimits} \newcommand{\FILL}{\mathop{\bf FILL}\nolimits} \newcommand{\OVER}{\mathop{\bf OVERLAP}\nolimits} \newcommand{\OVERp}{\mathop{\bf OVERLAP'}\nolimits} \newcommand{\BASE}{\mathop{\bf BASE}\nolimits} \newcommand{\NON}{\mathop{\bf NONOVERLAP}\nolimits} \newcommand{\VALID}{\mathop{\bf VALID}\nolimits} \newcommand{\TOUCH}{\mathop{\bf TOUCH}\nolimits} \newcommand{\id}{\mathop{\rm id}\nolimits} \newcommand{\Im}{\mathop{\rm Im}\nolimits} \newcommand{\scol}{\mathop{\,;\,}\nolimits}
## Motion of Objects in Contact #### J. Hopcroft & G. Wilfong ###### Younesse Kaddar ##### *Article étudié:* **Motion of Objects in Contact** (J. Hopcroft & G. Wilfong, 1986) [Version PDF](/assets/RobotMotionPlanning/Rapport.pdf) / [Slides](/assets/Slides/Motion-of-objects-in-contact/Motion-of-objects-in-contact.html) / [Rapport](http://younesse.net/Robot-motion-planning/Rapport/)

## Introduction ### De l'importance de la contractilité ____ ## I. Espace des configurations ## II. Détermination de **TOUCH** ## III. Connexité et contractilité ## IV. Mayer-Vietoris

I. Introduction

Théorème principal

Article fondateur (1986):

  • premier pas pour poser les bases d’une théorie des transformations d’objets

  • démontre un théorème d’existence de mouvement en contact

Ce que nous avons vu en cours sous la forme:

“Dès qu’il y a un chemin dans l’espace libre, il y a un chemin au contact”.

Théorème principal (Hopcroft & Wilfong):

Il existe mouvement de rotations et de translations entre 2 configurations où les objets forment une composante connexe,

⟹ il existe un mouvement entre ces 2 configurations tel qu’à tout instant, les objets forment une composante connexe.

Illustration du théorème

De l’importance de la contractilité

L’espace des configurations n’est pas contractile

le théorème ne s'applique pas

Illustration du théorème

Illustration du théorème

Espace des configurations

  • Objet: partie de $ℝ^n$

    • convexe
    • compacte
    • égale à l’adhérence de son intérieur
    • bornée par un nombre fini de surfaces algébriques
    • Origine ⟶ position/l’orientation
  • Objet composé:

    • plusieurs sous-objets ⟶ graphe des sous-objets sont qui s’intersectent
    • base: son origine = celle de l’objet composé
  • Configuration: est un vecteur de position et d’orientation des objets

    • espace de configuration
    • $B(x)$ / $b(x)$

Intersection, Chevauchement, Toucher

Si $x$ est une configuration, on dit que deux objets $B_i, B_j$:

   
s'*intersectent* en $x$ si $B_i(x) ∩ B_j(x) ≠ ∅$
se *chevauchent* en $x$ si $\int(B_i(x)) ∩ \int(B_j(x)) ≠ ∅$
se *touchent* en $x$ si $B_i(x) ∩ B_j(x) ≠ ∅ ∧ \int(B_i(x)) ∩ \int(B_j(x)) = ∅$

Ensembles de configurations

Ensemble Configurations $x$ en lesquelles
PROPER chaque objet composé a un graphe associé connexe (objets composés connexes et configurations propres)
VALID chaque objet composé est connexe et est tel que tous les sous-objets qui s’intersectent se touchent (configurations valides)
PROPER
Ensemble Configurations $x$ valides telles qu’il existe (au moins) deux objets
INTERSECT qui s’intersectent en $x$
OVERLAP qui se chevauchent en $x$
TOUCH qui se touchent en $x$
INTERSECT
Ensemble Configurations $x$ propres telles que
BASE la base d’un objet composé intersecte la base d’un autre
INTERSECT

Enfin, on pose \NON ≝ \VALID\backslash\OVER \\ \FILL ≝ \cl(\OVER) ∪ \BASE

INTERSECT

Pourquoi ?: En ajoutant $\BASE \not⊆ \VALID$ à $\cl(\OVER)$, on rend \NON ∪ \FILL\\ = \NON ∪ \cl(\OVER) ∪ \BASE contractile.

INTERSECT </div>

Détermination de TOUCH

Attention avec TOUCH

INTERSECT
\TOUCH = \NON ∩ \cl(\OVER)

Esquisse de preuve:

  • Objets sont

    • égaux à l’adhérence de leur intérieur (pour $⊆$) - de même pour les composés, car $\cl(\int(\bu))$ préseve l’union finie
    • compacts (pour $⊇$)

⟹ on montre que \underbrace{\left\lbrace x \mid ∃i≠ j. \overbrace{A_i}^{\llap{\text{objet composé}}}(x) ∩ \overbrace{A_j}^{\rlap{\text{objet composé}}}(x) ≠ ∅ \right\rbrace}_{\text{noté } \INTp \not⊆ \VALID} = \cl\Bigg(\underbrace{\left\lbrace x \mid ∃i≠ j. \int(A_i(x)) ∩ \int(A_j(x)) ≠ ∅ \right\rbrace}_{\text{noté } \OVERp \not⊆ \VALID}\Bigg)

Par fermeture de $\VALID$:

\cl\Big(\underbrace{\OVER}_{≝\, \OVERp ∩ \VALID}\Big) = \cl(\OVERp) ∩ \VALID

Et enfin

\begin{align*} \TOUCH & = \OVERp^c ∩ \INTp ∩ \VALID\\ &= \OVERp^c ∩ \VALID ∩ \INTp ∩ \VALID\\ & = \underbrace{\OVERp^c ∩ \VALID}_{ = (\OVERp ∪ \VALID)^c ∩ \VALID \, =\, \NON} ∩ \cl(\OVER) \\ & = \NON ∩ \cl(\OVER) \end{align*}

Puis, comme

\BASE ∩ \NON ⊆ \TOUCH
\TOUCH = \FILL ∩ \cl(\OVER)

Connexité et contractilité

INTERSECT

Connexité par arcs

BASE et FILL sont connexes par arcs


Lemme: De toute configuration dans VALID (resp. BASE), il existe un chemin dans VALID (resp. BASE) vers une configuration dans BASE où les origines des objets composés coïncident.


Corollaire: \FILL ∪ \NON = \BASE ∪ \VALID est contractile (et donc connexe par arcs)

Mayer-Vietoris

La suite suivante est exacte:

\begin{align*} H_1(\FILL ∪ \NON) &{\xrightarrow {\partial _{*}}}\,H_0(\FILL ∩ \NON)\\ &{\xrightarrow {(i_{*},j_{*})}}\,H_0(\FILL)\oplus H_0(\NON) \\ & {\xrightarrow {k_{*}-l_{*}}}\,H_0(\FILL ∪ \NON) \\ & {\xrightarrow {\partial _{*}}}\, \lbrace 0 \rbrace \end{align*}

où $i, j, k, l$ sont les inclusions, $\partial _{*}$ est défini à partir de l’opérateur bord

Intuitivement:

  • l’homologie est l’ensemble des invariants topologiques de $X$, indiqués par des groupes d’homologie
  • le $k$-ième groupe d’homologie $H_{k}(X)$ a autant de copies de $ℤ$ que $X$ contient de “trous” de dimension $k$
INTERSECT

Il vient que:

\Big(\underbrace{H_0(\FILL)}_{≃ ℤ}\oplus H_0(\NON)\Big)/\underbrace{\Im (i_{*},j_{*})}_{≃ \,H_0(\TOUCH)} \\≃ H_0(\FILL ∪ \NON) ≃ ℤ
⟹ H_0(\NON) ≃ H_0(\TOUCH)

Puis, on déduit que chaque composante connexe de $\NON$ contient une et une seule composante connexe de $\TOUCH$

IV. Conclusion