Balanced connected task allocations for multi-robot systems: An exact flow-based integer program and an approximate tree-based genetic algorithm

Task allocation for a multi-robot system is often imposed with various constraints to promote efficiency and avoid unwanted consequences. This study focuses on the min-max balanced connected q-partition problem (BCPq) that seeks the early completion time of a multi-robot system while satisfying mission constraints. In the problem, each environmental region is modeled as a weighted node of a graph and the graph is to be partitioned into a predefined number, q, of disjoint node sets, such that nodes in each set are connected and the largest “sum of the set” is as small as possible. The problem is NP-hard in general cases, and has a brute-force search space exponential to the number of nodes. BCPq arises in many fields besides robotics. To date, existing work has mainly been conducted on special versions of the problem, such as small q or special types of graphs. In this study, we propose two approaches for the general case: one is exact and suitable for graphs of less than 200 nodes, while the other is approximate and can handle graphs with up to 3000 nodes. Specifically, this study presents the first exact mixed integer linear program (MILP) in the literature that can partition an arbitrary graph into a given arbitrary number of components. The MILP is based on a flow model and can solve graphs with 100 more nodes than the existing MILP that can only tackle 2-partition in the q=2 case. The study also presents an approximate genetic algorithm (GA) based on tree partition and tree evolution. It is the first GA that can handle BCPq (q ≥ 2) problems. On graphs of less than 500 nodes and 2-partition, the GA achieved all the optima in 20 runs. On q ≤ 12, this GA also can achieve results close to the optima after a few individuals were evolved, i.e., a gap smaller than 3% of the ideal average value. Moreover, the GA is scalable to q as the consumed time is nearly stable, independent of q.