Voronoi Based Coverage Control

21 05 2008

Di milis sc-ina, sedang dilaksanakan e-kolokium, dimana e-kolokium pertama yang diisi oleh Mas Azwirman Gusrialdi (Mas Iman) tanggal 1-15 Mei 2008 dengan tema Voronoi Based Coverage Control with Anisotropic Sensor. Tema yang diangkat sangat menarik dan merupakan pembelajaran baru bagi saya. Thanks to Mas Iman dan Mas Anto atas e-kolokium yang telah dilaksanakan. Saya buat catatan sedikit untuk mengingatkan beberapa diskusi yang muncul.

Q : Dari latar belakang yang diceritakan, tidak ada satupun referensi yang terkait dengan penggunaan anisotropic sensor. Apa memang belum ada yang mengerjakan, atau belum ada hasil yang signifikan mengenai itu?
A : Memang untuk coverage control dengan menggunakan anisotropic sensor ini, setahu pengetahuan saya saya yang pertama kali mengerjakan. Ada sih yang juga menggunakan anisotropic sensor, cuman definisi anisotropicnya beda, yaitu jika sensornya hanya bisa mensense sampai besaran sudut alpha saja (tidak 360 derajat). Tetapi dia tetap mengasumsikan sensing performance sebagai fungsi dari jarak saja.

Q : Apakah ada bentuk fisik dari anisotropic sensor? Misalnya kalau di mobile robot sangat umum dipakai laser range finder, ultrasonic sonar dsb. IMHO: kalau misalnya laser range finder disusun menjadi array secara merata di badan mobile robot maka hasilnya adalah isotropic sensors, kalau anisotropic?
A : Pertanyaan yang bagus sekali. Sebenarnya anisotropic sensor itu contohnya seperti radar, kamera, directional microphone dll. Cuman model saya disini tidak bisa mewakili semuanya secara precise. Saya sengaja mengambil model ellipse karena ini yang paling “gampang” dianalisanya. Alasannya karena saya ingin menyelidiki dulu ke applicabily-an dari Voronoi method ini untuk anisotropic sensor model ini dan ternyata sayang sekali tidak cukup baik untuk dipakai. Saya juga telah mempublish paper untuk model sensor anisotropic kamera dengan model yang cukup precise, tapi dengan menggunakan method lain. Kalau tertarik bisa saya kirim japri papernya.

Q : Apakah ada interpretasi/penjelasan secara teknis dari cost function equation (3)?
A : Ini juga pertanyaan yang bagus sekali. Untuk menjelaskan arti dari cost function ini saya ingin sedikit memberikan keterangan. Pertama di cost function itu ada function f yang merupakan fungsi dari jarak. f ini menggambarkan sensing performance dari sensornya. Artinya semakin jauh jarak titik yang mau disense dengan sensornya, nilai f semakin kecil i.e. sensing performancenya semakin jelek. Kemudian ada phi yang merupakan fungsi yang menggambarkan pentingnya suatu daerah. Kalau phi tinggi artinya daerah itu penting. Kita tentunya ingin sensor2 kita lebih mendekat ke daerah yang penting maka kita meminimalkan perkalian dari f dan juga phi. Jadi intinya, kita pengen nyuruh sensor2 kita pergi ke daerah yang penting. Kira2 begitu artinya Pak Imam.

Q : Cost function H eq (3), non-negative bounded from below kan mas Iman? Maksudnya there exists a positive real number x such that H >= x? dan min H = x? :d Kalau f kecil dikalikan \phi besar jadinya gmn? Misalnya f=0 dan H=10000, maka nilai optimalnya tidak unik, karena semua f(q_i-p_i)=0 merupakan solusi?
A : Maaf mas,saya agak kurang mengerti. Memang solusinya tidak unik, karena tergantung kita mulainya dimana, tergantung initial positionnya. Tapi yang jelas dengan meminimalkan H, kita akan mencapai suatu (local) optimal configuration. Hal ini juga lumrah karena kita hanya mempunyai local informasi, bukan global informasi.

