Algorithms on path planning for mobile robots

• Main Author: Ong, Jun Heng
• Other Authors: Huang Shell Ying
• Format: Final Year Project
• Language: English
• Published: Nanyang Technological University 2024
• Subjects: Computer and Information Science; Path planning; Sampling based algorithm
• Online Access: https://hdl.handle.net/10356/181176
• Institution: Nanyang Technological University

This project aims to study advantages and disadvantages of different Rapidly Exploring Random Tree as an algorithm for path planning as well as the sampling methods used in each algorithm. The purpose is to explore the feasibility of each algorithm and sampling method in different environments by measuring the performance and then extrapolating the data for visualization. The task was broken down into smaller, more manageable tasks to progressively move the project along. The first task – Literature Review, was done by identifying the academic papers that introduces the proposed variation of the Rapidly Exploring Random Tree together with the sampling method used in the algorithm. Additional review was carried out to identify sampling methods to further improve the algorithm. The next task was to program the algorithm and sampling methods described in each paper in MATLAB and test them. The algorithm had to be modular to allow for the sampling method to be easily switched out. Configuration spaces was also added to run and test each algorithm with the different sampling methods. Configuration space were created with different layout for testing in separate environments, such as a ‘Maze’, ‘Corridor’ and ‘Empty’ environment. Each algorithm is tested using different sampling methods in various environments to obtain performance results for analysis and visualization. Identifying the ideal algorithm and sampling method given an environment can help reduce the time computing to obtain the path as well as reduce path lengths. Depending on the use case, the requirements will be different. Autonomous drones are often used in search and rescue missions where navigating through unmapped areas needs to be done quickly, hence requiring a low computational time in exchange a less optimized path. In automated warehouses, where autonomous robots transport items efficiently between places, real-time responsiveness is not as crucial and therefore rather spend the computational time to improve the path length, reducing inefficiency and wasted energy