Finding optimal isomorphic goal adjacency

Abstract

In many multirobot applications, the overall goal topology of the robot formation is more important than achieving a specific adjacency. In such cases, it is convenient to revise the given goal adjacency matrix so that it is more apt to the robots' configuration. In this paper, we present a solution to this problem. For this, we first formulate the problem as finding an optimal isomorphic adjacency matrix and then propose a two-stage method for solving it. In the first stage, an optimal orthogonal matrix that solves the problem is determined while in the second stage, the search for the optimal permutation matrix is conducted - based on the approximation of the resulting orthogonal matrix by a non-commutative convex combination of permutation matrices. Extensive simulation results indicate that an adjacency matrix that is more apt to the robots' locations can be determined with the optimality of the resulting solution tuning the accuracy parameter.