Q : Dari objective function yang diberikan, ada continuous density distribution function theta(q). Kira-kira continuous density distribution function apa yang digunakan? dan Kenapa?
A : Contoh density functionnya mis : e^-(x^2 + y^2) dengan x, y adalah posisi point yang mau disense. Sengaja dipilih continuous agar collision avoidance bisa terjamin (agar centroid berada di dalam Voronoinya)

Q (Comment) : Untuk mengkonfirmasi saja, berarti pointnya di sini ada pada ‘contiunuous’-nya ya Mas Iman? Sedangkan bentuk distribusinya tidak berpengaruh pada masalah optimasi yang muncul.
A (Comment) : Iya, menurut saya begitu Pak Yudi. Karena density function itu hanya menggambarkan/memodelkan penting tidaknya suatu point yang hendak di sense sama sensor kita.

Q : Sekalian juga kalau bisa dapat penjelasan mengenai objective function (overall sensing cost function) yang digunakan. Apakah ini yang ‘umum’ digunakan? Apakah mungkin ada variasi yang bisa diaplikasikan?
A : Sebenarnya pendefinisian dari cost functionnya tergantung dari approach (asumsi etc) dan juga tujuan yang hendak dicapai (common behaviournya). Berhubung saya memakai Voronoi approach i.e. setiap sensor diasumsikan mempunyai daerah kekuasaannya sendiri, maka cost function itu yang dipakai. Cost function ini juga sebenarnya modifikasi sedikit dari kasus yang isotropic yang sudah pernah ada sebelumnya. Jadi tergantung asumsi2 yang kita buat dan juga approachnya. Untuk selain Voronoi approach tentu saja beda cost functionnya.

Q : Apakah secara teknis dynamic equation (\dot{p}_i=u_i) di equation (4) cukup untuk mewakili dynamics dari mobile sensors? IMHO: misalnya pesawat terbang, mobil, mobile robots dll yang membawa sensor adalah sistem yang nonholonomic dan paling tidak dynamicsnya adalah 4-th order dan nonlinear. Apakah perlu feedback linerization supaya eq (4) bisa menjadi reasonable?
A : Bener sekali pak. Sebenarnya sengaja dipilih model (4) biar gampang analisisnya (sebenarnya dengan model (4) aja udah jatuh bangun ngerjainnya). Tetapi menurut saya untuk model yang lebih rumit juga bisa saja. Intinya setiap agent pergi menuju ke centroid dari daerah kekuasaannya. Sepertinya ada beberapa orang yang mengerjakan untuk kasus non-holonomic atau dynamic yang lebih rumit.

Q (Comment) : Iya betul mas, saya kira tidak mungkin bagi kita untuk mengerjakan semuanya. Tapi saya kira ada model yang juga linear tapi lebih reasonable dari $\dot{p}_i=u_i$ di persamaan (4) yaitu $\ddot{p}_i=u_i$ (dot di ganti ddot). Banyak kasus di mobile robot yang nonholonomic bisa di feedback linearization-kan sehingga menjadi persamaan ini. Tapi $\ddot{p}_i=u_i$ pun masih sangat mungkin untuk di ubah ke bentuk $\dot{p}_i=u_1$ dengan mendefinisikan: u_i=u_1+u_2, dengan u_2=-\dot{p}_i+\ddot{p}_i.
A (Comment) : Bener sekali mas Imam. Model dengan double integrator tentunya lebih reasonable. Cuman saya waktu ngeriset ini lebih tertarik ke pengaruh anisotropic sensor modelnya ke Voronoi approach ini. Tentunya bisa diextend ke double integrator untuk dynamicnya. Ini hanya masalah selera mas🙂 .

