Path Planning and Obstacle Avoidance for Autonomous Mobile Robots: A Review
Voemir Kunchev1, Lakhmi Jain1, Vladimir Ivancevic2, and Anthony Finn2
School of Electrical and Information Engineering, Knowledge Based Intelligent Engineering Systems Centre, University of South Australia, Mawson Lakes SA 5095, Australia kunvy001@students.unisa.edu.au,
Lakhmi.Jain@unisa.edu.au 2 Defence Science and Technology Organisation {Vladimir.Ivancevic, Anthony.Finn}@dsto.defence.gov.au
Abstract. Recent advances in the area of mobile robotics caused growing atten- tion of the armed forces, where the necessity for unmanned vehicles being able to carry out the “dull and dirty” operations, thus avoid endangering the life of the military personnel. UAV offers a great advantage in supplying reconnais-
sance data to the military personnel on the ground, thus lessening the life risk of the troops. In this paper we analyze various techniques for path planning and obstacle avoidance and cooperation issues for multiple mobile robots. We also present a generic dynamics and control model for steering a UAV along a colli-
sion free path from a start to a goal position. 1 1 Introduction
In the past few decades there has been a great interest in the problem of motion plan-ning for autonomous mobile robots. To better define motion planning problem we can decompose it into path planning and trajectory planning. Path planning is taking care of the generation of obstacle free path taking into consideration geometric characteris-tics of obstacles and the kinematic constrains of the robot. Trajectory generation deals with the robot’s dynamics, moving obstacles or obstacles not known priori which are time dependent constrains [1]. The basic mobile robot navigation can be divided into the following tasks:
? Generate a model of the environment in the form of map. ? Compute a collision free path from a start to a goal position.
? Traverse the generated trajectory (with specified velocity and acceleration and avoid collision with obstacles.
Among the mobile robot research society reactive behavior and planning behavior are often accepted as opposite approaches. The mobile robot must be able to act accord-ingly when unforeseen obstacles are found on the fly. If the robot rely only on pure path planning the robot is prone to physical collision with an unforeseen obstacle. On the other hand without path planning, with the use of reactive obstacle avoidance method only it will be impossible for the robot to reach its goal location.
B. Gabrys, R.J. Howlett, and L.C. Jain (Eds.: KES 2006, Part II, LNAI 4252, pp. 537 – 544, 2006. ? Springer-Verlag Berlin Heidelberg 2006
538 V. Kunchev et al.
Considering the robot environment motion planning can be either static or dy-namic. We have static environment when the location of all the obstacles is known priori. Dynamic environment is when we have partial information about obstacles prior the robot motion. The path planning in a dynamic environment is done first. When the robot
follows its path and locates new obstacles it updates its local map, and changes the trajectory of the path if necessary.
In his work Fox [2] divides the collision avoidance problem into “global” and “lo-cal”. The global techniques that involve path planning methods rely on availability of a topological map defining the robots workspace and obstacle location. He explains that the benefit from using path planning is that the entire path from start to goal can be planned, but this method is not suitable for fast collision avoidance due to its slow-ness cause by their complexity. On the other hand the local approaches of using pure obstacle avoidance methods suffer from the inability to generate an optimal solution. Another problem is that when using local approach only the robots often get ensnared into a local minimum. Because of these shortcomings, a reactive local approach rep-resenting obstacle avoidance cannot be considered feasible for dealing with robot navigation. Due to the reason that there is not a single universal method that can deal with both problems we need to combine both obstacle avoidance and path planning techniques to develop a hybrid system (combining reactive and deliberative ap-proaches overcoming the weakness of each of the methods.
The hybrid architecture unites the reaction with planning in a heterogeneous sys-tem by combining “low-level control” and “high-level reasoning” [3]. The most common hybrid systems are comprised of three layers [4]:
? Reactive layer uses low level sensor based decisions.
? Deliberative layer (planning layer provides global planning. Its decisions can be based on predefined data (map or data learned from sensors.
? Executive layer is the intermediate layer between the other two. It process com mands from the planning to the reactive layer.
In that sense we can divide robot navigation problem into two sub tasks:
? Obstacle avoidance ? Path planning
2 Review of Obstacle Avoidance Techniques
During the last decades scientists working in AI have contributed to development of planning methods and algorithms for the purpose of navigation of mobile robots. Con-siderable work has been done in the development of new motion planning and path planning techniques. This section is surveying common obstacle avoidance algorithms. The purpose of obstacle avoidance algorithms is to avoid collisions with obstacles. Obstacle avoidance algorithms deals with moving the robot based on the feedback information from its sensors. An obstacle avoidance algorithm is modifying the tra-jectory of the mobile robot in real time so the robot can avoid collisions with obsta-cles found on its path.
Path Planning and Obstacle Avoidance for Autonomous Mobile Robots: A Review 539 ? Virtual Force Field
Bornstein’s research [5] on real-time obstacle avoidance for a mobile robot is based on Virtual Force Field (VFF method. This method involves the use of histogram grid for representing the robots work area and dividing it into cells forming the grid. Any of these cells have a “Certainty Value C (i, j” showing the measure of confidence that an obstacle is located in the cell. During its movement the robot maps the “range readings” into the Certainty Grid. In the same time the VVF method examines a frame area in the Certainty Grid for the occupied cells. Then the occupied cells repel the robot away. The extent of repellent force depends on the concentration of occupied cells in the examined frame, and it is “inversely proportional to the square of the dis-tance between the cell and the robot”.
? Vector Field Histogram
Even though the VFF method performs quite fast it has its shortcomings. The imple-mented test-bed shows that often the robot would not move between obstacles to close to each other due the repellent effect from both sides, causing the robots to repel away, a problem also experienced in the Potential Field method [6]. To solve the problems with VFF Borenstein and Koren [7] developed the Vector Field Histogram VFH technique. The method employs the use of 2D histogram grid to represent the environment, being reduced to single dimension “polar histogram” which is build around the position of the robot in a certain moment. The sectors presented in the polar histogram show the “polar obstacle density”. The direction of the robot is com-puted by choosing the sector with least concentration of obstacles. The map repre-sented by the histogram grid is renewed from the robot’s sensors with data containing the distance between the robot and obstacles.
? VFH+
The VFH+ method [8] is similar to the VFH but introduces some novelties by em-ploying “threshold hysteresis” to improve the shape of the trajectory, and the use of a cost function. The cost function is used to choose the best direction in between all candidate directions (which are free of obstacles provided by the polar histogram. The selected direction is the one with the lowest cost. The new VFH+ method consid-ers the vehicle width by enlarging the cells containing obstacles, which makes it easy to experiment with various vehicle dimensions. The trajectory of the vehicle is also considered with by “masking sectors that are blocked by obstacles in other sectors”.
? Dynamic Windows Approach
The Dynamic Window Approach (DWA [9] is another method for reactive obstacle avoidance dealing with the kinematical and dynamic constraints of the vehicle in contrast to VFF and VFH methods. The method might be described by a “search for commands” computing the velocities of the vehicle which are then passed to the ve-locity space. The
自主式移动机器人的路径规划和避障-综述概要
