自主机器人路径规划的群体智能和分流函数.doc

外文原文Autonomous Robot Path Planning Based on SwarmIntelligence and Stream FunctionsChengyu Hu, Xiangning Wu, Qingzhong Liang, and Yongji WangDepartment of Control Science and Engineering,Huazhong University of Science & Technology, Wuhan, China 430074, School of Computer, China University of Geosciences, Wuhan, China 430074WXN000, Abstract. This paper addresses a new approach to navigate mobile robot in static or dynamic surroundings based on particle swarm optimization (PSO) andstream functions (or potential flows). Stream functions, which are introduced from hydrodynamics, are employed to guide the autonomous robot to evade the obstacles. PSO is applied to generate each optimal step from initial position tothe goal location; furthermore, it can solve the stagnation point problem that exists in potential flows. The simulation results demonstrate that the approach isflexible and effective.1 IntroductionIn the last few decades we have witnessed a rapidly increasing interest in mobile robot navigation and path planning, as it has a lot of applications such as assembly, manufacturing, transportation and services. The definition of robot path planning given by most researchers is typically formulated as follows: given a robot and description of an environment, plan a path from an initial location to the goal location, which is collision-free and satisfies optimization criteria 1. The path planning problem could be divided into two sub-problems, one is to establish the surroundings model, generate path by some traditional approaches; the other is to avoid obstacle in the surroundings.There are many traditional approaches to establish the surroundings model. According to the knowledge of the environments, the methods can be classified as local methods and global methods. Visibility graph 4, free space approach 5 and grids 6 are envisioned as global methods. Artificial potential field 8, neural network algorithms 2 and fuzzy logic algorithms 19 are looked upon as local methods. Among these approaches, artificial potential field (APF) is used widely to solve the problem of path planning, as it is simple and easily implemented. However, some drawbacks such as local minimum, could not reach goal if obstacle nearby. Many researchers proposed improved APF 9-11, S Waydo and R M Murray 14-16 borrowed a concept from hydrodynamic analysis and then presented the potential flows algorithm in 2003. This algorithm has been proved effective to generate smoother path (i.e. more suited to aircraft-like vehicles) than other methods and solves the local-minima in artificial potential field, whereas bring with the stagnation point problem where the velocity of the fluid is zero 16Recently many heuristic approaches are employed to solve path planning problems. In order to find one optimal path, human take nature life such as birds, ants or other social insects as an example and develop algorithms inspired by their strictly selforganized behaviors. These algorithms such as ant colony optimization (ACO) and particle swarm optimization (PSO) can be subsumed under the concept of “Swarm Intelligence”. For instance, Zhang R B 12 proposed one global path planning method based on ACO, the author first used grids to establish the surroundings model and then applied ACO to path optimization, Kang F 13 combined improved artificial potential field approach with genetic algorithm to navigate mobile robot, Qin Y Q 17 used MAKLINK graph to build the working space of the mobile robot, then obtained the shortest path from the start point to the goal point by the Dijkstra algorithm, finally adopted PSO to find the best path. However, these heuristic algorithms are mainly used to find one best path from existed paths generated by the concept of configuration space 7.In this work, we proposed a new method for mobile robot path planning. In the approach, Stream functions are used to push the robot away from obstacles. PSO is employed to generate every optimal forward step from the initial position to goal location and all the steps make up of the whole path. The stagnation point existed in potential flows could easily be solved by the introduction of swarm intelligence. The rest of the paper is structured as follows. In Section2, how to use the stream functions to avoid obstacles is reviewed and the drawback of stream functions is brief described. The PSO algorithm and the proposed approach are introduced and developed in detail in Section 3. In Section 4, simulation results are presented. Finally, a conclusion is drawn in Section 5.2 Obstacles Avoidance in Potential FlowsAs have been mentioned above, stream functions could be used to establish the potential area and navigate mobile robot with collision free. Consider the robot as the fish, and then follow the stream line passing through the rock. Consider a uniform flow with strength U, supposed that a single, stationary obstacle with radius a is placed at (bx, by), letb = bx + iby , thenb = bx iby . The complex potential would become the following equation 15The complex velocity can then be calculated using the following formula:Just for simplicity, suppose the circular obstacle is located at origin (0, 0). We havethe following equation 15Assumed that the robot i is currently ( xi xi1 2 , ), thenWe could use equation (4) to evade the obstacle, free-collision path will be generated when the stream line pass through the obstacle.Undoubtedly the technique for single obstacle can be extended for the cases with multiple obstacles. In Fig.1, the left and right figure show how the robot passes through a single and multiple obstacles using the model above.Fig. 1. This left figure shows a uniform flow with strength U pass through a single, stationaryobstacle with radius a, the right figure shows a uniform flow with strength U pass throughmultiple stationary obstacles with different radiusThough the stream functions are very simple and a much smoother path could be generated by the equation (4), the SP problem mentioned above exists nonetheless. In Fig. 2 show the stagnation point in the potential flows. Fig. 2. This left figure show where the stagnation point occur, the right figure shows theemulation that the robot plunge into stagnation point in multiple obstacle surroundingThe stagnation points may occur at the A and C Point When the stream line pass through the centre of a circle showed in the left figure in Fig.2. The right figure shows the stagnation point in multiple obstacles surrounding, which simulated by Matlab 6.0. We could see that once a robot moves onto the stagnation point, it will stop and can not reach the target.3 Path Planning Based on Swarm Intelligence and Stream Functions3.1Particle Swarm Optimization (PSO)Particle swarm optimization is firstly invented by Kennedy and Eberhart in 1995 18. The algorithm is a stochastic optimization method based on the social behavior of individuals living together in groups. Each individual tries to improve itself by observing other group members and imitating the better ones. In that way, the group members are performing an optimization, which can be described with the following model:Every particle has a position present in the search space, and each is able to calculate the corresponding objective function value, and moves in the search space with a velocity V. During the whole optimization process, all particles stay alive; they just change their position and velocity. The best position one particle has reached so far is called its private guide pBest and the best position ever visited by one of its neighbors is the particles local guide gBest.In each iteration t, the particles velocities are updated, directing each particle towards its local and its private guide and keeping a proportion of the old velocity. The velocity and position of each particle is updated with the following equation.Here Vt is the particle velocity at the time t, present is the current position of particle, pBest is the particle best position and gBest is a global best position, rand is a random number between (0,1), w is inertia weight and C1, C2 are learning factors. Much work has been done to prove that the choice of inertia weight w has no fastness value 3. The inertia weight w plays an important role for the convergence behavior of the technique. It is used to control the impact of the previous history of velocities to the current velocity of each particle, regulating the trade-off between the global and local exploration abilities of the swarm, since large values of w facilitate global exploration of the search space (visiting new regions) while small values facilitate local exploration. In order to perform more refined search of the already detected promising regions, the common measure is that uses large values of w at the first steps of the algorithm and gradually decrease during the optimization process. In the paper we set the w initial value as 0.9 and the ending value as 0.4, and then decreasing the w linearly by each epoch. The equation is:Here t is the current iteration, tmax is the max iteration.3.2Model Based on PSO and Stream functionsRegard the robot as fish, we consider such a scenario: a school of fish pass through the reefs to find the food, each fish follows the leader which has the best position and each fish remember its best position, at the same time, the reefs will take effect on the fish, all the fish just follow the stream line evading the obstacles. Suppose that the working space of the mobile robot is that:the mobile robot moves in a two-dimensional space; there are numbered static or dynamic obstacles in the space, and the obstacles could be abstracted as circular obstacles with radius; if some obstacles are polygon, we replace them with circumcircle; the robot could been seen as a particle robot.Then the current position and velocity of robot can be seen as the particles. Set theposition of particle i as X(xi,yi), velocity as (Vxi,Vyi), and the global extreme value isG(gx,gy). We use the distance from current position to the goal location to evaluate each particles performance, i.e. use the sphere function to guide the particle. The equation is following:In the process of the particles moving to the goal, each best position (i.e. gBest) in iteration act as the node where the robot pass through, the distance between two adjacent nodes is the robot motion step, so line the nodes together we could get the planning path.The path planning problem criteria may include distance, time, and energy. The distance is the most common criterion. We use the equation (9) to compute all the virtual robots paths, selects the shortest path as the planning path.Here stepi is the distance between two adjacent nodes, and tmax is the max iteration. The distance must restrict within the max gait that the robot could move, i.e. the max flying distance of particle in each iteration could not exceed the gait of robot.The new approach describes in detail as following:Step1, select parameters to initialize particle swarm with initial positions. Set the value that sensors could detect.Step2, compute the fitness by equation (8) and judge whether the swarm particles reach the goal location, if arrive at the specified position, then go to step5. Step3, multiple particles begin to fly and adjust theirs own “flying” according to theirs “flying” experience as well as the experience of the other particles. They update their positions and velocities by the equation (5), (6).Step4, at the ending of particles flying, stream functions will have an effect on the velocity of each particle, push the particle away the obstacle, if some particles are stuck into the stagnation point, they could pull themselves out by the experience of other virtual robot.Step5, Judge whether the stopping criterion is satisfied, if satisfied, all virtual robot stop flying, compute the distance of the all robots paths by equation (9), select the shortest path as the planning path, if not go to Step3.4 Simulation ResultsSimulation are implemented with Matlab 6.0, supposed that robot could detect all obstacles in the space. The results show the effectiveness of the approach discussed in Section 3. Fig.3 is the snapshots of simulation results of mobile robot navigated by PSO and Stream functions.In simulations, the left figure shows only one static circular obstacle with radius 1 in the surroundings, which centered at (2,2), the right figure is the case for multiple obstacles avoidance. There are three obstacles centered at (-2,6), (-4,-2), (4,2) and with radius 1, 0.6 and 0.8 respectively. The strength U of the uniform flows is 2. The initial positions of all the particles are random positions within the range of a square area which centered at (-8,-8). In regard to the parameters of PSO algorithm during the experiments, C1=C2=2, size of the particle swarm is 10, maximum number of iterations is 200, the stopping criterion ErrGoal is 0.01, w is set according to equation (7).Fig. 3. Simulation of robot navigated by PSO and stream functions with single or multipleobstacles in the surroundingsIn the Fig.3, blue circle represents the obstacle, if the obstacle is not a circle such as a polygon, we could use a circumscribed circle to substitute it. The green circle is the goal. The blue line with red dots on is the optimal path. Every red dot represents the forward gait of the mobile robot in the evolution.The approach could be used in dynamic surroundings. Suppose that in the Fig.4, one hollow circular obstacle with radius 0.8 is moving from the position (4,-7) to (4, 2) at a fix speed which should not exceed the robot motion speed. From the results, we could see no matter what the surroundings is, the proposed approach could lay out one optimal path.The contribution of PSO could make a summary of two aspects, one is that itguides the robot to evade the obstacles, move to the target location, and finally make aoptimization of the paths that it has generated; the other is that it could solve thestagnation point problem which exists in potential flows. When some particles areplunged into the stagnation point, they could escape by their inertia and otherFig. 4. Simulation of robot navigated by PSO and stream functions in dynamic surroundingsneighbor particles traction. The stream functions make a repulsive force on the robot to push the robot away from obstacles.5 Conclusions and Future WorkIn this paper, we present a new approach to navigate mobile robot in a static or dynamic environment based on PSO and stream functions. Extensive simulation results illustrate the effectiveness of the proposed method.One key development is the introduction of PSO that effectively guides the robot to the goal location and deals with the SP problem which exists in potential flows. Another key development is the employment of stream functions that guarantee the particle swarms evade the multiple obstacles. The combination of PSO and stream functions is the ally of global method and local method; they could draw the advantages from each other and effectively navigate the mobile robot. Research is underway for further in-depth analysis of the proposed technique. We will emphasize future work on the following issues: one is how to compute the repulsive force if the obstacle could not be abstracted as a simple circle obstacle with radius, the other is whether the model is applicable when the objects move at a variable velocity rather than to a fixed one.References1.Thomaz, C.E., Pacheco, M.A.C., Vellasco, M.M.B.R.: Mobile Robot Path Planning Using Genetic Algorithms. In: International Conference on Evolutionary Computation in Engineering (1999)2.Balakrishnan, K., Honavar, V.: Some Experiments in evolutionary Synthesis of Robotic Neurocontrollers. In: Proceeding of the World Congress on Neural Networks, San Diego, CA, September 15-20, 1996, pp. 10351040 (1996)3.Shi, Y.H., Eberhart, R.C.A.: Modified Particle Swarm Optimizer A. In: International Conference on Evolutionary Computation C, pp. 6973. IEEE, Anchorage (1998)4.Pere: Automatic planning of manipulator movements. IEEE Transactions on Systems, Man, and Cybernetics 11(11), 681698 (1981)5.Habib, M K, Asama, H.: Efficient method to generate collision free path for autonomous mobile robot based on new free space structuring approach. In: Proc. IEEE/RSJ IROS, pp. 563567 (1991)6.Zhaoqing, M., Zenren, Y.: Mobile robot real-time navigation and avoidance based on grids. Robot 61, 344348 (1996)7.Liu, Y.H., Arimoto, S.: Proposal of tangent graph and extended tangent graph for path planning of mobile robots. In: Proceedings of IEEE International Conference on Robotics and Automation, vol. 1, pp. 312317 (1991)8.Khatib, O.: Real-time obstacle avoidance for manipulators and mobile robots. Int. J.Robot. Res. 5(1), 9098 (1986)9.Geand, S.S., Cui, Y.J.: New potential function for mobile robot path planning. IEEE Transactions on Robotics and Automation 16(10), 615619 (2000)10.Koren, Y., Borenstein, J.: Potential field methods and their inherent limitations for mobile robot navigation. In: Proc. IEEE Conf. Robotics and Automation, Sacramento, CA, April 712, 1991, pp. 13981404 (1991)11.Chuang, J.H., Ahuja, N.: An analytically tractable potential field model of free space and its application in obstacle avoidance. IEEE Trans. Syst., Man, Cybern. B 28, 729736 (1998)12.Zhang, R.B., Guo, B.X., Xiong, J.: Research on global path planning for robots based on ant colony algorithm. Journal of Harbin Engineering University 25(6) (December 2004)13.F