Q : Untuk ‘Mobile Sensors Dynamic’ p_i = u_i yang digunakan, seperti diskusi yang sudah muncul, kelihatannya ada beberapa variasi yang bisa digunakan. CMIIW. Bisa gak diceritakan lebih detail Mas Iman, apa kelebihan dan kekurangan variasi yang ada.
A : Benar sekali Pak Yudi. Seperti dijelaskan Mas Imam, model saya masih terlalu sederhana untuk robot/vehicle yang sebenarnya. Selain model saya masih banyak model dynamics yang lain seperti double integrator, non-holonomic (kalau misalnya agentnya non-holonomic) sampai model2 rumit lainnya. Kelebihannya tentu saja modelnya lebih detail dan lebih menggambarkan sistem kita yang sebenarnya. Kekurangannya analisisnya lebih rumit🙂 . Dan juga, suatu cara yang alamiah untuk meng-extend kerjaan kita adalah dengan melihat model2 yang lebih detail/rumit. Ini kebanyakan saya liat dari paper2 di bidang cooperative control ini. Cuman saya kurang tertarik mengutak atik lebih detail di modelnya. Tapi sebenarnya model yang single integrator (yang saya pakai di paper) juga tidak terlalu jelek. Karena saya sudah memakainya untuk eksperimen.

Q : Btw, saya ada sedikit pertanyaan/komentar tentang control law di persamaan (10). Mohon dijelaskan kalau salah. Berdasarkan persamaan (4) -> \dot{p}_i=u_i , maka sekilas kita tahu (karena sistemnya linear, dari fundamental control theory: necessary and sufficient condition) untuk membuat sistemnya assymptotically stable ke c_i adalah dengan men-set u_i= -f(p_i-c_i), dengan f(.,.) > 0. Intinya dengan control law ini maka pole dari persamaan (4) akan berada di left-half plane. Tapi Proof untuk Proposisiton 4.1 Mas Iman sampai harus men-invoke la-Salle invariant principle? apakah perlu? Bukankah f(.,.)=k(p_i-C_{v*i}), dengan k positive maka f(.,.) akan non negative (dan polenya pasti akan berada di left half plane) yang artinya sistemnya pasti assymptotically and exponentially stable? Maksudnya kita tidak harus membunuh nyamuk dengan bom kan?
A : Mungkin belum saya jelaskan kalau control law-nya itu adalah continuous time version Lloyd algorithm. Biasanya di dunia computer science kita menjumpai Lloyd algorithm yang discrete yaitu pertama kita buat Voronoi, hitung centroid lalu pergi ke centroid, lalu hitung lagi Voronoi … diulang2 sampai berhenti algoritmanya. Nah di sini saya membuat versi continuousnya. Seperti dijelaskan di papernya, kalau Voronoi ini tergantung pada posisi. Jadi sebenarnya waktu agentnya bergerak ke centroid dia akan langsung membuat Voronoi yang baru, menghitung centroidnya dan pergi ke centroid yang baru i.e. agentnya belum sampai ke centroid waktu Voronoi yang baru dibentuk (ini mungkin bisa dilihat di video eksperimentnya). Ini dilakukan terus menerus dan finally akan converge ke suatu critical point (satu lagi yang belum saya sampaikan, di cooperative control, kita tidak menggunakan term stable, tapi lebih ke converge to critical points/convergence). Nah ini yang saya tidak bisa lihat di analisis yang Mas Imam berikan karena kelihatannya itu hanya untuk discrete versionnya saja. Dan juga sebenarnya pernghitungan dV/dt (penurunan Lyapunov functionnya) tidak bisa langsung dihitung dengan mudah. Karena Voronoi depends on the position of the agent. Jadi harus melalui beberapa tahap perhitungan.

Q : Tentang asumsi ke-1 yang digunakan, kenapa harus memilih jarak non-Euclidean?
A : Sebenarnya ini trik saya. Alasannya sangat sederhana, saya ingin menganalisis dari sensor model yang sangat sederhana. Karena isotropic sensor bisa dimodelkan dengan lingkaran, maka secara alamiah, extensionnya adalah sebuah ellipse yang menggambarkan anisotropic sensor. kebetulan ellipse ini bisa dirumuskan dengan asumsi-1 (kalau dijabarkan maka persamaan di asumsi satu akan menjadi persamaan ellipse). Selain itu dengan memilih asumsi 1 ditambah fixed and equal orientation, maka masalahnya bisa ditransfer ke isotropic case. Jadi kira2 itu alasannya pak.

