3D Global Dynamic Window Approach for Navigation of Autonomous Underwater Vehicles
3D Global Dynamic Window Approach for Navigation of Autonomous Underwater Vehicles
International Journal of Fuzzy Logic and Intelligent Systems. 2013. Jun, 13(2): 91-99
Copyright ©2013, Korean Institute of Intelligent Systems
This is an Open Access article distributedunder the terms of the CreativeCommons Attribution Non-Commercial License( which permits unrestricted noncommercialuse, distribution, and reproductionin any medium, provided the originalwork is properly cited.
  • Received : January 09, 2013
  • Accepted : June 07, 2013
  • Published : June 30, 2013
Export by style
Cited by
About the Authors
Inara, Tusseyeva
Department of Computer Science and Engineering Research Institute (ERI), Gyeongsang National University, Jinju, Korea
Seong-Gon, Kim
Research Institute, LG Electronics, Seoul, Korea
Yong-Gi, Kim

An autonomous unmanned underwater vehicle is a type of marine self-propelled robot that executes some specific mission and returns to base on completion of the task. In order to successfully execute the requested operations, the vehicle must be guided by an effective navigation algorithm that enables it to avoid obstacles and follow the best path. Architectures and principles for intelligent dynamic systems are being developed, not only in the underwater arena but also in related areas where the work does not fully justify the name. The problem of increasing the capacity of systems management is highly relevant based on the development of new methods for dynamic analysis, pattern recognition, artificial intelligence, and adaptation. Among the large variety of navigation methods that presently exist, the dynamic window approach is worth noting. It was originally presented by Fox et al. and has been implemented in indoor office robots. In this paper, the dynamic window approach is applied to the marine world by developing and extending it to manipulate vehicles in 3D marine environments. This algorithm is provided to enable efficient avoidance of obstacles and attainment of targets. Experiments conducted using the algorithm in MATLAB indicate that it is an effective obstacle avoidance approach for marine vehicles.
1. Introduction
An autonomous unmanned underwater vehicle (AUV) is a marine robot that moves under water in order to collect helpful information about different conditions at the bottom of the ocean, the structure of the upper sediment layer, or the presence of objects and obstacles. Intellectualization of AUV’s control system is critical in order for it to fulfill its mission even in unforeseeable circumstances. The robot must have the ability to control its motion by learning and making logical conclusions [1 , 2] . The main challenge being experienced by all existing mobile devices that move independently without any control by humans remains that of navigation. Bukhari et al. [3] did considerable work on this problem using fuzzy logic to try to solve the issue of multiple vessel navigation.
For successful sailing in open space, the onboard robot system should be able to build the route, control the motion parameters, and keep track of its own position in real-time mode. One of the approaches to this issue is the integration of the novel algorithm called the dynamic window approach (DWA) to control the motion of the vehicle. Fox et al. [4] were the first to propose the approach in 1997. That proposal led to the changing of automatic control notion in non-permanent environments and enabled the vehicle to move at high speeds. Thus, a dynamic window can be specified as the area of obstacle detection, which depends on the speed of the vessel and can be changed dynamically. The values of several variables of motion must be evaluated after each limited time interval. This process makes it possible for a robot to switch from one to another appropriate velocities and courses while moving at a high speed.
Like all nautical algorithms, DWA chooses and constructs the most appropriate trajectories from initial to destination positions. The major difference from other approaches is that it controls the speed of a vehicle in order to avoid obstacles. For instance, when its sensors detect an obstacle, the robot will decrease its velocity or even stop. Additionally the algorithm allows the AUV to go on at maximal speed if there are no blockages in its path. It is obvious that all the calculations and decision-making processes must be handled dynamically [5] .
However, to the best of our knowledge, no research work has been done toward the integration of DWA into autonomous unmanned vehicle navigation systems. We have attempted just such an integration, which we call 3-dimensional (3D) Global DWA. 3D Global DWA enhances DWA with the ability to move in narrow 3D ocean environments.
The remainder of this paper is organized as follows: In Section 2, we discuss the basic ideas underlying a number of previous works related to the topic. In Section 3, we provide the details of our proposed approach. In Section 4, we discuss the results of experiments conducted. Finally, we conclude this paper in Section 5.
2. Related Work
A number of methods and approaches applicable to robotics and designed for surroundings rarely change have been presented by researchers [6 , 7] . However, the types of algorithms used in these approaches are not able to manage and make decisions when faced with dynamic circumstances.
DWA changed the notion of automatic control of objects in unstable conditions, while providing the ability to move robots at high speeds [4] . A dynamic window is the area of obstacle detection that is changing dynamically depending on the speed of the vessel [8] .
Initially the technology was applied only to robots that were to be used as serving staff inside an office [4 , 9] . Another practical example of its application is shown in [10] , where the robot with integrated system was tested during exploration in a museum in order to conduct various excursions for visitors.
The number of scientists interested in this method has increased over several decades. This fact is the evidence of its effectiveness. Among these researchers are Brock and Khatib [8] , whose work differs from Fox and many others in that they applied the DWA algorithm to holonomic robots, whereas Fox initially applied this method to synchro-drive robots [9] . In addition, the search space in Fox’s approach had a square shape while in Brock’s approach it was a circle.
Researchers started to improve the DWA’s equations after noticing that the robot was likely to go far away from its goal and to increase its speed in some cases while maximizing the objective function. This is why the approach in [11] is stated as being more efficient than the original DWA. In [11] , the robot utilizing the proposed motion planning is able to decrease its speed before changing direction on detecting an obstacle.
Seder and Petrovic [12] highlighted the differences between global and local path planning and proposed the idea of combining these two methods into one algorithm for more safe motion that is free of collisions. Their research was based on their previous work [13] but it improved on it by introducing changes that gave robots the ability to avoid collisions even with dynamically moving objects.
Another attempt to improve the global DWA was made by Schroter et al. [14] , who tried to use clothoid curves instead of circle to make the process of motion planning more real and closer to machine moving simulation. Their proposed approach was compared with vector field histogram. The virtual force field algorithm has since been modified and expanded to modified virtual force field (MVFF) by Kwon et al. [15] . They incorporated fuzzy logic in order to provide safe tracking without collisions. Their approach is very similar to the one proposed in this article in terms of the way in which obstacles are detected: both our approaches use a circle (in 3D) as a space to control, monitor, and detect any obstacles around the vessel on a distance equal to the radius of the circle far from it.
3. Novel Navigation Approach
To describe the proposed algorithm improvements, general information of the marine world and navigation systems must first be provided. An AUV is a marine robot, an automatic self-propelled vehicle with research equipment, which moves under water in order to collect information about the topography of the bottom or the presence of any objects. Usually, the ocean environment is narrow and full of objects travelling independently. One of the works done toward solving the problem of multiple vessels navigating using fuzzy logic was shown in [11] . In that research, vehicles were guided in ocean space by calculating time to closest point of approach (TCPA) and distance to closest point of spproach (DCPA) and bearing values in order to prevent any collisions and provide safe motion from start to target destinations. One of the techniques successfully used in navigation is the Bandler and Kohout’s fuzzy relational products (BK-products) [16] . One of the attempts related to this was done by Anwary et al. [2] , who integrated ARTMAP and the fuzzy BK-product method into the onboard system of an AUV and demonstrated its effectiveness by developing a camera based motion system [17] .
- 3.1 DynamicWindow Approach
The limitations of the autonomous planning methods has led researchers to study real-time planning, which is based on the knowledge gained from probing the local surroundings to handle unknown obstacles as far as the robot traverses a path in this environment [18 - 21] . Similar characteristics are possessed by the approach described in this section based on DWA. We discuss the original DWA in this section and describe the novel navigation algorithm called 3D Global DWA in the ensuing section.
As mentioned before, Fox et al. [4] were the first to propose DWA in 1997. The original purpose of DWA was to handle collision avoidance in robots travelling at high speeds in hazardous and populated environments. Its original idea was to face the problem of the robot’s dynamics by considering only the speed of a vehicle.
DWA works out with the limitations of velocities and accelerations and provides command generation in a small period of time. This approach is based on a two-dimensional search space using two types of velocities. The pair of values ( v , w ) is used to designate the velocity of the vehicle, where v is the translational velocity and w – rotational. The set of values ( v , w ) contains the speeds at which the vehicle can stop before colliding with any obstacles. These pairs are called admissible velocities and they construct a dynamic window with the current velocity as the center point ( Figure 1 ).
PPT Slide
Lager Image
Dynamic window.
Admissible velocities, indicated as Va in Figure 1 , can be calculated using (1) below:
PPT Slide
Lager Image
where ( v , w )is the set of velocities, translational and rotational, which can also be defined as the speed vector
PPT Slide
Lager Image
are accelerations for breakage; and dist ( v , w ) is the distance between the vehicle and the closest obstacle along the trajectory.
When searching for the set of admissible velocities, the objective function must be taken into account by maximizing its value, as shown in (2) below:
PPT Slide
Lager Image
where heading ( v , w ) is the variable that indicates the progress in the process of arriving at the target; vel ( v , w ) is the translational (or forward) velocity, which provides fast movement of the vehicle.
The overall search space ( Vs ) boils down to the dynamic window, which includes the set of paces Vd that can be obtained within the next time period t . This space can be defined as shown in (3):
PPT Slide
Lager Image
where v and w are actual velocities; and
PPT Slide
Lager Image
are values of translational and rotational velocity accelerations.
As shown in Figure 1 , the space of velocities Vs contains the values of velocities Va , whereas of Vd involves all velocities from Vr . Consequently, the resulting search area can be represented as the traversal of the bounded spaces (4):
PPT Slide
Lager Image
We constructed a unified modeling language (UML) diagram to demonstrate the logic of DWA ( Figure 2 ). First, the acceptable velocity of the vessel to reach the goal must be evaluated taking into account the actual position. Second, the algorithm calculates the allowable linear and angular velocities based on the vehicles dynamics. The following process must be repeated in a loop for the list of allowable velocities: measure the nearest obstacle while the robot travels at a suggested velocity; check whether the values of the braking distance and the distance to the nearest obstacle are equal. The speed must be determined as admissible or nonadmissible. The next step is to measure the objective function, which consists of heading and clearance values. The final step is to determine the cost value for the suggested admissible velocity and to compare it with all the other costs. If the result obtained is the best cost, then the velocity must be considered as the best. Consequently, this velocity will be set to the robots acceptable trajectory.
- 3.2 3D DynamicWindow Approach
In the previous section, we described DWA’s underlying principles. The next step toward the novel navigation approach is the development of motion control in a 6DOF system. In order to implement this idea, the 3D configuration space (CSPACE) was confined to a 3D dynamic window. This window must be enlarged to the shape of a sphere with radius r containing the space condition of a vehicle (obstacle and AUV itself) on a distance equal to r ( Figure 3 ).
With regard to the global coordinate system, the robot’s current position at time t is defined as x ( t ), y ( t ), and z ( t ) for three axes respectively. The set of values ( x , y , z , θ ) determines the kinematic configuration of the vehicle, where θ ( t ) is the heading direction, or orientation, in another words.
PPT Slide
Lager Image
Control flow diagram (unified modeling language) of theproposed approach.
PPT Slide
Lager Image
Simple representation of dynamic window approach in 3D.
The following formulas present the motion equation for three axes (5):
PPT Slide
Lager Image
One conclusion can be done based on the formulas above. To achieve a specific command of the speed changing when accelerating at a constant velocity, the vehicle moves along a quadratic curve. It continues along until the desired speed approved by the algorithm is not achieved by the AUV [8 , 22] . Although the cardioids of these spherical curves depend on the magnitude of the acceleration, acceleration and curvature are mutually proportional. For instance, a small acceleration creates a small curvature of the trajectory and allows the simulation of behavior that is similar to cars [4] .
The dynamic window is presented as the set of velocities Vd accessible within the next time interval t (3). Figure 4 illustrates the feasible trajectories of a vehicle in 3D ocean space.
If the vehicle can decrease its speed or even stop before collision with obstacles while following the path along the chosen trajectory, then the velocity pair ( v , w ) from the set of DW velocities is regarded as safe (or admissible) (1).
Another indicator related to trajectory is known as the path
PPT Slide
Lager Image
Possible robot trajectories in 3D ocean space.
PPT Slide
Lager Image
3D view of x-y-z path with obstacle avoidance.
alignment measure vpath (6) [13] :
PPT Slide
Lager Image
where Nt is a discontinuous set of points on the trajectory; Np is a set of points on the effective path ( Figure 5 ); dij is the Euclidean distance between two points i (on trajectory) and j (on the effective path); and Dmax and Dmin are two limit values of the number of points on a curve, maximal and minimal, respectively.
The effective path is a line consisting of a number of points. It binds two states on the path: actual position of the vehicle and a way-mark on the route, as shown in Figure 5 .
- 3.3 Combination of Avoidance Algorithms: 3D Global DynamicWindow Approach
Nowadays, the effective navigation method is usually presented as a system of algorithms genetically related to each other by combining both the autonomous monitoring mode and the realtime path navigation mode (DWA) with a simple map and efficient planning algorithm. The first part of the sailing approach, called autonomous planner, is looking for the best global path from the start to the target, whereas the second part is handling any possible crashes with previously unknown objects. This process is done by replacing a part of the planned global-optimal path with the auxiliary path [23] .
The proposed algorithm is an evolutionary navigator that combines autonomous and real-time planning modes with a simple highly accurate map and an efficient planning approach. The algorithm first reads the map and receives the initial and target coordinates.
The Global DWA has already been proposed by Brock and Khatib in [3] . In its essence, DWA has no knowledge about the linkages of points on a path in free space. This is the reason why, in cooperation with a motion-planning algorithm, DWA can overcome this weakness. This function finds the motion that is free of collisions from the initial position to the target point. Our proposed 3D Global DWA (3D GDWA) is based on this concept and underlying idea.
The best-matched motion algorithm has been proved to be the neuro-fibromatosis type-1 (NF1) because of its global, local minima free features [8] . The GDWA path planner is based on the NF1 navigation approach. GDWA integrates the sensor data into an occupancy grid where the robot is presented in the form of a dot. It simplifies the route planning process in a way that the robot will detect the free cell and classify it as the obstacle-free area. The best way from the start to the goal position is denoted as the shortest path that can be found by the NF1 algorithm [24] .
While the GDWA is an extension of the original DWA, it is obvious that it uses the same logic and equations as its predecessor. The key difference among them is the objective function (2), which evaluates the possibility of selecting among the potential moves that the robot can make. The novel objective function (7) presented above is changed by adding nf 1( v , w )instead of heading ( v , w ) that centralizes the path of the vehicle toward the target point:
PPT Slide
Lager Image
To determine nf 1( v , w ), the weight of nf1 must be matched at the cells bordering the robot’s location. Additionally, the function
PPT Slide
Lager Image
shows the extent to which the motion command will decrease the space between the vehicle’s current position and the target point during the next repetitions.
In previous sections of this paper (Section 2 and Section 3.1), a number of approaches were described. According to the information collected, our proposed 3D GDWA is considered to be one of the best methods for navigation systems for AUVs in narrow marine environments. The reason is that it complies with the requirements for any navigation algorithm described subsequently.
The main purpose of motion planning and path following approaches is to avoid collisions, not to stop the vehicle if there are still possible ways to go, and finally allow the robot to go as fast as possible. An algorithm is called an obstacle avoidance algorithm if it prevents the robot from colliding during its traversal of the entire path, which increases the importance of the accuracy and speed of searching new obstacles. Obviously, the map must be precise. There are several factors that can affect the velocity of the vehicle, but the narrowness of the surroundings should not force the algorithm to reduce the speed to any large extent.
It is a well-known fact that the histogram grid is a quick and secure mapping technique for tracing dynamically moving obstacles. In addition, it helps in collision avoidance by dividing velocities into admissible and non-admissible groups (DWA). The vehicle can be pulled away from the problem of getting stuck by using the histogram grid because another non-blocked way of travelling can be found.
In conformity with the information provided in this paper, 3D GWA has been demonstrated as an approach that has the capacity to securely navigate obstacle courses while moving at a high speed.
In summary, in the first part of the proposed algorithm, (autonomous planner), the robot looks for a globally optimal path from the start to the target, while in the second part, the 3D GDWA algorithm is responsible for processing potential collisions or previously unknown objects, replacing part of the original global path to a sub-optimal path. Finally, in experiments conducted, both in the articles referenced above and in
PPT Slide
Lager Image
Results obtained using theMATLAB simulator.
this research paper, it is proven that the robot with the integrated approach has the ability to navigate obstacle courses traveling as fast as the platform allows. On the basis of these conclusions, we chose the 3D GDWA as the algorithm to implement and further test.
4. Experimental Results
To evaluate the reliability of the proposed method, we conducted experiments in which we used MATLAB (Mathworks, Natick, MA, USA) to handle all the calculations and draw the images of the resulting paths, as shown in Figures 6 and 7 .
The results of the experiments conducted illustrate that the algorithm is supremely managed all the assigned navigation tasks. More specifically, it built the most optimal path from the start to the target points; herewith, it did not expose the AUV to any risk of colliding with any of numerous obstacles ( Figures 6 , 7 a–d). These obstacles were presented in the form of spheres and cylinders. As can be seen in the image, the robot avoided the obstacles and successfully reached the target without any crashes.
Furthermore, 3D GDWA provides additional features for controlling the dynamically changing speed values. As shown in Figure 7 e, the speed of the AUV varied (rising and decreasing) depending on the route, presence of obstacles, and remoteness from the goal point.
The above arguments point to the effectiveness of the proposed algorithm while using it in the narrow surroundings of the underwater world, which in turn can be used for any type of AUVs.
We also set motion planning values for the vehicle that was used in the simulator ( Table 1 ). They were generated based on
PPT Slide
Lager Image
Results obtained from theMATLAB simulator. (a) Front view, (b) bottom view, (c) top view, (d) side view, (e) speed changes.
Technical prerequisites for motion planning
PPT Slide
Lager Image
Technical prerequisites for motion planning
the basic requirements for a vehicle that is able to perform tasks related to AUVs.
5. Conclusion
In the various attempts to create an autonomous moving vehicle or mobile agent, a number of issues have appeared, organized under the title “navigation tasks.” This is not only about movement on the Earth’s surface but also about the movement of vehicles or guided missiles.
Global planning algorithms incorporate information about the whole space in order to identify areas where it is possible to move, and then determine the best path. The planning heuristic methods reduce the complexity of the task and the sensitivity to errors in the data in various ways. Thus, for the development of a universal autonomous robot path following system, a navigation evolutionary algorithm was selected.
The Global DWA was developed for 3D marine environments and proved to be an effective solution to navigate AUVs in underwater surroundings.
Selection of this algorithm makes it possible to take into account a set of behaviors of a vehicle and the environmental aspects in the path planning stage. However, one key challenge in the proposed method still remains: namely, inability of the vehicle to go up or down when avoiding obstacles. Another aspect to take into consideration is the factor of dynamic obstacles because they were not simulated in the current study. Additionally, it must be supposed that the vehicle does not know the exact trajectory of these kinds of obstacles. The solution to these problems will form the basis of future research.
This research was supported by the Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education, Science and Technology (No. 2012R1A1A2038601).
Naik A. , M.S. thesis 2005 “Arc path collision avoidance algorithm for autonomous ground vehicles” Department of Mechanical Engineering, Virginia Polytechnic Institute and State University Blacksburg, VA M.S. thesis
Anwary A. R. , Lee Y. I. , Jung H. , Kim Y. G. 2008 “Unsupervised real-time obstacle avoidance technique based on a hybrid fuzzy method for AUVs” International Journal of Fuzzy Logic and Intelligent Systems 8 (1) 82 - 86    DOI : 10.5391/IJFIS.2008.8.1.082
Bukhari A. C. , Tusseyeva I. , Lee B. G. , Kim Y. G. 2013 “An intelligent real-time multi-vessel collision risk assessmentsystem from VTS view point based on fuzzyinference system” Expert Systems with Applications 40 (4) 1220 - 1230    DOI : 10.1016/j.eswa.2012.08.016
Fox D. , Burgard W. , Thrun S. 1997 “The dynamic windowapproach to collision avoidance” IEEE Robotics & Automation Magazine 4 (1) 23 - 33    DOI : 10.1109/100.580977
Simmons R. 1996 “The curvature-velocity method for localobstacle avoidance” in Proceedings of 1996 IEEE International Conference on Robotics and Automation Minneapolis, MN 3375 - 3382    DOI : 10.1109/ROBOT.1996.511023
Kim N. , Yoon G. H. , Lee D. 2009 “Intelligent navigationand control of an autonomous underwater vehicle based onQ-learning and self-organizing control” in Proceedings of 2009 ICCAS-SICE Fukuoka 630 - 634
Kureichik V. M. 2002 Genetic algorithm and its application,Taganrog TRTU
Brock O. , Khatib O. 1999 “High-speed navigation usingthe global dynamic window approach” in Proceedings of 1999 IEEE International Conference on Robotics and Automation Detroit, MI 341 - 346    DOI : 10.1109/ROBOT.1999.770002
Fox D. , Burgard W. , Thrun S. 1996 “Controlling synchrodriverobots with the dynamic window approach to collisionavoidance” in Proceedings of 1996 IEEE/RSJ International Conference on Intelligent Robots and Systems Osaka 1280 - 1287
Fox D. , Burgard W. , Thrun S. , Cremers A. B. 1998 “Ahybrid collision avoidance method for mobile robots” in Proceedings of 1998 IEEE International Conference on Robotics and Automation Leuven 1238 - 1243    DOI : 10.1109/ROBOT.1998.677270
Stachniss C. , Burgard W. 2002 “An integrated approachto goal-directed obstacle avoidance under dynamic constraintsfor dynamic environments” in Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems Lausanne 508 - 513    DOI : 10.1109/IRDS.2002.1041441
Seder M. , Petrovic I. 2007 “Dynamic window based approachto mobile robot motion control in the presence ofmoving obstacles” in Proceedings of 2007 IEEE International Conference on Robotics and Automation Roma 1986 - 1991    DOI : 10.1109/ROBOT.2007.363613
Seder M. , Macek K. , Petrovic I. 2005 “An integratedapproach to real-time mobile robot control in partiallyknown indoor environments” in Proceedings of 31st Annual Conference of IEEE Industrial Electronics Society Raleigh, NC 1785 - 1790    DOI : 10.1109/IECON.2005.1569176
Schroter C. , Hochemer M. , Gross H. M. 2007 “A particlefilter for the dynamic window approach to mobile robotcontrol” in Proceedings of the 25nd International Scientific Colloquium (IWK) Ilmenau 425 - 430
Kwon K. Y. , Cho J. , Joh J. 2006 “Collision avoidanceof moving obstacles for underwater robots” Journal of Systemics, Cybernetics and Informatics 4 (5) 86 - 91
Bui L. D. , Kim Y. G. 2004 “A new approach of BK productsof fuzzy relations for obstacle avoidance of autonomousunderwater vehicles” International Journal of Fuzzy Logic and Intelligent Systems 4 (2) 135 - 141    DOI : 10.5391/IJFIS.2004.4.2.135
Kim H. S. , Jin T. S. , Sur J. N. 2011 “Intelligent 3-D obstacleavoidance algorithm for autonomous control of underwaterflight vehicle” Journal of Korean Institute of Intelligent Systems 21 (3) 323 - 328    DOI : 10.5391/JKIIS.2011.21.3.323
Mi Z. S. , Kim Y. G. 2009 “Intelligent 3D obstacles recognitiontechnique based on support vector machines forautonomous underwater vehicles” International Journal of Fuzzy Logic and Intelligent Systems 9 (3) 213 - 218    DOI : 10.5391/IJFIS.2009.9.3.213
Kim H. S. , Kang H. J. , Ham Y. J. , Park S. S. 2012 “Developmentof underwater-type autonomous marine robot-kit” Journal of Korean Institute of Intelligent Systems 22 (3) 312 - 318    DOI : 10.5391/JKIIS.2012.22.3.312
Joh J. S. , Kwon K. Y. , Lee S. M. 2002 “Collision avoidingnavigation of marine vehicles using fuzzy logic” International Journal of Fuzzy Logic and Intelligent Systems 2 (2) 100 - 108    DOI : 10.5391/IJFIS.2002.2.2.100
Jin T. S. 2012 “Obstacle avoidance of mobile robot based onbehavior hierarchy by fuzzy logic” International Journal of Fuzzy Logic and Intelligent Systems 12 (3) 245 - 249    DOI : 10.5391/IJFIS.2012.12.3.245
Khatib O. 1986 “Real-time obstacle avoidance for manipulatorsand mobile robots” International Journal of Robotics Research 5 (1) 90 - 98    DOI : 10.1177/027836498600500106
Bouguet J. Y. , Perona P. 1995 “Visual navigation using asingle camera” in Proceedings of 5th International Conference on Computer Vision Cambridge, MA 645 - 652    DOI : 10.1109/ICCV.1995.466877
Latombe J. C. 1991 Robot Motion Planning Kluwer Academic Publishers Boston