PENCARIAN JALUR TERPENDEK PADA PEMODELAN PERGERAKAN AGEN CERDAS DENGAN ALGORITMA ANT COLONY SYSTEM

PENCARIAN JALUR TERPENDEK PADA PEMODELAN PERGERAKAN AGEN CERDAS DENGAN ALGORITMA ANT COLONY SYSTEM Endah Damayanti1), Supeno Mardi SN2) Moch.Hariadi3) 1,2,3

Pasca Sarjana Jaringan Cerdas Multimedia (Game Teknologi) Teknik Elektro,Teknologi Industri ITS Jurusan Teknik Elektro, Fakultas Teknologi Industri ITS Jl. Keputih Sukolilo,Surabaya, 60111 E-mail : [email protected] 1),[email protected]), [email protected])

ABSTRAK Dalam game moderen berbasis artificial intelligence masih bergantung pada pendekatan behavior manusia dan kondisi dunia nyata. Game yang realistis didukung oleh implementasi human like behavior pada player / Non Player Character / agen cerdas dalam game. Untuk menghidupkan perilaku dari agen cerdas perlu diterapkan kecerdasan buatan. Pergerakan agen cerdas di suatu game sangat erat kaitannya dengan path finding (pencarian jalan). Path finding merupakan salah satu dasar algoritma dalam konsep menggerakkan karakter dalam game. Dengan algoritma pencarian jalan , agen cerdas dalam game bisa bergerak dan berperilaku human like behavior. Yang menjadi masalah adalah bagaimana memberi perilaku yang cerdas pada agen agar dapat mencari jarak terpendek dengan goal/target. Banyak hal yang dapat diamati dari manusia di mall, misalnya saja tentang pergerakan dan perilaku manusia . Dan hal ini dapat diimplementasi dalam sebuah game yang menarik. Pada penelitian kali ini menggunakan algoritma Rule Base System sebagai implemetasi perilaku agen cerdas dan Ant Colony System sebagai algoritma pencarian jalur terpendek di mall. Kata kunci : pathfinding, perilaku, agen cedas, game, algoritma Ant Colony System, Rule Base System 1. PENDAHULUAN Industri game komputer komersial merupakan perwujudan pengembangan industri kreatif. Perkembangan game juga didukung dengan kemajuan grafis yang membuat game environment dan jalannya permainan menjadi lebih realis. Namun grafis yang telah dibangun tidak akan menghasil sebuah game yang realistis jika tidak didukung oleh implementasi behaviors agen cerdas/ player/ NPC (Non Player Character) dalam game. Untuk menghidupkan perilaku dari agen cerdas pada gema simulasi perlu diterapkan AI (artificial intelligence) (Thurau, 2005). Pergerakan agen cerdas di suatu game sangat erat kaitannya dengan path finding (pencarian jalan). Path finding atau pencarian jalan adalah salah satu dasar algoritma dalam konsep menggerakkan karakter dalam game. Strategi Path finding biasanya digunakan sebagai inti dari setiap pergerakan AI (Graham, 2005).

Dengan algoritma pencarian jalan terpendek , agen cerdas dalam game dapat berjalan dan bergerak seperti perilaku manusia di dunia nyata. Bila game tersebut tidak dilengkapi algoritma pencarian jarak maka agen bisa berjalan, namun belum tentu karakter tersebut bergerak sesuai perilaku manusia. Salah satu tantangan dalam desain realistis AI di komputer permainan agen adalah gerakan (Graham, 2005). AI merupakan teknologi yang mensimulasikan kecerdasan manusia dan mencoba menyelesaikan persoalan menggunakan komputer dengan meniru bagaimana manusia menyelesaikan dengan cepat. Yang menjadi masalah adalah bagaimana memberi behavior yang cerdas pada agen cedas agar dapat mencari jarak terpendek dengan goal/target. Banyak hal yang dapat diamati dari perilaku manusia didalam mall atau pusat perbelanjaan misalnya saja tentang pergerakan dan behavior . Dan hal ini dapat diimplementasi dalam sebuah game yang menarik. Agar NPC selaku agen cerdas dapat bergerak sealami mungkin, maka pada agen cerdas tersebut diberi kecerdasaan untuk menemukan jalan di loronglorong mall agar bisa sampai ditempat yang diinginkannya. Penentuan jalan yang dipilih untuk agen cerdas adalah algoritma ACS serta menggunakan RBS sebagai implementasi pemodelan behavior . 2. LANDASAN TEORI Feromon merupakan zat kimia berasal dari kelenjar endokrin yang digunakan makluk untuk mengenali sesama jenisnnya, individu lain, kelompok, dan untuk membantu proses reproduksi. Berikut ini cara semut untuk mendapatkan jalur yang paling optimal (wardy, 2006) : - Semut berjalan acak untuk menemukan makanan dan meninggalkan feremon pada jalan yang dilaluinya.

