implementasi reinforcement learning pada simulasi penentuan jalur robot bertipe line-follower

Prosiding Teknik Elektro & Informatika, Volume 1, Nomor 1, Mei 2012

Implementasi Reinforcement Learning pada Simulasi

Penentuan Jalur Robot Bertipe Line-Follower Anggrahita Bayu Sasmita (13507021), Nur Ulfa Maulidevi (197603092008012010)

Program Studi Teknik Informatika, Sekolah Teknik Elektro dan Informatika, Institut Teknologi Bandung,

Jalan Ganeca 10 Bandung, Jawa Barat, Indonesia

[email protected]

[email protected]

Abstrak-- Line-follower merupakan tipe robot yang

diprogram untuk bergerak mengikuti lajur tertentu

sehingga dapat menjadi agent dalam persoalan pencarian

jalur (pathfinding). Hal ini dapat dilakukan dengan

berbagai macam metode baik dengan menggunakan

informasi tertentu maupun tidak. Solusi yang diberikan

dalam menyelesaikan pencarian jalur terdekat ini

menggunakan akuisisi informasi melalui reinforcement

learning, khususnya Q-Learning. Pembelajaran

dilakukan melalui simulasi. Pada simulasi tersebut, agent

melakukan eksplorasi pada lajur tertentu untuk

memperoleh informasi reward. Informasi ini kemudian

digunakan oleh agent dalam eksploitasinya, yaitu memilih

jalur yang paling efektif dalam percabangan lajur.

Eksploitasi agent dilakukan menggunakan metode Greedy

Best First Search yang dimodifikasi. Implementasi

reinforcement learning mengakibatkan peningkatan

efisiensi yang ditunjukkan dengan reduksi penempuhan

lajur menuju goal state sebanyak 32,39%. Reduksi

tersebut dibandingkan dengan pencarian Depth-First

Search. Angka tersebut relatif terhadap rata-rata pilihan

jalur dalam setiap percabangan. Sebagai kesimpulan,

pembelajaran mesin dapat digunakan dalam akuisisi

informasi pada kasus pathfinding. Informasi tersebut

kemudian dapat diacu menggunakan metode pencarian

informed search. Implementasi pembelajaran mesin ini

dapat dikembangkan lagi dalam dua hal. Pengembangan

pertama dapat dilakukan dengan memodifikasi sensor

robot sehingga dapat mengakomodasi pilihan

percabangan yang lebih banyak. Pengembangan

berikutnya dilakukan dalam modifikasi representasi

state-action untuk digunakan sebagai informasi dalam

metode searching lainnya.

Kata kunci-- Line follower, reinforcement learning, Q-

Learning, Greedy Best-First Search, penentuan jalur,

simulasi

1. PENDAHULUAN

A. Latar Belakang

Dalam keseharian aktivitas masyarakat, pemenuhan

kebutuhan suatu produk didukung dengan adanya kegiatan

produksi dalam aktivitas industri. Pemanfaatan teknologi

robot pada kegiatan produksi merupakan salah satu

pendekatan mekanisasi atas persoalan performansi aktivitas

industri yang fluktuatif.

Dalam kajian pembangunannya, robot memiliki tiga aspek

berupa mekanisme gerak, rangkaian elektrik berupa sensor

dan aktuator, serta program yang mengendalikan kerja robot

tersebut. Untuk kasus-kasus tertentu, kerja robot merupakan

suatu aktivitas dengan algoritma tertentu untuk dipetakan

dalam suatu program. Salah satu kasusnya adalah aktivitas

yang melibatkan penyelesaian penentuan jalur (pathfinding).

Salah satu contoh teknologi robot yang dikembangkan

dalam kegiatan industri adalah robot bertipe line-follower.

Robot ini merupakan suatu perangkat yang melakukan

perpindahan berdasarkan masukan berupa deteksi optik

terhadap lajur kontras [1].

Lajur yang menjadi salah satu persoalan pada line-follower

adalah lajur bercabang. Secara pragmatis, metode pencarian

jalur pada line follower merupakan serangkaian percabangan

kondisional (if-then-else). Hal ini mengakibatkan

peningkatan kerumitan bergantung pada jumlah titik

percabangan dan rata-rata jumlah pilihan pada setiap

percabangan [2].

Permasalahan yang mengakibatkan adanya algoritma yang

kompleks dapat diselesaikan melalui pendekatan metode

pembelajaran mesin [2]. Salah satu metode pada

pembelajaran mesin ialah reinforcement learning. Metode ini

merupakan analogi terhadap metode pelatihan yang

menerapkan aspek reward [3]. Metode ini digunakan sebagai

pembelajaran bagi agent untuk menyelesaikan masalah yang

membutuhkan pengetahuan agent terhadap kondisi per-

bagian kasus dalam detil tertentu.

Jurnal Sarjana Institut Teknologi Bandung bidang Teknik Elektro dan InformatikaVolume 1, Number 1, April 2012

1

My Computer

Rectangle

My Computer

Stamp


