The boundary node method for multi-robot multi-goal path planning problems

In this paper, we investigate the multi-goal path planning problem to find the shortest collision-free path connecting a given set of goal points located in the robot working environment. This problem combines two sub-problems: first, optimize the sequence of the goal points located in the free workspace; second, compute the shortest collision-free path between goal points. In this study, a genetic algorithm is used to optimize the sequence of the goal points that the robot should visit. Once the sequence of the goal points is available, our developed method called Boundary Node Method (BNM) is applied to generate an initial collision-free path between every pair of the sequenced goal points. Subsequently, an additional developed method called Path Enhancement Method (PEM) is used to find an optimal or near-optimal path by reducing the overall initial path length. In the BNM, the robot and its immediate surroundings are simulated by a nine-node quadrilateral element, where the centroid node represents the robot's position. The robot moves between goals with boundary nodes in the working environment depending on the boundary node's potential value. The potential value of each point in the working environment is calculated based on the proposed potential function. Additionally, this article investigates the multi-goal path planning problem for multi-robot systems, when each goal reached by several robots. Finally, simulations and experiments are performed on a real mobile robot to demonstrate the effectiveness of the developed methods.