Dalam seminar ini Program Studi Matematika mengundang Prof. Chao Yang, Department of Applied Mathematics, School of Mathematics and Statistics, Guangdong University of Foreign Studies, China. Webinar ini terlaksana pada 6 Desember 2023 yang dihadiri oleh dosen PS Matematika dan dilaksanakan secara hybrid.
Dalam dunia pengaturan dan perencanaan gerakan, kompleksitas komputasi memainkan peran utama dalam menentukan seberapa efisien suatu sistem dapat merencanakan gerakan pada graf. Ketika kita membahas masalah perencanaan gerakan pada graf, kompleksitas komputasi menjadi sorotan utama karena mencakup sejumlah tantangan yang mempengaruhi kinerja sistem.
Perencanaan gerakan pada graf adalah tentang menemukan lintasan yang optimal atau memadai bagi agen (misalnya, robot atau kendaraan) untuk bergerak dari titik awal ke titik tujuan, dengan mempertimbangkan kendala lingkungan, seperti rintangan, zona terlarang, atau batasan fisik lainnya.
Kompleksitas komputasi masalah ini bergantung pada sejumlah faktor, termasuk ukuran graf (jumlah simpul dan tepi), kompleksitas algoritma yang digunakan, serta struktur dan konfigurasi lingkungan. Misalnya, dalam graf yang sangat padat dengan simpul-simpul yang saling terhubung erat, mencari jalur terpendek mungkin relatif mudah dilakukan dengan algoritma seperti A* atau Dijkstra. Namun, ketika lingkungan menjadi lebih kompleks dengan hambatan-hambatan yang kompleks dan banyak, seperti dalam lingkungan yang dipenuhi dengan objek dinamis atau bergerak, masalah perencanaan gerakan menjadi lebih sulit dan memerlukan pendekatan yang lebih canggih.
Menurut Prof. Chao Yang, “Salah satu masalah paling mendasar dalam ilmu komputer teoretis adalah hubungan antar kelas kompleksitas komputasi. Menentukan kompleksitas komputasi suatu masalah tertentu adalah cara untuk mendapatkan pemahaman yang lebih mendalam tentang kelas kompleksitas komputasi. Sejak diperkenalkannya 21 soal NP-lengkap oleh Karp pada tahun 1972, NP-lengkap telah menjadi kelas soal yang lebih akrab bagi matematikawan dan ilmuwan komputer.”
“Dalam pembicaraan ini, kami fokus pada kelas kompleksitas lain, kelas masalah yang dilengkapi SPACE. Salah satu jenis permasalahan lengkap PSPACE adalah permasalahan perencanaan gerak pada grafik. Namun, sulit untuk menentukan kompleksitas komputasi yang tepat dari beberapa masalah perencanaan gerak. Dalam menentukan kompleksitas komputasi Jam Sibuk 1 kali 1, beberapa metode utama dikembangkan, seperti logika batasan non-deterministik (NCL) dan Subway Shuffle berorientasi 2 warna, oleh Erik Demaine dkk. Kami akan memperkenalkan metode bermanfaat ini dalam pembicaraan ini. Sebagai aplikasi, kami akan menyebutkan pekerjaan kami pada kompleksitas beberapa masalah perencanaan gerak” lanjut beliau.
Salah satu tantangan utama dalam perencanaan gerakan pada graf adalah trade-off antara keakuratan solusi dan waktu komputasi. Misalnya, algoritma yang memastikan solusi optimal mungkin memerlukan waktu komputasi yang sangat lama, terutama dalam graf yang besar atau lingkungan yang sangat kompleks. Di sisi lain, algoritma yang menghasilkan solusi sub-optimal mungkin lebih cepat tetapi kurang dapat diandalkan dalam lingkungan yang dinamis.
Selain itu, kompleksitas komputasi juga dipengaruhi oleh dinamika lingkungan. Misalnya, dalam lingkungan yang berubah secara dinamis, seperti lingkungan yang diisi dengan objek atau agen yang bergerak, perencanaan gerakan harus dapat menyesuaikan rencana sesuai dengan perubahan lingkungan dengan cepat dan efisien. Dengan demikian, memahami dan mengelola kompleksitas komputasi dalam perencanaan gerakan pada graf menjadi kunci dalam merancang sistem yang efisien dan andal dalam berbagai lingkungan dan situasi. Ini melibatkan penggunaan algoritma yang tepat, pengoptimalan parameter, serta pengembangan teknik yang inovatif untuk mengatasi tantangan kompleksitas yang terus berkembang dalam domain ini.
Dokumentasi.