B. Rumusan Masalah

Berdasarkan penjelasan mengenai latar belakang persoalan

tersebut, maka pada penelitian ini terdapat dua rumusan

masalah, yaitu.

1. Bagaimana memodelkan reinforcement learning untuk

adaptasi pathfinding pada line-follower?

2. Apa saja perubahan efisiensi pengambilan langkah

robot, baik keuntungan maupun kerugian, apabila robot

dilengkapi dukungan reinforcement learning

dibandingkan tanpa dukungan tersebut?

C. Tujuan

Kedua rumusan masalah tersebut menjadi dasar bagi

tujuan penelitian ini. Oleh karena itu, terdapat dua poin yang

menjadi tujuan untuk menjawab rumusan masalah di atas.

Poin-pointersebut yaitu:

1. Membangun suatu model pembelajaran mesin

reinforcement learning untuk adaptasi penentuan jalur

pada robot bertipe line follower sebagai alternatif

dalam pembangunan robot tersebut pada sisi

pemrograman.

2. Menguji efisiensi robot line-follower dalam

pengambilan langkah pathfinding, baik keuntungan

maupun kerugian, melalui simulasi dengan

pembandingan terhadap metode pathfinding tanpa

reinforcement learning.

2. LANDASAN TEORI

A. Spesifikasi Line-Follower

Robot bertipe line-follower merupakan suatu mesin

terprogram yang memiliki kemampuan bergerak mengikuti

suatu jalur yang telah ditentukan [1]. Robot ini memiliki

sensor optik sebagai pendeteksi jalur. Adapun deteksi

percabangan membutuhkan konstruksi sensor dalam

morfologi tertentu. Sebagai contoh, sensor yang disusun

cembung terhadap lajur memberikan kemampuan deteksi

percabangan bagi robot [4]. Sensor pada spesifikasi untuk

penelitian ini dibatasi dengan kemampuan membaca hingga

empat pilihan percabangan.

Robot line-follower ini bergerak dengan aktuator yang

terhubung dengan roda. Oleh karena itu, robot ini dapat

dilengkapi dengan rotary encoder sebagai sensor untuk

mengukur jarak tempuh. Sensor ini melakukan pengukuran

secara diskrit. Oleh karena pengukuran diskrit tersebut, maka

robot dalam spesifikasi ini memiliki keterbatasan dalam detil

informasi jarak.

B. Metode Reinforcement Learning

Pembelajaran mesin metode reinforcement learning

menjadi suatu pilihan dalam penentuan pengendalian robot

[2]. Metode ini mengasumsikan bahwa lingkungan terdefinisi

sebagai himpunan keadaan (states) S dengan agen (robot)

memiliki pilihan aksi A dengan jumlah tertentu. Untuk setiap

langkah, yang didefinisikan sebagai pembagian waktu secara

diskrit, agen melakukan pengamatan terhadap keadaan

lingkungan, st ,dan memberikan keluaran berupa aksi, at.

Agen mendapatkan suatu reward, R yang

menunjukkan kualitas aksi yang diberikan agen berdasarkan

ekspektasi pemrogram. Agen kemudian melakukan observasi

ulang terhadap lingkungannya, . Keadaan yang dituju

dari metode pembelajaran ini ialah mendapatkan experience

tuples (st, , , ), dan mendapatkan pembelajaran atas

suatu pemetaan keadaan-keadaan untuk mengukur nilai

jangka panjang pada keadaan tersebut. Pemetaan tersebut

didefinisikan sebagai optimal value function.

Salah satu algoritma reinforcement learning yang dapat

digunakan adalah Q-Learning [3]. Algoritma ini memiliki

optimal value function sebagai berikut:

( ) ( ) ( )

Fungsi tersebut merepresentasikan nilai reward akibat

agent mengambil aksi a dari keadaan s yang mengakibatkan

perpindahan keadaan menjadi s’. Parameter merupakan

discount factor sebagai ukuran terhadap reward yang pada

proses berikutnya. Setelah mendapatkan Q-function yang

optimal, terdapat pertimbangan optimasi π*(s) yang

merupakan nilai maksimum dari suatu keadaan.

( ) ( )

Nilai Q-function disimpan dalam suatu struktur tabel

dalam indeks yang mengacu pada state dan action. Untuk

setiap waktu robot menghasilkan aksi, experience tuple

dihasilkan dan tabel untuk keadaan s dan aksi a diperbaharui

dengan acuan sebagai berikut:

( ) ( ) ( )

Dalam pemrograman robot, implementasi reinforcement

learning merupakan dukungan yang mempermudah

hubungan aksi robot terhadap keadaan lingkungan. Suatu

robot dapat memandang sebuah task sebagai fungsi reward

yang lebih terbebas dari bias program dibandingkan melalui

pemetaan kondisional.

Dalam penelitian ini, persoalan penentuan jalur merupakan

suatu persoalan deterministik yang dapat dikategorikan

sebagai exploration problem. Dalam hal ini, agent