Gambar 1 : Lintasan awal mencari sumber makanan - Feromon konsentrasi tinggi menarik semut lain untuk berpindah jalur, menuju jalur paling optimal.

Gambar 2 : Jalur Optimal Ant System atau sering disebuat Ant Colony Optimization (ACO) merupakan suatu metodologi yang dikemukakan pada tahun 1991 oleh Marco Dorigo. Tahun 1997, Dorigo dan Gambardella memperkenalkan Ant Colony System (ACS) (Refianti, 2005). Ant system telah diterapkan di banyak permasalahan optimisasi kombinatorial, sebagai contoh traveling salesman problem, quadratic assignment problem, jobscheduling, vehicle routing, graph coloring,network routing (Dorigo, 1999). Pada ant system dikenal istilah randompropotional rule yang merupakan probabilitas dari semut k pada node r yang menuju node s, dan hal ini dapat dituliskan sebagai berikut (Dorigo, 1997) : ⎧ ⎪⎪ p k (r , s ) = ⎨ ⎪ ⎩⎪

[τ (r , s )].[η (r , s )] β ∑ [τ (r , u )].[η (r , u)]β

jikaS ∈ J k (r )

u∈J k ( r )

0

sebaliknya

Dimana : τ = feromon

1. Aturan transisi status pada ACS diberikan untuk menyeimbangkan antara penjelajahan (exploration) ruas-ruas yang baru dengan eksploitasi (exploitation) dari sebuah priori dan pengetahuan yang dihimpun masalah yang ada. 2. Aturan pembaruan feremon global hanya dilakukan pada lintasan dengan tour terbaik. 3. Aturan pembaruan feremon lokal (local feremon updating rule) digunakan saat ant membangun solusi Aturan transisi status pada ACS berlaku pada ant yang berada node r memilih bergerak menuju node s dan berikut ini persamaan aturan transisi status pada ACS (Dorigo, 1997) : ⎧arg max {[τ ( r , u )].[η (r , u )] β } jika q < q (exp loration ) ⎪ S =⎨ ⎪⎩

o

u∈J k ( r )

S

sebaliknya (biased exp loration )

Dimana : q = bilangan pecahan antara 0 sd 1 [0 .. 1] qo = parameter (0< qo<1) S = variabel acak dipilih berdasarkan distribusi probalilitas pada persamaan pertama Pembaharuan feremon global hanya dilakukan ants yang membuat lintasan terpendek sejak awal perjalanan . Tingkat feremon pada lintasan yang ditebar oleh ants berdasarkan persamaan berikut (Refianti, 2005) :

τ (r , s) ← (1 − α ).τ (r , s) + α .∆τ (r , s)

η= 1

δ merupaka visiblity (invers dari jarak δ (r , s)) δ (r , s) = kumpulan node yang dikunjungi oleh semut

Dimana

⎧ (L ∆ τ ( r , s ) = ⎨ gb ⎩

)

−1

: jika ( r , s ) ∈ golobal − best − tour 0 sebaliknya

0 < α < 1 = parameter feremon decay = panjang tour terbaik sejak awal perjalanan/percobaan Feremon lokal yang dapat diltuliskan dengan persamaan berikut (Refianti, 2005) : Lgb

k [( xr − x s ) 2 + ( y r − y s ) 2 ]1 2

δ (r , s) = Jk(r) = kumpulan node yang akan dikunjungi oleh semut k yang sedang berada pada node r β = parameter yang mengontrol bobot relatif dari feremon terhadaf jarak relatif ( β >0) Pada ant system setelah melakukan ants membuat tour, maka ants akan melakukan pembaharuan feremon global sebagai berikut (Dorigo, 1997):

τ (r , s ) ← (1 − α ).τ (r , s) + ∑k =1 ∆τ k (r , s ) m

(3) dimana

