Pengembangan Algoritme Modified Ant Colony Optimization untuk Task Allocation pada Sistem Multi-Robot

Abstract

Sistem multi-robot adalah sekumpulan robot yang dapat berkolaborasi untuk menyelesaikan suatu tugas (task) dengan cara berkomunikasi dan berkoordinasi antar robot. Masalah task allocation pada sistem multi-robot adalah masalah pengalokasian beberapa robot yang berkolaborasi untuk menyelesaikan suatu task dengan optimal. Salah satu algoritme optimasi yang dapat digunakan untuk menyelesaikan masalah task allocation adalah Ant Colony Optimization (ACO). Beberapa penelitian sebelumnya telah meneliti kinerja dari algoritme ACO dalam menyelesaikan masalah task allocation. Beberapa penelitian memodifikasi algoritme ACO agar mendapatkan hasil yang paling efisien. Namun, sebagian besar penelitian tersebut belum mempertimbangkan faktor-faktor yang ada di lingkungan nyata, seperti apa yang sebenarnya dibutuhkan dan berapa yang perlu dioperasikan. Penelitian-penelitian terdahulu juga belum mempertimbangkan utilisasi kemampuan robot dalam menyelesaikan task sehingga dapat mengurangi efisiensi dari kinerja sistem multi-robot. Penelitian ini memodifikasi algoritme ACO yang telah dikembangkan pada penelitian sebelumnya dengan menambahkan faktor utilisasi kapabilitas sistem dalam menyelesaikan task. Pada penelitian sebelumnya, terdapat nilai efisiensi yang digunakan untuk memperbaharui feromon pada tiap jalur yang dapat dilewati. Algoritme yang diusulkan dalam penelitian ini menambahkan persentase utilisasi kapabilitas robot yang digunakan ke dalam perhitungan nilai efisiensi tersebut. Selain itu, penelitian ini mengimplementasikan algoritme ACO yang diusulkan ke suatu sistem multi-robot yang dirancang menggunakan satu komputer sebagai server dan lima robot bertipe gripper sebagai klien. Masing-masing robot gripper dilengkapi dengan modul komunikasi sehingga dapat berkomunikasi dengan server menggunakan teknik komunikasi client-server yang paralel. Pada penelitian ini, diasumsikan terdapat satu target yang membutuhkan beberapa kemampuan dari robot agar task dapat diselesaikan. Kumpulan robot yang memiliki kemampuan yang dibutuhkan oleh target dengan sisa kemampuan yang tidak terpakai (wasted capabilities) paling sedikit adalah koalisi robot yang terbaik. Pencarian koalisi robot terbaik dilakukan di server dengan menggunakan algoritme ACO yang diusulkan. Kemudian, hasil koalisi terbaik tersebut dikembalikan ke tiap robot. Tiap robot akan bertindak sesuai hasil yang didapatkan, bergerak lurus jika robot termasuk ke dalam hasil koalisi tersebut atau diam di tempat jika selainnya. Simulasi yang telah dilakukan menunjukkan bahwa algoritme yang diusulkan berhasil menemukan koalisi robot terbaik dengan wasted capabilities ±10% lebih rendah dari algoritme pendahulunya. Dengan kata lain, algoritme ACO yang diusulkan lebih efisien dalam hal utilisasi robot dibandingkan algoritme pendahulunya. Penggunaan algoritme ACO yang diusulkan pada lingkungan nyata dapat mengoptimalkan jumlah robot yang terpakai, sehingga biaya pengoperasian sistem multi-robot lebih rendah. Penelitian ini juga telah merancang sistem multi-robot secara nyata untuk menguji algoritme dan berhasil menunjukkan bahwa hanya robot yang termasuk ke dalam koalisi terbaik saja yang bergerak lurus mendekati target.

A multi-robot system is a collection of robots that can collaborate to complete a task by communicating and coordinating between the robots. A task allocation problem in a multi-robot system is a problem of allocating several robots that can collaborate to complete and solve a task optimally. One of the optimization algorithms that can be used to solve this task allocation problem is Ant Colony Optimization (ACO). Previous studies have examined the performance of the ACO algorithm in solving task allocation problems. Several studies modify the ACO algorithm in order to get the most efficient results. However, most of these studies have not considered the factors that exist in the real environment, such as what is actually needed and how much needs to be operated. Previous studies have also not considered the utilization of the abilities of the robots to complete the task which may reduce the efficiency of the multi-robot system performance. This study modifies the ACO algorithm that has been developed in a previous study by adding a robot capability utilization factor when completing the task. In previous studies, there were efficiency values used to renew pheromones on each passable path. The algorithm proposed in this study adds the percentage of robot capability utilization used in the calculation of the efficiency value. In addition, this study implements the proposed ACO algorithm into a multi-robot system that designed as one computer as a server and five gripper-type robots as the clients. Each gripper robot is equipped with a communication module so that it can communicate with the server using parallel client-server communication techniques. In this study, it is assumed that there is one target that requires several abilities from the robot so that the task can be completed. The set of robots that have the capabilities required by the target with the least amount of wasted capabilities is the best robot coalition. The search for the best robot coalition is carried out on the server using the proposed ACO algorithm. Then, the results of the best coalition are returned to each robot. Each robot will act according to the results, which is to move in a straight line if the robot is included in the coalition results or to stay in place if otherwise. The simulations that have been carried out showed that the proposed algorithm finds the best robot coalition with ±10% lower wasted capabilities than its predecessor algorithm. In other words, the proposed ACO algorithm is more efficient in terms of robot utilization than its predecessor algorithm. The use of the proposed ACO algorithm in a real environment can optimize the number of robots used, so that the operating costs of the multi-robot system are lower. This research has also successfully designed a real multi-robot system to test the algorithm and showed only the robots that included in the best coalition were moving in a straight line towards the target.