membutuhkan tahapan khusus untuk mempelajari lajurnya

dan menyimpan informasi hasil pembelajarannya. Eksplorasi

yang dilakukan sebagai tahapan pembelajaran peta lajur

dilakukan menggunakan strategi pencarian tertentu.

Implementasi Reinforcement Learning pada Simulasi Penentuan Jalur Robot Bertipe Line-Follower

2

My Computer

Rectangle


C. Greedy Best-First Search

Strategi pencarian yang diimplementasikan dalam

penyelesaian pencarian jalur pada penelitian ini

menggunakan metode Greedy Best-First Search. Bentuk

sederhana dalam metode ini adalah mencari pengambilan

estimasi langkah terpendek menuju goal state [5]. Fungsi

yang menghitung estimasi tersebut dinamakan fungsi

heuristik yang dilambangkan dengan h:

h(n) = estimasi langkah terpendek menuju goal

Dalam strategi ini, agent diprogram untuk mengambil

keputusan berupa action dengan nilai reward tertentu. Nilai

reward tersebut menjadi informasi bagi agent untuk memilih

action yang mengakibatkan pengambilan langkah terdekat

terhadap goal. Nilai tersebut didapatkan melalui

reinforcement learning dan digunakan untuk diacu sebagai

fungsi heuristik pada strategi pencarian Greedy Best-First

Search.

D. Depth-First Search

Metode pencarian Depth-First Search (DFS) merupakan

metode uninformed search. Hal ini menunjukkan bahwa

pencarian melalui DFS dilakukan tanpa dukungan informasi

nilai apapun, termasuk jumlah langkah menuju goal state.

Dalam metode ini, agent hanya mampu membedakan state

yang berkedudukan sebagai goal dan yang bukan (Russel,

1995).

Apabila dimodelkan melalui graf pohon pencarian, agent

pada metode DFS melakukan pencarian yang terfokus pada

kedalaman aras di setiap titiknya. Apabila agent sudah tidak

bisa lagi mencari lebih dalam sedangkan ia berada pada state

non-goal, agent akan melakukan backtracking menuju state

pada aras lebih rendah. Agent yang melakukan bactracking

melakukan pencarian melalui sisi yang belum dicari pada

titik di aras yang lebih rendah. Ekspansi dilakukan hingga

agent menemukan goal state.

3. ANALISIS SOLUSI

A. Representasi Pathfinding dalam Model Reinforcement

Learning

Persoalan yang diselesaikan melalui pendekatan

pembelajaran mesin reinforcement learning memiliki

sejumlah keadaan yang tertentu (state) yang diperoleh

berdasarkan aksi (action) yang dilakukan agent. Aksi yang

dilakukan disertai dengan nilai reward tertentu bergantung

pada pendekatan penyelesaian masalah. Melalui proses

learning, agent berusaha mencari sejumlah aksi yang

memberikan nilai reward maksimal hingga goal state

tercapai dan agent menghentikan pencarian action. Proses

learning yang dilakukan dapat disederhanakan sebagai entry

nilai bagi tabel state-action-reward yang menjadi model yang

dibangun sebagai acuan fungsi target dalam kondisi

pengujian.

Dalam penerapan pembelajaran mesin menggunakan Q-

learning, sebagaimana penjelasan pada dasar teori

sebelumnya, terdapat suatu nilai Q yang merupakan reward

akibat pengambilan suatu action dari state tertentu, dengan

suatu nilai tambahan. Nilai ini didapat melalui pengalian

suatu faktor secara rekursif terhadap rangkaian reward pada

agent. Rangkaian reward tersebut mendapatkan referensi

nilai terhadap immediate reward pada goal state.

Sebagaimana penjelasan sebelumnya, goal state bersifat

absorptif sehingga eksplorasi yang mencapai state tersebut

menghentikan eksplorasi agent. Ilustrasi mengenai abstraksi

ini dapat dilihat pada Gambar 1.

Gambar 1: Ilustrasi action (tanda panah)terhadap setiap state (persegi).

Agent memiliki susunan informasi mengenai reward untuk

setiap aksi dalam bentuk table entry yang diperbarui dalam

setiap pembelajaran. Informasi mengenai reward untuk setiap

action dalam state tertentu pada table entry ini diinisiasi

dengan nilai nol. Pembaruan nilai mengacu pada fungsi

Q(s,a) yang telah didefinisikan sebelumnya. Secara ilustrasi,

pembaruan ini diperjelas pada gambar 2.

( )

( )

* +

Gambar 2: Pembaruan table entry berdasarkan aksi akanan yang

memindahkan agen R dari S1menuju S2.

Persoalan yang diharapkan dapat diselesaikan oleh sebuah

robot bertipe line follower dalam tugas akhir ini adalah

persoalan pencarian jalur terdekat menuju keadaan akhir

(pathfinding) yang berkaitan dengan pemilhan jalur dalam

sebuah jalur bercabang. Oleh karena itu, implementasi

learning ke dalam program terlebih dahulu perlu diawali