Q : Tentang asumsi ke-2, dikatakan bahwa parameter oritentationnya diset statis. Tetapi di Remark ke-3 dikatakan kalau orientationnya diset tidak statis akan memberikan hasil yang lebih baik. Kenapa tidak sekalian menjelaskan tentang optimisasi dengan orientasi yang tidak statis?
A : Jadi salah satu key point dalam mendesign algorihma control-nya adalah agar bagaimana control law-nya itu distributed. Nah dengan anisotropic model ini, Voronoi diagramnya akan kehilangan sifat local information ini, maksudnya untuk membentuk Voronoi diagram yang anisotropic case, diperlukan informasi semua agent. Jadi saya mengasumsusikan orientasinya harus fixed dan sama. meskipun orientasinya tidak sama, saya telah membuktikan (meskipun tidak ditulis di paper buktinya, karena lumayan panjang) kalau control law yang sama akan didapat, hanya saja control law ini tidak distributed. Sedangkan untuk orientasi yang sama tapi tidak statis, tidak logis untuk mengoptimisasi terhadap orientasi, karena control lawnya tidak terdistribusi juga jadinya. Jadi intinya ada di distributed control law-nya pak.

Q : Apakah ini mengimplikasikan bahwa pemodelan dengan orientasi tidak fixed, tidak bisa diaplikasikan (inapplicable)?
A : Sebenarnya bisa saja diaplikasikan Pak Yudi. Hanya saja algoritmanya menjadi tidak terdistribusi. Kita jadi membutuhkan semacam kamera di langit untuk mengetahui posisi ataupun orientasi dari setiap agent. Salah satu jalan lain adalah dengan memodifikasi anisotropic voronoi dengan beberapa asumsi pada sensor modelnya (saya sudah punya beberapa ide, cuman belum pernah dicoba, jadi tidak bisa memberitahu lebih detail).

Q : Apakah algoritma ini sudah diujicoba pada masalah aplikasi riil (misalnya manipulation in hazardous env., seperti pada introduction)? Kalau sudah pernah dicoba barangkali bisa diceritakan mengenai hal tsb. Kalau belum, kira-kira hal apa saja yang perlu dikerjakan sebelum algoritma ini bisa diterapkan pada aplikasi praktis?
A : Mengenai aplikasi algoritma ini, khusus untuk masalah coverage control saya belum menemukan group yang mencoba pada masalah yang sebenarnya, seperti benar2 pada lingkungan beracun etc. semuanya hanya sebatas eksperimen saja. Sedangkan beberapa group e.g. dari Caltech (Richard Murray), University of Pennsylvania (George Pappas) dan juga group Mark Spong sudah pernah menerapkan cooperative control selain coverage control dengan menggunakan UAV. Untuk lebih lengkapnya bisa disearch di website mereka. Menurut pendapat saya, algoritma ini bisa diterapkan pada masalah yang sebenarnya dengan memakai sensor beneran (selama ini eksperimen saya hanya mengasumsikan bahwa di robotnya ada sensor), tentunya kalau beberapa masalah di bawah bisa diselesaikan :
1. Localization. Seperti tersirat di algoritmanya, setiap sensor harus mengetahui posisinya masing2 agar bisa mengkomunikasikannya dengan sensor yang lain. Selama ini saya menggunakan kamera yang ditaruh di atap dan dengan sedikit image processing untuk menentukan posisi suatu agent. Tentunya di dunia real ini tidak mungkin. Salah satu kemungkinan adalah dengan gps.
2. Density function harus diketahui secara lebih dahulu. Namun sekarang sudah ada algoritma yang mengasumsikan kalau kita tidak tahu density functionnya.
3. Region of interestnya harus convex. Algoritma ini tidak bisa diterapkan untuk non-convex region e.g. suatu museum dengan banyak ruang.
4. Telah ada hardware (komunikasi, robot yang dapat memproses data yang diterima untuk menentukan langkah selanjutnya) yang memenuhi. Tapi ini juga tidak ada masalah.

Semoga bermanfaat dan maaf kalau ada salah edit.


Actions

Information

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s




%d bloggers like this: