Bab 1 Pendahuluan 1.1 Latar Belakang Tugas akhir ini menyajikan sebuah metodologi dalam kemasan simulasi bagi perilaku sistem agen banyak. Model yang diajukan dibuat berdasarkan kenyataan yang terjadi di alam. Pendahuluan makalah ini akan diisi oleh beberapa hal terkait yang melatarbelakangi makalah ini diantaranya kecerdasan swarm, fenomena agent-based dan flocking yang mengacu pada model Pursuit-Evasion beserta eksplorasi dan pemanfaatannya sejauh ini.
1.1.1 Kecerdasan Swarm Kecerdasan Swarm (Swarm Intelligence) telah banyak digunakan oleh perusahaaanperusahaan besar di dunia untuk meningkatkan efisiensi dan juga digunakan dalam kemiliteran untuk mengembangkan robot yang digunakan baik di darat maupun di udara. Tidak hanya itu, kelak ia akan berperan besar dalam mengatasi kemacetan di pagi hari, mempercepat pemberangkatan di bandara atau mengalihkan rute pesawat dari kemungkinan terjadinya cuaca buruk di malam hari dan masih banyak lagi (Lihat 4). American Air Liquide, sebuah perusahaan industri gas di Houston, telah menggunakan strategi agent-based untuk mengurus masalah-masalah bisnis mereka 1
BAB 1. PENDAHULUAN
2
antara lain penjadwalan pengiriman barang. Air Liquide mengembangkan sebuah model yang algoritmanya terinspirasi dari perilaku semut Argentina (Linepithema humile) yakni suatu spesies yang menghasilkan subtansi kimia (pheromones) saat mereka keluar dari sarangnya untuk mencari makanan. Penyelidikan mengenai perilaku sekerubung semut dengan pheromones-nya untuk menjalankan apa yang disebut foraging-tasks adalah salah satu teladan yang sangat menarik. Dapat kita perhatikan bagaimana saat satu semut keluar dari sarangnya untuk mencari makanan, lalu kemudian kembali lagi ke sarangnya dan mendapati sarangnya sudah penuh dengan makanan. Guna membantu mereka menyelesaikan tugasnya, masing-masing agen meninggalkan jejak berupa subtansi kimia yang dinamakan pheromones dan merespon kembali sinyal dari pheromones lainnya dalam cara yang berbeda-beda. Darisini, para peneliti mulai tertarik untuk menyesuaikan konsep pheromones pada beragam tugas agen tiruan. Terinspirasi oleh perilaku semut dalam menemukan sumber makanannya, Marco Dorigo seorang peneliti dari Universitas Libre di Brussels pada tahun 1991 menggunakan pengetahuannya untuk menciptakan prosedur yang berguna untuk menyelesaikan masalah-masalah yang cukup rumit antara lain penjadwalan pesawat komersial dan pemanduan robot-robot militer. Banyak perusahaan-perusahaan lain yang juga mendapatkan keuntungan dengan menerapkan strategi yang ditiru dari cara kerja semut-semut. Beberapa diantaranya mencoba menggunakan aturan bagaimana cara semut mencari makanannya untuk mencari rute pengiriman terbaik, meningkatkan pelayanan pemberangkatan pesawat di bandara dan optimalisasi jaringan telepon. Pemanfaatan kecerdasan swarm juga terjadi di dunia maya. Wikipedia dan Google adalah dua bukti nyata yang mendapatkan sukses besar lewat pemanfaatan ini. Perhatikan bagaimana Google menggunakannya untuk membantu kita menemukan informasi yang kita perlukan. Setelah kita mengetikkan kata yang kita cari, Google kemudian menggunakan grup-grup cerdasnya untuk mensurvei jutaan halaman web yang telah didaftarkan terlebih dahulu pada database-
BAB 1. PENDAHULUAN
3
nya (proses ini disebut juga indexing) untuk mengidentifikasi mana yang paling relevan. Setelah itu Google kemudian mengurutkan halaman-halaman itu berdasarkan seberapa banyak halaman itu tersambung dengan halaman lainnya. Hasilnya adalah situs yang paling populer akan dipilih sebagai situs yang diletakkan paling depan pada halaman hasil pencarian. Darisini kita dapat menyimpulkan bahwa kecerdasan kolektif (collective intelligence) berperan besar dalam menentukan halaman-halaman atau situs-situs yang dipandang penting. Lalu-lintas di darat dan di udara adalah sebuah sistem yang self-organize yang sesuai dengan model pencarian makanan yang dilakukan semut-semut atau model flocking yang juga dikenal sebagai model agent-based (Lihat 5). Agen adalah satuan individu yang melakukan aksi antara lain membuat keputusan-keputusan dengan segera berdasarkan lingkungan disekitarnya. Definisi agen menurut Bonabeau (Lihat 6) adalah, an agent is a computational entity which may be scheduled to perform some action, and which can manipulate the environment. Agen adalah sebuah entitas komputasional yang dapat diatur sedemikian rupa untuk menjalankan suatu aksi dan kemudian memanipulasi lingkungan. Kalau sebuah mobil dapat dipandang sebagai agen, maka ia dapat menjalankan alur perintah yang dipengaruhi oleh semua kemungkinan yang akan dihadapi oleh pengemudinya. Jika semua mobil di jalan raya bergerak layaknya agen, maka setiap mobil dapat melakukan penyesuaian-penyesuaian yang memungkinkan lalu lintas dapat berjalan lebih mulus. Lalu lintas udara disisi lain telah dilengkapi dengan regulasi yang sangat ketat. Para peneliti sampai saat ini telah menjalankan serangkaian uji coba dari sistem agent-based untuk melihat apakah pesawat udara mampu melakukan selforganize secara aman dan efektif. Melihat perkembangan yang pesat dibidang penerbangan saat ini, adalah memungkinkan bagi tiap pesawat untuk dimonitor oleh pusat kendali. Hal ini sangat berguna bagi pesawat tersebut untuk melakukan penyesuaian-penyesuaian antara lain menjaga jarak sesama pesawat terbang
BAB 1. PENDAHULUAN
4
sementara itu diwaktu yang sama mencari rute-rute yang pendek dan aman agar terhindar dari cuaca buruk atau bandara-bandara yang padat.
1.1.2
Flocking dan Pursuit model
Bayangkan sekawanan burung dara yang berhamburan terbang kesana kemari di atas taman kota. Lambat laun mereka akan turun dan beristirahat sejenak di atas rerumputan di sekeliling taman. Lalu seorang anak kecil berlari ke arah kawanan burung dara tersebut berusaha mengganggu dan menakuti mereka dan saat itu juga burung-burung dara tersebut ”serentak” berterbangan dengan teratur. Perhatikan bahwa burung-burung yang berterbangan itu ternyata dapat terkoordinasi dengan baik tanpa adanya pemimpin. Tidak satupun dari mereka memberitahu satu sama lain apa yang harus dilakukan, namun, masing-masing dari mereka memperhatikan satu sama lain. Tiap burung mengikuti aturan-aturan sederhana saat mereka berada di angkasa. Kendatipun sederhana, aturan ini dapat dengan cepat mereka gunakan untuk mengambil keputusan selanjutnya. Aturan-aturan seperti ini–yang terjadi secara umum pada kawanan hewan-hewan di alam bebas–lalu dikenal sebagai kecerdasan swarm (swarm intelligence). Vijay Kumar, seorang profesor dibidang Teknik Mesin Universitas Pennsylvania mengatakan bahwa jika kita berbicara mengenai kelompok yang besar dalam biologi maka sebagian besar dari kelompokkelompok itu sangat terdistribusi dalam artian mereka tidak menginstruksikan sesuatu kepada sesamanya, mereka bereaksi pada informasi di sekitarnya dan mereka semua anonim. Darisini, untuk membangun suatu rancangan model tiruan mulai dari satu agen sampai dengan agen banyak, kita harus memperhatikan tiga ide dasar tersebut. Pada tahun 1986 Craig Reynolds menciptakan sebuah model pergerakan hewan terkoordinasi layaknya kawanan burung dan ikan-ikan. Model tersebut berdasarkan pada perhitungan geometri yang biasa digunakan pada animasi komputer. Simulasi sekawanan makhluk itu kemudian diberi nama boids (Lihat 2 dan
BAB 1. PENDAHULUAN
5
3). Dalam simulasinya itu, generic birdlike objects, atau boids, masing-masing agen diberikan tiga instruksi: 1) hindari keramaian dari boids sekitar, 2) bergerak ke arah ”average direction” dari boids sekitar dan 3) tetap berada dekat dengan boids sekitar. Hasilnya ternyata adalah simulasi yang meyakinkan dari sebuah flocking, termasuk pergerakan yang tak menentu dan tidak dapat ditebak. Sejak 1987 telah dibuat banyak aplikasi sejenis yang menyerupai model boids yakni sebuah model di dalam lingkup animasi perilaku (behavioral animation). Animasi ini pertama kali diperlihatkan dalam sebuah film buah karya Tim Burton yang berjudul Batman Returns pada tahun 1992. Dalam film ini kita dapat temukan kerumunan kelalawar dan sekawanan pinguin yang dihasilkan lewat simulasi komputer sebagai pengembangan dari model boids. Kerumunan kelalawar tiruan yang tampak realistis itu diciptakan oleh Andy Kopra. Sementara kawanan pinguin yang berbaris layaknya tentara di jalan-jalan kota Gotham dikerjakan oleh Andrea Losch dan Paul Asdown. Bermula dari boids inilah kita dapat melihat perkembangan simulasi flockers yang lebih efisien dalam hal konsumsi memori sehingga mampu menampilkan simulasi agen banyak yang lebih rumit.
Gambar 1.1: Aplikasi MASON: simulasi flockers untuk 3 agen
BAB 1. PENDAHULUAN
6
Beberapa dari paket simulasi yang menyertakan simulasi flocking diantaranya adalah NetLogo dan MASON sebuah paket simulasi yang dikembangkan oleh Sean Luke dan George Mason University (Lihat 7 dan 8). Melalui demonstrasi model-model yang self-organize untuk menirukan perilaku swarm, Reynolds telah memberikan pemikiran baru bagi para insinyur robot. Sebuah tim robot-robot yang dapat berkoordinasi layaknya kawanan burung dapat menawarkan berbagai keuntungan yang signifikan. Bila disebarkan secara merata pada sebuah wilayah yang luas, sebuah tim robot-robot dapat berfungsi layaknya jaringan sensor bergerak yang dapat diandalkan untuk memperoleh informasi mengenai segala hal di wilayah tersebut. Jika kelompok tersebut mengalami gangguan maka mereka dapat merespon dengan cepat lalu kemudian melakukan penyesuaian. Sama seperti semut-semut, jika salah satu dari mereka rusak maka robot lainnya dalam kelompok itu dapat segera menggantikan posisinya, dan yang terpenting kendali dari kelompok itu tidak terpusat yakni tidak ada yang bertugas sebagai pemimpin atau penyelia dalam kelompok tersebut. Sama seperti boids, Pursuit model yang diperkenalkan dalam makalah ini merupakan contoh dari sebuah model individual-based, yaitu semacam simulasi yang dibuat untuk menangkap sebuah gambaran global atas perilaku dari sejumlah besar agen-agen otonom yang berinteraksi satu dengan lainnya. Model Individualbased atau agent-based ini banyak digunakan dalam biologi, ekologi, ekonomi, ilmu komputer dan bidang-bidang penting lainnya. Pada makalah ini, penulis akan menyajikan sebuah model beserta simulasi bagi sistem multi pursuer. Kelebihan dari model ini adalah dapat diperluas untuk lebih banyak pengejar. Bentuk sederhana dari strategi penghindar-pengejar (pursuer-evader) pada model ini diharapkan mampu menawarkan implementasi praktis bagi suatu real-time systems yang applicable.
BAB 1. PENDAHULUAN
7
1.2 Rumusan Masalah Pursuit model sejatinya berisi agen yang memilih satu diantara dua peran: pengejar (pursuer) atau penghindar (evader). Tugas evader adalah menghindar dari kejaran sementara tugas pursuer adalah mengejar/mengikuti agen lain di depannya. Simulasi yang akan diilustrasikan dalam makalah ini diberi nama HunterPrey Simulation (simulasi Pemburu-Mangsa) dan dirumuskan dengan baik dalam suatu sistem dinamik dengan posisi tiap-tiap agen dinyatakan dalam bentuk parametrisasi (x(t), y(t)). Bila diberikan satu agen sebagai mangsa maka kita ingin agar agen-agen lainnya mengejar si agen tadi sehingga kita peroleh suatu simulasi iring-iringan yakni semua pengejar bergerak sesuai incaran yang diberikan. Lebih dalam lagi, akan disimulasikan pula model yang mengatur agar sesama Hunter tidak bentrok satu dengan lainnya. Masalah lainnya adalah setelah menentukan jarak aman yang berupa suatu nilai tertentu apakah proses pengejaran berhenti atau tidak. Pada dasarnya simulasi akan berjalan terus sampai saat yang ditentukan bahkan saat salah satu pemburu sudah sangat dekat dengan mangsa. Hal ini tentu tidak kita inginkan, oleh karena itu kita perlu mendeklarasikan suatu jarak aman tertentu yang manakala ditembus oleh salah satu pemburu mengakibatkan simulasi terhenti seketika.
1.3 Tujuan Penulisan Penulis memulai bekerja pada Pursuit model sebab kita membutuhkan suatu perangkat/model simulasi yang membuat perilaku agent-based pada swarm menjadi relatif lebih mudah untuk dimengerti dan dikembangkan. Disamping itu tentu dibutuhkan suatu model yang applicable dengan kriteria dan berbagai keunggulan diantaranya, 1. Sederhana dalam konsep
BAB 1. PENDAHULUAN
8
2. Sederhana dalam perhitungan 3. Implementasi yang relatif mudah 4. Dapat dihubungkan dengan beragam masalah sistem sosial
1.4 Ruang Lingkup Beberapa bahasan yang akan dikaji pada tugas akhir ini adalah beda hingga dengan normalisasi vektor dan kaitannya dengan sistem persamaan differensial bagi simulasi pursuit model yang berjudul Hunter-Prey Simulation. Simulasi pengejaran akan dibatasi hanya pada sebuah bidang yang bebas penghalang (obstaclefree). Pada tugas akhir ini juga terdapat beberapa pembahasan yang terkait dengan metode numerik yang membuat pencarian solusi menjadi mudah untuk dipahami.
1.5 Sistematika Penyajian Makalah ini akan diatur sebagai berikut. Pada bab 1 dibahas mengenai latar belakang, definisi, permasalahan yang didiskusikan, tujuan singkat dan ruang lingkup pembahasan. Bab 2 membahas mengenai normalisasi vektor dan kaitan antara beda hingga dengan persamaan differensial. Bab 3 menampilkan diagram alir beserta cara kerja simulasi juga ulasan singkat mengenai simulasi Pursuit model: Hunter-Prey Simulation untuk 3 agen dengan beberapa pengali kelajuan serta posisi awal yang diberikan dan menghitung posisi pada saat t satuan waktu melalui pendekatan numerik. Darisini, simulasi model akan ditampilkan dalam bentuk plot parametrik. Bab 4 akan mempersembahkan hasil simulasi berupa snap shot sementara simulasi Hunter-Prey dalam bentuk animasi selengkapnya dapat kita temukan pada CD yang disertakan bersama makalah ini. Terakhir, Bab 5 menyimpulkan isi makalah ini.
