Multi-Robot Path Planning Using Sampling-Based Algorithms and Reinforcement Learning

In today’s world, robots are becoming extremely useful in many facets of life. With the recent increase in applicable uses of robots, multi-robot path planning has emerged as a fundamental research area. Multi-robot path planning is the process of developing a coordinated plan which is utilized by multiple robots to efficiently work together to complete a common goal. Over the history of multi-robot path planning, many new path planning methodologies have been developed with the goal of outperforming the last, boasting better efficiency and optimality. In this thesis, an analysis of various multi-robot path planning methodologies is carried out with the goal of comparing and contrasting the advantages and limitations of each. This study puts sampling-based algorithms such as RRT (Rapidly-exploring Random Trees), RRT*, and M* to the test to determine which has the best performance in terms of time spent developing and executing the path plan, overall path plan route length, completion success rate, and scalability to more complex situations. A reinforcement learning approach is also applied, with the aim to increase the completion success rate and overall scalability while maintaining comparable time and route efficiency metrics. The simulation results show that the reinforcement learning approach produces much higher completion success rates, increased scalability, and comparable route efficiency metrics at the cost of much higher computation times as compared to the sampling-based algorithms