Multiple Mobile Robots Scheduling Based on Simulated Annealing Algorithm

Task Scheduling assumes an integral topic in the efficiency of multiple mobile robots systems and is a key part in most modern manufacturing systems. Advances in the field of combinatorial optimisation have allowed the implementation of algorithms capable of solving the different variants of the vehicle routing problem in relation to different objectives. However few of this approaches are capable of taking into account the nuances associated with the coordinated path planning in multi-AGV systems. This paper presents a new study about the implementation of the Simulated Annealing algorithm to minimise the time and distance cost of executing a tasks set while taking into account possible pathing conflicts that may occur during the execution of the referred tasks. This implementation uses an estimation of the planned paths for the robots, provided by the Time Enhanced A* (TEA*) to determine where possible pathing conflicts occur and uses the Simulated Annealing algorithm to optimise the attribution of tasks to each robot, in order to minimise the pathing conflicts. Results are presented that validate the efficiency of this algorithm and compare it to an approach that does not take into account the estimation of the robots paths.