We consider the problem of dynamic reconfiguration by modular self-reconfigurable robots (MSRs) in the presence of uncertainty in their motion and the environment. Specifically, we consider the situation where the MSR is unable to continue its motion in its current configuration and needs to identify a new configuration among the existing modules, which would be the most configuration suitable for performing the robot's assigned task under the current circumstances. To address this problem, we propose a new data structure called an uncertain coalition structure graph (UCSG) that accommodates uncertainty in the MSR's motion and the environment, using a framework from cooperative game theory called the coalition structure graph. We then propose a new search algorithm called searchUCSG that intelligently prunes nodes from the UCSG using a modified branch-and-bound technique. We have shown analytically that our algorithm is anytime, that is, if it terminates arbitrarily, it returns the best solution found thus far, which is guaranteed to be within a constant bound from the optimal solution. We have verified the performance of our algorithm experimentally in simulation and shown that it is able to find a solution that is within the worst bound of 80% of the optimal solution while exploring only half of the nodes in the UCSG. Our algorithm also takes lesser computation time than the existing algorithms (that do not model uncertainty) for solving similar problems. Finally, to verify the operation of our algorithm, we have implemented it to partition a set of mobile e-puck robots into clusters and shown how different number of robots and different robot motion uncertainty parameters affect the formed clusters.

We present the synthesis and analysis of distributed ensemble control policies to enable a team of robots to control their distribution across a collection of tasks. We assume that individual robot controllers are modeled as a sequential composition of individual task controllers. A macroscopic description of the team dynamics is then used to synthesize ensemble feedback control strategies that maintain the desired distribution of robots across the tasks. We present a distributed implementation of the ensemble feedback strategy that can be implemented with minimal communication requirements. Different from existing strategies, the approach results in individual robot control policies that maintain the desired mean and the variance of the robot populations at each task. We present the stability properties of the ensemble feedback strategy, verify the feasibility of the distributed ensemble controller through high-fidelity simulations, and examine the robustness of the strategy to sensing and/or actuation failures. Specifically, we consider the case when robots are subject to estimation and navigation errors resulting from lossy inter-agent wireless communication links and localization errors.

Evaluative techniques offer a tremendous potential for online controller design. However, when the optimization space is large and the performance metric is noisy, the overall adaptation process becomes extremely time consuming. Distributing the adaptation process reduces the required time and increases robustness to failure of individual agents. In this paper, we analyze the role of the four algorithmic parameters that determine the total evaluation time in a distributed implementation of a Particle Swarm Optimization (PSO) algorithm. For an obstacle avoidance case study using up to eight robots, we explore in simulation the lower boundaries of these parameters and propose a set of empirical guidelines for choosing their values. We then apply these guidelines to a real robot implementation and show that it is feasible to optimize 24 control parameters per robot within 2 h, a limited amount of time determined by the robots' battery life. We also show that a hybrid simulate-and-transfer approach coupled with a noise-resistant PSO algorithm can be used to further reduce experimental time as compared to a pure real-robot implementation.