Plan de cours, présentation générale et historique

Automne 2019
 Pourquoi êtes-vous ici?
• Parce que les autres cours disponibles
m’intéressent moins ?
• Par intérêt personnel (cours à option) ?
• Pour me préparer à design III ?
• Maitrise IA professionnel ?
• Pour faire carrière dans le domaine ?
• Pour poursuivre des études dans le domaine ?

GLO-4001/7021 Introduction à la robotique mobile 2

 Plan de cours

GLO-4001/7021 Introduction à la robotique mobile 3

 Informations générales

Site web du cours

http://www.ift.ulaval.ca/~pgiguere/cours/IntroRobotique/index.html

Disponibilités : mercredi 14h00 à 16h00 PLT-3976

Accommodements scolaires ou absence aux examens :

rapport d’anomalie (2 premières semaines)
http://www.fsg.ulaval.ca/fileadmin/fsg/documents/PDF/Politique-Facultaire-Accommodements.pdf.

GLO-4001/7021 Introduction à la robotique mobile 4

 Manuel du cours : 2 proposés
• Manuel utilisé par le
passé

• Disponible sur Amazon

GLO-4001/7021 Introduction à la robotique mobile
• Je le connais moins
5
 Autres références

Version électronique téléchargeable

via librairie U. Laval
GLO-4001/7021 Introduction à la robotique mobile 6
 Évaluations
Examen intra : mardi 22 octobre. 1 feuille au plomb, recto-verso
Examen final : mardi 17 décembre. 2 feuilles au plomb, recto-verso
(dont celle de l’intra)
2 travaux pratiques
Présentation orale de 15 min. pour GLO-7021, 29 nov, 8%.
Projet
GLO-4001 GLO-7021
Taille des équipes 1-4 1-3
Rapport écrit 17 % 17 %
(incluant résumé 3-5 articles)
Objectif Démontrer l’assimilation Assimilation et pousser plus
des concepts du cours loin que ce qui est vu en classe
Portée Démo / reproduction de Cas idéal : mènerait à une
résultats publication scientifique
Proposition de projet : 8 novembre Rapport final : 22 décembre
Démo filmée : pour éviter le stress du « live »…
Prêt des équipements en fonction de la taille des équipes 7
 Rapport du TP et retards
• Pour étudiants 2ème / 3ème cycle, rapport en latex  pdf
• MikTex sur Windows, pdflatex sur Ubuntu
• Overleaf en ligne.
• Toujours fournir le code source
• Retards : -10% -20% -30%

78%
68%
58%
48%
remise
23h55
0%
remise +
1jour
8
 Politique sur le plagiat
• Veuillez en prendre connaissance

GLO-4001/7021 Introduction à la robotique mobile 9

 Robots + capteurs
Kobuki Kangaroo
gyroscopes
(interne)

tous accessibles à partir de matlab ou python

odométrie
(11.7 impuls./mm)

télémètre infrarouge
scanneur
laser 2D 2x Kinect
10
 Laboratoires du vendredi
• ~9 séances d’expérimentations
– familiariser avec les capteurs et le robot
– application concrète et visible des algorithmes
• 14 robots
• Vendredi 8h30-10h20 ou 10h30 à 12h20
– selon votre inscription
• Instructeur: Maxime Vaidis
• Premier laboratoire: 13 septembre

11
 3 facettes
(1) Boîte à outils des connaissances,
technologies et algorithmes utilisés en
robotique mobile

algorithmes
(2) Développer une compréhension verticale
capteurs actionn. et holistique d’un système robotisé
environnement

(3) Expérimenter!

GLO-4001/7021 Introduction à la robotique mobile 12

 Pourquoi la robotique mobile?
• … ne pas manquer le bateau…
• Prochaine révolution technologique? (Industrie 4.0)
– machine à vapeur
– chemin de fer Google car (Waymo)
– radio/télévision
– informatique
– réseautique (Internet)

on construit 60 millions
GLO-4001/7021 Introduction à la robotique mobile voiture par an… 13
 Pourquoi la robotique mobile?
• Waymo (Google) • nuTonomy
• Zoox • Argo AI
• Tesla • AutoX
• Uber ATG • Cruise Automation
• Nissan • Lyft
• Toyota Research Institute • NIO
• Bosch R&D (Palo Alto) • et +…
• Groupe Volkswagen (Audi)
• Ford

GLO-4001/7021 Introduction à la robotique mobile 14

 Pourquoi la robotique mobile?
