A bottom-up search algorithm for size-constrained partitioning of modules to generate configurations in modular robots

Abstract

We consider the problem of partitioning a set of modules for efficient and dynamic shape or configuration generation in modular robotic systems, where the size of any configuration formed by the modules is constrained by a maximum, user-provided value denoted by ${\mathit{n}}_{max}$ . The objective is to determine the best partition of the module set that gives the highest utility to the modules. This problem is non-trivial as the set of partitions that needs to be explored grows exponentially with the number of modules and an exhaustive search in the space of partitions makes the problem intractable. To address this problem, we propose a branch and bound based search algorithm, called bottomUpCSGSearch, which is able to intelligently prune the unpromising search space and find the best partition of the modules in a reasonable amount of time. We have provided analytical results related to the completeness, anytime nature and time complexity of our proposed algorithm. Our experimental results show that our proposed algorithm performs better in terms of number of nodes explored (up to $2^8$ times fewer nodes explored) and the time required to find the best partition (improvement up to the order of ${10}^4\text{ms}$ ) than existing comparable algorithms. We have simulated with different number of modules and different values of maximum coalition size of a modular self-reconfigurable robot (MSR) called ModRED, and, shown that our algorithm takes nominal time to find the best solution.