Halaman jurnal: http://jurnal.yudharta.ac.id/v2/index.php/EXPLORE-IT/
Akreditasi Sinta 5 (S5) – SK No. 36/E/KPT/2019 p-ISSN 2086-3489 (Print)- e-ISSN 2549-354X (Online) DOI https://doi.org/10.35891/explorit

## Perancangan Prediktor Untuk Permasalahan Konsesus Dengan Delay Input Dan Komunikasi Dengan Menggunakan Graf Komplit
Moh. Yasya Bahrul Ulum 1 , Trihastuti Agustinah 2
1, 2) Departemen Teknik Elektro, Institut Teknologi Sepuluh Nopember, Surabaya, Indonesia email: 1 yasyabahrululum@gmail.com , 2 trihastuti@ee.its.ac.id
INFO ARTIKEL ABSTRAK
Sejarah Artikel:
Diterima 14 Februari 2022
Direvisi 19 Maret 2022
Disetujui 8 Juni 2022 Dipublikasi 8 Juni 2022 Rancangan prediktor berbasis input delay (dengan bukti) dapat mengkompensasi efek dari  delay  komunikasi  berupa  osilasi  dan  adanya  batas  kestabilan  pada  permasalahan konsensus  dengan  delay  input  dan  delay  komunikasi.  Penelitian  ini  bertujuan  untuk mengetahui  bagaimana  efek  penggunaan  prediktor  berbasis  input  delay  ke  sebuah permasalahan  konsensus  dengan  delay.  Metode  yang  digunakan  dalam  penelitian  ini berdasarkan pada konsep partisi graf dapat menjadi beberapa graf yang komplit. Hasil penelitian didapatkan prediktor untuk mengkompensasi delay sepenuhnya menghilangkan efek dari delay  melakukan peniadaan  komponen dengan delay  dengan cara memanipulasi graf agar menjadi graf komplit. Terdapat tiga metode mengkompensasi sepenuhnya delay yaitu walk-based, sequential predictive predictive, dan  graf khusus.
Katakunci: Permasalahan Konsensus Delay
Prediktor Graf

## ABSTRACT
Keyword: Consensus Problems Delay Prediktor Graf
Predictors  design  based  on  input  delay  (with  evidence)  can  compensate  for  the  effects  of communication  delays  (in  the  form  of  oscillations  and  the  existence  of  stability  limits)  on consensus problems with input delays and communication delays.  This study  aims to find out the effect of using input delay-based predictors to a consensus problem with delay. The method used in this study is based on the concept of partitioning graphs into several complete graphs. The results provide analytical evidence that prediction method can be developed to completely eliminate the effects of delay by manipulating the graph into a complete graph. There are three methods; walk-based, sequential predictive predictive, and special graph.
DOI Artikel 10.35891/explorit.v14i1.2933
@2022 diterbitkan oleh Prodi Teknik Informatika Universitas Yudharta Pasuruan

## 1. Pendahuluan
Teori graf adalah cabang matematika yang memiliki aplikasi praktis yang luas. Banyak masalah yang timbul dalam bidang yang beragam seperti psikologi, kimia, teknik industri dan listrik, perencanaan transportasi, manajemen, pemasaran, dan pendidikan dapat diajukan sebagai masalah dari teori grafik. Karena itu, teori grafik tidak hanya merupakan bidang yang menarik dalam dirinya sendiri tetapi juga dasar pemersatu dari mana hasil dari bidang lain dapat dikumpulkan, dibagikan, diperluas, dan disebarluaskan. Tidak seperti bidang ilmiah lainnya, teori grafik memiliki ulang tahun yang  pasti.  Makalah  pertama  tentang  grafik  ditulis  oleh  matematikawan  Swiss  Leonhard  Euler  (1707-1783)  dan  diterbitkan  pada  tahun  1736  oleh Academy of Science di St. Petersburg. Studi Euler tentang grafik dimotivasi oleh apa yang disebut masalah jembatan Konigsberg.
Permasalahan konsensus adalah salah satu jenis permasalahan dasar pada sistem multi agen [2]-[3]. Pada permasalahan konsensus, setiap agen  saling  berkomunikasi  dan  memiliki  tujuan  dapat  berkumpul  pada  satu  titik  yang  sama.  Permasalahan  konsensus  ini  menjadi  permasalahan mendasar  pada  kontrol  kooperatif  sistem  multi  agen  seperti  permasalahan  flocking  dan  kontrol  formasi.  Beberapa  contoh  penerapan  permasalahan konsensus diantaranya penggunaan jaringan sensor dan formasi pesawat. Pada permasalahan sistem multi agen ini, sekelompok agen dihubungkan oleh sebuah sistem komunikasi sehingga dapat menyelesaikan suatu masalah dimana masalah tersebut tidak dapat diselesaikan apabila ada agen yang tidak bekerja sama [2].
Pada  Penelitian  [3],  menjelaskan  bahwa  pada  permasalahan  konsensus  dapat  divariasikan  dalam  berbagai  asumsi.  Salah  satunya  adalah adanya kekurangan dalam hal komunikasi dalam bentuk delay komunikasi. Adanya delay pada permasalahan konsensus membuat akar Karakteristik sistem  menjadi  bilangan  tidak  riil  sehingga  memunculkan  osilasi.  Osilasi  sendiri  meskipun  tidak  berpengaruh  pada  laju  konsensus  namun mengakibatkan energi yang dibutuhkan semakin besar dan apabila diaplikasikan pada kontrol formasi dapat menyebabkan tabrakan antar agen. Semakin besar  delay  membuat  osilasi  semakin  besar  bahkan  pada  batas  tertentu  menjadi  tidak  stabil.  Pada  nilai  tertentu,  ada  batas  maksimal  delay  yang diperbolehkan agar sistem menjadi stabil.
Adapun permasalahan konsensus paling dasar yang dijelaskan pada Penelitian [3] memiliki solusi yang dapat dirumuskan dalam bentuk persamaan differensial biasa sehingga membentuk sistem linier. Sistem linier dengan delay input dapat menjadi sebuah desain sebuah prediktor berbasis input delay sehingga dapat mengurangi bahkan dapat menghilangkan sifat delay.
Maka dari itu penulis ingin mengetahui bagaimana efek penggunaan prediktor berbasis input delay ke sebuah permasalahan konsensus dengan delay. Terutama  pada  penelitian  [1]  yang  menggunakan  prediksi  satu  langkah  untuk  mengkompensasi  delay  input  namun  belum  untuk  delay  komunikasi dimana masih bergantung pada hasil penelitian [2].
Pada penelitian ini, penulis ingin menggunakan predikasi dua langkah ataupun tiga langkah untuk mengkompensasi delay input dan delay komunikasi.

