Hexagonal Lattice Formation in Multi-Robot Systems
Agreement on Stochastic Multi-Robot Systems with Communication Failures
Multi-Robot Systems Engineering
The swarm of robots used for Dr. McLurkin's work is shown below, and was built during my tenure at iRobot corporation as project manager and lead software engineer on the DARPA-funded Swarm project. The core of the system is the infrared inter-robot communication and localization system. This hardware was designed to provide each robot with its local network geometry: network connectivity and local pose estimation of neighboring robots. Multi-robot configuration control algorithms must be able to sense the geometry of the network. The most common sensor models assume that either only the ranges between robots is known, or that there is a global coordinate system. However, range-only models require extensive computation to produce useful geometric information, and global coordinates might not be available in all environments. The local network geometry model is a compromise between these two that is well-suited to multi-robot systems.
Dynamic Task Assignment
Most applications require subgroups of robots to perform different tasks. To support this, we designed a set of four distributed algorithms for dynamic task assignment. Given an input of desired task ratios, each robot selects a task such that the final global distribution best matches the input distribution. Although all four algorithms have the same final goal, each of them represents different trade-offs in running time, communications usage, and accuracy of the final result. These trade-offs were interesting, and pointed towards a model of conserved quantities in multi-robot computation.
Boundary Detection
We are currently finishing work on distributed boundary detection. Similar in spirit to the alpha-shapes of Edelsbruner, it creates a "skin-tight" boundary around the network, detecting convex and concave sections. Unlike the centralized definition of the alpha-shape, my work defines the boundary based on the local network geometry, and allows a robot to efficiently compute its boundary status using a distributed algorithm. The pictures below show the results from simulations from two configurations. The algorithm efficiently classifies robots as internal, boundary, or local articulation points. A local articulation point is a robot whose removal disconnects a local region of the graph. These robots are vulnerable points in the network, and can be reinforced by reconfiguring the nearby network to add redundancy to the connectivity. I used boundaries in the directed dispersion algorithm to guide robots into unexplored areas.