• Kiva system (inspiré de RoboCup, 775 M$ Amazon)

15
 Pourquoi la robotique mobile?
• Endroits dangereux pour les humains
– Centrales nucléaires Fukushima en 2011

GLO-4001/7021 Introduction à la robotique mobile 18

 Pourquoi la robotique mobile?
• Exploration spatiale

Sojourner
(1997)

Curiosity (2012)
Spirit + Oportunity
(2003) 19
 Pourquoi la robotique mobile?
• Entretient ménager

Roomba de iRobot Neato Robotics Asus

d’Husqvarna
Automower

LawnBott
GLO-4001/7021 Introduction à la robotique mobile 20
 À quand la certification des V.A.?
• Taux de mortalité : 1.09 / 100 millions miles
• Pour démontrer fiabilité d’un V.A.
– conduire environ 8.8 milliards de miles
– Pour 100 V.A., 24h/365j @25 m/h: 400 ans!

Beaucoup de Certification
V.A. sur la route des V.A.

N. Kalra, S. M. Paddock, Driving to Safety: How Many Miles of Driving Would It

21
Take to Demonstrate Autonomous Vehicle Reliability? RAND Corporation, 2016.
IBM Roomba-Based Robot Measures Data Centre Heat

Vous devriez comprendre ce

diagramme à la fin du cours
http://www.techweekeurope.co.uk/news/ibm-roomba-data-centre-heat-emc-117925 22
Vue générale de la robotique mobile

23
 Boucle sense-think-act
Abstrait intelligence
(algo)

Réalité

capteurs modifie env. actionneurs

(moteurs)

• batteries
• communication (radio)
GLO-4001/7021 Introduction à la robotique mobile 24
 Tout est étroitement imbriqué
• Bons capteurs ($)
– facile d’interpréter l’information (perception)
– algorithmes traitement moins poussés
– e.g. caméra 3D Kinect vs. 1 caméra RGB
• Bons actionneurs/design mécanique
– « intelligence mécanique »
– réduit les besoins en capteurs et intelligence

RHex
25
 Expérimentation en robotique
• Permet de voir si la théorie tient la route!
– Nos approximation sont-elles valides?
– Est-ce que nos modèles (capteurs) sont valides?
– L’algorithme est-il robuste?
– A-t-on pensé à tout?
– Qu’en est-il des changements de lieu d’opération,
d’éclairage, de température, sol, météo, etc.
– « when the rubber meets the road »
En théorie, il n’y a pas de différence entre la théorie
et la pratique, mais en pratique, il y en a une.
GLO-4001/7021 Introduction à la robotique mobile 26
 Robotique vs. Robotique Mobile
• Travail dans un espace beaucoup plus grand
– quelques m3 pour un bras robotisé vs. plusieurs
millions de m3 pour un véhicule routier autonome
• Beaucoup plus d’inattendus
– environnements non-contrôlés
– distributions à longue traîne

GLO-4001/7021 Introduction à la robotique mobile 27

Apprentissage automatique + robotique
• Pour améliorer les performances du système

GLO-4001/7021 Introduction à la robotique mobile 28

Problématique de la robotique mobile

Aller de A à B
monde W

A
B

• Décliné en plusieurs sous-objectifs

GLO-4001/7021 Introduction à la robotique mobile 30
 Sous-problème 1

Où suis-je?
Xt  ?
• A: En me basant sur mes commandes u?
• B: En me basant sur un capteur? deux capteurs?
dix capteurs? Les plus fiables seulement?
(fusion d’information)
• En combinant A et B?
31
 Sous-problème 2

Comment me déplacer?
• Plusieurs designs mécaniques possibles
• Roues, pattes, chenilles, ailes, hélices
• Quelles sont les modèles (équations) de
déplacement selon les commandes u?

32
 Sous-problème 3
Carte du monde
• Comment représenter le monde W? (problème universel
de la représentation de la connaissance en IA)

obstacles : polygones? obstacles : grille d’occupation

• Choix intimement relié avec la tâches à accomplir

• Compromis entre : mémoire - temps de calcul - précision
33
 Sous-problème 4
Perception
• Identifier les objets statiques et objets
dynamiques (véhicules, vélos, piétons)
• Faire le suivi des trajectoires
– Modèles de déplacement
– Complexité : Voiture < moto < vélo < piéton
• Crucial pour les voitures autonomes

(OEDR: object and event detection and response)

GLO-4001/7021 Introduction à la robotique mobile 34
 Sous-problème 4