## 2. Metodologi Penelitian
Akan  digunakan  sejumlah 𝑁 agen  dengan  masing-masing  agen  memiliki  plant  identik  yaitu  single  integrator  dengan  delay  input 𝜏 𝑖𝑛 . Berikut adalah model agen 𝑖 𝑥̇ 𝑖 (𝑡) = 𝑢(𝑡 − 𝜏 𝑖𝑛 ),   𝑖 = 1,2, … , 𝑁
(1)
Agen-agen tersebut berkomunikasi membentuk graf 𝒢 = (𝒱, ℰ) dimana vertex dari 𝒢 menyatakan agen-agen, 𝒱 = {1,2, … , 𝑁} . Kemudian (𝑖, 𝑗) ∈ ℰ jika dan hanya jika agen 𝑖 dan 𝑗 berkomunikasi. Untuk mempermudah, pasangan agen (𝑖, 𝑗) yang dapat berkomunikasi dikatakan berdekatan / adjacent . Agen 𝑖 dan 𝑗 yang berkomunikasi memiliki delay dalam penyampaian informasi dari 𝑖 ke 𝑗 ataupun dari 𝑗 ke 𝑖 sebesar 𝜏 𝑐 atau pada bahasan ini disebut delay komunikasi.
Tujuan dari permasalahan konsensus adalah ∀𝑖, 𝑗 ∈ 𝒱 memenuhi
𝑙𝑖𝑚 𝑡→∞ 𝑥 𝑖 (𝑡) − 𝑥 𝑗 (𝑡) = 0
(2)
Pada umumnya, jika tanpa prediktor maka sistem seharusnya seperti yang telah dijelaskan pada Penelitian [3] dimana 𝑥 merupakan variabel state Nx1 vektor. Matriks N x N merupakan Matriks Laplacian.
𝑥̇(𝑡) = −𝐿𝑥(𝑡 − 𝜏)
(3)
Rancangan penyelesaian pada Penelitian ini adalah mempartisi graf menjadi beberapa graf komplit. Misal 𝒢 1 , 𝒢 2 , … , 𝒢 𝑀 adalah partisi dari 𝒢 sedemikian sehingga masing-masing 𝒢 𝑘 𝑘 = 1,2, … , 𝑀 , adalah graf komplit. Sebagai contoh partisi yang dimaksud ada pada Gambar 1. berikut.
Gambar 1. Contoh lustrasi partisi menjadi graf komplit.
Kemudian didefinisikan pula 𝐋 𝛼 adalah matriks Laplacian yang hanya memuat semuat edge dari 𝒢 1 , 𝒢 2 , … , 𝒢 𝑀 sedangkan 𝐋 𝛽 adalah matriks Laplacian yang memuat semua edge selain dari 𝒢 1 , 𝒢 2 , … , 𝒢 𝑀 . Definisikan agen 𝑖 dan agen 𝑗 sekawan apabila terdapat 𝑘 sehingga (𝑖, 𝑗) ∈ 𝒱 𝑘 . Misal 𝐋 adalah matriks Laplacian dari 𝒢 maka 𝐋 𝛼 + 𝐋 𝛽 = 𝐋 (4)
Tanpa mengurangi keumuman misal:
𝐋 𝛼 = [ 𝐊 1 0 ⋯ 0 0 𝐊 2 ⋯ 0 ⋮ ⋮ ⋱ ⋮ 0 0 ⋯ 𝐊 𝑀 ] (5)
Definisikan 𝐊 𝑖 adalah Laplacian dari graf komplit 𝒢 𝑖 untuk 𝑖 = 1,2, … , 𝑀 .
Kemudian, nilai 𝐋 harus dipecah dahulu menjadi 𝐋 𝛼 dan 𝐋 𝛽 sebab pembuatan prediksi selalu terdapat matriks 𝐞 −𝐋 . Sementara, elemen- elemen 𝑙 𝑖𝑗 pada 𝐋 apabila 𝑖 dan 𝑗 tidak  berkomunikasi  maka 𝑙 𝑖𝑗 = 0 namun [𝐞 −𝐋 ] 𝑖𝑗 ≠ 0 sehingga  apabila  komunikasi  terbatas,  maka  tidak  dapat dilakukan prediksi. Namun pada graf komplit semua agen pada graf tersebut berkomunikasi sehingga dapat dilakukan prediksi. Misal 𝐱 = [𝑥 1 𝑥 2 … 𝑥 𝑁 ] T . Berikut persamaan konsensus yang diharapkan: 𝐱̇(𝑡) = −𝐋 𝛼 𝐱(𝑡) − 𝐋 𝛽 𝐱(𝑡 − 𝜏 𝑐 ) (6)
Pada  umumnya,  prediktor  akan  bekerja  hanya  ketika  graf  mewakili  agen,  yakni  adalah  graf  komplit.  Dalam  Penelitian  [10]  telah  dijelaskan  cara meningkatkan respon sistem dengan graf komplit gabungan antara koefisien yang tidak tertunda dan koefisien tertunda untuk mengurangi efek delay.
2.1 Perancangan Prediktor
Pada Persamaan (6) masing-masing agen 𝑖 memerlukan informasi antara lain 𝐋 𝛼𝑖 ′ 𝐱(𝑡 + 𝜏 𝑖𝑛 ) dan 𝐋 𝛼𝑖
′ 𝐮 𝛽 (𝑡) dimana 𝐋 𝛼𝑖 ′ adalah baris ke 𝑖 matriks 𝐋 𝛼 ′ = 𝐞 −𝑘 𝛼 𝐋 𝛼 𝜃 . Sehingga untuk mendapatkan Persamaan (6) masing-masing agen 𝑖 memerlukan informasi semua state 𝑥 𝑗 pada waktu 𝑡 + 𝜏 𝑖𝑛 dimana agen 𝑗 adalah agen yang sekawan dengan agen 𝑖 . Maka pada setiap agen 𝑖 juga harus melakukan prediksi untuk mendapatkan 𝐱̂(𝑡 + 𝜏 𝑖𝑛 ) = 𝐞 −𝑘 𝛼 𝐋 𝛼 𝜏 𝑐 𝐱(𝑡 + 𝜏 𝑖𝑛 − 𝜏 𝑐 ) + ∫ 𝐞 𝑘 𝛼 𝐋 𝛼 𝜃 (−𝑘 𝛽 𝐋 𝛽 𝐱(𝑡 − 𝜏 𝑐 + 𝜏 𝑖𝑛 + 𝜃)) 𝑑𝜃 0 −𝜏 𝑐 (7)
Kemudian hasil dari Prediksi (7) digunakan untuk memprediksi 𝐱(𝑡 + 𝜏 𝑖𝑛 + 𝜏 𝑐 ) . Misalkan 𝐱̂̂ menyatakan hasil prediksi dua langkah dari 𝐱 maka
𝐱̂̂(𝑡 + 𝜏 𝑖𝑛 + 𝜏 𝑐 ) = 𝐞 −𝑘 𝛼 𝐋 𝛼 𝜏 𝑐 𝑥̂(𝑡 + 𝜏 𝑖𝑛 ) + ∫ 𝐞 𝑘 𝛼 𝐋 𝛼 𝜃 (−𝑘 𝛽 𝐋 𝛽 𝐱̂(𝑡 + 𝜃 + 𝜏 𝑖𝑛 )) 𝑑𝜃 0 −𝜏 𝑐 = 𝐞 −2𝑘 𝛼 𝐋 𝛼 𝜏 𝑐 𝐱(𝑡 + 𝜏 𝑖𝑛 − 𝜏 𝑐 )
−𝐞 −𝑘 𝛼 𝐋 𝛼 𝜏 𝑐 ∫ 𝐞 𝑘 𝛼 𝐋 𝛼 𝜃 𝑘 𝛽 𝐋 𝛽 𝐱(𝑡 + 𝜏 𝑖𝑛 − 𝜏 𝑐 + 𝜃)𝑑𝜃 0 −𝜏 𝑐 − ∫ 𝐞 𝑘 𝛼 𝐋 𝛼 𝜃 𝑘 𝛽 𝐋 𝛽 𝐞 −𝑘 𝛼 𝐋 𝛼 𝜏 𝑐 𝐱(𝑡 + 𝜏 𝑖𝑛 − 𝜏 𝑐 + 𝜃)𝑑𝜃 0 −𝜏 𝑐 + ∫ ∫ 𝐞 𝑘 𝛼 𝐋 𝛼 𝜃 𝑘 𝛽 𝐋 𝛽 𝐞 𝑘 𝛼 𝐋 𝛼 𝜙 𝑘 𝛽 𝐋 𝛽 𝐱(𝑡 + 𝜏 𝑖𝑛 − 𝜏 𝑐 + 𝜃 + 𝜙) 0 −𝜏 𝑐 𝑑𝜙 0 −𝜏 𝑐 𝑑𝜃 (8)
Definisikan  kembali 𝑟 𝑖𝑗 (𝜃) = (𝐞 𝑘 𝛼 𝐋 𝛼 𝜃 ) 𝑖𝑗 dan 𝑠 𝑖𝑗 (𝜃, 𝜙) = (𝐞 𝑘 𝛼 𝐋 𝛼 𝜃 𝑘 𝛽 𝐋 𝛽 𝐞 𝑘 𝛼 𝐋 𝛼 𝜙 ) 𝑖𝑗 untuk  mempersingkat  persamaan  maka  pada  masing-masing  agen melakukan prediksi dua langkah
𝑥̂̂ 𝑖 (𝑡 + 𝜏 𝑖𝑛 + 𝜏 𝑐 ) = ∑ 𝜉 𝑖𝑗 𝑁 𝑗=1 Dengan 𝜉 𝑖𝑗 = (𝑟 𝑖𝑗 (−2𝜏 𝑐 )𝑥̂ 𝑗 (𝑡 + 𝜏 𝑖𝑛 − 𝜏 𝑐 ) − ∫ 𝑠 𝑖𝑗 (𝜃 − 𝜏 𝑐 , 0) 0 −𝜏 𝑐 𝑥̂ 𝑗 (𝑡 + 𝜏 𝑖𝑛 − 𝜏 𝑐 + 𝜃)𝑑𝜃 − ∫ 𝑠 𝑖𝑗 (𝜃, −𝜏 𝑐 ) 0 −𝜏 𝑐 𝑥̂ 𝑗 (𝑡 + 𝜏 𝑖𝑛 − 𝜏 𝑐 + 𝜃)𝑑𝜃
+ ∫ ∫ 𝑠 𝑖𝑗 (𝜃, −𝜏 𝑐 )𝑢̂ 𝛽𝑗 (𝑡 − 𝜏 𝑐 + 𝜃 + 𝜙) 0 −𝜏 𝑐 𝑑𝜙 0 −𝜏 𝑐 𝑑𝜃
Berikut ilustrasi untuk mempermudah alur prediksi dua langkah pada Gambar 2.
Gambar 2. Alur pengiriman informasi antar agen.
𝑥̂ 𝑖 (𝑡 + 𝜏 𝑖𝑛 ) = 𝑥 𝑖 (𝑡) + ∫ 𝑢 𝛼𝑖 (𝑡 + 𝜃) + 𝑢 𝛽𝑖 (𝑡 + 𝜃 − 𝜏 𝑐 )𝑑𝜃 0 −𝜏 𝑖𝑛 1. Menerima informasi state 𝑥̂ 𝑗 (𝑡 + 𝜏 𝑖𝑛 − 𝜏 𝑐 ) dan 𝑥̂̂ 𝑗 (𝑡 + 𝜏 𝑖𝑛 ) dari agen yang berdekatan. 2. Memberikan sinyal input 𝑢 𝛼𝑖 (𝑡) = −𝑘 𝛼 ∑ 𝑙 𝛼𝑖𝑗 𝑥̂̂ 𝑗 (𝑡 + 𝜏 𝑖𝑛 ) 𝑁 𝑗=1 . 3. Memberikan sinyal input 𝑢 𝛽𝑖 (𝑡 − 𝜏 𝑐 ) = −𝑘 𝛽 ∑ 𝑙 𝛽𝑖𝑗 𝑥̂ 𝑗 (𝑡 + 𝜏 𝑖𝑛 − 𝜏 𝑐 ) 𝑁 𝑗=1 . 4. Melakukan prediksi 𝑢̂ 𝛽𝑖 (𝑡) = −𝑘 𝛽 ∑ 𝑙 𝛽𝑖𝑗 𝑥̂ 𝑗 (𝑡 + 𝜏 𝑖𝑛 ) 𝑁 𝑗=1 . 5. Melakukan prediksi dua langkah 𝑥̂̂ 𝑖 (𝑡 + 𝜏 𝑖𝑛 + 𝜏 𝑐 ) . 6. Mengirimkan informasi 𝑥̂̂ 𝑖 (𝑡 + 𝜏 𝑖𝑛 + 𝜏 𝑐 ) , 𝑥̂ 𝑖 (𝑡 + 𝜏 𝑖𝑛 ) dan 𝑢 𝛽𝑖 (𝑡) ke agen yang berdekatan dengan agen 𝑖 .
Gambar Error! No text of specified style in document. . Blok diagram masing-masing agen.
Untuk memperjelas berikut contoh blok diagram untuk sistem dengan dua agen dan saling berkomunikasi disajikan dalam Gambar 3.

## Gambar 4. Blok diagram untuk kasus 2 agen.
Gambar 4 menjelaskan masing-masing agen memiliki model yang sama baik plant ( single integrator ), delay dan prediktor. Prediktor sebelum input masing-masing agen menggunakan prediksi 1 langkah digunakan untuk mengkompensasi input delay. Sedangkan Prediktor pada output menggunakan prediksi 2 langkah dimana hasil state yang terprediksi di kirim ke agen yang lain dan terdapat delay pada pengiriman informasi ke agen yang lain.

## 3. Hasil Uji Coba Dan Pembahasan
3.1 Deskripsi Data
Penelitian ini menghasilkan metode bagaimana mengkonstruksikan graf lengkap dengan memanfaatkan agen sebagai penghubung informasi. Sebagaimana diketahui bahwa sekelompok agen yang terhubung oleh sistem komunikasi akan memecahkan masalah apabila bekerja sama, sementara jika tidak bekerja sama satu sama lain maka tidak dapat menyelesaikan masalah [9]. Berikut adalah contoh pada graf lengkap yang memanfaatkan agen sebagai penghubung informasi. Pada Gambar 4  terlihat informasi state dari agen 1 bisa disampaikan ke agen 10 dengan melalui agen 4 kemudian 5 kemudian 10.

## Gambar 5. Contoh Graf
Sedemikian sehingga apabila semua informasi dari setiap agen terkirim ke setiap agen maka berapapun besar delaynya ( time independent) akan tetap bisa stabil konsensus dengan respon sistem yang proporsi dengan gain sistem.  Graf komplit juga diterapkan pada Penelitian [5] dalam menganalisis
sifat stabilitas sekelompok agen yang berkomunikasi melakukan penyesuaian vektor kecepatan dan mengupayakan kestabilkan jarak antar-agen dengan menggunakan aturan interaksi terdekat yang terdesentralisasi, bertukar informasi melalui topologi jaringan yang berubah-ubah.
Berikut merupakan beberapa contoh metode mengkompensasi sepenuhhnya delay:
3.1.1Walk Based
Pada metode ini ide dasarnya adalah mengirimkan nilai state agen melalui perantara agen-agen yang lain. Infromasi dari agen 𝑖 ke agen 𝑗 disampaikan melalui walk terdekat dari 𝑖 ke 𝑗 . Sedemikian sehingga masing-masing state perlu menyimpan agen yang lain dan apabila delay komunikasi antar agen adalah 𝜏 maka delay pengiriman informasi ke semua agen adalah 𝑚𝜏 dengan 𝑚 adalah besar diameter.
Gambar 6 memberikan contoh sederhana bagaimana metode ini bekerja. Pada mulanya agen terhubung melalui edge yang bewarna biru. Sehingga graf mulanya adalah 𝒱 = {1,2,3,4,5}, ℰ = {(1,2), (1,4), (2,3), (3,4), (4,5)} dengan delay komunikasi sebesar 𝜏 . Maka informasi state dari agen dua dapat dikirimkan ke agen 4 melalui agen 1, begitu pula dari agen 1 ke agen 3, agen 1 ke agen 5 dan agen 3 ke agen 5 dengan delay komunikasi 2𝜏 . Pada Gambar 6 direpresentasikan dalam edge warna hijau. Kemudian agen 2 mengirimkan informasi ke agen 5 melalui perantara agen 1 dan 4 dengan delay 3𝜏 . Diameter pada graf ini adalah 3 .
Gambar 6. Contoh pengiriman informasi berdasarkan Walk.
Karena graf merupakan graf lengkap dengan delay 3𝜏 maka untuk graf secara umum dapat dibuat persamaan konsensus
𝐱̇(𝑡) = −𝐋𝐱̂(𝑡) (9) dan prediksi state
𝐱̂(𝑡 + 𝑚𝜏) = 𝐞 −2𝑚𝐋 𝐱(𝑡 − 𝑚𝜏) (10)
untuk kasus khusus pada Gambar 6 memiliki nilai 𝑚 = 3 . Nilai 𝑒 −2𝑚𝐿 dapat dibentuk karena masing-masing agen memiliki state dari semua agen yang ada.    Adapun  kelemahan  dalam  metode  ini  adalah  masing-masing  agen  harus  menyimpan  state  dari  setiap  agen  atau  memori  masing-masing  agen memiliki kompleksitas 𝑂(𝑁) .
3.1.2 Sequential Predictive
Metode ini adalah kelanjutan dari apa yang dijelaskan pada Bab 3. Yaitu adanya subgraf komplit pada Bab 3 adalah mendapatkan state konsensus dari subgraf tersebut yaitu jumlahan dari setiap state yang ada pada subgraf komplit 𝐾 𝑖 .
𝑥 𝑖1 + 𝑥 𝑖2 + ⋯ + 𝑥 𝑖𝑘 , 𝑖 1 , 𝑖 2 , 𝑖 3 , … , 𝑖 𝑘 ∈ 𝐾 𝑖 𝑑(𝑥 𝑖1 + 𝑥 𝑖2 + ⋯ + 𝑥 𝑖𝑘 )
𝑑𝑡
= [ 0 𝟏 |𝑉 𝑖 | 0 ] 𝑇

## 𝐋𝐱 = 0
Sehingga nilai tersebut akan konstan apabila tidak ada gaya dari luar subgraf komplit tersebut. Kemudian dibuatlah metode bagaimana membuat dua atau lebih subgraf komplit bertukar consensus state sedemikian sehingga didapatkan state konsensus dari gabungan beberapa subgraf komplit. Berikut ilustrasi dengan Gambar 7 yang menggunakan graf yang sama dengan Gambar 8.
Gambar 7. Ilustrasi Sequential Predictive .
Apabila menggunakan matriks Laplacian 𝐋 dengan
𝐋 = [ 𝑁 − 1 −1 ⋯ −1 −1 𝑁 − 1 ⋯ −1 ⋮ ⋮ ⋱ ⋮ −1 −1 ⋯ 𝑁 − 1 ]
maka
𝐞 −𝐋𝜃 = [ 𝐴 𝑁 (𝜃) 𝐵 𝑁 (𝜃) ⋯ 𝐵 𝑁 (𝜃) 𝐵 𝑁 (𝜃) 𝐴 𝑁 (𝜃) ⋯ 𝐵 𝑁 (𝜃) ⋮ ⋮ ⋱ ⋮ 𝐵 𝑁 (𝜃) 𝐵 𝑁 (𝜃) ⋯ 𝐵 𝑁 (𝜃) ]
karena 𝐋𝟏 𝑁 = 0 maka 𝐞 −𝐋𝜃 𝟏 𝑁 = 𝟏 𝑁 maka
𝐴 𝑁 (𝜃) + (𝑁 − 1)𝐵 𝑁 (𝜃) = 1
dan karena 𝐋 [ 𝑁 − 1 −𝟏 𝑁−1 ] = 𝑁 [ 𝑁 − 1 −𝟏 𝑁−1 ] maka 𝐞 −𝐋𝜃 [ 𝑁 − 1 −𝟏 𝑁−1 ] = 𝐞 −𝑁𝜃 [ 𝑁 − 1 −𝟏 𝑁−1 ] maka
(𝑁 − 1)𝐴 𝑁 (𝜃) − (𝑁 − 1)𝐵 𝑁 (𝜃) = 𝑒 −𝑁𝜃 (𝑁 − 1)
𝐴 𝑁 (𝜃) − 𝐵 𝑁 (𝜃) = 𝑒 −𝑁𝜃
⟹ 𝐴 𝑁 (𝜃) = 1 + (𝑁 − 1)𝑒 −𝑁𝜃 𝑁 , 𝐵 𝑁 (𝜃) = 1 − 𝑒 −𝑁𝜃

## 𝑁
sehingga masing-masing agen 𝑖 dapat menyatakan Persamaan (5.34) dan (5.35) dalam state konsensus 𝑥 1 + ⋯ + 𝑥 𝑛 dan state agen 𝑖 sendiri yaitu 𝑥 𝑖 . Adapun dengan asumsi rata-rata penggabungan beberapa graf adalah dua graf misal 𝒢 𝑎 dan 𝒢 𝑏 bergabung menjadi 𝒢 maka agar konsensus state dari 𝒢 𝑎 menjangkau semua agen pada 𝒢 𝑏 diperlukan maksimal sebesar diameter dari 𝒢 𝑏 atau sebaliknya. Maka apabila 𝑓(𝒢) menyatakan banyak walk yang diperlukan untuk mengirimkan informasi state konsensus ke semua agen pada 𝒢 maka :
𝑓(𝒢) ≤ max{𝑓(𝒢 𝑎 ), 𝑓(𝒢 𝑏 )} + max{diam(𝒢 𝑎 ), diam(𝒢 𝑏 )}
pada kasus terburuknya :
max{𝑓(𝒢 𝑎 ), 𝑓(𝒢 𝑏 )} + max{diam(𝒢 𝑎 ), diam(𝒢 𝑏 )} ≤ 𝑓(𝒢 − {𝑣}) + diam{𝐺} − 1
apabila dilakukan secara rekursif maka :
𝑓(𝒢) ≤ 1 + 2 + 3 + ⋯ + diam{𝐺} − 1 = 𝑂(𝑚 2 )
dengan salah satu kesamaan terjadi saat graf berbentuk path dan penggabungan antar graf dilakukan 1 per satu. Sehingga apabila delay komunikasi adalah 𝜏 maka delay keseluruhan adalah 𝑂(𝑚 2 𝜏) dengan 𝑚 diameter graf. Adapun apabila menggunakan algoritma divide and conquer nilai 𝒢 𝑎 dan 𝒢 𝑏 memiliki  diameter  yang  sama  dan 𝒢 𝑎 maupun 𝒢 𝑏 juga  dipartisi  dalam  2  graf  dengan  diameter  yang  sama  dan  seterusnya  maka  nilai 𝑓(𝒢) dapat diminimalkan hingga
𝑓(𝒢) ≤ diam(𝒢 𝑎 ) + diam (𝒢 𝑎 2 ) + ⋯ + diam (𝒢 𝑎 2 𝑘 ) ≤ 2diam(𝒢) = 2𝑚 dan memori yang digunakan masing-masing agen adalah 𝑂(log 𝑁) .

## 3.1.3 Graf Khusus
Pada Subbab memiliki kelemahan memori 𝑂(𝑁) tetapi travel time 𝑂(𝑚𝜏) dengan 𝑚 adalah diameter sedangkan pada Subbab 4.10.2 memiliki kelebihan memori yang digunakan maksimal sebesar 𝑂(log 𝑁) . Pada graf tertentu diameternya bisa sangat besar yaitu mendekati 𝑁 − 1 ditemukan pada graf berbentuk path atau 𝑁 2 yaitu pada circle. Sehingga pada graf tertentu nilai 𝑚 bisa sangat kecil. Pada bahasan ini akan dibahas graf yang merupakan Kronecker Product dari beberapa graf komplit.
𝒢 = 𝐾 1 ⊗ 𝐾 2 ⊗ … ⊗ 𝐾 𝑙
Karena 𝐾 𝑖 adalah  graf  lengkap  maka  diameternya  adalah 𝑙 dan 𝑁 = |𝐾 1 |. |𝐾 2 | … |𝐾 𝑙 | ≥ 2.2.2 … 2 = 2 𝑙 maka 𝑙 ≤ log 2 𝑁 atau 𝑙 = 𝑂(log 𝑁) . Algoritmanya pun lebih mudah yaitu untuk 𝑗 = 𝑙, 𝑙 − 1, … ,1 dengan 𝒢 0 adalah sebuah vertex. Masing-masing subgraf berbentuk 𝒢 𝑗 = 𝐾 1 ⊗ 𝐾 2 ⊗ … ⊗ 𝐾 𝑗 dipartisi menjadi |𝐾 𝑗 | buah subgraf 𝒢 𝑗−1 = 𝐾 1 ⊗ 𝐾 2 ⊗ … ⊗ 𝐾 𝑗−1 .
Adapun contoh kasus ini yaitu pada graf hypercube yang disajikan pada Gambar 8.
Gambar 8. Hypercube
3.2 Pembahasan Pendekatan Deret Mc Laurin pada Prediktor
Perhatikan Persamaan (9) dan (10), sebenarnya dapat menggunakan pendekatan
𝐞 −2𝐋𝜏 = 𝐈 − 2𝐋𝜏 + 4𝐋 2 𝜏 2 2 − ⋯ (−2𝐋𝜏) 𝑛 𝑛! = 𝑃(−2𝐋𝜏)
Pendekatan tersebut bersifat naif sehingga akan dibuktikan jika 𝑛 < ∞ maka sistem akan tidak stabil jika 𝜆𝜏 cukup besar dengan 𝜆 adalah eigenvalue dari 𝐋 . Perhatikan dari Persamaan (4.34) dan (4.35).
𝐱̇(𝑡) = −𝐋𝐱̂(𝑡) = −𝐋𝑃(−2𝐋𝜏)𝐱(𝑡 − 2𝜏)
kemudian, ambil persamaan Karakteristiknya didapatkan :
𝐈𝑠 = −𝐋𝑃(−2𝐋𝜏)𝑒 −2𝑠𝜏
gunakan dekomposisi terhadap eigenvector 𝐯 maka dengan Cayley-Hamilton karena 𝑥𝑃(−2𝑥𝜏) adalah polinomial maka :
⟹ 𝑠 = −𝜆𝑃(−2𝜆𝜏)𝑒 −2𝑠𝜏 ⟹ 2𝑠𝜏 𝑒 2𝑠𝜏 = −2𝜆𝜏𝑃(−2𝜆𝜏)
dengan lemma pada Subbab 2.1.2 maka agar sistem stabil harus berlaku : 𝜋
2 > −2𝜆𝜏𝑃(−2𝜆𝜏) > 0
Padahal −2𝜆𝜏𝑃(−2𝜆𝜏) adalah polinom tidak mungkin terbatas di atas dan di bawah. Berikut adalah hasil perhitungan batas 𝜆𝜏 untuk beberapa nilai 𝑙 agar sistem menjadi stabil
Tabel 1:  Batas nilai 𝜆𝜏 𝒍 𝐬𝐮𝐩 𝝀𝝉 𝐢𝐧𝐟 𝝀𝝉 𝒍 = 𝟏 𝐬up 𝜆𝜏 = 0.5 inf 𝜆𝜏 = 0 𝒍 = 𝟐 𝐬up 𝜆𝜏 = 0.920343 inf 𝜆𝜏 = 0 𝒍 = 𝟑 𝐬up 𝜆𝜏 = 0.798036 inf 𝜆𝜏 = 0 𝒍 = 𝟒 𝐬up 𝜆𝜏 = 1.24175 inf 𝜆𝜏 = 0 𝒍 = 𝟓 𝐬up 𝜆𝜏 = 1.0903 inf 𝜆𝜏 = 0 𝒍 = 𝟔 𝐬up 𝜆𝜏 = 1.58543 inf 𝜆𝜏 = 0
Maka terbukti untuk 𝑛 < ∞ sistem akan tidak stabil jika 𝜆𝜏 cukup besar. Adapun dengan Teorema Cayley-Hamilton pula nilai 𝐞 −2𝐋𝜏 dapat dinyatakan dalam berhingga suku, lebih tepatnya 𝑁 suku.
𝐞 −2𝐋𝜏 = ∑ 𝛼 𝑖 (−2𝐋𝜏) 𝑖 𝑁−1
𝑖=0
sehingga dapat direalisasikan menggunakan metode walk-based namun sama-sama memiliki memori 𝑂(𝑁) .

## 4. Kesimpulan
Pemanfaatan agen sebagai penghubung informasi dapat membantu mengkonstruksikan graf lengkap sebagai prediktor. Rancangan prediktor berbasis input delay (dengan bukti) dapat mengkompensasi efek dari delay komunikasi pada permasalahan konsensus dengan delay input dan delay komunikasi. Metode mengkompensasi delay sepenuhnya yang diuraikan dalam penelitian ini terdapat tiga, yaitu walk-based, sequential predictive predictive, dan graf  khusus.  Ketiga  metode  prediksi  menjadi  benar-benar  menghilangkan  efek  dari  delay  (meniadakan  komponen  dengan  delay)  dengan  cara memanipulasi graf agar menjadi graf komplit.

## 5. Daftar Pustaka
[1] D.Jungnickel. Graphs, Networks, and Algorithms vol.5., Leipzig: Springer, 2006.
[2] B. Zhou and Z. Lin, “Consensus of high-order multi-agent systems with large input and communication delays,” Automatica, vol. 50, no. 2, pp. 452–464, 2014.
[3] R. Olfati-Saber and R. M. Murray, “Consensus problems in networks of agents with switching topology and time-delays,” IEEE Trans. Automat. Contr., vol. 49, no. 9, pp. 1520–1533, 2004.
[4] D. Tsubakino, M. Krstic, and T. R. Oliveira, “Exact prediktor feedbacks for multi-input LTI systems with distinct input delays,” Automatica, vol. 71, pp. 143–150, 2016.
[5] A. Ramirez and R. Sipahi, “Single-delay and multiple-delay proportional-retarded (PR) protocols for fast consensus in a large-scale network,” IEEE Trans. Automat. Contr., vol. 64, no. 5, pp. 2142–2149, 2019.
[6] M. Mesbahi and M. Egerstedt, “Graph Theoretic Methods in Multiagent Networks,” in Princeton, 2010, pp. 14–60.
[7] S.-I. Niculescu and K. Gu, “Advances in Time-Delay Systems,” in Springer-Verlag Berlin Heidelberg, 2004, pp. 31–43.
[8] Fuzhen Zhang, “Matrix Theory,” in Springer New York Dordrecht Heidelberg London, 2010, Theorem 8.12, pp. 274
[9] S. Izumi, S. I. Azuma, and T. Sugie, “ On a relation between graph signal processing and multi-agent consensus,” in Proc. 55th Conf. Decision and Control, 2016, pp. 957–961.