Toward Robust Swarm Algorithms via Precise Causal Analysis

Swarm robotics is an emerging research area due to its diverse applications, such as environmental monitoring, disaster recovery, logistics, and even military operations, which are challenging for individual robots. Under the hood, a swarm algorithm is the core decision-making component that controls and coordinates multiple drones. Testing a swarm algorithm is crucial for developing robust drone swarms. However, it is challenging to analyze swarm systems due to the overwhelming complexity and dependencies among the components. Swarm is highly reactive to various environmental factors (e.g., obstacles), and swarm algorithms make extremely dynamic decisions based on them. In particular, swarm behavior is difficult to measure, which is critical for understanding swarm algorithms. Unfortunately, existing metrics (e.g., swarm size, coherence, or accuracy) have a limited reflection of dynamic behavior change caused by the impact of environmental factors.
In this work, we propose systematic approaches that debug configuration bugs, discover logical flaws, and generate tests for swarm algorithms. In particular, we introduce a novel abstraction of robotics behavior, which we call the degree of causal contribution (DCC), based on the idea of counterfactual causality. By leveraging DCC, we measure swarm behavior in terms of interaction with environmental factors. First, we propose a swarm debugging system that automatically diagnoses and fixes buggy behaviors caused by misconfiguration. Then, we build a feedback-guided greybox fuzz testing system to discover logic flaws, leveraging DCC as a feedback metric. We also build a system that generates tests with an enhanced mission environment so that the swarm leads to more complex behavior. We evaluate our approaches using real-world swarm algorithms to show generality and effectiveness. We also conduct real-world experiments using physical drones to show their applicability in the real-world.