⎧⎪ 1 jika(r, s) ∈ Tour dilakukan semut k ∆τ k (r, s) = ⎨ Lk sebaliknya ⎪⎩ 0 α = parameter feremon decay (0< α <1) Lk = panjang tour yang dilakukan oleh semut m = jumlah ants Ant colony system merupaka pengembangan dari ant system (ant colony atau ACO) dengan memiliki tingkat efiesiensi lebih tinggi pada aplikasi yang lebih komplek (Refianti, 2005). Ada 3 hal mendasar yang membedakan ACS denganACO, yaitu (Dorigo, 1997) :

τ (r , s) ← (1 − ρ ).τ (r , s ) + ρ .∆τ (r , s)

0< ρ <1 = sebuah parameter yang dibuat.

3. PERENCANAAN DAN PEMBAHASAN Tujuan akhir dari penelitian membuat simulasi game kejadian yang sering terjadi dimall, misalnya saja seorang ibu (mom) sebagai player yang bingung mencari anaknya yang menghilang dari sisinya. Untuk perilaku dari agen diatur dalam tabel RBS yang sebelumnya perilaku tersebut telah didefinisikan dalam FSM. Pada pergerakan agen dibutuhkan pencarian jalur terpendek mencari jalan yang paling dekat dan cepat untuk mencapai goal tertentu didalam mall. 3.1 Desain Enviroment Mall Berdasarkan data yang didapatkan dari ”data arsitek” maka dapat dirancang sebuah environment mall dan dilanjutkan dengan pembuatan graph dari jalur yang akan dilalui oleh player maupun NPC. Data arsitek merupakan panduan yang berisi standart ukuran gangway, tinggi pintu, jendela, tata

letak ruangan dan segala peraturan untuk merancangan pelbagai macam jenis bangunan. Setelah path planing dari enviroment mall dibuat maka dilanjutkan dengan pembuatan node dan path yang akan dilalui oleh player maupun NPC

Gambar 4 : denah dan graph mall

. 3.2 Mendeskripsikan Perilaku Agen Cerdas Game dengan FSM (Finite State Machine)

Salah satu cara untuk mengambarkan skenario dari suatu game serta perilaku agen cerdas agar mudah diimplemen tasikan dalam pembuatannya adalah dengan pembuatan FSM FSM merupakan pemodelan dari perilaku dari sebuah obyek yang kompleks dengan state/keadaan yang didefinisikan dan mode transisi yang berubah sesuai keadaan. Misalnya saja pada FSM behavior anak, pada kondisi ”berjalan di lorong mall” akan berubah menjadi ”menoleh kanan/kiri” jika anak sedang ”berfikir” dan akan berlaku ”mencari jalan lain” jika ada ”badut”.

Gambar 5 : FSM Anak

Penerapan RBS pada koding pemrograman ditulis dalam format “IF.......THEN…” atau juga bisa dituliskan lebih lengkap sebagai berikut ”IF.....THEN.....ELSE.....BECAUSE.....”. Berikut ini tabel dan keterangan tabel :

3.3 Pendefinisian Aturan dari Perilaku Agen Cerdas dengan RBS (Rule Base System)

Perilaku agen cerdas yang telah digambarkan dalam bentuk FSM kemudian diubah terjemahkan ke dalam tabel RBS yang berisi peraturan – peraturan berdasarkan keadaan dan peristiwa yang terjadi sehingga mendapatkan goal yang dituju. Misalnya saja pada “rule 1” agen anak dengan kondisi lelah dan jalan padat maka anak akan mencari jalur alternative menghindari jalan yang rame untuk mencari tempat duduk.

3 : tempat duduk 4 : counter minum 7 : counter minum di food court

Tabel 1 : RBS dari perilaku anak IF R U L E

KONDISI TUBUH

LELAH

1 2 3 4 5 6 7 8 9 10 11 12

THEN

HAUS

BOSAN MAEN GAME

BOSAN BACA BUKU

KONDISI GANGWAY

INGIN KE TOILET

PADAT

X X X X X X

NORMAL

ADA BADUT

KERUMUN AN DI ATRIUM

JALUR TERPEN DEK

X

X X

X X

X X X

X

3.4 Percobaan Pencarian Jalur Terpendek

