Supervised Classification of Motion Graphs for Swarm Robotics
Master of Science
Tasks for robot swarms, such as measuring performance, diagnosing robots, and allocating actions, can all be improved by empirically understanding how the swarm is behaving. For many of these tasks, direct observation is typically used to understand whether a group of robots is correctly completing some task. However, this is especially challenging for swarms with a large number of robots spread around a wide geographical area. To bridge this gap, we focus on classifying behaviors. Although methods exist for classifying groups of robots assuming global localization, this is the first study to automatically classify one group of robots with another using fully distributed sensing. This work develops a method for classifying motion of groups of robots using a novel graph-based data structure, which we call a motion graph, that embeds continuous motion into a discrete graph. We explore the use of k-Graphlets to exploit local structures in the graph. Using k-Graphlets classifies several simulated behaviors with 85% accuracy, but runs relatively slowly. To improve this, we develop an algorithm using path lengths, which proves to be just as accurate as k-Graphlets but orders of magnitude faster, making it well within practical use for problems like diagnostics, automatic deployment of robots, and task allocation.