bab vi prngantar robotika

Bab VI Mobile Robot Motion Planning

1

Untuk apa Motion Planning?p g• Untuk menentukan kemana akan bergerak

tanpa menabrak halangan (obstacle)tanpa menabrak halangan (obstacle)

2

Materi yang dibahasy g• Dasar

– Ruang Konfigurasi (Configuration Space)– C-obstaclesC obstacles

• Metoda-metoda Motion Planning– Roadmap Approaches

• Visibility graphsV i di• Voronoi diagram

– Cell Decomposition• Trapezoidal Decomposition• Quadtree Decomposition

– Potential Fields– Bug Algorithms

• Referensi :– G Dudek M Jenkin Computational Principles of Mobile Robots– G. Dudek, M. Jenkin, Computational Principles of Mobile Robots,

MIT Press, 2000 (Chapter 5)– J.C. Latombe, Robot Motion Planning, Kluwer Academic

Publishers, 1991.

3

Configuration SpaceNotasi:

A: Obyek kaku (rigid) –(misalnya robot)

W: Ruang Euclidean dimana A bergerak;

B1,…Bm: halangan (obstacle) kaku dan tetap (fixed) tersebar dalam W

32 RatauRW =

tersebar dalam W• FW – KK Bumi (fixed frame)• FA – KK robot (moving frame)

K fi i d i A d l h ifik iKonfigurasi q dari A adalah spesifikasi dari status/keadaan fisik dari A terhadap FW.

B1Bm

4

Configuration Space (Ruang Konfigurasi) adalah ruang semua kemungkinan konfigurasi gerak robot

Configuration Space

Ruang konfigurasi A adalah ruang (C ) semua kemungkinn k fi i Akonfigurasi A.Perhatikan robot titik (free-flying, no constraints)

CCfree

qgoal

Cobs

goal

qstart

5

Untuk robot titik yang bergerak dalam bidang 2-D , Ruang konfigurasi (C-space) adalah 2R

Configuration SpaceC

Ζy

qgoalCfree

Cobs

x

qstart

Untuk robot titik yang bergerak dalam bidang 3-D , Ruang konfigurasi (C-space) adalah 3R

6

Apa perbedaan antara Euclidean space (ruang euclidean) dengan C-space (ruang konfigurasi) ?

Configuration Spaceg pY

Robot bergerak hanya translasi dalam bidang

X

C-space: 2-D (x, y)

X

Euclidean space: 2R

Y Robot bergerak translasi dan rotasi dalam bidang

θθ

XY

C-space: 3-D (x, y, )

7

Xx

Configuration Space

270

360

qrobot

180

β

β90

qsl g

α

α090 18013545

qslug

8

Configuration SpaceRobot akan menabrak halangan jika konfigurasi robot dalam daerah warna biru

270

360

qrobot

warna biru

180

β

β90

qsl g

α

α090 18013545

qslug

Representasi “C-space”

9

Berapakah dimensi dari C-space untuk robot PUMA (6R)?

Visualisari C-space untuk dimensi yang banyak sangat sulit

Motion Planning ProblemMencari jalur bebas halangan (collision free) mulai dari konfigurasi awal menujufree) mulai dari konfigurasi awal menuju konfigurasi akhir (goal) dengan memperhatikan kendala2 (geometri, fi ik t l)fisik, temporal)

Konsep C-space memberikan kerangka kerja umum untuk

l j imempelajari persoalan motion planning

10

Bagaimana jika robot bukan dianggap sebagai sebuah titik ?

11

Bagaimana jika robot bukan dianggap sebagai sebuah titik ?

Memperluas Halangan

12

Obstacles Configuration Spaceg pC-obstacle

13Point robot

Free SpacepFromRobot Motion PlanningJ C L bJ.C. Latombe

14

Minkowski SumsPerluasan bentuk bidang planar oleh bidang lain disebut dengan Minkowski sum ⊕Minkowski sum ⊕

robot persegi yang hanya bergerak translasi

RP ⊕ R

P

P ⊕ R = { p + r | p ∈ P and r ∈ R } (Dilation operation)

15

{ p | p }( p )

Penambahan DimensiBagaimana bentuk ruang C-obstacle jika robot persegi dapat bergerak translasi dan rotasi dalam bidang.

(Kotak biru adalah halangan)

