Comparative Analysis of KNN, RNG and K-RNG for Inter-Robot Communication

In distributed multi-robot exploration, effective communication among mobile robots significantly impacts the efficiency of area coverage, mapping accuracy, and collaborative decision-making. Typically, robots share their information map based on dynamically established network topologies to balance communication overhead and information accuracy. This paper comparatively analyzes three dynamic topology construction strategies for mobile robots exploring unknown environments: the Relative Neighborhood Graph (RNG), the k-Relative Neighborhood Graph (K-RNG), and the K-Nearest Neighbors (KNN). RNG is a graph-based approach that maintains adaptive links based on geometric proximity, efficiently managing connectivity while reducing redundant data exchanges. The K-RNG generalizes RNG by allowing a tunable number of points within the geometric neighborhood, providing flexible control over network density. In contrast, KNN selects neighbors by prioritizing robots in immediate proximity, quickly adapting to local density changes. We conduct extensive simulations to evaluate these strategies against critical Quality-of-Service (QoS) metrics, including packet delivery ratio and latency. Results demonstrate RNG's effectiveness in reducing unnecessary data transmissions while maintaining stable connections, K-RNG's performance tunability based on the parameter <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$k$</tex>, and the strong dependency of KNN's performance on the choice of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$k$</tex>.