Perception
• Forte influence du Deep Learning
Réseau YOLO

• Deep n’est pas couvert dans ce cours

GLO-4030/7030 Apprentissage par réseaux de neurones profonds
35
 Sous-problème 5
Quelle trajectoire suivre
entre A et B?
• Planification (path planning)
• Basé sur la carte du monde W + la trajectoire
des objets dynamiques (véhicules, piétons, etc.)
• Contente souvent d’une solution sous-optimale
• Critères supplémentaires à minimiser :
• le temps
• le risque (ravin, mines, détection par ennemi)
• l’énergie (en vélo on évite les côtes…)
• la probabilité de se perdre (navigation côtière/coastal
navigation)
• complexité des instructions (GPS qui retourne 300 virages?) 37
 Sous-problème 6
Comment construire une carte?
Robot démarre sans carte du
monde : tabula rasa
monde W ?
?
A ?
?
? ? ?
carte du monde, Grèce antique

38
 Sous-problème 6
Comment construire une carte?
• SLAM : Simultaneous Localization and Mapping

Pose
X
pour pour
estimer la créer
pose la carte

carte
m

39
 Sous-problème 7
Suis-je déjà passé par là?
• Pour ne pas dupliquer les lieux dans la carte
• Fermeture de boucle pour SLAM
• Reconnaissance de lieux (par vision)
“Corn maze”

crédit photo: the Armstrong Hotel 40

 Vue d’ensemble
carte
planification
m
Commandes
u
Pose
X

Mesures z actionneurs

capteurs

41
 Approche traditionnelle vs. Deep
Modèles Agent autonome
dynamiques
Estimateur (traditionnel)
d’état
Capteurs
Détecteur Planificateur Contrôleur Actionneurs
objets

Agent end-to-end
(Deep learning)
Capteurs Réseau de neurones Actionneurs

Difficile de débugger/vérifier/certifier
une approche non-modulaire! 42
 Paradoxe de Moravec
• Raisonnement de haut niveau est plus facile à reproduire
dans un robot que les aptitudes sensorimotrices
• Selon Moravec, l’évolution explique ce paradoxe
• Tâches sensorimotrices
– perfectionnées durant des millions d'années (œil: 400M ans)
– co-évolution sens, muscles, système nerveux
• Facultés de raisonnement
– apparues très récemment sur le plan biologique
– ne se sont pas encore aussi perfectionnées
Ce qui vous semble simple est
souvent difficile pour un robot
43
https://en.wikipedia.org/wiki/Moravec%27s_paradox
Paradoxe de Moravec

45
 Gestion de l’incertitude : probabilités
• Changement de paradigme : stochastique
déterministe (en partie aléatoire)
représentation

Variable aléatoire X
Variable x

p(x)
float x;
x
float x, sx;

• Devra connaître (approximer) les distributions pour :

– l’état X du système
– les mesures z des capteurs
– les commandes u (déplacements)
– etc
46
 Outils mathématiques
• Robotique mobile combine plusieurs outils
– trigonométrie
– algèbre linéaire (matrice)
– calcul différentiel (Jacobienne) et intégral
– probabilités et statistiques
• Sera l’occasion de les appliquer de manière
concrète

47
 Outils mathématiques

ON
Et
Non
Moi-même
derrière
mes
sur
NE
non
mon
TOUCHE
outils,
mais
mon
j'y
établi,
c'est
ai
char,
c'est
PAS
jamais
ysacré.
parce
j'ai
aÀmesMES
mon
touché.
que
outils.
OUTILS!
établi.
moi dans
mon garage,
« …Et su mon établi, y a MES outils. Et ça, mes outils, c'est sacré. O.K.
là? Bon. ON TOUCHE PAS À MES OUTILS! Moé-même j'y ai jamais touché. »
Yvon Deschamps, « Les adolescents » 48
 Exemple d’application des outils math.
• Objet en chute libre, départ à hauteur h0 et angle q0, mesures bruitées
(V) de distance l via capteur infrarouge, vitesse angulaire w (rad/s) via
gyroscope. Cherche la hauteur h(t) et l’angle q(t).
Probabilités : Filtre Kalman Étendu
1 2
1 T  
Algèbre linéaire :
T
x(k  1)    x(k )   2 g
 
0 1 
 T  Intégrale : h(t )   accélération
capteur de
distance
h
Trigo : l = r
cos(q )
q
g=9.8 m/s²
l h
Mesure
z

(Projet de 2013) 49
Contenu du cours

51
 Contenu (1)