y robot persegi yang dapat bergerak translasi dan rotasi

16x

C-obstacle in 3-D

3 D

Bagaimana bentuk ruang C-obstacle jika robot persegi dapat bergerak translasi dan rotasi dalam bidang.

3-D(Kotak biru adalah halangan)

y 360º

180º

17x 0º

this is twisted...

C-obstacle in 3-D

3 D

Bagaimana bentuk ruang C-obstacle jika robot persegi dapat bergerak translasi dan rotasi dalam bidang.

3-D(Kotak biru adalah halangan)

y 180º

18x 0º

Untuk satu irisanPerhatikan satu irisan dari C-obstacle dimana rotasi robot sebesar 45o

P ⊕ R y

45 degreesR

P

19x

Proyeksi 2-D

y

x

20

Topik yang dibahasp y g

• Configuration Space• Motion Planning Methods

R d A h– Roadmap Approaches– Cell Decomposition– Potential FieldsPotential Fields– Bug Algorithms

21

Metoda Motion Planning Komponen dasar motion planning dapat diuraikan sbb :

Input OutputInput Output• deskripsi geometri robot dan lingkungannya (obstacles) • jalur mulai dari posisi awal

• konfigurasi awal (initial) dan tujuan (goal)

(start) menuju posisi akhir (finish)

qq qgoalqrobot Aplikasi :Robot-assisted surgeryAutomated assembly plansDrug-docking and analysisM i i d

22What to do?

Moving pianos around...

Metoda Motion Planning

(1) Roadmap approachesTujuan mengurangi N-dimensi