Pada pemodelan pergerakan agen cerdas yang berperilaku menggunakan environment di mall ini memerlukan suatu algoritma pencarian jalur terpendek untuk menggerakan agen cerdas dari tempat agen berada menuju goal tertentu yang telah diatur dalam tabel RBS dengan jarak yang seminimal mungkin. Untuk pencarian jalar terpendek dapat dicari dengan pelbagai macam algoritma path finding, diantaranya dijkstra, BFS, A*, GA , AS, ACO, ACS dan lain sebagainya. Sebagai langkah awal percobaan pemodelan pergerakan agen ini dengan mencoba algoritma Ant Colony pada aplikasi Travelling Salesmen Problem. Pemodelan pergerakan agen cerdas mempunyai kesamaan dengan aplikasi Travelling Salesmen Problem., dimana agen mencari jarak terdekat dari goal yang digambarkan dalam node-node, namun bedanya dalam aplikasi Travelling Salesmen Problem. menggunakan node tertutup sedangkan pada aplikasi pergerakan agen menggunakan node terbuka.

X X X X X

X X

X X X X X X

JALAN ALTER NATIF

X

X X X X

X X

X X X X

X X X

X X

Node-node Travelling Salesmen Problem diasumsikan sama dengan posisi took atau lokasi yang dituju pada aplikasi pemodelan pergerakan agen cerdas dimall. Sedangkan jalur antar node diasumsikan sebagai lorong-lorong di mall. Untuk simulasi aplikasi ini diawali dengan pembuatan : ƒ

tabel inisialisasi posisi node-node (dalam grap) yang dituliskan dalam matrik.

ƒ

dibutuhkan juga tabel jarak antar node

ƒ

tabel kadar feremon pada lintasan/path. Algoritma ant colony system diperlukan proses untuk perhitungan propabilitas sejumlah ant untuk berjalan dari sejumlah yang dilalui

ƒ

kemudian diteruskan dengan proses updating feromon yang ada pada lintasan antar node dengan menggunakan persamaan berikut :

τ (r , s ) ← (1 − α ).τ (r , s) + ∑k =1 ∆τ k (r , s ) m

G O A L

3 3 3 3 3 3 4,7 4,7 4,7 4,7 4,7 4,7

τ (r , s) merupakan nilai feremon dari node r (titik asal) ke node s (titik tujuan) yang telah terupdate untuk kemudian nilai feromon ini di masukan ke persamaan propabilitas kunjungan ant ke node-node yang ada. Semakin besar nilai feremon pada statu jalur maka semakin besar pula probabilitas jalur tersebut akan dilalui oleh ant yang artinya semakin besar nilai feremon pada suatu jalur maka semakin dekat jarak antar node tersebut . Sedangkan “m” merupakan jumlah ant yang digunakan pada percobaan, ant berkeliling ke sejumlah node r sampai s. Dari percobaan yang telah dilakukan menggunakan jumlah node 15 , β =5, α = 1 dan variasi jumlah ant dari 10 sampai 800 didapatkan hasil bahwa jumlah semut akan mempengaruhi iterasi panjang tour pembelajaran. Lebih detil dapat dilihat dari tabel berikut :

merupakan hasil pencarian jarak terpendek dengan menggunakan 100 ant pada 15 node.

Gambar 6: jarak terpendek dengan jumlah ant 100

4. KESIMPULAN

Jumlah Ant

Iterasi untuk mencapai jalur optimum

10

63.744

20

69.520

30

59.409

40

56.315

Dari hail penelitian didapatkan hasil bahwa algorimt Ant Colony dapat digunakan menjalankan pergerakan agen cerdas dengan mencari jalan terpendek dengan terlebih dahulu melakukan pembelajaran jalur yang dilakukan oleh sejumlah ant. Pada percobaan didapatkan dengan jumlah 100 ant didapat hasil yang optimal dengan iterasi 45.562 kali iterasi, dimana jumlah ant menentukan besarnya nilai feremon yang nantinya juga mempengaruhi probabilitas sejumlah ant untuk berjalan mencari jalan terpendek dalam lorong – lorong mall untuk menuju node (posisi tujuan agen) dalam mall.

50

55.033

5. RISET KE DEPAN

60

51.003

70

50.056

80

51.843

90

50.278

100

45.562

200

45.562

400

45.562

Pada penelitian selanjutnya akan dikembang implementasi Ant Colony System sebagai algoritma pencarían jalan terpendek. Algoritma Ant Colony System diterapkan pada agen agar agen dapat berlaku cerdas untuk mencari jalan paling dekat dan cepat serta dapat menghindari halangan yang tidak diinginkan oleh agen untuk menuju tempat/goal tertentu melalui lorong – lorong mall . Dengan menggunakan algoritma Ant Colony System akan membuat agen dapat berperilaku seperti manusia didunia nyata sehingga agen dalam game simulasi yang akan disajikan akan terlihat seperti nyata.

800

45.562

Tabel 2 : Iterasi dan jumlah semut