• Introduction et historique

• Révision (au fil des cours)

– algèbre linéaire (matrices et vecteurs)
– trigonométrie
– dérivée et intégration
– probabilités

GLO-4001/7021 Introduction à la robotique mobile 52

 Contenu (2)
• Capteurs standards en robotique
– encodeurs d'angle
– sonar
– télémètres infrarouge (labo!)
– télémètres laser (labo!)
– GPS (Global Positioning System)
– centrale inertielle (accéléromètres et gyros) (labo!)
– magnétomètres

GLO-4001/7021 Introduction à la robotique mobile 53

 Contenu (3)
• Capteurs visuels
– caméra simple (modèle pin-hole) (labo!)
– paire de caméras stéréo
– caméra 3D Kinect de Microsoft (labo!)
– caméra « temps de vol » (phase)
– marqueurs fiduciaires
– descripteurs SIFT, SURF, ORB (labo!)
– descripteurs quantifié : approche bag-of-words
• Odométrie visuelle
GLO-4001/7021 Introduction à la robotique mobile 54
 Contenu (4)
• Estimation robuste (RANSAC) (labo!)

• Locomotion (à roues) (labo!)

• Cinématique directe et cinématique inverse

GLO-4001/7021 Introduction à la robotique mobile 55

 Contenu (5)
• Représentation de l'espace et planification
– Cartographie (métrique, topologique, topométriques,
grilles d’occupation)
– Navigation :
• graphes de visibilité et de Voronoï
• champs de potentiels
• rapidly exploring random trees RRT
• Calage de nuage de points ICP (labo!)

GLO-4001/7021 Introduction à la robotique mobile 56

 Contenu (6)
• Fusion de capteurs
– modélisation
• Estimation d'état (Localisation) :
– filtrage Bayésien
• filtre de Kalman (labo!)
• filtre de Kalman étendu
• filtre de Kalman non-parfumé
• filtre à particules
• filtre Rao-Blackwelllisé

GLO-4001/7021 Introduction à la robotique mobile 57

 Contenu (7)
• Simultaneous Localization and Mapping (SLAM)
– Problématique du loop closure
• Reconnaissance de lieu par vision : Visual SLAM
– par filtre EKF
– par filtre Rao-Blackwellisé : FastSLAM
– par optimisation non-linéaire de graphe :
GraphSLAM

GLO-4001/7021 Introduction à la robotique mobile 58

 Autre vue du cours

algorithmes
paramètres
modélisation probabiliste

principe de fonctionnement
des capteurs + déplacements

59
Historique

60
 Talos : 400 av. J.-C.
• Homme géant de bronze
• 3 tours/jours
• Côte de Crète :1 046 km
• Vitesse moyenne: 130 Km/h

61
 Héron d’Alexandrie 10-70 ap. J.-C.

tube pneumatique
•Ingénieur et mathématicien grec
•Traité des automates Αυτόματα
•Un des premiers capteurs: l’odomètre

L'éolipyle
« boule d’Éole »

GLO-4001/7021 Introduction à la robotique mobile

Automates de Léonard de Vinci (1452-1519)

automate programmable
64
 Automates “modernes”

« Canard Digérateur » de
Jacques de Vaucanson « Le turc mécanique », 1770
1793 Gagnant contre Napoléon
Bonaparte, Benjamin Franklin,
Catherine de Russie
GLO-4001/7021 Introduction à la robotique mobile 65
 Automates “modernes”

« Canard Digérateur » de
Jacques de Vaucanson « Le turc mécanique », 1770
1793 Supercherie découverte en 1820
seulement!

GLO-4001/7021 Introduction à la robotique mobile 66

 Amazon Mechanical Turk
• Pour faire du « crowdsourcing » de tests en
intelligence artificielle

GLO-4001/7021 Introduction à la robotique mobile 67

Automates servant le thé, 19ème siècle, Japon

GLO-4001/7021 Introduction à la robotique mobile 68

Nikola Tesla (1898)
Brevet américain 613 809

69
Invention du terme “Robot” (1923)
• “Rossum's Universal Robots” par Karel Čapek.
• Tchèque robota  travail forcé

• Après plus de 2 000 ans, le concept d’être artificiel

intelligent est finalement baptisé! 70
 Missile V1 (1944)

autopilote capteur

actionneur
GLO-4001/7021 Introduction à la robotique mobile 71
 Robots mobiles (1950)
• La Tortue (turtoise) de Walter

GLO-4001/7021 Introduction à la robotique mobile 72

 Un précurseur du Roomba?

