91 American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) ISSN (Print) 2313-4410, ISSN (Online) 2313-4402 © Global Society of Scientific Research and Researchers http://asrjetsjournal.org/ Path Planning, Motion Control and Obstacle Detection of Indoor Mobile Robot Ali Khaleel Mahmooda*, Robert Bickerb aHay al-jamiaa, Baghdad 14001,Iraq bNewcastle University, Address, Newcastle Upon Tyne NE1 7RU, UK aEmail: ali_khalil.mahmud@yahoo.com bEmail: robert.bicker@newcastle.com Abstract In this paper, A* path planning algorithm has been represented for a mobile robot to be able to follow a constructed path from its current position to a specified goal within its environment. To ensure that the mobile robot follow the constructed path by path planning algorithm, a motion control algorithm has been built. In the same time, to detect static obstacles and avoid collision with them, an obstacle detection algorithm has been used as a final algorithm that will be used as a part of the whole system to give the robot the ability to move from its initial known position to a specific goal in an optimum way. Keywords: Kinematic; A* Algorithm; Odometry; Kinematic. 1. Introduction Mobile robotics is a growing part in the robotics field, which is becoming progressively more important, useful, and commonplace in modern society. For the reason that they are providing the functionality, mobility, and multi-media possibilities in all areas of everyday life: at home, at work, in public environments, and in remote locations such as space and deep sea, they are being employed not only in industry but also in service-oriented applications. The ability of mobile robots to perform a significantly extended range of tasks and services many locations offer a great request for specialized applications that lead to increase the interest in mobile robots. This leads to increase the interest in mobile robots [1]. ------------------------------------------------------------------------ * Corresponding author. http://asrjetsjournal.org/ American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2016) Volume 26, No 1, pp 91-107 92 The mobile robots have potential application in many areas for example: • Service Robots: o Transportation of food and medication. o Automatic cleaning of large areas (e.g. airports, industrial sites, supermarkets, domestic vacuum- cleaner). o Client support (e.g. exhibitions guides, Museum tours) o Agricultural: Planting, fruit and vegetable picking. o Forests : Cleaning, tree cutting and fire preventing • Space: o Space exploration o Remote inspection of space stations • Elderly and Handicapped o Assistance to handicapped or elderly people, helping in transportation, healthcare [2]. The aim of this study is to design, analyze, assesse a set of algorithms to give the robot the ability to follow the optimum path when move in known environment form known position to a specific goal. To achieve the above aim, three main algorithms will be built. Firstly, a path planning algorithm to construct the required path. Secondly, a motion control algorithm to successfully follow the constructed path from the first algorithm. Finally, An obstacle detection algorithm to ensure that the robot will not hit any object while move to its goal. 2. Robot Kinematic To be able to create a control program for mobile robot hardware, it is important to understand the mechanical behavior of that robot. The process of understanding the behavior of a mobile robot starts with the procedure of describing each wheel contribution for the robot motion hence; each wheel has a role in final robot movement. This section describes the construction of simple forward kinematic model of the robot motion. Then derives equations for combine the kinematics construction of wheels then combine them with the kinematic constraints of the robot to express the whole robot’s kinematic. With these equations, the robot’s maneuverability will be defined and the path of the robot will be evaluated. The NI LabVIEW Robotics Starter Kit robot has two wheels, each with radius r. Given a point P in the center between the two drive wheels; L is the distance from the wheel to P, the spinning speed of the right and left wheels are �̇�𝜓𝑅𝑅 and �̇�𝜓𝐿𝐿 respectively; θ represent the angle. The overall speed of the robot will be predicted by the forward kinematic in the robot reference frame: American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2016) Volume 26, No 1, pp 91-107 93 𝜉𝜉�̇�𝑅 = � �̇�𝑋𝑅𝑅 �̇�𝑌𝑅𝑅 �̇�𝜃𝑅𝑅 � = 𝑓𝑓(𝐿𝐿, 𝑟𝑟,𝜃𝜃, �̇�𝜓1, �̇�𝜓2) (1) By supposing that the local reference frame of the robot is aligned such that the +XR of the robot is in the direction of movement as shown in Figure (2) Figure 1: Wheel to wheel distance and wheels radius Figure 2: Mobile robot coordinate If one wheel spins while the other wheel is stationary and contributes nothing, because point P is halfway between the two wheels, the robot will move instantaneously with half the speed: 𝑟𝑟 �̇�𝜓𝐿𝐿 2𝐿𝐿 = �̇�𝑋𝑅𝑅1 𝐿𝐿 ⟹ �̇�𝑋𝑅𝑅1 = 1 2 𝑟𝑟 �̇�𝜓𝐿𝐿 (2) American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2016) Volume 26, No 1, pp 91-107 94 In a differential drive mobile robot, these two contributions can simply be added to calculate the �̇�𝑋𝑅𝑅 of 𝜉𝜉�̇�𝑅 The value of �̇�𝑌𝑅𝑅 is always zero because the wheels cannot contribute to sideways motion in the reference frame of the robot �̇�𝑌𝑅𝑅 = 0 . Finally, it is essential to compute the rotational component �̇�𝜃 of𝜉𝜉�̇�𝑅. The contributions of each wheel can be computed independently and just added Combining these individual formulas (�̇�𝑋𝑅𝑅 , �̇�𝑌𝑅𝑅 , �̇�𝜃𝑅𝑅) yields a kinematic model for the differential-drive mobile robot: 𝑟𝑟 �̇�𝜓𝑅𝑅 2𝐿𝐿 = �̇�𝑋𝑅𝑅2 𝐿𝐿 ⟹ �̇�𝑋𝑅𝑅2 = 1 2 𝑟𝑟 �̇�𝜓𝑅𝑅 (3) �̇�𝑋𝑅𝑅 = 1 2 𝑟𝑟 �̇�𝜓𝐿𝐿 + 1 2 𝑟𝑟 �̇�𝜓𝑅𝑅 (4) 𝑤𝑤1 = −𝑟𝑟 �̇�𝜓𝐿𝐿 2𝐿𝐿 (5) 𝑤𝑤 = �̇�𝜃 = −𝑟𝑟 �̇�𝜓𝐿𝐿 2𝐿𝐿 + 𝑟𝑟 �̇�𝜓𝑅𝑅 2𝐿𝐿 (6) 𝜉𝜉�̇�𝑅 = ⎣ ⎢ ⎢ ⎢ ⎡ 𝑟𝑟 �̇�𝜓𝐿𝐿 2 + 𝑟𝑟 �̇�𝜓𝑅𝑅 2 0 −𝑟𝑟 �̇�𝜓𝐿𝐿 2𝐿𝐿 + 𝑟𝑟 �̇�𝜓𝑅𝑅 2𝐿𝐿 ⎦ ⎥ ⎥ ⎥ ⎤ (7) �̇�𝑋𝑅𝑅1 𝑟𝑟 �̇�𝜓𝐿𝐿 𝐿𝐿 𝐿𝐿 Right wheel �̇�𝑋𝑅𝑅2 𝑟𝑟 �̇�𝜓𝑅𝑅 𝐿𝐿 𝐿𝐿 Left wheel American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2016) Volume 26, No 1, pp 91-107 95 3. Path-Planning, Motion control and Obstacle Detection Subsystems Find-path problem or Path planning is popular in robotics since it has an essential role in the navigation of autonomous mobile robots. Accurate path planning is very important for the robot to be able to track an optimal path between start position and goal position without collision with obstacles. According to [3], there are two main types of path planning: global path planning and local path planning. Global path planning needs all terrain to be static. In addition, there should be a complete awareness about the environment. In contrast, the implementation of the local path planning is while the robot is moving. Therefore, the local path planning has the ability to produce a new path when there is a change in the environment. For this project the local path planning will be used since the robot needs to check if there is an obstacle within its path to avoid it by change its path [3]. The general idea of local path planning is that, based on the current knowledge, a path is selected between two points. Then, when the mobile robot gets new information form the sensor about the environment, the previous path will be updated since there could be an obstacle in the selected path between starting point and the goal point [4]. For this project, the following steps will summarize the use of path planning and obstacle detection: • Step 1: Path planning: Based on the current knowledge of the environment, a path between the current node to the target node will be planned using A* path planning algorithm. • Step 2: Sensing: The mobile robot will take the sensor data and detect the obstacles position. If there is no obstacle within the planned path go to step 4, else go to step 3. • Step 3: Re-plan the path: For the reason that the previous path is not available hence there is an obstacle across this path, the A* path planning algorithm will be used again for path planning. • Step 4: motion control: After detecting the final path of the mobile robot, the motors velocity should be adjusted in order to follow the desired path [2]. 3.1 The Basic Approach of A* Path planning Algorithm A* algorithm is used to select the shortest path between start and goal nodes by efficiently compute optimal solutions when combine features of two searches; the uniform-cost search and pure heuristic search. For the A* search algorithm, the cost associated with a node is f (n) which estimates the lowest total cost of all paths going through node n. f (n) = g(n) + h(n) Where: g (n) = the cost of the path from the initial state to node n. h (n) = the heuristic estimate or the cost or a path from node n to a goal. American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2016) Volume 26, No 1, pp 91-107 96 After finding f (n) for each point, the node with the lowest f (n) will be chosen for the expansion [5]. Terminology: 1- Calculate g(n) the
cost (or distance) of the path from the starting point to any vertex n..
 2- Calculate h (n) (the
heuristic
estimated
cost
from
any
vertex
n
to
the
goal).

 3- Calculate f (n) = g (n) + h (n). The value of f (n) will be used by A* to select the next step in the path. Figure 3: A* path planning steps [6] It is important to notice this approach has the following assumption: Firstly, the region of interest is larger than the sensing range of the sensor. Secondly, the sensor has the ability to measure 180⁰ (from -90⁰ to +90⁰. Finally, the initial position of the robot is known. 3.2 Motion control Odometry is the most commonly used method for the instantaneously position determining of the mobile robot, hence real time positioning information is easily accessible for positioning information [7]. Odometry can be defined as the estimation of the change in the position of a mobile robot over time by using the data from motion sensors (i.e. optical encoder). In wheeled mobile robot, the odometry used to estimate its position relative to a starting location. The main benefit of using odometry in most practical applications is that it provides easily accessible to positioning information for real time position measurements. However, this method is very sensitive to errors that produced as a result of integration the velocity measurements over time to give the robot position estimates. For this reason, this method needs calibration and processing to give accurate data collection [8]. After calibrating the encoder to give the nearest readings to the real robot movement, it will be a feedback signal for the motion control. American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2016) Volume 26, No 1, pp 91-107 97 After achieving the path planning algorithm, it is essential to give accurate values for the motor velocities to ensure that the robot follow the required path. Because the map of the environment is divided into cells, the robot movement can be either diagonal or orthogonal. As shown in figure (4), there are eight possible directions to move (A, B, C, D, E, F, G and H) Figure 4: Possible directions of robot movement To simplify the algorithm, all these cases can be achieved by using the same forward and angular velocities just by adjusting the time of movement. The following flowchart describes the complete process of motion control: Figure 19: Motion control algorithm American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2016) Volume 26, No 1, pp 91-107 98 3.3 Obstacle Detection Subsystem Obstacle detection algorithm was integrated with the path planning algorithm hence it has been used to modify the direction of the mobile robot based on obstacles detection in its path. It executes this algorithm to search for the obstacles, if any obstacle is found on the mobile robot path, the old path will be replaced with a new one to avoid that obstacle as shown if Figure (5) and Figure (6) where Figure (5) shows the original path before executing the obstacle detection algorithm while Figure (6) shows the modified path depending on the sensor readings. In Figure (6) the blue squares represent the obstacles that are not included in the map of the environment. For this reason it is important to integrate the path planning algorithm with the obstacle detection algorithm. Figure 5: planned path between the starting point and the targrt Figure 6: Modified path after map observation American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2016) Volume 26, No 1, pp 91-107 99 The sensor information will used to continuously update the path. For this reason, the obstacle avoidance algorithm with the path planning algorithm will constantly re-plan the path so this continuous re-planning allows the mobile robot to deal with dynamic environments in addition to avoid collision. The Scanning range finder URG-04LX will be used to measure the environment. It will be used for the obstacle avoidance in addition to using it in the localization algorithm [7]. 4. Software methodology The LabVIEW Robotics Module includes several path planning algorithms including A* [9]. The following example will be used in the main program with some modifications to be compatible with the main localization algorithm. The following steps have been followed: • Building the Map : Figure 20 In LabVIEW Robotics, a 2D array of non-zero values is used to represent a map where each value in this map is represented by a cost that associated with moving from one node to another. For this project, a simple map of two values will be used, therefore, a 2D array of Boolean values will be used as a map input. • Plan the path: The next step after building the map is plan the path from one position to another. To plan a path, it is required to detect the start and target positions on the map to be able to apply A* algorithm in order to provide the best American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2016) Volume 26, No 1, pp 91-107 100 path between them. Figure 8: path planning portion of the LabVIEW code [7] Figure 9: Final complete algorithm [9] • Display the complete algorithm, the maze and the planned path. Figure 10: End result of the A* path planning algorithm American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2016) Volume 26, No 1, pp 91-107 101 The end result is shown in Figure (10) : It is best to understand the algorithm conceptually so that you can use it most effectively. In this tutorial, you will learn the concepts behind A* as well as see a simple example that implements A* using NI LabVIEW. The final path planning and obstacle detection: Figure 21 5. Test and Calibration This section includes the calibration of the system component to be ready and efficient to use in the program. This include two main parts, the first part include the odometry calibration while the second part is the calibration of the sensor readings. 5.1 Odometry Calibration American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2016) Volume 26, No 1, pp 91-107 102 For odometry calibration, two main were used; the first test is for the linear odometry error and the second test is for the angular error • Linear odometry calibration For the linear calibration, known velocities was given to the motors; for a specific amount of time (t), the robot will move a distance (d). The error in the readings can be found by comparing the distance calculated theoretically, by applying robot kinematics, with the value measured practically. From equation (3-4), �̇�𝑋R = 0.025(�̇�𝛹R + �̇�𝛹L) Because �̇�𝑋R = 𝑑𝑑 𝑡𝑡 , 𝑡𝑡 = 𝑑𝑑 �̇�𝑋R Figure 11: Linear odometry test This equation will be used to calculate the required time of the robot movement to achieve the required distance (d). There are three different set of velocities have been used to test the linear encoder error; the distance used for this test is (4m) so the X =4m (400 cm) and Y =0 (forward displacements only) Test1: Motors velocity (�̇�𝛹R= �̇�𝛹L = 5 rad/s) , d=4m Calculation of t value: Test 2: Motors velocity (�̇�𝛹R= �̇�𝛹L = 10 rad/s) , d=4m Calculation of t value: Test 3: Motors velocity (�̇�𝛹R= �̇�𝛹L = 13.33 rad/s) , d=4m �̇�𝑋𝑅𝑅 = 0.025 (5 + 5) = 0.25 𝑚𝑚 𝑠𝑠 , 𝑡𝑡 = 𝑑𝑑 �̇�𝑋𝑅𝑅 = 4 0.25 = 16 𝑠𝑠𝑠𝑠𝑠𝑠 �̇�𝑋𝑅𝑅 = 0.025 (10 + 10) = 0.5 𝑚𝑚 𝑠𝑠 𝑡𝑡 = 𝑑𝑑 �̇�𝑋𝑅𝑅 = 4 0.5 = 8 𝑠𝑠𝑠𝑠𝑠𝑠 American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2016) Volume 26, No 1, pp 91-107 103 Calculation of t value: After giving motors the required velocities for the calculated period, a practical reading for the distance values have been taken. Table (1) shows the measured distance values and the error (E) for these three tests. Error E = [calculated position – measured position] Table 1: Comparison of actual and measured distances by encoder Test 1 Test 2 Test 3 X =398 cm E=2cm Y = 0 cm E=0cm X =394 cm E = 6 cm Y = -3 cm E= 3 cm X =390 cm E = 10 cm Y = -6 cm E = 10 cm X =396 cm E=4cm Y = -2 cm E= 2 cm X =396 cm E = 4 cm Y = -1 cm E = 1 cm X =395 cm E = 5 cm Y = -2 cm E = 2 cm X =396 cm E=4 cm Y = -3 cm E = 3 cm X =395 cm E = 5 cm Y = -2 cm E = 2 cm X =393 cm E = 7 cm Y = -4 cm E = 4 cm X =397 cm E = 3 cm Y = -1 cm E = +1 cm X =396 cm E = 4 cm Y = -2 cm E = 2 cm X =398 cm E = 2 cm Y = -2 cm E = 2 cm Table (1) shows that higher motors velocity leads to higher odometry error in both axes. This calibrated error will be considered in the calculation of the motion control. • Angular odometry calibration Figure 12: Starting position of the robot �̇�𝑋𝑅𝑅 = 0.025 (13.33 + 13.33) = 0.667 𝑚𝑚 𝑠𝑠 , 𝑡𝑡 = 𝑑𝑑 �̇�𝑋𝑅𝑅 = 4 0.667 = 6 𝑠𝑠𝑠𝑠𝑠𝑠 American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2016) Volume 26, No 1, pp 91-107 104 In order to measure the angular odometry error, the robot has been rotated around its centre without any linear motion. For this test, motors speed are known (�̇�𝛹R= 5 rad/s, �̇�𝛹L = -5); also, the angle that the robot has to rotate is known also (θ = 90°) and it is required to calculate the time that should be given to the robot to rotate 90°. From equation (7): Figure 13: Required and actual robot orientations Figure (13) shows the required and actual robot orientations, hence the robot has to rotate 90° but the actual rotation is about 105°. This test is repeated more than one time and all the results almost the same. Despite this value of error is relatively high (15° per 90°), it is easy to deal with because it is repeatable. In other words, by inserting this value in the calculations, correct rotation can be achieved. Figure 14: Final odometry test �̇�𝜃 = −𝑟𝑟 �̇�𝜓𝐿𝐿 2𝐿𝐿 + 𝑟𝑟 �̇�𝜓𝑅𝑅 2𝐿𝐿 = −(−0.05×5) 2×0.17 + 0.05×5 2×0.17 = 1.471 𝑟𝑟𝑟𝑟𝑑𝑑/𝑠𝑠, But �̇�𝜃 = θ 𝑡𝑡 , 𝑡𝑡 = θ �̇�𝜃 = 90 ×(𝜋𝜋÷180) 1.471 = 1068 ms American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2016) Volume 26, No 1, pp 91-107 105 The final step in the odometry calibration is testing the linear and angular robot displacements as shown in the Figure (14). At this test, the robot behave correctly. 5.2 Sensor Calibration The sensor has been tested before connecting it to the robot as shown in Figure (15). This test was to find the maximum reliable range for the sensor. Despite that the sensor has the ability to measure up to 5.6m; the reliable readings are within 4m range. For this reason, the maximum range of the sensor that will be used in the program is 4m. Figure 15: sensor calibration Figure 16: Sensor readings for zero distance While doing the previous test, it has been recognized that the sensor gives zero distance reading when there is no object in its field. So, a calibration for the sensor readings has been made. The first part of this calibration is American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2016) Volume 26, No 1, pp 91-107 106 to test the sensor readings when the actual distance from the sensor to the object is zero. As shown in Figure (16), the minimum sensor readings when there is an obstacle in the sensor field is about 85 mm. From this figure, it can be concluded that the only case that the sensor gives distance readings equal to zero is when there is no object in its field. For this reason, the sensor readings will be calibrated to give 5.6m instead of zero when the sensor field is empty. Figure(17) shows the block diagram of the program that has been used to calibrate the sensor. The main idea in this program is comparing the sensor reading with very small value, which is 10mm in this program (or any value less than 85mm). If the sensor reading is less than 10mm, return sensor reading as 5600mm (5.6m). Else, return the same value of the sensor reading. Figure 17: Block diagram of the sensor calibration program Figure 18: modified sensor readings After achieving the previous calibration, the sensor readings became as shown in Figure(18) American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2016) Volume 26, No 1, pp 91-107 107 6. Conclusion The aim of the research was analyzing and implementing algorithms for a mobile robot to has the ability to follow an optimum path when move from its position to a specific target position when put it a known environment. To achieve this aim, there are three algorithms have been built, tested and evaluated, path planning, motion control and obstacle detection algorithms. In addition to building these algorithms, there are a set of calibration steps were done. The first calibration was done for odometry. This calibration has two main calibration types; the first test was to find the linear odometry error while the second test was to find the angular odometry error. The second odometry was for the sensor that will be used to get the environment readings. References [1] B. Brumson. (2012, 20 August). New Applications for Mobile Robots. Available: http://www.robotics.org/content-detail.cfm/Industrial-Robotics-Industry-Unsights/New-Applications - for-Mobile-Robots/content id/3362 [2] P. Lima and M. I. Ribeiro, “Mobile Robotics,” Institute for Systems and Robotics (ISR/IST, 2012. [3] R. Sharma, “DESIGN AND IMPLEMENTATION OF PATH PLANNING ALGORITHM FOR WHELLED MOBILE ROBOT IN A KNOWN DYNAMIC ENVIRONMENT,” International Journal of Research in Engineering and Technology, vol. 02, 2013. [4] T. Ersson and X. Hu, “ Path planning and navigation of mobile robots in unknown environments,” in Intelligent Robots and Systems, 2001 IEEE/RSJ International Conference on, 2001, pp. 858-864. [5] S. Mahadevi, K. R. Shylaja, and M. E. Ravinandan, “Memory of Based A-Star Algorithm for path planning of a Mobile Robot,” International Journal of Science and Research (IJSR), vol. 36, pp. 37- 48, 2009 [6] Robin. (2009) Heuristic Search. [7] C. Popirlan and M.Dupac, “ An optimal Path Algorithm for Autonomous Searching Robots,” Annals for the University of Craiova-Mathematics and Computer Science Series, Vol. 36, pp. 37-58, 2009. [8] T. Yap Jr “ Mobile Robot Navigation with low cost sensors,” UNIVERSITY OF CALIFORNIA RIVERSIDE, 2009. [9] pjtanz. (2010, 4 August). An Introduction to A Path Planning (Using LabVIEW). Available: https://decibel.ni.com/content/docs/DOC-8983. http://www.robotics.org/content-detail.cfm/Industrial-Robotics-Industry-Unsights/New-Applications%20-for-Mobile-Robots/content%20id/3362 http://www.robotics.org/content-detail.cfm/Industrial-Robotics-Industry-Unsights/New-Applications%20-for-Mobile-Robots/content%20id/3362 https://decibel.ni.com/content/docs/DOC-8983 5. Test and Calibration 5.1 Odometry Calibration  Linear odometry calibration  Angular odometry calibration The final step in the odometry calibration is testing the linear and angular robot displacements as shown in the Figure (14). At this test, the robot behave correctly.