Percobaan menggunakan jumlah semut dari 10 sampai dengan 800. Dari percobaan di atas didapatkan jumlah semut 100 didapat hasil yang optimal, yaitu 45.562 kali iterasi. Untuk jumlah ant di atas 100 nilainya sama dengan jumlah iterasi jira menggunakan 100 ant. Nilai iterasi merupakan nilai perulangan untuk mengetahui dan mendapatkan jalar terpendek antar node. Gambar dibawah

DAFTAR REFERENSI Adler, David. (1999), Metric Handbook Planning and Design Data, 2nd Edition, Architectural Press Boden, MA. (1996), Artificial Intelegence, Academic Press INC,USA Bjornsson, Yngvi., Halldorsson, Kari. (2006) Improved Heuristics for Optimall Path finding on Game Maps,Proceedings of the Elevent

International in Computer Game Conference, PP 11-22 Dorigo, Margo., Caro Gainni Di., Gambardella L.M. (1999), Ant Algorithms for Discrete Optimazation, Artificial Life, No 5(2), 1999, hal 137-172 Dorigo, Margo., Caro Gainni Di., Gambardella L.M. (1997), Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem, IEEE Transactions on Evolutionary Computation, Vol.1, No.1 Dorigo, M., Maniezzo, V., Coloni, A. (1996), Ant Colony ptimization Artificial Ants as a Computational Intelligence Technique, IEEE Transactions on Systems, Man, and Cybernetics-Part B, 26(1), hal 29-41 Gasbaoui, Brahim., Allaoua*, B. (2009), Ant Colony Optimization Applied on Combinatorial Problem for Optimall Power Flow Solution, Leonardo Journal of Sciences, Issue 14, January-June 2009, hal 1-17. Gopi, E.S. (2007), Algorithm Collections for Digital Signal Processing Applications using Matlab, Springer, The Netherlands Graham, Ross., McCabe, Hugh., dan Sheridan Stephen. (2005), Realistic Agen Movement in Dynamic Game Environment, Procceding of Digra Graham, Ross., McCabe, Hugh., dan Sheridan Stephen. (2003) Path finding in Computer, ITB Journal Issue Kauko, Jarmo., Mattila, Ville Veikko.(2006), Mobile Games Path finding, Scandinavian AI Conference, P 176-182 Lanctot, Marc., Sun, NNM., dan Verbrugge. (2005) Path finding for Large Scale Multiplayer Computer Games, GameOn-NA, pp 23-32 Niuewenhuisen*, D., Kamphuis, A., Overmars. (2007), High Quality Navigation in Computer Games, online at www.sciencedirect.com, Science of Computer Programing 67 (2007) 91-104

Purwanto, Wawan Drs, SE. MM., Perilaku Konsumen, Pusat Pengembangan Bahan Ajar, UMB Refianti Rina., Mutiara., A Benny., (2005), Solusi Optimall Travelling Salesman Problem dengan Ant Colony System (ACS), Journal of Informatics and Computer, Gunadarma Univeristy Reynolds Craig W , (1999) , Steering Behaviors for Autonomous Characters, proceedings of Game Developers Conference, Pages 763-782 Schawab, Brian. (2004), AI Game Engine Programming,1st edition, Charles River Media, INC, New York. Sipahutar, Muara Parlindungan. (2007), Prediksi dan Simulasi Kebangkrutan Perusahaan, Undergraduate Theses from JBPTITBPP , ITB Subakti, Irfan. (2006), Sistem Berbasis Pengetahuan, Modul,FTI, ITS, Surabaya Thurau, Christian., Bauckhage, Christian., dan Sageger, gerhard,. (2005) Learning Human Like Movement Behavior for Computer Games, ACM International Conference Proceeding Series Vol 265. Treuille, Adrien., Cooper, Seth., Popovic. (2006), Continuum Crowds, ACM SIGGRAPH 2006 Papers , pp. 1160-1168 Wardy, Ibnu Sina. (2006), Penggunaan Graf dalam Algoritma Semut untuk Melakukan Optimasasi, Teknik Informatika, ITB Wangsa, Lily Setiawati., (2007), Perilaku Konsumen dalam Memilih Pusat Perbelanjaan Berdasarkan Usage, Attitude,dan Image, Skripsi, Program Manajemen Pemasaran Fakultas Ekonomi, Universitas kristen Petra Wahono, R.M. (2003), Pengantar Multi Agent Sistem (MAS), www. IlmuKomputer.Com