GLO-4001/7021 Introduction à la robotique mobile 73

 Shakey (1966 -1972 )
• Shakey
– Stanford Research Institute/SRI
– premier robot “autonome” : IA
• Capteurs
– télémètre optique
– caméra pivotante
– pare-chocs tactiles
• Ordinateur avec 192 Ko mémoire
• Monde simplifié (cube world)
• Reconnaissance objet
• Action simples (pousser objet)
• Trajectoire vers l’objet
• Planification avec STRIPS (symbolique)
GLO-4001/7021 Introduction à la robotique mobile 74
 Shakey (1966 -1972 )
• Démontre planification, algorithme de vision,
localisation via repères visuels (coins de plancher)

75
 Stanford Cart (1973-1979)
– Développé par Hans Moravec

– Imagerie stéréo par caméra

glissante

– Évaluation automatique de la
distance vers les obstacles

– Suivi de lignes blanches au sol

– Environ 15 minutes pour

chaque mètre de déplacement!
GLO-4001/7021 Introduction à la robotique mobile 76
 Véhicule robotisé (fin 80)
• VaMoRs: conduite sur autoroute
• Suivi des lignes blanches avec filtre de Kalman
• Que faire si ligne blanche disparaît?

GLO-4001/7021 Introduction à la robotique mobile 80

 Suite du projet VaMoRs
Détection et suivi (tracking) d’autres véhicules

GLO-4001/7021 Introduction à la robotique mobile 81

 ALVINN (1992)
Autonomous Land Vehicle In a Neural Network
commande
direction

réseau
neurones

30x32
image Video Input
Retina

115 km/h sur 150 km autoroute

GLO-4001/7021 Introduction à la robotique mobile 82

 Navlab 5 du CMU (mi-90)
• Conduite autonome sur 2797/2849 miles
(98.2%) d’autoroute : traversée des États-Unis
• Accélérateur et frein commandé manuellement

83
 DARPA Grand Challenge (2004)
• But: conduite
autonome dans le
désert sur trajet de
240 km
– Prix: 1 million $
– Meilleure équipe :
11.8 km!

GLO-4001/7021 Introduction à la robotique mobile 84

 DARPA Grand Challenge (2005)
• Prise 2, sur 212 km
– 5 équipes finissent la course!
 DARPA Urban Challenge (2007)
• Conduite autonome urbaine sur 96 km.
BOSS de
Carnegie
Mellon
University

Aurora
GLO-4001/7021 Introduction à la robotique mobile 86
« Google Car » (2010)

87
 Ford aussi… (13 déc. 2013)

http://www.motorauthority.com/news/1089080_ford-testing-autonomous-
driving-with-fusion-hybrid-research-vehicle
GLO-4001/7021 Introduction à la robotique mobile 88
 2015 Darpa Robotics Challenge (DRC)
• 1. Drive a utility vehicle at the site. • 5. Climb an industrial
• 2. Travel dismounted across rubble. ladder and traverse an
• 3. Remove debris blocking an entryway. industrial walkway.
• 4. Open a door and enter a building. • 6. Use a tool to break
through a concrete panel.
• 7. Locate and close a valve
near a leaking pipe.
• 8. Connect a fire hose to a
standpipe and turn on a
valve.

GLO-4001/7021 Introduction à la robotique mobile 89

 Nvidia end-to-end learning (2016)
• Basé sur les réseaux de Actionneurs (volant, pédales)

neurones profonds
convolutifs (CNN)

250,000 paramètres
Apprentissage

http://images.nvidia.com/content/tegra/automotive/images/
2016/solutions/pdf/end-to-end-dl-using-px.pdf 3 caméras 90
Nvidia end-to-end learning (2016)

GLO-4001/7021 Introduction à la robotique mobile 91

Exploration Mars

Curiosity
Spirit+Oportunity (2012)
(2003)

Sojourner
(1997)
Exploration Mars
MER (2003) Mars Exploration Rover

• Vitesse : 50 mm/s
• Distance totale: 22 mars juin
2010 2018
– Spirit : 7,7 km.
– Opportunity : 45,16 km.
• Processeur
– RAD 6000 (RISC 32 Bits, 20 MIPS)
– 128 Mo i386 – i486

MSL (2012) Mars Science Laboratory

• Vitesse : 25 mm/s
• Processeur PowerPC
– RAD750 (200 MHz, 266 MIPS)
– 256 Mo Processeurs peu puissants :
algorithmes efficaces!