dengan representasi persoalan pathfinding dalam suatu model

reinforcement learning. Persoalan tersebut dalam hal ini

difokuskan pada penyelesaian melalui Q-learning.

G

akanan

7

3 6

6 8

1

10

0

9

0 8

1 8

1

10

0

Keadaan S1 Keadaan S2

R G R G

Anggrahita Bayu Sasmita, et al.

3

My Computer

Rectangle


Dalam subbab Landasan Teori, telah dijelaskan bahwa

spesifikasi line-follower yang akan digunakan memiliki

kemampuan optimal dalam mendeteksi lajur dan percabangan

empat. Oleh karena itu, representasi model dalam

reinforcement learning pada kasus pathfinding ini dapat

dinyatakan sebagai berikut:

State Set : {s | s = percabangan lajur}

Action Set : {a| a = pemilihan cabang}

Kesesuaian model representasi state-action tersebut

terhadap lajur dapat dilihat pada Gambar 3 dan Gambar 4.

Gambar 3: Contoh jalur (kiri) dan representasi state (lingkaran) terhadap

jalur tersebut (kanan).

Gambar 4: Model state-action terhadap jalur pada Gambar 3

B. Simulasi Eksplorasi

Pembelajaran melalui metode Q-learning dalam persoalan

pathfinding dapat diselesaikan secara episodik. Dalam hal ini,

agent mendapatkan pembaruan untuk keseluruhan nilai

melalui proses pelatihan yang berulang. Di awal

pembelajaran, seluruh nilai diinisiasi dengan nol.

Pembelajaran dimulai dengan menempatkan agent dalam

state tertentu dan memrogramnya untuk memilih action yang

terdapat pada state tersebut hingga ia mencapai goal state.

Keadaan pada goal state merupakan absorbing state sehingga

agent yang telah mencapai keadaan tersebut dengan segera

menghentikan pemilihan action.

Pada metode reinforcement learning dalam tugas akhir ini,

tahap pembelajaran dilakukan melalui eksplorasi oleh agent.

Agent melakukan eksplorasi lajur dengan metode DFS dan

menyimpan urutan state yang dilalui dari awal hingga

mencapai goal state. Setelah mencapai goal state, nilai

reward dihitung menggunakan faktor untuk seluruh state

yang dilalui secara berkebalikan.

Eksplorasi lajur oleh robot disimulasikan oleh agent

dengan strategi seperti DFS. Penggunaan strategi seperti DFS

ini tidak dilakukan untuk mencari goal state, tetapi untuk

memberikan kepastian bahwa agent melakukan eksplorasi

untuk seluruh kemungkinan jalur menuju goal state. Hal ini

dilakukan untuk menghindari pencarian yang mengakibatkan

pengulangan tanpa kondisi akhir (endless loop). Melalui

strategi ini, agent memilih satu action pada setiap state

hingga menuju goal state atau percabangan buntu. Setelah

keadaan tersebut didapat, maka agent akan mengevaluasi

reward apabila keadaan tersebut adalah goal state serta

melakukan bactracking menuju state sebelumnya. Pada state

tersebut, agent kembali memilih percabangan yang belum

dilalui.

Adapun mengenai tahapan simulasi pembelajaran

dijelaskan menggunakan ilustrasi pada Gambar 5 dan

Gambar 6 yang menggunakan contoh model state-action

seperti pada Gambar 4. Dalam contoh berikut, adalah 0,9.

Gambar 5. Kondisi pre-learning

Pembelajaran Episode I

Posisi Awal : p

Pemilihan Jalur Acak : p q r s goal

Pembaruan Tabel :

I

( )

( )

*+

II

( )

( )

* +

III

( )

( )

* +

a

G

b

G

q

r

s

p

goal

0

0

0

0

0

0

0

0

0

0

0

0

0


4

My Computer

Rectangle


IV

( )

( )

* +

Gambar 6. Kondisi pasca pembelajaran episode I

Ilustrasi pada Gambar 5 dan 6 menggambarkan satu

episode eksplorasi yang dilakukan oleh agent dengan lajur

seperti pada Gambar 3 sebagai lingkungan persoalannya

(environment). Eksplorasi dilakukan konvergen hingga

mencapai keadaan akhir. Keadaan tersebut terjadi ketika

agent memiliki informasi reward pada environment-nya

seperti pada Gambar 7.

Gambar.7. Informasi akhir hasil eksplorasi

Simulasi tersebut menunjukkan suatu prosedur pembaruan

nilai sebagai sekumpulan reward dengan suatu susunan

struktur data berdasarkan state dan action tertentu. Nilai tabel

tersebut menjadi acuan bagi agent dalam melakukan

pencarian jalur. Suatu agent membaca keberadaannya dalam

satu state, kemudian secara deterministik memilih state

berikutnya menggunakan acuan fungsi optimal yang

terpetakan dalam tabel tersebut.

C. Analisis Kompleksitas pada Eksplorasi

Strategi eksplorasi yang digunakan pada penelitian ini

