Abstract
In this paper we consider a system of multiple mobile robots (MMRS) and the process of their concurrent motion in a shared two-dimensional workspace. The goal is to plan the robot movement along given fixed paths so as to minimize the completion time of all the robots while ensuring that they never collide. Thus, the considered problem combines the problems of robot schedule optimization with collision and deadlock avoidance. The problem formulation is presented and its equivalent reformulation that does not depend explicitly on the geometry of the robot paths is proposed. An event-based solution representation is proposed, allowing for a discrete optimization approach. Two types of possible deadlocks are identified and deadlock avoidance procedures are discussed. We proposed two types of solving methods. First, we implemented two metaheuristics: the local-search-based taboo search as well as the population-based artificial bee colony. Next, we implemented 14 simple constructive algorithms, employing dispatch rules such as first-in first-out, shortest distance remaining first, and longest distance remaining first, among others. A set of problem instances for different numbers of robots is created and provided as a benchmark. The effectiveness of the solving methods is then evaluated by simulation using the generated instances. Both deterministic and lognormal-distributed uncertain robot travel times are considered. The results prove that the taboo search metaheuristic obtained the best results for both deterministic and uncertain cases, with only artificial bee colony and a few constructive algorithms managing to remain competitive. Detailed results as well as ideas to further improve proposed methods are discussed.