Equation d'attraction/repulsion pour navigation d'un robot

Réponses à toutes vos questions après le Bac (Fac, Prépa, etc.)
crossrobotik
Membre Naturel
Messages: 18
Enregistré le: 13 Juin 2006, 12:07

equation d'attraction/repulsion pour navigation d'un robot

par crossrobotik » 13 Juin 2006, 15:29

Bonjour a toutes et a tous,

Je suis etudiant en robotique et j'ai un petit probleme avec une notion de physique (trajectoire pour etre plus exact).

Description du probleme :
J'ai un robot equipé de capteur laser (scrutateur laser).
Le laser me renvoie pour chaque angle (tous les 1°) la distance de l'objet detecté (jusqu'a 80m). La mesure se fait toutes les secondes.

Je dois deduire de ces informations la trajectoire que je vais prendre (droite ou gauche). Mais je dois en plus quantifier le poids de l'obstacle selon une priorité (plus il est proche plus je dois l'eviter fortement mais en tenant compte des autres obstacles ...)

Les données que je connais sont celles-ci :
Ma position actuelle : X_act, Y_act, A_act (Angle actuel)
Ma position de destination : X_dest, Y_dest, A_dest

On peut determiner la position de l'obstacle avec la trigonometrie et les données renvoyer par le capteur laser.

Ma question : (j'y reflechis depuis pret d'un mois et je ne trouve pas grand chose).
Comment mettre en equation le systeme de calcul de la trajectoire.
Soumettez moi vos idées, meme partielles.
Merci pour vos reponses



Avatar de l’utilisateur
mathelot
Habitué(e)
Messages: 13688
Enregistré le: 08 Juin 2006, 09:55

par mathelot » 13 Juin 2006, 16:42

est-ce qu'on peut assimiler le champ de vision à un cercle trigonométrique dans un plan horizontal dont l'oeil du robot est le centre. Le cerveau du robot découpe 360 petits arcs de cercle de un degré , pour chaque arc, il note 1 si l'arc est dégagé de tout obstacle, zéro s'il est obstrué et avance d'un pas dans la direction médiane du plus grand arc de cercle dégagé de tout obstacle si sa taille lui permet de passer.Ensuite,au bout d'un pas,il recommence l'algo.
dis-moi si je rêve ?

crossrobotik
Membre Naturel
Messages: 18
Enregistré le: 13 Juin 2006, 12:07

par crossrobotik » 13 Juin 2006, 17:05