adalah DFS. Oleh karena itu kompleksitas algoritma

eksplorasi sangat dipengaruhi kompleksitas DFS.

Kompleksitas DFS dalam notasi big-O adalah O(bd) dengan b

adalah banyaknya pilihan pada satu state dan d adalah

kedalaman persoalan yang dicari penyelesaiannya. Pada

penelitian ini, pencarian menggunakan DFS dilakukan

sebanyak jumlah state (n). Karena percabangan pada

pencarian dibatasi hingga empat pilihan, kompleksitas

algoritma eksplorasi adalah ekponensial yaitu O(n4d).

Oleh karena pada persoalan ini d ≤ n, maka notasi big-O

algoritma eksplorasi dapat didefinisikan sebagai O(n4n).

Dengan kata lain, algoritma eksplorasi pada persoalan dalam

tugas akhir ini memiliki kompleksitas eksponensial.

D. Analisis Eksploitasi Pathfinding dengan Informasi

Reward

Eksplorasi reinforcement learning yang dilakukan pada

simulasi menghasilkan table yang menyimpan nilai reward

untuk pasangan state-action. Nilai tersebut menjadi informasi

bagi agent untuk mengambil keputusan dalam memilih

percabangan pada tahap eksploitasi. Nilai reward tersebut

dapat digunakan sebagai informasi heuristik bagi strategi

Greedy Best-First Search. Strategi ini menggunakan fungsi

h(n) untuk mencari action dengan reward terbesar untuk

setiap state. Dalam persoalan pathfinding ini, fungsi h(n)

didefinisikan sebagai berikut:

h(n) = reward terbesar pada state n

Definisi tersebut selaras dengan optimal policy π*(s).

Melalui definisi tersebut, dalam eksploitasinya, agent akan

mencari action dengan reward terbesar untuk setiap state.

Hal ini sesuai dengan strategi Best-First Search yang

mengambil keputusan berdasarkan estimasi efisiensi terbaik.

E. Analisis Representasi Robot dalam Agen pada Simulasi

Dalam simulator, lajur yang dilalui robot direpresentasikan

dalam matriks. Nilai dari setiap sel matriks menunjukkan titik

tersebut merupakan lajur atau bukan lajur. Lajur terdiri dari

lajur biasa, percabangan, dan goal. Lajur pada percabangan

diberikan atribut khusus yang menunjukkan bahwa posisi

tersebut merupakan sebuah state. Atribut tersebut menjadi

acuan pada Q-Learning. Skema ini dapat dilihat pada

Gambar 8.

3

Gambar 8. Skema matriks simulasi untuk lajur pada Gambar 3

Semua jalur yang keluar dari percabangan tersebut

diidentifikasi sebagai action. Identifikasi tersebut

q

r

s

p

goal

0

0

100

0

0

0

0

0

0

0 90

81

72,9

q

r

s

p

goal

100

100

100

81

90

81

90

81

90

90

90

90

90


5

My Computer

Rectangle


mengakibatkan seluruh pilihan lajur pada cabang tersebut

memiliki nilai reward.

Koordinat pada matriks yang berisi informasi state

disimpan dalam sebuah tabel yang menyimpan semua state

yang terdapat dalam sebuah jalur. Setiap state merupakan

struktur data yang menyimpan informasi posisi koordinat

jalur, posisi sebagai goal, dan semua action yang mungkin

diambil agent pada pada state tersebut. Berdasarkan analisis

mengenai bentuk fisik agent yang hanya mampu

mengidentifikasi empat aksi, maka setiap state yang terdapat

pada sebuah jalur dibatasi penyimpanan action-nya hingga

maksimum empat macam.

Struktur data yang menyimpan nilai terhadap aksi

dipisahkan dengan matriks representasi. Struktur tersebut

menggambarkan asosiasi antara state dan action beserta

reward untuk masing-masing action. Nilai reward pada

setiap action diisi melalui setiap episode agent melakukan

pembelajaran. Struktur tersebut dapat dilihat pada Tabel 1.

TABEL 1

ASOSIASI STATE-ACTION

Nama

State

Posisi

State

(x,y)

Action

Next State

(Nama)

Next

State

(x,y)

Reward

p 1,4

up q 4,1 90

down s 4,7 90

right r 4,4 90

q 4,1

down r 4,4 90

right goal 7,4 100

left p 1,4 81

r 4,4

up q 4,1 90

down s 4,7 90

right goal 7,4 100

left p 1,4 81

s 4,7

up r 4,4 90

right goal 7,4 100

left p 1,4 81

F. Informasi Jarak

Pemberian nilai immediate reward dapat dilakukan dengan

menggunakan nilai jarak yang didapatkan ketika eksplorasi.

Nilai jarak merupakan hasil penghitungan jarak tempuh agent

menuju goal state. Akuisisi ini dapat dilakukan dengan

asumsi bahwa robot dapat dilengkapi dengan pendeteksi

perpindahan menggunakan rotary encoder.

Dari simulasi, immediate reward diberikan nilai nol. Hal

