Embed Size (px)
Citation preview
Planification de trajectoires par échantillonnage
IFT702 – Intelligent Design
Daniel Castonguay
Simon Chamberland
Projet conjoint IFT593
Modéliser le robot Azimut-3
Plan
Problématique Apport de l’équipe Démonstration Résultats Améliorations possibles Questions
Plan
Problématique Apport de l’équipe Démonstration Résultats Améliorations possibles Questions
Problématique Planification de trajectoires pour un robot
au sein d’un environnement avec obstacles statiques
ApprochesExactes
Détermine si une solution existe et la retourne Couverture complète de l’espace d’états
Par échantillonnage Discrétise l’espace d’états selon une résolution
croissante Couverture partielle de l’espace d’états
Problématique
Approche par échantillonnage Construction d’une roadmap
1. Échantillonner des états
2. Établir le voisinage
3. Vérifier les collisions
4. Rechercher une solution (DFS, A*, …)
5. Retourner à l’étape 1 si aucune solution
Problématique
Échantillonner des états
Problématique
Établir le voisinage
Problématique
Vérifier les collisions
Problématique
Rechercher une solution
Plan
Problématique Apport de l’équipe Démonstration Résultats Améliorations possibles Questions
Apport de l’équipe
Utilisation de la librairie OOPSMPAuteur Erion Plaku,
http://www.kavrakilab.org/OOPSMP/index.html
Implémentation facile de nouveaux algorithmes de planification
Apport de l’équipe
Implémentation et comparaison de divers algorithmes de planificationGrilleTreillis (lattice)PRM
Séquence aléatoire Séquence déterministe
Apport de l’équipe
Illustration en direct des approches
Apport de l’équipe
Implémentation de différentes méthodes de résolutionMulti-querySingle-query
Exploration incrémentale Lazy collision checking
Apport de l’équipe
Multi-query
Apport de l’équipe
Multi-query
Apport de l’équipe
Multi-query
Apport de l’équipe
Multi-query
Apport de l’équipe
Multi-query
Apport de l’équipe
Single-query exploration incrémentale
Apport de l’équipe
Single-query exploration incrémentale
Apport de l’équipe
Single-query exploration incrémentale
Apport de l’équipe
Single-query exploration incrémentale
Apport de l’équipe
Single-query exploration incrémentale
Apport de l’équipe
Single-query exploration incrémentale
Apport de l’équipe
Single-query exploration incrémentale
Apport de l’équipe
Single-query exploration incrémentale
Apport de l’équipe
Single-query lazy collision checking
Apport de l’équipe
Single-query lazy collision checking
Apport de l’équipe
Single-query lazy collision checking
Apport de l’équipe
Single-query lazy collision checking
Apport de l’équipe
Single-query lazy collision checking
Apport de l’équipe
Single-query lazy collision checking
Apport de l’équipe
Single-query lazy collision checking
Apport de l’équipe
Single-query lazy collision checking
Plan
Problématique Apport de l’équipe Démonstration Résultats Améliorations possibles Questions
Plan
Problématique Apport de l’équipe Démonstration Résultats Améliorations possibles Questions
Résultats
Single-query
Nombre de requêtes résolues
0
5
10
15
20
25
30
35
40
45
50
Lattice Grid PRM Halton Hammersley
Default
Env1
Env2
Env3
Résultats
Single-queryNombre moyen d'états valides utilisés
0
200
400
600
800
1000
1200
Lattice Grid PRM Halton Hammersley
Default
Env1
Env2
Env3
Résultats
Single-queryNombre moyen de chemins entre les états
0
1000
2000
3000
4000
5000
6000
Lattice Grid PRM Halton Hammersley
Default
Env1
Env2
Env3
Résultats
Single-query lazy collision checkingNombre de requêtes résolues
0
5
10
15
20
25
30
35
40
45
50
Lattice Grid PRM Halton Hammersley
Default
Env1
Env2
Env3
Résultats
Single-query lazy collision checkingNombre moyen d'états valides utilisés
0
100
200
300
400
500
600
700
800
900
Lattice Grid PRM Halton Hammersley
Default
Env1
Env2
Env3
Résultats
Single-query lazy collision checkingNombre moyen de chemins entre les états
0
20
40
60
80
100
120
140
160
180
200
Lattice Grid PRM Halton Hammersley
Default
Env1
Env2
Env3
Plan
Problématique Apport de l’équipe Démonstration Résultats Améliorations possibles Questions
Améliorations possibles
Importance sampling« Encourager » les valeurs importantesConcentration de l’échantillonnage le long des
obstacles
Questions?
