An Estimation of Distribution Algorithm for Multi-robot Multi-point Dynamic Aggregation Problem

Abstract

Multi-Point Dynamic Aggregation (MPDA) is a novel task model for describing the process of multiple robots performing time-variant tasks. In the MPDA problem, several task points are located in different places and their states change over time. Multiple robots aggregate to these task points and execute the tasks cooperatively to make the states of all the task points change to zero. The task planning of MPDA is a typical NP-hard combinatorial optimization problem. Estimation of Distribution Algorithms (EDA) are evolutionary techniques based on probabilistic models. In this paper, a permutation-based EDA is proposed to solve the task planning problems in MPDA. The algorithm uses K-means clustering to update its probabilistic model which follows the multi-modal Gaussian distribution. Experimental results show that the proposed algorithm outperforms other compared methods in solving the task planning problems of MPDA.