ini bertujuan untuk menunjukkan bahwa reward yang

diperhitungkan secara utama hanya bergantung pada jumlah

state dan nilai reward pada action menuju goal.

Prioritas tertinggi informasi jarak adalah informasi jarak

yang bernilai terkecil. Eksploitasi membutuhkan metode

greedy yang mencari nilai terkecil. Kebutuhan ini terpenuhi

dengan memberikan nilai acuan selisih. Nilai acuan selisih ini

menghasilkan angka besar bila jarak semakin dekat. Angka

besar tersebut dapat diacu dengan fungsi greedy yang sama

dalam memilih nilai reward.

4. PERANCANGAN DAN IMPLEMENTASI

SIMULATOR

A. Mekanisme Simulator

Dalam penelitian ini, implementasi reinforcement learning

dilakukan melalui simulasi dalam program perangkat lunak.

Program ini mendukung implementasi dan pengujian Q-

Learning dalam kasus pencarian jalur sebagaimana dijelaskan

pada bab sebelumnya. Perangkat ini memfasilitasi pengguna

untuk mengubah data lajur menjadi model state-action,

melakukan pembelajaran mesin bagi agent, serta memantau

hasil eksploitasi agent dalam kasus pencarian jalur.

Simulasi yang akan diberikan dalam program ini terdiri

atas empat tahapan. Tahapan-tahapan tersebut yaitu:

1. Konversi jalur-matriks

2. Inisialisasi

3. Eksplorasi (learning)

4. Eksploitasi (solving)

Tahapan pertama adalah konversi jalur-matriks. Tahapan

ini merupakan bagian awal program yang mengubah

representasi jalur dalam file berekstensi .maz menjadi

matriks. Tahapan ini kemudian memberikan umpan-balik

pada pengguna berupa antarmuka jalur tersebut. File yang

digunakan dibuat menggunakan program lain yang

menangani peyuntingan jalur menjadi representasi matriks.

Pada tahapan ini, program juga memberikan respon bagi

input pengguna apabila terdapat initial state yang merupakan

poin start bagi agent pada jalur yang belum terepresentasi.

Tahapan mekanisme berikutnya adalah Inisialisasi.

Tahapan ini merupakan pembacaan program terhadap

representasi matriks untuk menentukan posisi state yang akan

dideteksi agent. Program mendeteksi jalur yang memiliki

percabangan secara terurut indeks matriks. Percabangan akan

dideteksi sebagai state dan disimpan dalam tabel berisi daftar

informasi tersebut.

Penyimpanan state juga disertai adanya deteksi pilihan

jalur pada setiap state. Deteksi ini dilakukan untuk

menyimpan informasi bagi action yang terdapat pada

masing-masing state terhadap state berikutnya. Jalur yang

tidak menjadikan agent bergerak menuju suatu state akan

diisi dengan informasi yang menyatakan bahwa jalur tersebut

diabaikan.

Mekanisme kemudian dilanjutkan pada tahapan Eksplorasi

(learning). Tahapan eksplorasi merupakan tahapan

pembelajaran yang memberikan prosedur program yang

serupa dengan skenario pada bagian III.F. Untuk setiap

episode pembelajaran, agent melakukan penelusuran state

dan memilih salah satu action pada setiap state yang dilalui.

Pemilihan dilakukan menggunakan strategi DFS. Agent

kemudian menyimpan action yang dipilihnya ke dalam suatu


6

My Computer

Rectangle


stack. Penyimpanan pada stack beserta penelusuran jalur

berhenti ketika agent mencapai goal.

Ketika penelusuran berhenti, informasi pada stack action

di-pop untuk direferensikan program. Program kemudian

mengisi reward berdasarkan fungsi pembelajaran yang

diimplementasikan dalam simulasi ini. Skenario pengisian

reward mengacu pada skenario yang telah ditunjukkan pada

analisis.

Analisis mengenai skenario pembelajaran menunjukkan

bahwa nilai reward yang telah tersimpan tidak bersifat

konstan dan dapat diperbarui apabila agent melakukan

eksplorasi jalur lain. Hal ini mengakibatkan nilai reward

dapat terus diperbarui hingga mencapai konvergensi.

Pembelajaran dapat dilakukan berulang-ulang dengan

parameter iterasi yang kompleks.

Dengan tujuan mempersingkat episode pembelajaran,

maka penelusuran pada tahap eksplorasi disertai batasan-

batasan tertentu untuk mencegah pembelajaran yang tidak

berujung. Batasan-batasan tersebut antara lain:

1. Dalam satu episode, agent tidak memilih jalur yang

telah dilalui sebelumnya.

2. Untuk episode yang berbeda, agent mengacu pada

informasi jalur yang sudah tersedia dan

memprioritaskan pengisian reward yang masih nol.

3. Prioritas eksplorasi dilakukan secara seragam dengan

adanya prioritas pilihan jalur dalam satu episode.

Tahapan yang dilakukan setelah pembelajaran adalah

