Towards use of dijkstra algorithm for optimal navigation of an unmanned surface vehicle in a real-time marine environment with results from artificial potential field

• Autorzy: Singh Y. , Sharma S. , Sutton R. , Hatton D.

Identyfikatory

DOI

10.12716/1001.12.01.14

• Języki publikacji: EN

Abstrakty

EN

The growing need of ocean surveying and exploration for scientific and industrial application has led to the requirement of routing strategies for ocean vehicles which are optimal in nature. Most of the op-timal path planning for marine vehicles had been conducted offline in a self-made environment. This paper takes into account a practical marine environment, i.e. Portsmouth Harbour, for finding an optimal path in terms of computational time between source and end points on a real time map for an USV. The current study makes use of a grid map generated from original and uses a Dijkstra algorithm to find the shortest path for a single USV. In order to benchmark the study, a path planning study using a well-known local path planning method artificial path planning (APF) has been conducted in a real time marine environment and effectiveness is measured in terms of path length and computational time.

Słowa kluczowe

EN

autonomous vehicles; dijkstra’s algorithm; Unmanned Surface Vehicle (USV); port of portsmouth; Artificial Path Planning (APF); Artificial Potential Field; real-time marine environment; optimal navigation

• Wydawca: Faculty of Navigation, Gdynia Maritime University
• Czasopismo: TransNav : International Journal on Marine Navigation and Safety of Sea Transportation
• Rocznik: 2018
• Tom: Vol. 12, no. 1
• Strony: 125--131
• Opis fizyczny: Bibliogr. 28 poz., rys., tab., fot.

Twórcy

autor

Singh Y.

• Plymouth University, Plymouth, United Kingdom

autor

Sharma S.

• Autonomous Marine Systems Group, Plymouth University, United Kingdom 

autor

Sutton R.

• Plymouth University, Plymouth, United Kingdom

autor

Hatton D.

• Plymouth University, Plymouth, United Kingdom

Bibliografia

• 1 Ahuja, R.K.., Mehlhorn, K., Orlin, J.B., and Tarjan, R.E. 1990. Faster Algorithms for the Shortest Path Problem, Journal of Association for Computing Machinery (ACM), 37 (2):213–223.
• 2 Baxter, J.L., Burke, E.K., Garibaldi, J.M., and Norman, M. 2007. Multi-robot search and rescue: A potential field based approach, Autonomous Robots and Agents, Springer, 9-16.
• 3 Baxter, J.L., Burke, E.K., Garibaldi, J.M., and Norman, M. 2009. Shared potential fields and their place in a multi-robot co-ordination taxonomy, Robotics and Autonomous Systems, 57(10):1048-1055.
• 4 Borenstein, J., and Koren, Y. 1991. The vector field histogram-fast obstacle avoidance for mobile robots, IEEE Trans. Robotics and Automation, 7:278-288.
• 5 Campbell, S., Naeem, W. and Irwin, G.W. 2012. A review on improving the autonomy of unmanned surface vehicles through intelligent collision avoidance manoeuvres, Annual Reviews in Control, 36: 267–83.
• 6 Chakravarthy, A., and Ghose, D. 1998. Obstacle avoidance in a Dynamic Environment: A Collision Cone Approach, IEEE Trans. Systems, Man and Cybernetics, Part A: Systems and Humans, 28:562-74.
• 7 Dijkstra, E. 1959. A note on two problems in connexion with graphs, Numer. Math. 1, 269-271.
• 8 El-Hawary, F. 2000. The Ocean Engineering Handbook, CRC Press, 1-416.
• 9 Fahimi, F., Nataraj, C., and Ashrafiuon, H. 2009. Real-time obstacle avoidance for multiple mobile robots, Robotica, 27(2): 189-198.
• 10 Fiorini, P., and Shiller, Z., 1998. Motion planning in dynamic environments using velocity obstacles, Int. J. Robotics Research, 17:760-772.
• 11 Ge, S.S., and Cui, Y.J., 2002. Dynamic motion planning for mobile robots using potential field method, Autonomous Robots, 13(3):207-222.
• 12 Hart, P.E., Nilsson, N.J., and Rapheal, B. 1968. A formal basis for the heuristic determination of minimum cost paths, IEEE Transactions on System and Scientific Cybernetics 4, 100-107.
• 13 Kala, R. 2016. Potential-Based Planning, On-Road Intelligent Vehicles, Ch.11:318-356.
• 14 Khatib, O. 1986. Real time obstacle avoidance for manipulators and mobile robots, Int. J. Robotic Research, 5:90-98.
• 15 Koenig, S., and Likhachev, M. 2002. D* Lite, AAAI/IAAI, 476-483.
• 16 Kruger, D, Stolkin, R., Blum, A., and Briganti, J. 2007. Optimal AUV path planning for extended missions in complex, fast-flowing estuarine environments, In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), 4265-4271.
• 17 Latombe, J. 1991. Robot Motion Planning, Klumer Academic Publishers, Norwell, USA.
• 18 Legrand, J., Alfonso, M., Bozzano, R., Goasguen, G., Lindh, H., Ribotti, A., Rodrigues, I., Tziavos, C. 2003. Monitoring the Marine environment: Operational Practices in Europe, In Third International Conference on Euro GOOS.
• 19 Likhachev, M., Ferguson, D.I., Gordon, G.J., Stentz, A. and Thrun, S. 2005. Anytime Dynamic A*: An Anytime, Replanning Algorithm, ICAPS, 262-271.
• 20 Nash, A., Daniel, K.., Koenig, S. And Felner, A. 2007. Theta*: any-angle path planning on grids, In Proceedings of the National Conference on Artificial Intelligence, 1177-1183.
• 21 Prasanth-Kumar, R., Dasgupta, A., Kumar, C. 2005. Real-time optimal motion planning for autonomous underwater vehicles, Ocean Engineering 32, 4265-4271.
• 22 Serreze, M.C. 2008. Arctic sea ice in 2008: standing on the threshold, In MTS/IEEE OCEANS’08 Conference.
• 23 Song, C.H. 2014. Global Path Planning Method for USV System Based on Improved Ant Colony Algorithm, Applied Mechanics and Materials, 568-570.
• 24 Song, L., Mao, Y., Xian, Z., Zhou, Y., and Du, K. 2015. A Study on Path Planning Algorithms Based upon Particle Swarm Optimization, Journal of Information and Computational Science 12, 673-680.
• 25 Stentz, A. 1995. The Focussed D* Algorithm for Real-Time Replanning, IJCAI 95, 1652-1659.
• 26 Tam, C., Bucknall, R., and Greig, A. 2009. Review of collision avoidance and path planning methods for ships in close range encounters, Journal of Navigation 59, 27-42.
• 27 Tu, K., and Baltes, J., 2006. Fuzzy potential energy for a map approach to robot navigation, J. Robotics and Autonomous Systems, 54(7):574-589.
• 28 Yang, Y., Wang, S., Wu, Z., and Wang, Y. 2011. Motion planning for multi-HUG formation in an environment with obstacles, Ocean Engineering 38, 2262-2269.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2018).