Platformă de e-learning și curriculă e-contentpentru învățământul superior tehnic
Geometrie computationala
26. Planificarea algoritmica a miscarii
Roboti
lumea realafictiune
Planificarea miscarii robotilor
Spatiu liber
Obstacole
Planificarea miscarii robotilor
• Spatiu de lucru: Mediul in care opereaza robotul
• Obstacole: Spatii deja ocupate in mediul respectiv.
• Spatiu liber: Spatiu neocupat al mediului.
Spatiu de configurare (C-Space)
• Ajuta in determinarea locurilor in care poate merge un robot
• Modelarea unui robot
▫ Configurare: Valori ce specifica pozitia
unui robot
▫ Descrierea formelor geometrice
Planificarea miscarii
Fiind dat un robot, sa se gaseasca o secventa de configurari valide ce deplaseaza robotul de la sursa la destinatie.
start
destinatieobstacole
Spatiul de configurare
• Configurare: Specificarea pozitiei robotului relativa la un sistem de coordonate fix.
• De obicei un set de valori exprimate ca un vector de pozitii/orientari.
• Spatiu de configurare: este spatiul tuturor configuratiilor posibile ale robotului.
Exemplu spatiu de configurare (1)
punct de referinta
x
y
robotdirectie de referinta
spatiu de lucru
– Reprezentare in 3 parametri: q = (x,y,)
– In 3D: 6 parametri - (x,y,z,)
Exemplu spatiu de configurare (2)
X
Y
robot care se poate translata in plan
X
Y
robot care se poate translata si roti in plan
x
Y
C-space:
C-space:
2-D (x, y)
3-D (x, y, )
Spatiu euclidian2R
Exemplu spatiu de configurare (3)
q1
q2
q = (q1,q2,…,q10)
Configuration Space /ObstaclesCircular Robot
C-Obstacles
▫ Convex polygonal robot
Sume Minkowski
A B = { a+b | a A, b B }
Sume Minkowski
• Sumele Minkowski in 3D sunt greu de calculat
• Aplicatii multiple▫ Calcularea spatiului de configurare
▫ Deplasari
▫ Morphing
▫ Analize de amplasarea
▫ Modele de frecare
Planificare in C-Space
• Grafuri de vizibilitate
• Descompunerea celulelor
• Potential Fields
• Multi alti algoritmi
Graf de vizibilitate in C-Space (1)
start
final
Fiecare drum in c-space din start in final reprezinta o miscare
viabila din start in final a robotului in spatiul original.
Graf de vizibilitate in C-Space (2)
Fiecare drum in c-space din start in final reprezinta o miscare
viabila din start in final a robotului in spatiul original.
start
final
Descompunerea celulelor:
descompunere trapezoidala (1)
FINAL
START
1
3
2
4
5 8
7
9
10
11
12
13
6
Se descompune regiunea in celule
Descompunerea celulelor:
descompunere trapezoidala (2)
FINAL
START
1
3
2
4
5 8
7
9
10
11
12
13
6
Se construieste graful de adiacenta
Descompunerea celulelor:
descompunere trapezoidala (3)
FINAL
START
Descompunerea celulelor:
alte abordari
Uniforma Arbori patratici
Metoda potentialului (field potential)
• Campul este modelat printr-o functie de potential
U(x,y) peste spatiul C
• Miscarile se efectueaza in sensul scaderii gradientului
functiei de potential