Exploitasi (solving). Tahapan ini adalah penyelesaian

pencarian jalur oleh agent yang mengacu pada reward yang

didapat dari proses eksplorasi. Pengguna dapat memberikan

masukan posisi robot (agent) bagi program agent akan

mengeksploitasi value function secara mandiri untuk

mencapai goal state.

Batasan program mengakibatkan pengguna hanya dapat

memberikan masukan posisi agent pada koordinat matriks

yang merupakan state. Dengan kata lain, secara nyata, robot

hanya dapat ditempatkan pada posisi awal start point atau

percabangan.

Penempatan agent pada koordinat state memberikan

informasi bagi program mengenai posisi agent. Agent

kemudian menelusuri jalur dan memilih action dengan nilai

reward terbesar ketika melalui setiap state hingga mencapai

goal. Abstraksi pemilihan tersebut dilakukan menggunakan

skema strategi Greedy Best-First Search sebagaimana

penjelasan pada III.D.

B. Pseudocode

5. HASIL PENGUJIAN

Pengujian yang dilakukan memiliki tujuan sebagai berikut:

1. Mengevaluasi kinerja agent setelah diberlakukan

proses pembelajaran mesin.

2. Membandingkan kinerja eksploitasi hasil pembelajaran

mesin dengan eksploitasi metode Depth-First Search

(DFS).

Hasil evaluasi kinerja dibandingkan dengan metode DFS

karena dalam implementasi pembelajaran mesin, eksplorasi

dilakukan secara DFS.

Pengujian tersebut dibatasi dalam beberapa spesifikasi

berikut:

1. Titik start, titik akhir, serta semua titik percabangan

berada dalam graf terhubung.

2. Semua percabangan memiliki tidak lebih dari 4 cabang

(semua titik memiliki tidak lebih dari 4 sisi).

3. Kurva lajur dapat disederhanakan menjadi rangkaian

segiempat.

4. Titik start diambil dari titik yang sudah ditentukan atau

dari titik percabangan.

KAMUS pathElmt: {elemen representasi matrix} stateElmt x:pointElmt y:pointElmt actionlist: array [1..4] of action {action yang dipilih ketika DFS} {x y adalah posisi pada state} ALGORITMA procedure explore (input state:array [1..n] of stateElmt, Pmatrix: array [1..n] of array [1..n] of pathElmt) KAMUS LOKAL

xinit,yinit:pointElmt {elemen x dan y pada posisi state}

i:integer level:integer

ALGORITMA level = 0 for i-> 0 to jumlah elemen pada state do setAgent(state[i].x, state[i].y) xinit = state[i].x yinit = state[i].y repeat

DFS until

bertemu goal (mengacu Pmatrix, level

berubah sesuai aras state) if isGoal(state[i].x, state[i].y) then rewarding until x=xinit dan y=yinit dan level=0 procedure exploit(input state:array [1..n] of stateElmt, Pmatrix: array [1..n] of array [1..n] of pathElmt, posisix, posisiy:pointElmt) KAMUS LOKAL A: action ALGORITMA while not isGoal(posisix,posisiy) do A: getDirectMax(posisix,posisiy) doAction(A) procedure setAgent(input x,y:pointElmt) {memposisikan Agent pada xy} procedure doAction(input:action) {melakukan pergerakan agen} function isGoal(input x,y:pointElmt) -> boolean {true bila state pada xy adalah goal} function getDirectMax(input x,y:pointElmt) ->real {mengembalikan reward maksimum untuk action pada state di xy}


7

My Computer

Rectangle


5. Selang waktu dihitung per-langkah agent dalam

representasi matriks sehingga memiliki satuan yang

sama dengan jumlah langkah perpindahan agent.

6. Posisi x,y dihitung dari ujung kiri-atas matriks.

7. Sel kosong pada dimensi bidang yang melebihi

dimensi masuk dalam penghitungan kordinat matriks.

Adapun pengujian terhadap beberapa lajur dapat dilihat

pada Gambar 9-11 beserta penjelasannya.

Gambar 9. Lajur I -Koordinat goal (x,y): (8,5)

Hasil pengujian lajur I

Eksplorasi: 648 Langkah

Rata-rata tempuh DFS: 12,75 Langkah

Rata-rata tempuh hasil pembelajaran: 5,25 Langkah

Persentase Langkah (DFS : learned): 41,18 %

Gambar 10. Lajur II -Koordinat goal (x,y): (5,7)

Hasil pengujian lajur II

Eksplorasi: 1.872 Langkah




Gambar 11. Lajur III -Koordinat goal (x,y): (29,15)

Hasil pengujian lajur III

Eksplorasi: 58.872 Langkah




Rata-rata Persentase Langkah:

(41,18 % + 36,78 % + 19,22 %) / 3 = 32,39%

Hasil pengujian di atas menunjukkan peningkatan efisiensi

pada pengambilan langkah pasca implementasi pembelajaran

mesin. Hal tersebut disebabkan simulasi pemilihan jalur

dengan metode DFS dilakukan tanpa dukungan informasi

