An algorithm of avoiding obstacles with intelligent objects

Recent Innovations in Mechatronics (RIiM) Vol. 2. (2015). No. 1-2. DOI: 10.17667/riim.2015.1-2/14. 1 An algorithm of avoiding obstacles with intelligent objects Şahin YILDIRIM Mechatronic Engineering Erciyes University Kayseri, TURKEY [email protected] Ebubekir YAŞAR Vocational School, Computer Programming Dept. Gaziosmanpaşa University Tokat, TURKEY [email protected] Abstract—In this research a path planning which is the first step of motion planning in robotic applications, away from an obstacle in an environment where exist many obstacles is developed. Different from the algorithms in literature, a path away from an obstacle is planned without determining the configuration free space in a place that contains many different shaped obstacles with the help of intelligent objects that are created object oriented programming(OOP). With the help of this developed algorithm not only the probable paths but also finding the shortest path and correcting it with the help of intelligent objects are evaluated at the same time. This algorithm is so profound that it can form the basic principles of many original Works with the additional in future works. Keywords—Avoiding obstacles, path planning I. INTRODUCTION The motion planning process always produces motion in order to combine starting point with the target point avoiding obstacles. Robot motion planning focuses on only robot changes and necessary turns undervaluing the dynamic structures and limitations [2]. Path planning Works are based on finding a path away from an obstacle. In this situation researchers are focused on producing an algorithm which provides a path without any crash. Planning a path is highly needed for mobile robots in accordance with the concept that a robot can make its duties with the help of motion in real world. Many methods are developed in this subject. Motion planning are searched from many researches during 1970‘s. For the first time in 1969 Nilsson made a mobil robot definition which had the ability of motion planning. Nilsson introduced the visibility graph method which was combined with A* searching algorithm, that provides a point robot find the shortest way away from obstacles within the polygonal and geometrical shaped obstacles. This method remained very popular[8]. Udupa suggested the idea of making the robot as small as a point for avoiding obstacle algorithms. With the help of this idea Lozano Perez and Wesley suggested a more general and systematic idea in order to plan a path for polyhedral/polygonal robots without touching polyhedral/polygonal obstacles [10]. This work pave the way fort he idea of configuration space. This configuration idea expresses the robot to be represent just one point in parameter space that defines robot‘s degrees of freedom[8]. While the representing forbidden areas in configuration space, the opposite part of configuration space represents free space [8]. This is the probable motion area of the robot. In 1979 Tomas LozanoPerez and Michael A. Wesley investigated the shortest way in their works changing the method named visibility diagram into graph theory thanks to line which is formed combining the whole obstacles‘ face to face corners. Andrews and Hogan in 1983 and Khatip[6] in1985 developed the potential field method by thinking the area, where the robot is working is in the imaginary potential field. In this potential field where the robot is in, target point forms attractive and obstacles form a propulsive potential field. The robot in this potential field goes towards to the target avoiding the obstacles effected by attractive and propulsive forces as if there is a slope in the field. Having local minimums is the biggest problem of this potential field method. This situation brings out the result that as if the robot reaches the target before it reaches the target and this situation is named local minimum. In 1987 B Chazelle investigated the path that goes the target over the cells that didn‘t touch the obstacles with a technique he developed by dividing the working area, where the obstacles also exist in, into approximate decomposition cells. If the cells touching the obstacles doesn‘t reach the target, the action of dividing is repeated by making the cells smaller. One of different application of cell algorithm is vertical decomposition method. Here, center point of the line connected between the two obstacles or obstacles and any corners is obstacles-free points. The shortest path is investigated changing these points into graph theory like in visibility diagram method[2]. In 1991 F Aurenhammer‘s voronoi diagram method divides the plane according to nearest neighbor rule. This rule is each point is related to nearest plane field. The diagram is formed combining the points that exist at the same distance to its two nearest obstacles. The shortest path is investigated among the probable paths with this diagram. In 1994 Kavraki et al. Tried to combine the near corners with a line the help of local planner accepting the point, which is randomly taken from configuration space as a corner point if the point belongs to free space (Cfree) in their probability based path finding method (PRM). Local planner controls the formed line if they are on the obstacles or not. Valid combinations are added to graph theory. LaValle and Knuffer[13] in 1998 formed tree structures finding and connecting the nearest points and step by step widening the firs example which is taken from configuration space in their algorithm. That they developed in their random three structured fast searching method(RRT). In this three structure new points exist randomly. The field is formed from Recent Innovations in Mechatronics (RIiM) Vol. 2. (2015). No. 1-2. DOI: 10.17667/riim.2015.1-2/14. 2 three structures which had connecting branches as many as the repetitions in this way. In these mentioned works the shortest points that connect the starting and the target are found after determining the probable points away from the obstacles. A path is formed by connecting these points. This path has discontinuous characteristic. Later this discontinuous path is changed to a continues path without any sharp turns and away from obstacles by straightening. II. FINDING A PATH AWAY FROM OBSTACLE In this work a direct-line connection is created between the starting point and the target by connecting the intelligent objects each other which are produced with Delphi one of object oriented programming language. Thanks to that unimportant obstacles can be ignored while determining the path to the target. It isn‘t needed also to determine the configuration space that reduces the robot as small as a point. Because if the size of the objects are determined according to the robot‘s maneuver ability, time spent configuration space isn‘t needed. In this work the environment is accepted being two dimensions and the obstacles randomly may have any shape, position and edge number. A. Intelligent Objects Algorithm 1. First the obstacles that exist in the environment are reduced to two colors with threshold method that includes starting and the target point and then starting point and target point are red colored are added. Fig. 1, Environment with obstacles 2. The shape and size of the objects should be determined. In our application the shape of the objects is round and its size is 10x10 pixels. The size can be determined according to robot link size. 3. Determined amount of round objects are created on a linear line from starting point to the target with the help of the equation below. Amount of the intelligent objects are determined obstacles size, amount and shape situations. 2 2 12 12 xx yy xx yy      (1) Slope is counted like below. 12 12 xx yy m   (2) In this formula (x1,y1) are starting coordination and (x2,y2) are target coordination. Fig. 2, Placement of objects according to the equation 1 4. In this step an object will pass over the obstacle that is under the object moving up or down according to the figure below. The equation of the lines of each object which are formed to be right to the line which has a motion line formed according to equation 1 can be found below. ).( 11 xxmyy n  Above the slope is found according to the slope in the equation 2 1 n mxm (4) Fig. 3, The lines that objects can go down Recent Innovations in Mechatronics (RIiM) Vol. 2. (2015). No. 1-2. DOI: 10.17667/riim.2015.1-2/14. 3 Fig. 4, The lines that objects can go up If the edge of the obstacle is congruent with the environment‘s border, there is only one option for his obstacle. Because the robot cannot pass between the obstacle and environment border. There isn‘t any situation like this in the figure above. 5. While determining the direction of the motion, the motion that doesn‘t go further from the obstacle will take the minimum distance. Any minimum distance methods to determine the direction can be use in the literature. Intelligent objects can be directly used part of determining the minimum distance methods. While going on the determined direction, the objects should realize one of the objects in front of them at least (there shouldn‘t be any obstacle). If they don‘t see the obstacle they should go on the same direction until they realize the obstacle. The objects that are moved like this are shown filled objects below. If several objects don‘t see each other, amount of intelligent objects can be enhanced. If the objects don‘t fit between two obstacles (if it touches both of the obstacles) it goes on the same direction until the end of the following objects. Fig. 5, Objects go over the obstacles. 6. After determining the minimum distance now it‘s time to correct the path those are formed by the objects. Starting with the starting point, the objects that are situated between the two edges of face to face objects should be placed on the same direction. In this way the local curves are corrected. Fig. 6, Left, correcting the path and right, determining the distance. ACKNOWLEDGMENT In this work a different algorithm is created and used to determine a path away from obstacles. This algorithm, different from previous methods, wholly cover free configuration space (not needed), determining the points away from obstacles, determining the shortest path, correcting the determined path processes. While determining a path away from an obstacle produced with object oriented method, the path is determined considering the size of the robot. That prepared program can be used without showing if wanted. As a result visual drawing have meaning for the users. First, original characteristic of the program is that it can determine the shortest distance away from the obstacle using the structure that belongs object oriented programming. Second, original characteristic is that it investigates the shortest path without revealing the whole probable paths. The third one is that it can combine the correcting path work with the same object model. In traditional methods all these work are analyzed using different methods for each works. In following works for example as robots, like snake, goes faster in large environments, some times the shortest distance cannot be traveled mathematically in the least time. Changing the robot‘s size the area that big robots fit in can be used to determine the area that snake like robot‘s can go faster. REFERENCES [1] T. Lozano-Perez ve M. A., Wesley, ―An algorithm for planning collision-free paths among polyhedral obstacles,‖ Commun. Of ACM, 22 (1979), 560-570 [2] Steven M. LaValle, Planning Algorithms, Cambridge University Press, 2006, ISBN 0-521-86205-1. [3] B. Chazelle, ―Approximation and decomposition of shapes,‖ In J. T. Schwartz and C. K. Yap, editors, Algorithmic and Geometric Aspects of Robotics, pages 145–185. Lawrence Erlbaum Associates, Hillsdale, NJ, 1987. [4] F. Aurenhammer, ‗‗Voronoi diagrams—a survey of a fundamental geometric data structure,‘‘ ACM Comput. Surv., vol. 23, no. 3, pp. 345– 405, 1991. [5] J.C. Latombe, Robot Motion Planning, Kluwer Academic Publishers 1991 [6] O.Khatib, ―Real-time obstacle avoidance for manipulators and mobile robots,‖ The International Journal of Robotics Research, Vol. 5, No. 1, 1986 [7] Nilsson N.J., ―A mobile automaton: an application of artificial intelligence techniques,‖ Proc. 1. Int. Joint Conf. On Artificial Intelligence Washington D.C, 509-520 1969 Recent Innovations in Mechatronics (RIiM) Vol. 2. (2015). No. 1-2. DOI: 10.17667/riim.2015.1-2/14. 4 [8] J.C. Latombe, ―Motion planning: a journey of robots molecules digital actors and other artifacts,‖ The International Journal of Robotics Research 30: 846-894 1999 [9] Udupa,S., ―Collision detection and avoidance in computer controlled manipulators,‖ Ph.D. Dissertation, Dept. of Electrical Engineering, California Institute of Technology Pasadena, CA. 1977 [10] Lozano Perez T. ve Wesley M.A., ―An algorithm for planning collision free paths among polyhedral obstacles,‖ Comm. ACM 22(10):560-570 1979 [11] Lozano Perez T., ―Statial planning: a configuration space approach,‖ IEEE Tr. Computers, C-32(2):108-120 1983 [12] Kavraki, L. E., P. Svestka, J-C. Latombe, ve M. Overmars, "Probabilistic roadmaps for path planning in high dimensional configuration spaces," IEEE Transactions on Robotics and Automation, vol. 12, issue 4, no. 4, pp. 566-580, 1996. [13] S. M. LaValle and J. J. Kuffner, ―Randomized kinodynamic planning In Proceedings,‖ IEEE International Conference on Robotics and Automation, pages 473--479, 1999