Planification de trajectoires par échantillonnage IFT702 – Intelligent Design Daniel Castonguay...

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?