pada pemilihan aksinya. Hal ini menyebabkan pemilihan

jalur melalui DFS melibatkan proses backtracking yang

mengakibatkan penambahan selang waktu dalam pemilihan

jalurnya. Hal yang serupa tidak terjadi apabila eksploitasi

dilakukan berdasarkan informasi hasil pembelajaran mesin.

Melalui informasi tersebut, agent dapat memilih percabangan

secara greedy berdasarkan reward yang didapat melalui

pembelajaran mesin. Dapat disimpulkan bahwa pemilihan

jalur berdasarkan informasi hasil pembelajaran mesin

memiliki efisiensi yang lebih baik.

Pengujian menunjukkan reduksi penempuhan hingga

32,39%. Jumlah ini berkaitan dengan pembatasan pilihan

jalur hanya pada empat pilihan. Pembelajaran mesin

memberikan informasi pada agent sehingga agent dapat

langsung memilih satu jalur tanpa melakukan pemeriksaan

backtracking pada jalur lainnya. Hal tersebut memberikan

efisiensi bagi waktu dan jarak tempuh agent menuju goal.

Akan tetapi, hasil pengujian tersebut juga menunjukkan

selang waktu yang besar ketika eksplorasi pembelajaran

mesin dilakukan. Hal tersebut disebabkan pemrograman pada

agent untuk melakukan pemilihan pada seluruh kemungkinan

jalur. Pemilihan tersebut dilakukan mengacu pada simulasi

dalam subbab III.3 yang menunjukkan proses akuisisi nilai

reward bagi seluruh kemungkinan action. Dengan demikian,

dalam proses learning, dapat dikatakan bahwa agent

melakukan proses dengan kompleksitas pada worst-case

scenario DFS. Hal ini menyebabkan implementasi

pembelajaran mesin membutuhkan waktu yang jauh lebih

besar dalam proses akuisisi informasi reward yang digunakan

dalam eksploitasi.

6. SIMPULAN DAN SARAN

A. Simpulan

Berdasarkan hasil pengujian, dapat disimpulkan beberapa

hal sebagai berikut:

1. Pembelajaran mesin Q-Learning dapat

diimplementasikan pada penyelesaian persoalan

pathfinding. Implementasi tersebut dapat dilakukan

dengan memodelkan state-action sebagai representasi

terhadap percabangan lajur beserta pilihan jalur

cabangnya. Nilai reward dapat diberikan pada agent

apabila agent tersebut memilih cabang pada jalur

dengan jarak terdekat terhadap goal state.

2. Implementasi pembelajaran mesin ini meningkatkan

efisiensi penempuhan lajur menuju goal state tertentu.

G

G

G


8

My Computer

Rectangle

My Computer

Rectangle


Secara umum, langkah agent dapat direduksi hingga

32,39%. Informasi tersebut didapatkan dengan

membandingkan terhadap penyelesaian persoalan yang

sama menggunakan metode DFS. Akan tetapi,

implementasi pembelajaran mesin ini memiliki

kerugian berupa kebutuhan waktu yang besar dalam

proses eksplorasinya. Nilai reward untuk setiap action

hanya dapat diperoleh apabila agent telah melakukan

eksplorasi untuk seluruh kemungkinan percabangan.

Apabila eksplorasi dilakukan menggunakan DFS pula,

maka eksplorasi tersebut memiliki kompleksitas

eksponensial pada O(n x 4n).

B. Saran

Berkaitan dengan tugas akhir ini, dapat dilakukan

pengembangan berikutnya dalam beberapa persoalan:

1. Peningkatan resolusi sensor lajur pada robot dapat

meningkatkan kemampuan robot sebagai agent untuk

memilih lebih dari empat pilihan percabangan.

2. Pemodelan pembelajaran mesin dengan pendekatan

lain yang memungkinkan akuisisi informasi untuk

digunakan dalam metode pathfinding lainnya seperti

A*.

REFERENSI

[1]. Osorio C., Roman, dkk (2006). Intelligent Line Follower Mini Robot

System. International Journal of Computers, Communications &

Control.

[2]. Smart, William D. dan L. P. Kaelbling. (2002). Effective

Reinforcement Learning for Mobile Robot. MIT Computer Science and Artificial Intelligence Laboratory. Massachusetts Institue of

Technology. MA [3]. Mitchell, Tom M. Machine Learning. (1997). New York: NY.

McGraw-Hill.

[4]. Rachmatullah, Syawaluddin. (2009). Laporan Perancangan dan Realisasi Hardware: Robot Penjejak Garis SR2009LF (Line

Following Robot). Program Studi Teknik Elektro, Sekolah Teknik

Elektro dan Informatika, Institut Teknologi Bandung. [5]. Russel, Stuart J. dan Peter Norvig. (1995). Artificial Intelligence: A

Modern Approach. New Jersey. Prentice-Hall.


9

My Computer

Rectangle

implementasi reinforcement learning pada simulasi penentuan jalur robot bertipe line-follower

Education