en fait le champs de "vision" est de 180°, ta methode fonctionne dans certain mais pas dans le mien... je m'explique :
Ta methode ne permet pas de determiner la priorité d'evitement de l'obstacle, donc tu va très vite te retrouver coincé.
- prend par exemple deux obstacle un a 50cm et un 4m, celui qui est loin ne presente pas d'interet pour tout de suite alors que le plus pret presente un danger, ton algo ne permet pas de differencier les 2 et tu va te bloquer :'(

La reflexion est bonne mais il faut poursuivre un peu plus loin, j'ai recherché pas mal de document sur Google et on trouve enormement de thèse mais aucune n'est très explicite sur l'equation mathematique (dommage)

En tout cas merci de m'avoir repondu, je continu mes recherche de mon coté mais si quelqu'un trouve une solution, je le remercie de l'indiquer ici ;)

Avatar de l’utilisateur
mathelot
Habitué(e)
Messages: 13688
Enregistré le: 08 Juin 2006, 09:55

par mathelot » 13 Juin 2006, 23:40

peux-tu préciser quelques hypothèses ? est ce que le robot a un "diamètre"
d qui l'empêche de passer entre deux points A, B tel que d(A,B)<= d ?
y a t il des radiales (demi droites d'origine le centre du laser) qui peuvent
être dégagées jusqu'à l'infini ? acceptes-tu une solution discrète ou cherches-tu
au contraire des équations différentielles? et enfin ton mail est adressé
à des roboticiens ou à tout un chacun ?

crossrobotik
Membre Naturel
Messages: 18
Enregistré le: 13 Juin 2006, 12:07

par crossrobotik » 14 Juin 2006, 10:22

Le robot est rectangulaire, il fait 2m de longueur pour 1m10 de largeur.
Il dispose de 3 roues dont 2 roues folles, la roue principale est a la fois motrice et directrice.
Le capteur laser est situé au milieu des roues folles. Ce capteur a une portées de 80m, il renvoie la distance de l'obstacle ou 80m s'il n'y en a pas.

C'est dommage que je n'ai pas de dessin :'(
Image
Au niveau des equations je prefererais des equations discretes mais des equations differentiels pourrait aussi aller ^^

Ce mail est adressé à moi et ensuite je le retransmet a des automaticiens

Avatar de l’utilisateur
mathelot
Habitué(e)
Messages: 13688
Enregistré le: 08 Juin 2006, 09:55

par mathelot » 14 Juin 2006, 10:46

je ne suis pas du tout automaticien,désolé. Je te propose d'aller vers
l'abstraction pour obtenir une solution géométrique du problème.
déja pour simplifier, peut on considérer que le robot est un disque
avec un centre et un certain diamètre ?

crossrobotik
Membre Naturel
Messages: 18
Enregistré le: 13 Juin 2006, 12:07

par crossrobotik » 14 Juin 2006, 11:14

Oui le robot peut etre considéré comme un disque avec un diametre, le capteur laser etant le centre de ce disque.
Ce n'est pas une histoire d'automatisme mais une histoire de math plutot !
Avec les données que j'ai, je voudrais faire une equation (probablement complexe avec des dérivées ...)
Que veux tu dire par "abstraction" ?

Avatar de l’utilisateur
mathelot
Habitué(e)
Messages: 13688
Enregistré le: 08 Juin 2006, 09:55

par mathelot » 14 Juin 2006, 11:54

je réfléchis de la manière suivante, si tu veux bien me suivre:
on prend une feuille de papier, on dessine un point R qui est le centre
du robot et un petit cercle C de centre R qui est l'encombrement du robot.
ensuite, on trace des points (extérieur à C) autour du point R qui sont les
points d'impacts du laser, disons 5 points M1,M2,M3,M4,M5 autour de R
Dans la réalité, il y en a 360.
J'ai donc tracé 6 points pour l'instant. J'enferme ces 6 points
dans un grand cercle C1 de centre R qui est le cercle des points à l'infini.
On appelle D le point de destination finale du robot et la demi-droite (RD) recoupe le cercle C1 des points à l'infini en M6. L'idée est de tracer tous les triangles formés avec des triplets de points parmi M1,M2,M3,M4,M5,M6.
Le robot appartient à un ou plusieurs triangles et sa destination
à un ou plusieurs triangles. Pour chaque triangle de 3 points A,B,C
on regarde en considérant les distances d(A,B),d(A,C),d(B,C) si le robot
peut traverser le triangle ABC ou non. Est-ce que l'on est pas ramené à un problème simple,disons un problème de graphe pour trouver une succession
de triangles que le robot doive traverser pour aller dans un triangle
où se trouve sa destination finale D ? ça donnerait une indication
de chemin, une direction. le problème, c'est de réappliquer l'algorithme
un peu plus loin. est-ce que tout ça semble réaliste ?

crossrobotik
Membre Naturel
Messages: 18
Enregistré le: 13 Juin 2006, 12:07

par crossrobotik » 14 Juin 2006, 12:57

Ton système est réaliste, il permet bien d'eviter les obstacles et de trouver un chemin qui mene a la cible ... mais ce qui me gene c'est que ce chemin est flou ... on ne peut pas vraiment donner la direction a suivre au robot, en tout cas pas precisement.
C'est dommage car le systeme de graphe m'aurait bien soulagé !
Meme si le nombre de points est multiplié ça ne collera pas forcement a chaque fois (meme si ça sera corrigé a la scrutation suivante ^^)

J'ai peut etre trouvé une piste qui utilise une autre forme de geometrie : les vecteurs.
Je m'explique :
- Je connais la position de ma cible, donc je peux definir un vecteur qui me conduit directement a cette cible, notons le V1.
- En faisant une scrutation, j'ai une vue d'un obstacle avec un angle et une distance, donc je peux définir un vecteur pour cet obstacle, notons le V2.
- En ajoutant ces 2 vecteurs j'obtiens un vecteur qui me donne la route a suivre !
- Maintenant il faut gerer la priorité des vecteurs, pour les obstacles très proches je dois definir un vecteur de repulsion V2 très fort pour eviter mon obstacles et un vecteur très faibles pour les obstacles plus eloignés.
- Enfin la norme de mon vecteur me donne la vitesse à laquelle je dois allé pour atteindre mon but (je vais donc ralentir a l'approche d'un obstacle ou de ma cible comme cela je serais très precis)

Qu'en pense tu ?

nox
Membre Complexe
Messages: 2157
Enregistré le: 14 Juin 2006, 11:32

par nox » 14 Juin 2006, 14:07

yep

bon chui ptetre totalement hors sujet parce que la robotique c'est pas du tout ma branche...mais j'ai fait de l'automatique et du calcul de trajectoire optimal.

voila comment on gère les obstacles :

l'objet à éviter est modélisé sous la forme C( x(t) ) >= 0 où C : R^n -> R

apres il existe des théories de calculs de trajectoire comme la théorie LQ (linéaire quadratique) ou le Principe du maximum de Pontryagin qui sont relativement simples (surtout avec Matlab et la toolbox control) et qui permettent d'obtenir la trajectoire qui minimise une fonction de coüt (temps minimal, consommation d'énergie minimale etc...). Il suffit alors de pénaliser le coût avec l'intégrale de 0 au temps final de max(0, c (x(t) ) (intégrale éventuellement pondérée par un coefficient) pour obtenir la trajectoire optimale permettant d'éviter l'obstacle.

Je sais pas si l'explication est tres claire, ou si elle est d'une quelconque utilité mais bon...voila toujours une piste de recherche supplémentaire au cas où.

Avatar de l’utilisateur
mathelot
Habitué(e)
Messages: 13688
Enregistré le: 08 Juin 2006, 09:55

par mathelot » 14 Juin 2006, 14:42

à mon avis, les notions de géométrie pour définir la trajectoire
sont les vecteurs uniquement pour déterminer des directions de droites
et les distances entre les points, distances que l'on peut calculer
en transformant les coord. polaires des points en coord. cartésiennes.
la vitesse du robot n'est pas à prendre en compte. deux outils
intéressant: l'enveloppe convexe de n points qui est le plus petit
polygone convexe contenant les n points et la triangulation qui est le
découpage de l'espace délimité par les n points (leur enveloppe convexe)
en triangles,ceçi dit le problème reste entier !!! on peut travailler
dans un demi-disque délimité par les points à l'infini (rayon=80m)
et je cherche à trianguler notre espace de travail (le découper
en triangles). autre remarque: le meilleur moyen de passer au plus loin de deux points A et B quelconques est de viser le milieu de [AB].
dans ta recherche, il faut que tu tiennes compte des distances entre les
points à cause du diamètre du robot et pas seulement des directions
à prendre.

Avatar de l’utilisateur
mathelot
Habitué(e)
Messages: 13688
Enregistré le: 08 Juin 2006, 09:55

par mathelot » 14 Juin 2006, 15:37

nox, on va peut être avancer en s'y mettant à plusieurs, les objets à
éviter à la première scrutation sont des lignes polygonales (lignes brisées)
éventuellement fermées (elles délimitent alors des zones interdites). ces lignes
brisées sont les lignes de sommets où les sont les points détectés par le laser à la première scrutation avec où t est le diamètre du robot.

crossrobotik
Membre Naturel
Messages: 18
Enregistré le: 13 Juin 2006, 12:07

par crossrobotik » 14 Juin 2006, 15:53

Nox j'ai regardé la theorie et le principe mais je crois que c'est beaucoup trop compliqué pour moi et pour ce que je veux faire. En fait je n'ai pas compris les equations ... Mais c'est surement une très bonne methode (juste trop compliqué pour quelqu'un comme moi ^^)

Mathelot, je vois que tu comprend la ou je veux en venir !
En fait je n'ai pas besoin de definir de trajectoire a suivre, puisque a chaque scrutation je prend une decision sur la direction a prendre...

La vitesse est externe a mon equation. supposons la constante.

Ce qu'il me faut maintenant c'est les equations qui vont regir le systeme de vecteur... et là ça coince ... car il faut tenir compte de la priorité de l'obstacle, de la distance a parcourir pour arriver à la destination voulue ...

Voila comment je vois les choses, Plus on est eloigné de la destination plus les obstacle doivent etre prioritaire (pour les eviter) mais si on est proche de la destination alors la destination est prioritaire ...

En gros je vais faire fonctionner mon robot comme le courant d'une riviere ... Un rocher au mileu de l'eau est a eviter et la destination est comme un tourbillon !

nox
Membre Complexe
Messages: 2157
Enregistré le: 14 Juin 2006, 11:32

par nox » 14 Juin 2006, 16:04

np crossrobotik ^^

si vous vous en sortez vraiment pas je calculerai les équations exactes si tu veux. C'est la théorie classique pour le calcul de trajectoires donc ca devrait marcher :)
Ca me prendra plus de temps par contre et c'est vrai que c'est pas la meme maniere de raisonner. Disons que ca peut etre la solution de secours :p

Tenez moi au courant

crossrobotik
Membre Naturel
Messages: 18
Enregistré le: 13 Juin 2006, 12:07

par crossrobotik » 14 Juin 2006, 16:07

je compte bien trouver une solution simple et qui fonctionne bien !
Et ce qui est sur c'est que je posterais la solution definitive ici car je pense que je ne suis pas le premier a chercher se genre de chose et surement pas le dernier !

En tout cas je te remercie de ton aide Nox ;) en cas de probleme je ferais surement appel a toi pour m'expliquer ta solution ^^

Avatar de l’utilisateur
mathelot
Habitué(e)
Messages: 13688
Enregistré le: 08 Juin 2006, 09:55

par mathelot » 14 Juin 2006, 17:25

je crois avoir une solution niveau classe de terminale.
imagines qu'on doive éviter trois chiens en laisse qui aboient, attachés
à des points A,B,C et qu'on doive traverser le triangle ABC sans se faire
mordre. On va se situer sur la médiatrice de [AB] pour laisser les points A et
B à égale distance. Une fois arrivé au centre du cercle circonscrit de ABC,
on peut bifurquer sur une autre médiatrice du triangle ABC et ainsi traverser
le triangle ABC. j'en reviens au problème: à la 1ère scrutation, on détecte
n points M1,M2,..,M_{n} qu'il s'agit d'éviter. On découpe l'espace
en triangles de sommets M_{i} (triangulation) . on remplace l'ensemble des points M_{i} à éviter par le graphe G qui a pour sommets les centres des cercles circonscrits des triangles.
On se déplace sur ce nouveau graphe G à cause du principe des chiens. On est ramené à trouver un plus court chemin sur le graphe G par l'algorithme de Dijkstra (niveau Terminale) depuis le centre R du robot jusqu'à la destination. ça donne un plus court chemin qui évite les points M_{i}. En partant de R,
le centre du robot, on va au sommet suivant sur G et là et on recommence tout l'algo. qu'en penses-tu ?

Avatar de l’utilisateur
mathelot
Habitué(e)
Messages: 13688
Enregistré le: 08 Juin 2006, 09:55

par mathelot » 14 Juin 2006, 23:34

finalement, j'en suis arrivé à une densité de probabilité de présence d'un solide
en chaque point du plan, puisque l'information cartographique est parcellaire, à chaque étape, chaque nouvelle scrutation au laser détermine à la fois la trajectoire mais affine aussi la cartographie en modifiant la densité de probabilité de présence d'un solide...bref je jette l'éponge..le problème est trop difficile.

Avatar de l’utilisateur
mathelot
Habitué(e)
Messages: 13688
Enregistré le: 08 Juin 2006, 09:55

par mathelot » 15 Juin 2006, 10:10

on peut imaginer que le robot procède à deux taches qui ont une rétro-action l'une sur l'autre: une tache de cartographie pour laquelle ses mesures de scrutation permettent d'affiner la cartographie et une décision de trajectoire, lors de laquelle il prend une décision de se diriger à un endroit plutôt qu'à un autre. les deux taches réagissent l'une sur l'autre puisque une décision de trajectoire va aller affiner la cartographie dans un endroit précis et un affinage de la cartographie va permettre une décision de trajectoire. faut-il faire des hypothèses sur la densité de probabilité de présence d'un solide
dans le plan inversement proportionnelle en un point aux distances des solides avoisinants et avoir des hypothèses de cartographie:
par exemple si on s'aperçoit que la densité de probabilité de présence d'un solide en chaque point du plan est homogène (constante), on peut très bien être dans une pièce encombrée de mobilier mais aussi dans une forêt où les arbres sont espacés régulièrement. à l'inverse, dans une cartographie inhomogène, on pourrait détecter de grands espaces dégagés et des masses, ce qui indiquerait une cartographie standard en milieu naturel. On pourrait
donc distinguer deux types de topologie selon la répartition des masses: de grands espaces avec des masses ponctuelles (1) ou une répartition homogène qui conduit au parcours du chemin ou du labyrinthe (2). Dans la topologie (1) , on peut imaginer que le robot consacre tout son temps à l'exploration et à la cartographie dans son domaine de liberté et prenne une décision de trajectoire seulement tous les n coups... dans la topologie (2) l'activité exploratoire est réduite car le chemin a de fortes contraintes.

nox
Membre Complexe
Messages: 2157
Enregistré le: 14 Juin 2006, 11:32

par nox » 15 Juin 2006, 10:31

mathelot drogué à la robotique :p

n'empeche que avec tout ça vous allez bien finir par faire un truc nickel !!

on y croit ^^

Avatar de l’utilisateur
mathelot
Habitué(e)
Messages: 13688
Enregistré le: 08 Juin 2006, 09:55

par mathelot » 15 Juin 2006, 11:26

crossrobotik, as tu des hypothèses sur l'environnement: labyrinthe ou forêt, plantation régulière de type verger industriel, espace urbain, déserts, espace intersidéral ? (je les ai ordonnés selon une densité massique décroissante)
est-ce que les obstacles sont fixes ou mobiles ? peux-tu gérer une carte
style "jeu de bataille navale" pour la cartographie ?

 

Retourner vers ✯✎ Supérieur

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 35 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite