ANALISIS PERILAKU MODEL MULTI AGEN DENGAN GANGGUAN Sentot Achmadi1 dan Miswanto2 1Prodi Teknik Informatika ITN Malang e-mail: sentot_achmadi@yahoo.co.id 2Prodi Matematika Fak. Sains dan Teknologi Unair e-mail: miswanto@fst.unair.ac.id ABSTRAK Makalah ini membahas model multi agent pada ruang berdimensi N dengan fungsi penarik dan penolak. Pada model ini diberikan fungsi gangguan yang merupakan fungsi terbatas. Pada makalah ini juga dibahas tentang kestasioneran dari setiap agen dan analisis kestabilan model dengan Lyapunov. Dari hasil analitik diperoleh bahwa pusat dari multi agen bersifat stasioner. Juga uji kestabilan dengan metode kestabilan Lyapunov diperoleh bahwa model yang diajukan merupakan model yang stabil. Hasil simulasi numerik menunjukkan bahwa setiap agen konvergen ke suatu daerah yang mempunyai jarak tertentu terhadap pusat dari model multi agen. Kata kunci: Kestabilan Lyapunov, Multi Agen, Stasioner. ABSTRACT This paper discuss multi-agent model of the N-dimensional space with the function of attraction and repulsion. In this model is given the disturbance function which is a bounded function. In this paper also discuss about stationary of each agency and stability of the models use stability of Lyapunov. From the analytical results obtained center of the multi-agent is stationary. Also test the stability with Lyapunov method is obtained that the proposed model is a stable model. Numerical simulation results show that each agent will converges to a region that has a certain distance to the center of the multi-agent model. Keywords: Multi-Agent, Stability of Lyapunov, Stationary. PENDAHULUHAN Beberapa fenomena alam sangat menarik untuk dikaji secara fisika dan dimodelkan secara matematika. Salah satu fenomena alam yang menarik untuk dimodelkan secara matematika dan dikaji secara fisika adalah fenomena gerak bergerombol yang dinamakan dengan swarm. Fenomena alam ini banyak ditemukan pada beberapa organisme mulai dari yang sederhana (bakteri) sampai pada mamalia, sebagai contoh sekumpulan bakteri, sekawanan burung angsa, sekelompok singa dan sekelompok ikan. Dengan melakukan gerak bergerombol, mereka memperoleh beberapa keuntungan seperti terhindar dari pemangsa dan dapat meningkatkan efektifitas dalam pencarian makanan. Kelompok binatang (mangsa) memanfaatkan fenomena swarm untuk melindungi anggotanya dari serangan binatang lain (pemangsa). Di lain pihak pemangsa memanfaatkan fenomena swarm untuk efektifitas penyerangan terhadap mangsanya. Sekawanan burung angsa dalam melakukan terbang selalu membentuk formasi V terbalik. Dengan terbang dalam formasi V terbalik, sekawanan burung angsa memperoleh beberapa keuntungan, antara lain dapat meningkatkan jarak terbangnya lebih dari 71 % dan daya terbangnya 24 % lebih cepat dari pada terbang sendirian. Fenomena swarm banyak digunakan dalam ilmu teknik seperti optimalisasi gerak robot, gerak satelit, dan sebagainya. Dari kajian literatur yang dilakukan, penelitian tentang swarm sudah cukup banyak diantaranya Gazi dan Passino (2002, 2003 dan 2004), Chu et all (2005), tetapi tanpa menyertakan unsur gangguan serta masih terbatas pada perilaku anggota swarm disekitar pusat swarm. Fenomena swarm pertama-tama dimodelkan secara matematika oleh Breder (1954) yang membahas tentang gaya tarik (attractor force) dan gaya tolak (repellent force) antara dua individu. Sedangkan, Gazi dan Passino (2002, 2003 dan 2004) memodelkan swarm berdasarkan pengaruh perpaduan dari keluarga fungsi attractor dan repellent. Model Gazi dan Passino digeneralisasi oleh Wang et all (2004) dengan memasukkan faktor keterkaitan antara anggota swarm (coupling matrix) dan parameter positif. mailto:sentot_achmadi@yahoo.co.id mailto:miswanto@fst.unair.ac.id Sentot Achmadi dan Miswanto 190 Volume 2 No. 4 Mei 2013 Artikel ini mempelajari tentang model swarm yang merupakan modifikasi dari model Gazi dan Passino (2003), tetapi dengan menyertakan suatu fungsi gangguan yang terbatas. Untuk lebih jelasnya ditunjukkan dalam sub bab 2 di bawah ini. MODEL MULTI AGEN Diberikan model Multi Agent dengan M anggota pada ruang Euclidean berdimensi N sebagai berikut: �̇�𝑖 = βˆ‘ 𝑀𝑖𝑗 𝑓(π‘₯𝑖 βˆ’ π‘₯𝑗 ) + 𝛾𝑖 (𝑑), 𝑀 𝑗=1 (1) dengan �̇�𝑖 = 𝑑π‘₯𝑖 𝑑𝑑 , π‘₯𝑖 ∈ 𝑅 𝑁 menyatakan posisi dari agent ke i, 𝐺 = [𝑀𝑖𝑗 ] ∈ 𝑅 𝑁x𝑁 merupakan coupling matrik dengan 𝑀𝑖𝑗 adalah bilangan bulat nonnegative dan matrik G diasumsikan simetri (yaitu 𝑀𝑖𝑗 = 𝑀𝑗𝑖 ). Bentuk 𝑓( . ) menyatakan fungsi penarik dan penolak yang didefinisikan sebagai 𝑓(𝑦) = βˆ’π‘¦ (π‘Ž βˆ’ π‘Ÿ 𝑏+𝑐‖𝑦‖2 ), (2) dengan π‘Ž, 𝑏, 𝑐,dan π‘Ÿ adalah konstanta positif dengan π‘Ž << π‘Ÿ dan ‖𝑦‖ = βˆšπ‘¦π‘‡ 𝑦. Sedangkan γ𝑖 (𝑑) menyatakan fungsi gangguan yang didefinisikan sebagai γ𝑖 (𝑑) = 𝐾 exp(βˆ’Ξ²1 𝑑)sin(Ξ²2𝑑), (3) dengan 𝐾, Ξ²1, Ξ²2 adalah konstanta positif. ANALISIS DARI MODEL MULTI AGEN Pada sub-bab ini dibahas tentang kestasioneran dan kestabilan dari model (1) dengan fungsi penarik dan penolaknya model (2) dan fungsi gangguan (3) yaitu: �̇�𝑖 = βˆ’ βˆ‘ 𝑀𝑖𝑗 (π‘₯𝑖 βˆ’ π‘₯𝑗 ) 𝑀 𝑗=1 ΞΎij + γ𝑖 (𝑑) (4) dengan πœ‰π‘–π‘— = π‘Ž βˆ’ π‘Ÿ 𝑏+𝑐‖π‘₯π‘–βˆ’π‘₯𝑗‖ 2. Didefinisikan pusat dari model multi agen (4) sebagai berikut: οΏ½Μ…οΏ½ = 1 𝑀 βˆ‘ π‘₯𝑖 𝑀 𝑖=1 . (5) Teorema 1. Pusat οΏ½Μ…οΏ½dari model multi agen (4) yang didefinisikan pada persamaan (5) bersifat stasioner. Bukti: Dengan menurunkan persamaan (5) terhadap t diperoleh: οΏ½Μ‡Μ…οΏ½ = 1 𝑀 βˆ‘ �̇�𝑖 𝑀 𝑖=1 = 1 𝑀 βˆ‘ (βˆ’ βˆ‘ 𝑀𝑖𝑗 (π‘₯𝑖 βˆ’ π‘₯𝑗 ) (π‘Ž βˆ’ π‘Ÿ 𝑏 + 𝑐‖π‘₯𝑖 βˆ’ π‘₯𝑗 β€– 2 ) 𝑀 𝑗=1 + 𝛾𝑖 (𝑑)) 𝑀 𝑖=1 = βˆ’ 1 𝑀 βˆ‘ βˆ‘ 𝑀𝑖𝑗 (π‘₯𝑖 βˆ’ π‘₯𝑗 ) (π‘Ž βˆ’ π‘Ÿ 𝑏 + 𝑐‖π‘₯𝑖 βˆ’ π‘₯𝑗 β€– 2 ) + 1 𝑀 βˆ‘ 𝛾𝑖 (𝑑) 𝑀 𝑖=1 𝑀 𝑗=1 𝑀 𝑖=1 Karena G bersifat simetri dan fungsi (.)f simetri terhadap pusat koordinat maka: οΏ½Μ‡Μ…οΏ½ = 1 𝑀 βˆ‘ 𝛾𝑖 (𝑑) 𝑀 𝑖=1 = 𝐾 exp(βˆ’π›½1𝑑) sin(𝛽2𝑑) Diketahui 𝛾𝑖 (𝑑) merupakan fungsi terbatas. Hal ini berarti untuk 𝑑 β†’ ∞ berakibat οΏ½Μ‡Μ…οΏ½ menuju ke 0. β–  Selanjutnya dibahas tentang kestabilan model (4). Adapun untuk menganalisis kestabilan model digunakan kestabilan Lyapunov. Teorema 2: Perhatikan model multi agen (4) dengan fungsi gangguan (3). Untuk t menuju tak hingga, setiap agen i konvergen pada suatu daerah terbatas yang didefinisikan sebagai berikut: Ξ© = {π‘₯: βˆ‘ β€–π‘₯𝑖 βˆ’ οΏ½Μ…οΏ½β€– ≀ 𝜌 2𝑀 𝑖=1 } (6) Dengan 𝜌 = 𝐴𝐡+2𝐾 √2π‘Žπ‘€π‘€ , 𝐴 = βˆ‘ 𝑀𝑖𝑗 𝑀 𝑗=1 , 𝐡 = 1 2 π‘Ÿβˆš 1 𝑏𝑐 , dan 𝑀 elemen terkecil dari 𝑀𝑖𝑗 ,𝑀 β‰  0. Bukti: Misal 𝑒𝑖 = π‘₯𝑖 βˆ’ οΏ½Μ…οΏ½. Definisikan fungsi Lyapunov untuk model (4), yaitu 𝑉 = βˆ‘ 𝑉𝑖 𝑀 𝑖=1 dengan 𝑉 = 1 2 𝑒𝑖 𝑇 𝑒𝑖 sehingga 𝑉 = βˆ‘ 𝑉𝑖 = 𝑀 𝑖=1 1 2 βˆ‘ 𝑒𝑖 𝑇 𝑒𝑖 𝑀 𝑖=1 . Dengan menurunkan 𝑉𝑖 terhadap t diperoleh: οΏ½Μ‡οΏ½ = βˆ‘ �̇�𝑖 𝑀 𝑖=1 𝑉 Μ‡ = βˆ‘ 𝑒𝑖 𝑇 {βˆ’ βˆ‘ 𝑀𝑖𝑗 (π‘₯𝑖 βˆ’ π‘₯𝑗) (π‘Ž βˆ’ π‘Ÿ 𝑏 + 𝑐‖π‘₯𝑖 βˆ’ π‘₯𝑗‖ 2 ) 𝑀 𝑖=1 + 𝛾𝑖 (𝑑) βˆ’ 1 𝑀 βˆ‘ 𝛾𝑖 (𝑑) 𝑀 𝑗=1 } 𝑀 𝑖=1 = βˆ’ βˆ‘ βˆ‘ 𝑒𝑖 𝑇𝑀𝑖𝑗 (π‘₯𝑖 βˆ’ π‘₯𝑗) (π‘Ž βˆ’ π‘Ÿ 𝑏 + 𝑐‖π‘₯𝑖 βˆ’ π‘₯𝑗‖ 2 ) 𝑀 𝑗=1 𝑀 𝑖=1 + βˆ‘ 𝑒𝑖 𝑇 (𝛾𝑖 (𝑑) βˆ’ 1 π‘š βˆ‘ 𝛾𝑗 (𝑑) 𝑀 𝑗=1 ) 𝑀 𝑖=1 = βˆ’π‘Ž βˆ‘ βˆ‘ 𝑒𝑖 𝑇𝑀𝑖𝑗 (π‘₯𝑖 βˆ’ π‘₯𝑗) 𝑀 𝑗=1 𝑀 𝑖=1 + βˆ‘ βˆ‘ 𝑒𝑖 𝑇𝑀𝑖𝑗 (π‘₯𝑖 βˆ’ π‘₯𝑗) ( π‘Ÿ 𝑏 + 𝑐‖π‘₯𝑖 βˆ’ π‘₯𝑗‖ 2) 𝑀 𝑗=1 𝑀 𝑖=1 +     βˆ‘ 𝑒𝑖 𝑇 (𝛾𝑖 (𝑑) βˆ’ 1 𝑀 βˆ‘ 𝛾𝐽 (𝑑) 𝑀 𝑗=1 ) 𝑀 𝑖=1 Ambil 𝑀 elemen terkecil dari 𝑀𝑖𝑗 dengan 𝑀 β‰  0, maka: Analisis Model Multi Agen dengan Gangguan Jurnal CAUCHY – ISSN: 2086-0382 191 οΏ½Μ‡οΏ½ ≀ βˆ’2π‘Žπ‘€π‘€π‘‰ + βˆ‘ βˆ‘ 𝑒𝑖 𝑇 𝑀𝑖𝑗 (π‘₯𝑖 βˆ’ π‘₯𝑗 ) π‘Ÿ 𝑏 + 𝑐‖π‘₯𝑖 βˆ’ π‘₯𝑗 β€– 2 𝑀 𝑗=1 𝑀 𝑖=1 + βˆ‘ 𝑒𝑖 𝑇 𝑀 𝑖=1 (γ𝑖 (𝑑) βˆ’ 1 𝑀 βˆ‘ γ𝑗 (𝑑) 𝑀 𝑗=1 ) ≀ βˆ’2π‘Žπ‘€π‘€π‘‰ + βˆ‘ βˆ‘ 𝑀𝑖𝑗 ‖𝑒𝑖 𝑇 β€–β€–π‘₯𝑖 βˆ’ π‘₯𝑗 β€– π‘Ÿ 𝑏 + 𝑐‖π‘₯𝑖 βˆ’ π‘₯𝑗 β€– 2 𝑀 𝑗=1 𝑀 𝑖=1 + βˆ‘ 𝑒𝑖 𝑇 𝑀 𝑖=1 (γ𝑖 (𝑑) βˆ’ 1 𝑀 βˆ‘ γ𝑗 (𝑑) 𝑀 𝑗=1 ) . Karena β€–π‘₯𝑖 βˆ’ π‘₯𝑗‖ π‘Ÿ 𝑏+𝑐‖π‘₯π‘–βˆ’π‘₯𝑗‖ 2 adalah fungsi terbatas dan memiliki nilai maksimum pada β€–π‘₯𝑖 βˆ’ π‘₯𝑗 β€– = √ 𝑏 𝑐 maka, οΏ½Μ‡οΏ½ ≀ βˆ’2π‘Žπ‘€π‘€π‘‰ + 1 2 π‘Ÿβˆš 1 𝑏𝑐 βˆ‘ (‖𝑒𝑖 𝑇 β€– βˆ‘ 𝑀𝑖𝑗 𝑀 𝑗=1 ) 𝑀 𝑖=1 + βˆ‘ 𝑒𝑖 𝑇 𝑀 𝑖=1 (γ𝑖 (𝑑) βˆ’ 1 𝑀 βˆ‘ γ𝑗 (𝑑) 𝑀 𝑗=1 ) ≀ βˆ’2π‘Žπ‘€π‘€π‘‰ + 1 2 π‘Ÿβˆš 1 𝑏𝑐 βˆ‘ (‖𝑒𝑖 𝑇 β€– βˆ‘ 𝑀𝑖𝑗 𝑀 𝑗=1 ) 𝑀 𝑖=1 + βˆ‘β€–π‘’π‘– 𝑇 β€– (‖γ𝑖 (𝑑)β€– + 1 𝑀 β€–βˆ‘ γ𝑗 (𝑑) 𝑀 𝑗=1 β€–) . 𝑀 𝑖=1 Karena 𝛾𝑖 (𝑑) terbatas maka ‖𝛾𝑖 (𝑑)β€– ≀ 𝐾, sehingga οΏ½Μ‡οΏ½ ≀ βˆ’βˆšπ‘‰ (π‘Žπ‘€π‘€2βˆšπ‘‰ βˆ’ √2(𝐴𝐡 + 2𝐾)) dengan 𝐴 = βˆ‘ 𝑀𝑖𝑗 𝑀 𝑗=1 dan = 1 2 π‘Ÿβˆš 1 𝑏𝑐 . Agar syarat kestabilan Lyapunov dipenuhi, maka haruslah π‘Žπ‘€π‘€2βˆšπ‘‰ βˆ’ √2(𝐴𝐡 + 2𝐾) > 0, atau diperoleh: 𝑉 > ( 𝐴𝐡+2𝐾 √2π‘Žπ‘€π‘€ ) 2 . Hal ini berarti bahwa setiap agen i akan konvergen pada suatu daerah yang terbatas (6) β–  SIMULASI NUMERIK Pada bagian ini diperlihatkan beberapa hasil simulasi numerik yang merupakan ilustrasi dari model (1) pada ruang dimensi 2 dengan fungsi penarik/penolak (2) dan fungsi gangguan (3). Pada simulasi ini disimulasikan terhadap 10 agen, dengan posisi agen dapat dilihat pada tabel 1. Adapun, nilai konstanta pada fungsi penarik/penolak adalah ,1ο€½a ,1ο€½b ,2.0ο€½c dan 20ο€½r , konstanta ini menggunakan konstanta Gazi dan Passino (2003). Sedangkan nilai-nilai konstanta pada fungsi gangguan (3) adalah ,1ο€½K 8 1  dan 5.0 2  Simulasi numerik di bawah ini menunjukkan perilaku gerak pusat dari multi agen dan anggota dari model multi agen tersebut pada ruang dimensi dua. Tabel 1. Koordinat/posisi agen agen 1 agen 2 agen 3 agen 4 agen 5 (3,4) (4,3) (6,6) (6,5) (8,7) agen 6 agen 7 agen 8 agen 9 agen 10 (4,6) (9,9) (9,8.5) (8,9) (8,3) Pertama-tama disimulasikan gerak pusat dari model multi agen tanpa gangguan (3), kemudian juga disimulasikan pusat dari model multi agen dengan fungsi gangguan (3). Hal ini digunakan untuk melihat kestationeran model dengan pengaruh gangguan. Hasil simulasi numerik ditunjukkan pada gambar berikut ini. Gambar 1. Pergerakan Pusat Multi Agen tanpa Gangguan Hasil simulasi pada gambar 1, nampak bahwa pusat dari model multi agen bersifat stasioner. Sedangkan gambar 2 merupakan hasil simulasi pergerakan pusat dari model multi agen dengan gangguan. Dari gambar 2, nampak bahwa pusat dari model multi agen juga stasioner. Hal ini memperlihatkan bahwa model (4) merupakan model multi agen yang stabil. Selanjutnya dilakukan hal yang sama untuk gerak anggota dari model multi agen. Analisis kestabilan yang dibuktikan pada teorema 2, secara simulasi numerik ditunjukkan pada gambar 3 dan gambar 4. Hasil simulasi pada gambar 3, nampak bahwa gerak dari model multi agen konvergen pada daerah di sekitar pusat dari model multi agen. Sedangkan gambar 4 merupakan hasil 4 6 8 10 12 14 16 -6 -4 -2 0 2 4 6 8 Sentot Achmadi dan Miswanto 192 Volume 2 No. 4 Mei 2013 simulasi pergerakan dari model multi agen dengan gangguan. Dari gambar 4, nampak bahwa model multi agen juga konvergen pada daerah di sekitar pusat dari model multi agen. Hal ini memperlihatkan bahwa model (4) merupakan model multi agen yang stabil. Gambar 2. Pergerakan Pusat Multi Agen Dengan Gangguan Gambar 3. Pergerakan Multi Agen tanpa Gangguan Gambar 4. Pergerakan Multi Agen dengan Gangguan PENUTUP Dari analisis secara analitik, menunjukkan bahwa model multi agen (4) adalah suatu model yang stasioner dan stabil. Hal ini ditunjukkan dengan analisis pada teorema 1 dan teorema 2. Hasil ini juga didukung dengan simulasi numerik pada gambar 1, gambar 2, gambar 2, dan gambar 4. REFERENSI [1] Breder, C. M., 1954, Equation Descriptive of Fish Schools and Other Animal Aggregation, Ecology, Vol. 35, No.3, pp. 361-370. [2] Chu, T., Wang, L. dan Chen, T., 2005, Self- Organized Motion in a Class of Anisotropic Swarm: Convergence vs Oscillation, Proceedings American Control Conference, Portland. [3] Gazi, V. dan Passino, K.M., 2002, Stability Analysis of Swarms in an Environment with an Attractant/Repellent Profile, Proceedings of the American Control Conference, Anchorage. [4] Gazi, V. dan Passino, K.M., 2003, Stability Analysis of Swarms, IEEE Transaction on Automatic Control, Vol. 48, No.4. [5] Gazi, Veysel dan Passino, K.M., 2004, Stability Analysis of Social Foraging Swarms, IEEE Transaction on System, Man, and Cybernetics- Part B: Cybernetics, Vol. 34. [6] Wang, L., Shi, H., Chu, T., Zhang, W. dan Zhang, L., 2004, Aggregation of Foraging Swarms, In advance in Artificial Intelligence, Lecture Notes in Artificial Intelligence, Vo. 3339, Springer-Verlag. [7] Shi, H., Wang, L. dan Chu, T., 2004, Swarming Behavior of Multi-Agent System, Journal of Control and Applications, Vol. 4, pp. 313 – 318. 4 6 8 10 12 14 16 -6 -4 -2 0 2 4 6 8 0 5 10 15 20 25 -10 -5 0 5 10 15 agen 1 agen 2 agen 3 agen 4 agen 5 agen 6 agen 7 agen 8 agen 9 agen10 pusat agen 0 5 10 15 20 25 -10 -5 0 5 10 15 agen 1 agen 2 agen 3 agen 4 agen 5 agen 6 agen 7 agen 8 agen 9 agen10 pusat agen PENDAHULUHAN MODEL MULTI AGEN ANALISIS DARI MODEL MULTI AGEN SIMULASI NUMERIK PENUTUP REFERENSI