Framed-quadtree path planning for an underwater vehicle with the task of tracking a moving target

Abstract

An autonomous underwater vehicle (AUV) must use an algorithm to plan its path to distant, mobile offshore objects. Because of the uneven distribution of obstacles in the real world, the efficiency of the algorithm decreases if the global environment is represented by regular grids with all of them at the highest resolution. The framed quadtree data structure is able to more efficiently represent the environment. When planning the path, the dynamic object is expressed instead as several static objects which are used by the path planner to update the path. By taking account of the characteristics of the framed quadtree, objects can be projected on the frame nodes to increase the precision of the path. Analysis and simulations showed the proposed planner could increase efficiency while improving the ability of the AUV to follow an object.

Keywords

regular grid / framed quadtree / data structure / algorithm efficiency

References

[1] Branicky MS, LaValle SM, Olson K, Yang LB (2001). Quasi-randomized path planning. IEEE International Conference on Robotics and Automation, Seoul, Korea, 1481–1487.

[2] Chen D, Szczerba R, Uhran JJ Jr. (1995). Planning conditional shortest paths through an unknown environment: a framed-quadtree approach. Proceedings of the IEEE International Conference on Robotics and Automation, Albuquerque, USA, 33–38.

[3] Choset H., Burdick J. Sensor based motion planning: the hierarchical generalized Voronoi graph. International Journal of Robotics Research, 2000, 19(2): 96-125

[4] Choset H., Lynch K., Hutchinson S., Kantor G., Burgard W., Kavraki L.E., Thrun S. Principles of robot motion: theory, algorithms and implementation, 2005, Cambridge: The MIT Press, 7-101

[5] Dijkstra E.W. A note on two problems in connexion with graphs. Numerical Mathematics, 1959, 1(1): 269-271

[6] Latombe J. Robot motion planning, 1991, New York: Springer-Verlag, 1-40

[7] Levitin A. Introduction to the design & analysis of algorithms, 2003, New York: Addison-Wesley, 41-43

[8] Lindemann S., LaValle S.M. Current issues in sampling-based motion planning. Robotics Research: The Eleventh International Symposium, 2005, Berlin: Springer-Verlag, 36-54

[9] Lozano P. Spatial planning: a configuration space approach. IEEE Transactions on Computer, 1983, C-32(2): 108-132

[10] Mark de Berg, Cheong O., Van K.M., Overmars M. Computational geometry: algorithms and applications, 2008, New York: Springer-Verlag, 11-21

[11] McKeever S. Path planning for an Autonomous vehicle, 2000, Cambridge, USA: Massachusetts Institute of Technology, 25-45

[12] Murphy R. Introduction to AI robotics, 2000, Cambridge: MIT Press, 200-281

[13] Pearl J. Heuristics, 1984, New York: Addison-Wesley, 33-73

[14] Rohert H. Shortest path in the plane with convex polygonal obstacles. Information Processing Letters, 1986, 23: 71-76

[15] Samet H. Neighbor finding techniques for images represented by quadtrees. Computer Graphics and Image Processing, 1982, 18(1): 37-57

[16] Samet H. An overview of quadtrees, octrees, and related hierarchical data structures. NATO ASI Series, 1988, 40: 51-68

[17] Stentz A. Optimal and efficient path planning for unknown and dynamic environments. International Journal of Robotics and Automation, 1995, 10(3): 89-100

[18] Stentz A (1995b). The focused D* algorithm for real-time replanning. Proceedings International Joint Conference on Artificial Intelligence, Montreal, Canada, 1652–1659.

[19] Yahja A, Stentz A, Singh S, Brumitt L (1998). Framed-quadtree path planning for mobile robots operating in sparse environments. Proceedings of the IEEE Conference on Robotics and Automation, Leuven, Belgium, 650–655.