{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,13]],"date-time":"2026-01-13T01:12:10Z","timestamp":1768266730150,"version":"3.49.0"},"reference-count":30,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2019,1,21]],"date-time":"2019-01-21T00:00:00Z","timestamp":1548028800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"National Key Technology Support Program","award":["2014BAK12B06,2015BAG20B02"],"award-info":[{"award-number":["2014BAK12B06,2015BAG20B02"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11671400, 61672524"],"award-info":[{"award-number":["11671400, 61672524"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Sensors"],"abstract":"<jats:p>Maritime Autonomous Surface Ships (MASS) with advanced guidance, navigation, and control capabilities have attracted great attention in recent years. Sailing safely and efficiently are critical requirements for autonomous control of MASS. The MASS utilizes the information collected by the radar, camera, and Autonomous Identification System (AIS) with which it is equipped. This paper investigates the problem of optimal motion planning for MASS, so it can accomplish its sailing task early and safely when it sails together with other conventional ships. We develop velocity obstacle models for both dynamic and static obstacles to represent the potential conflict-free region with other objects. A greedy interval-based motion-planning algorithm is proposed based on the Velocity Obstacle (VO) model, and we show that the greedy approach may fail to avoid collisions in the successive intervals. A way-blocking metric is proposed to evaluate the risk of collision to improve the greedy algorithm. Then, by assuming constant velocities of the surrounding ships, a novel Dynamic Programming (DP) method is proposed to generate the optimal multiple interval motion plan for MASS. These proposed algorithms are verified by extensive simulations, which show that the DP algorithm provides the lowest collision rate overall and better sailing efficiency than the greedy approaches.<\/jats:p>","DOI":"10.3390\/s19020434","type":"journal-article","created":{"date-parts":[[2019,1,22]],"date-time":"2019-01-22T03:08:22Z","timestamp":1548126502000},"page":"434","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":48,"title":["Motion Plan of Maritime Autonomous Surface Ships by Dynamic Programming for Collision Avoidance and Speed Optimization"],"prefix":"10.3390","volume":"19","author":[{"given":"Xiongfei","family":"Geng","sequence":"first","affiliation":[{"name":"School of Software and Microelectronics, Peking University, Beijing 100871, China"},{"name":"China Waterborne Transport Research Institute, Beijing 100088, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4197-2258","authenticated-orcid":false,"given":"Yongcai","family":"Wang","sequence":"additional","affiliation":[{"name":"Department of Computer Sciences, Renmin University of China, Beijing 100872, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8854-2079","authenticated-orcid":false,"given":"Ping","family":"Wang","sequence":"additional","affiliation":[{"name":"School of Software and Microelectronics, Peking University, Beijing 100871, China"}]},{"given":"Baochen","family":"Zhang","sequence":"additional","affiliation":[{"name":"China Waterborne Transport Research Institute, Beijing 100088, China"}]}],"member":"1968","published-online":{"date-parts":[[2019,1,21]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1016\/j.arcontrol.2012.09.008","article-title":"A review on improving the autonomy of unmanned surface vehicles through intelligent collision avoidance manoeuvres","volume":"36","author":"Campbell","year":"2012","journal-title":"Annu. Rev. Control"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1016\/j.oceaneng.2018.04.018","article-title":"Developing a navigation, guidance and obstacle avoidance algorithm for an Unmanned Surface Vehicle (USV) by algorithms fusion","volume":"159","author":"Mousazadeh","year":"2018","journal-title":"Ocean Eng."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"9673","DOI":"10.3182\/20140824-6-ZA-1003.01872","article-title":"Collision Avoidance for Vessels using a Low-Cost Radar Sensor","volume":"47","author":"Schuster","year":"2014","journal-title":"IFAC Proc. Vol."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1016\/j.ssci.2013.02.006","article-title":"A spatial-temporal forensic analysis for inland-water ship collisions using AIS data","volume":"57","author":"Wang","year":"2013","journal-title":"Saf. Sci."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1016\/j.arcontrol.2016.04.018","article-title":"Unmanned surface vehicles: An overview of developments and challenges","volume":"41","author":"Liu","year":"2016","journal-title":"Annu. Rev. Control"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"52","DOI":"10.1016\/j.trc.2014.03.001","article-title":"Ship speed optimization: Concepts, models and combined speed-routing scenarios","volume":"44","author":"Psaraftis","year":"2014","journal-title":"Transp. Res. Part C Emerg. Technol."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"128","DOI":"10.1016\/j.oceaneng.2015.06.055","article-title":"Local reactive obstacle avoidance approach for high-speed unmanned surface vehicle","volume":"106","author":"Tang","year":"2015","journal-title":"Ocean Eng."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1109\/TSSC.1968.300136","article-title":"A Formal Basis for the Heuristic Determination of Minimum Cost Paths","volume":"4","author":"Hart","year":"1968","journal-title":"IEEE Trans. Syst. Sci. Cybern."},{"key":"ref_9","unstructured":"Stentz, A. (1994, January 8\u201313). Optimal and efficient path planning for partially-known environments. Proceedings of the 1994 IEEE International Conference on Robotics and Automation, San Diego, CA, USA."},{"key":"ref_10","unstructured":"Simmons, R. (1996, January 22\u201328). The curvature-velocity method for local obstacle avoidance. Proceedings of the IEEE International Conference on Robotics and Automation, Minneapolis, MN, USA."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Seder, M., Macek, K., and Petrovic, I. (2005, January 6\u201310). An integrated approach to real-time mobile robot control in partially known indoor environments. Proceedings of the 31st Annual Conference of IEEE Industrial Electronics Society, Raleigh, NC, USA.","DOI":"10.1109\/IECON.2005.1569176"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"760","DOI":"10.1177\/027836499801700706","article-title":"Motion Planning in Dynamic Environments Using Velocity Obstacles","volume":"17","author":"Fiorini","year":"1998","journal-title":"Int. J. Robot. Res."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Thrun, S., Brooks, R., and Durrant-Whyte, H. (2007). Field D*: An Interpolation-Based Path Planner and Replanner. Robotics Research, Springer.","DOI":"10.1007\/978-3-540-48113-3"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1109\/CC.2017.7868176","article-title":"Lanepost: Lane-based optimal routing protocol for delay-tolerant maritime networks","volume":"14","author":"Geng","year":"2017","journal-title":"China Commun."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Overmars, M., Karamouzas, I., and Geraerts, R. (2008). Flexible Path Planning Using Corridor Maps. European Symposium on Algorithms, Springer.","DOI":"10.1007\/978-3-540-87744-8_1"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Shaikh, F.K., Chowdhry, B.S., Zeadally, S., Hussain, D.M.A., Memon, A.A., and Uqaili, M.A. (2014). IBA: Intelligent Bug Algorithm\u2014A Novel Strategy to Navigate Mobile Robots Autonomously. Communication Technologies, Information Security and Sustainable Development, Springer.","DOI":"10.1007\/978-3-319-10987-9"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"1123","DOI":"10.1016\/j.robot.2012.05.021","article-title":"A novel obstacle avoidance algorithm: \u201cFollow the Gap Method\u201d","volume":"60","author":"Sezer","year":"2012","journal-title":"Robot. Auton. Syst."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"6477","DOI":"10.1007\/s13369-014-1154-z","article-title":"Advance Particle Swarm Optimization-Based Navigational Controller for Mobile Robot","volume":"39","author":"Deepak","year":"2014","journal-title":"Arabian J. Sci. Eng."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Ran, L., Zhang, Y., Zhang, Q., and Yang, T. (2017). Convolutional Neural Network-Based Robot Navigation Using Uncalibrated Spherical Images. Sensors, 17.","DOI":"10.3390\/s17061341"},{"key":"ref_20","unstructured":"Ogren, P., and Leonard, N.E. (October, January 30). A tractable convergent dynamic window approach to obstacle avoidance. Proceedings of the IEEE\/RSJ International Conference on Intelligent Robots and Systems, Lausanne, Switzerland."},{"key":"ref_21","unstructured":"Ko, N.Y., and Simmons, R.G. (1998, January 13\u201317). The lane-curvature method for local obstacle avoidance. Proceedings of the 1998 IEEE\/RSJ International Conference on Intelligent Robots and Systems, Victoria, BC, Canada."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"110","DOI":"10.1109\/JOE.2013.2254214","article-title":"Safe Maritime Autonomous Navigation With COLREGS, Using Velocity Obstacles","volume":"39","author":"Kuwata","year":"2014","journal-title":"IEEE J. Ocean. Eng."},{"key":"ref_23","unstructured":"Berg, J.v.d., Snape, J., Guy, S.J., and Manocha, D. (2011, January 9\u201313). Reciprocal collision avoidance with acceleration-velocity obstacles. Proceedings of the 2011 IEEE International Conference on Robotics and Automation, Shanghai, China."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Snape, J., van den Berg, J., Guy, S.J., and Manocha, D. (2009, January 11\u201315). Independent Navigation of Multiple Mobile Robots with Hybrid Reciprocal Velocity Obstacles. Proceedings of the 2009 IEEE\/RSJ International Conference on Intelligent Robots and Systems, St. Louis, MI, USA.","DOI":"10.1109\/IROS.2009.5354821"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"562","DOI":"10.1109\/3468.709600","article-title":"Obstacle avoidance in a dynamic environment: a collision cone approach","volume":"28","author":"Chakravarthy","year":"1998","journal-title":"IEEE Trans. Syst. Man Cybern. Part A Syst. Hum."},{"key":"ref_26","unstructured":"Meyer-Delius, D., Beinhofer, M., and Burgard, W. (2012, January 22\u201326). Occupancy Grid Models for Robot Mapping in Changing Environments. Proceedings of the AAAI 2012, Toronto, ON, Canada."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1163\/156855399X00928","article-title":"Trajectory planning in a dynamic workspace: a \u2019state-time space\u2019 approach","volume":"13","author":"Fraichard","year":"1998","journal-title":"Adv. Robot."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"1499","DOI":"10.1243\/09544070JAUTO1149","article-title":"Obstacle avoidance of autonomous vehicles based on model predictive control","volume":"223","author":"Park","year":"2009","journal-title":"Proc. Inst. Mech. Eng. Part D J. Automob. Eng."},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Magni, L., Raimondo, D.M., and Allgo\u030awer, F. (2009). Nonlinear Model Predictive Control: Towards New Challenging Applications, Springer. Lecture Notes in Control and Information Sciences.","DOI":"10.1007\/978-3-642-01094-1"},{"key":"ref_30","unstructured":"Ng, J. (2010). An Analysis of Mobile Robot Navigation Algorithms in Unknown Environments. [Ph.D. Thesis, University of Western Australia]."}],"container-title":["Sensors"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1424-8220\/19\/2\/434\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T12:27:43Z","timestamp":1760185663000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1424-8220\/19\/2\/434"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1,21]]},"references-count":30,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2019,1]]}},"alternative-id":["s19020434"],"URL":"https:\/\/doi.org\/10.3390\/s19020434","relation":{},"ISSN":["1424-8220"],"issn-type":[{"value":"1424-8220","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,1,21]]}}}