New Real Time (M-Bug) Algorithm for Path Planning and Obstacle Avoidance In 2D Unknown Environment

摘要

This paper proposes a new sensor-based path planning and collision avoidance algorithm for nonholonomic robot travelling in unknown 2D environment named as (M-Bug) algorithm in order to reduce the overall of traveled path. It uses the difference between slope lines to find and choose the smallest angle located between slope of straight line from mobile robot to goal point and slope from mobile robot and two endpoints of edges for obstacle, by choosing the smallest one which refers to nearest leave point to reach goal point and repeat this action with other obstacles until mobile robot reach to goal point. this algorithm based on using on-board sensors to generate information about the environment and obstacle located in front of mobile robot. This algorithm creates better performance when compared to the other traditional algorithms. It provides real time obstacle avoidance, compatible with LIDAR sensor and fast enough to be implemented on embedded microcontrollers. The used algorithm is based on a modification for existing path planning and obstacle voidance algorithms (Bug1, Bug2, Tangent-Bug, K-Bug, Dist-Bug ......etc.), and The Vector Field Histogram (VFH) Algorithm in unknown environment. The main advantage of this algorithm is that it is not limited to the origin-destiny line and changes the main line every leave point. MATLAB 2018a is used in simulation to validate the effectiveness of the proposed algorithm, and it is implemented on multiple scenarios to show the ability of the mobile robot to follow a path, detect obstacles, and navigate around them to avoid collision.