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