k fi i ( fi i(1) Roadmap approaches

(2) Cell decomposition

ruang konfigurasi (configuration space) menjadi pencarian jalur satu dimensi Tujuan menghitung semua ruang bebas(2) Cell decomposition

(3) Potential Fields

Tujuan menghitung semua ruang bebas

Tujuan menghasilkan strategi kendali lokal yang lebih fleksibel dibandingkan( )

(4) Bug algorithms

lokal yang lebih fleksibel dibandingkan dua metoda diatas

Perencanaan jalur dengan pengetahuan yg terbatas

23

Roadmap: Visibility Graphsp y pVisibility graphs: Ruang konfigurasi dalam bentuk poligon atau polyhendral yang membentuk segmen garis yang menghubungkan antar vertex.

24

The Visibility Graph y p

• Pertama kali tarik garis dari titik awal dan tujuan ke semua• Pertama kali, tarik garis dari titik awal dan tujuan ke semua vertex yang terlihat (“visible”) dan sudut (corner) dari Kerangka bumi

goal

start

25

The Visibility Graphy p

• Kedua, tarik garis dari setiap vertex halangan (obstacle) ke vertex dan sudut yang terlihat.

goal

start

26


goal

start

27


goal

start

28

The Visibility Graph y p

goal

start

Karena peta ini dalam ruang konfigurasi (C-space) setiap garis dapat

29

merepresentasikan bagian dari jalur pergerakan dari awal menuju tujuan.

Visibility graph drawbacksVisibility graphs sukar menunjukan jalur optimal pada dimensi yang tinggiyang tinggi

shortest pathshortest path

shortest path within the visibility graph

Tidak ada clearance

30

Roadmap: Voronoi diagramsp g• Generalized Voronoi

Diagram (GVG)Diagram (GVG) membentuk jalur yang berjarak sama (equidistant) terhadap 2 atau lebihterhadap 2 atau lebih halangan (obstacle) termasuk batas-batas ruang (workspace)

• Memaksimumkan clearance antara halangan.

32

• Metoda ini menghasilkan peta jalan (roadmap) yang menghindari halangan seaman mungkin

Voronoi Diagram: Metricsg• Beberapa cara untuk pengukuran jarak,

diantaranya :– L1 metric

• (x,y) : |x| + |y| = const– L2 metric

• (x,y) : x2 +y2 = const

33

Voronoi Diagram (L1)g ( )

id kL1 Tidak memiliki jalur yang j y gberbentuk

kurva

34

Voronoi Diagram (L2)g ( )

35

Metoda Perencanaan PergerakanRoadmap approaches

• Visibility Graph

• Voronoi Diagram

C ll d itiCell decomposition

• Exact Cell Decomposition (Trapezoidal)

• Approximate Cell Decomposition (Quadtree)

Potential Fields

Hybrid local/global

36

Exact Cell Decompositionp

P i (d i i )

Trapezoidal Decomposition:

Penguraian (decomposition) ruang bebas ke dalam bentuk sel trapezoidal & triangular

Grafik konektifitas yang menyatakan hubungan antara sel (Sweepline algorithm)

37

yang berdekatan

Exact Cell DecompositionTrapezoidal Decomposition:

Terdapat beberapa algoritma graph-search untuk menemukan jalur dari posisi awal sampai tujuan

38

Exact Cell DecompositionpTrapezoidal Decomposition:

Posisi jalur terletak di titik tengah ( mid points) garis sambung( mid-points) garis sambung (intersection) antar sel

39

OptimalisasiTrapezoidal Decomposition:

15 cells 9 cells

Cara yang dapat dilakukan hanya memperoleh jumlah minimum sel.

Metoda trapezoidal decomposition eksak (exact) dan lengkap (complete), tetapi tidak optimal

40

( p ), p p

Approximate Cell DecompositionQuadtree Decomposition:

Secara rekursif membagi (subdivides) daerah Q dt

41

g ( )bebas/halangan (free/obstacle (sub)region) kedalam 4 sisi (four quarters)

Quadtree:


42


l i j k if• sel persegi panjang secara rekursif diuraikan menjadi luas yang lebih kecil

• pada tingkat resolusi tertentu, hanya sel yang luasnya terletak dalam ruang bebasyang luasnya terletak dalam ruang bebas yang digunakan

Quadtree

43


Cell decomposition

• Exact Cell Decomposition (Trapezoidal)

• Approximate Cell Decomposition (Quadtree)

Potential Fields

Hybrid local/global

44

Potential Field

– Lokasi tujuan membangkitkan potensial atraktif (attractive potential)b j ik ( ll) b k j jyang bertujuan menarik (pull) robot untuk menuju tujuan

– Obyek halangan membangkitkan potensial repulsif (repulsive potential) yang bertujuan mendorong robot untuk menjauh dari halangan gradien negatif dari potensial total diperlakukan sebagai gaya artifisial– gradien negatif dari potensial total diperlakukan sebagai gaya artifisial yang diberikan kepada robot

-- Jumlah gaya keseluruhan digunakan untuk mengendalikan robot

C-obstacles

45

Potential Field• Perhitungan gaya atraktif untuk menuju ke tujuan

C-obstaclesMenuju nol ketika robot semakin mendekat ke tujuan

46

Attractive potential

Potential Field• Perhitungan gaya repulsif untuk menghindar halangan

47

Potential Field• Jumlah Potensial Attractive potential Repulsive potential

C-obstacle

48

Sum of potentials

Potential Field• pembangkitan gaya artificial (negative gradient)

• Jumlah gaya keseluruhan digunakan untukJumlah gaya keseluruhan digunakan untuk mengendalikan robot

Negative gradient

Equipotential contoursgradient

Total potential

49

p

Potential Field

• Perencanaan dan kendali bergabung dalam satu fungsiPros:

• dapat diperoleh jalur pergerakan yang halus (smooth paths)

Cons:• terjebak dalam lokal minima (perlu ada teknik random walk atau

backtracking untuk menghadapi lokal minima)

C

• pengetahuan tentang bentuk halangan harus jelas (seringkali tidak

mungkin)

50


• Visibility Graph

• Voronoi Diagram

C ll d iti Full-knowledgeCell decomposition

• Trapezoidal decomposition

Full-knowledge motion planning

• Quadtree decomposition

Potential Fields

Bug algorithm Limited-knowledge path planning

51

Bug Algorithms

Goal• diketahui arah dari tujuan

• Hanya memiliki sensor lokal

(walls/obstacles sensor)

52

Start

Bug Algorithms

Perpindahan pada 2 jenis tingkah laku sederhana:

Insect-inspired “bug” algorithmslaku sederhana:

1. Bergerak langsung menuju tujuan

2 M l i h l

“Bug” algorithm

2. Menelusuri halangan (Circumnavigating an obstacle)

1) Mengarah menuju tujuan

2) Ikuti halangan sampai ) g pdiperoleh LOS dari tujuan

3) Kembali ke tahap 1assume a leftist robot

53

leftist robot

bab vi prngantar robotika

Documents