Masalah Surplus Parking Gathering pada Grid Tak Hingga

Makalah ini memperkenalkan **Surplus Parking Gathering Problem** (

), tantangan koordinasi baru untuk robot pada grid tak hingga. Masalah ini melibatkan sekumpulan node parkir yang ditentukan, masing-masing dengan kapasitas yang telah ditetapkan, dan jumlah total robot yang melebihi total kapasitas parkir. Tujuannya adalah menjenuhkan setiap node parkir tepat pada kapasitasnya sambil mengumpulkan semua robot surplus pada satu node grid bersama yang tidak ditentukan sebelumnya. Robot-robot tersebut bersifat otonom, anonim, oblivious, identik, tanpa orientasi, dan homogen. Penulis mempertimbangkan model asinkron (\textsc{async}) dengan visibilitas global dan deteksi multiplisitas kuat global. Masalah ini memperluas masalah gathering dan parking klasik dengan memasukkan batasan kapasitas dan penanganan surplus. Makalah ini menetapkan kondisi yang diperlukan untuk solvabilitas dengan mengidentifikasi konfigurasi awal yang tidak mengizinkan algoritma terdistribusi deterministik. Untuk semua konfigurasi yang dapat diselesaikan, disajikan algoritma terdistribusi deterministik yang menyelesaikan masalah dalam waktu terbatas tanpa tabrakan. Algoritma berjalan dalam beberapa fase dan memastikan bahwa saat terminasi, setiap node parkir jenuh dan semua robot surplus berkumpul pada node gathering yang ditentukan secara unik. Kompleksitas perpindahan dianalisis, menghasilkan batas atas $O(n(a+b)+n^2)$ dan batas bawah kasus terburuk $\Omega (n(a+b))$, dengan $n$ adalah jumlah robot, $a$ adalah jumlah node parkir, dan $b$ adalah total kapasitas.

Penulis memodelkan sistem sebagai sekumpulan robot pada graf grid tak hingga. Robot beroperasi dalam siklus look-compute-move asinkron, dengan visibilitas global dan deteksi multiplisitas kuat. Node parkir adalah node grid tetap dengan kapasitas. Jumlah total robot melebihi jumlah kapasitas. Algoritma dirancang deterministik dan terdistribusi, tanpa pengenal robot. Pendekatan solusi melibatkan beberapa fase: