浏览全部资源
扫码关注微信
Published： 16 August 2023 ，
移动端阅览
王朝飞， 王慎执， 宋士吉， 王凯， 武帅， 黄高， 吴澄. 2023. 面向海域巡逻的多无人船路径规划方法及仿真. 中国图象图形学报， 28(08):2536-2548
Wang Chaofei， Wang Shenzhi， Song Shiji， Wang Kai， Wu Shuai， Huang Gao， Wu Cheng. 2023. Multiple unmanned surface vehicles-based path planning method for sea patrol. Journal of Image and Graphics， 28(08):2536-2548
目的
2
随着人工智能技术的大力发展，以无人船为代表的智能无人装备在海洋技术领域已开始实际应用。在大型海域巡逻任务中，相比传统的巡逻装备，多无人船协同执行区域覆盖任务具有运行时间短、效率高以及风险低等优势，但需要解决任务划分、能源补给等难点问题。针对上述问题，提出一套完整的解决大型海域巡逻任务的多无人船协同执行区域覆盖任务的解决方案，并进行面向实际海图的仿真实验。
方法
2
首先对多无人船海域巡逻任务进行了问题定义和建模，在构建栅格海域地图的基础上，提出了基于任务均衡的区域划分策略和多种评价指标；在分析比较多种传统遍历算法优劣的基础上，提出了无能源约束和有能源约束条件下的多无人船区域覆盖遍历算法，尤其在有能源约束条件下考虑了多种充电后路径规划策略。
结果
2
利用Python搭建仿真应用平台，对三沙市周边15 000多平方公里海域进行仿真实验，实验比较了不同遍历算法在无能源约束和有能源约束条件下的优劣，验证了所提出的区域划分策略和遍历算法的有效性和能源约束下无人船在充电后重新规划遍历路径策略的优越性，并对覆盖率和无人船电池里程等参数进行了消融实验。
结论
2
提出的方法和仿真分析结果为多无人船协同执行大型海域巡逻任务的实际应用提供了一定的借鉴作用。
Objective
2
The artificial intelligence （AI） technology based intelligent unmanned equipments like unmanned surface vehicles have been developing for such domains of marine technology-derived military operation and counter-terrorism， resource exploration， seabed topography mapping， water quality testing， and marine search and rescue. In recent years， such issues of unmanned surface vehicles-related path planning have been concerned about. However， existing tasks are still focused on the path planning of single unmanned surface vehicle. The methods and simulations are only based on narrowed water areas like lakes and ports， and the problem of energy constraint is required to be melted into as well. For large-scale sea patrol scenarios， multi-unmanned surface vehicles can be incorporated into coverage path planning tasks in terms of quick response-relevant fast speed， high efficiency and low risk. However， small unmanned surface vessels for sea patrol are mainly driven electrically. Their navigating range and operating time are limited. It is necessary to divide the large-scale sea patrol task into multiple tasks and the problem of energy constraint is required to be resolved for unmanned surface ships. Therefore， we develop a solution of area coverage path planning based on multiple unmanned surface vehicles-integrated large-scale sea patrol tasks.
Method
2
First， we define and model the problem of sea patrol of multi-unmanned surface vehicles， a task-equal region division strategy and multiple evaluation criteria are proposed and implemented through constructing the sea grid map. The task-equal region division strategy can make all unmanned surface vehicles get similar size of task area and ensure that the full task can be completed to reach the minimum total time. Second， we analyse and compare several traditional traversal algorithms， including round-trip traversal algorithm or spiral traversal algorithm. The breadth-first search algorithm is combined with these traversal algorithms to perform the area coverage path planning task. We demonstrate two sort of traversal algorithms under two different conditions， that is， energy constraint is included or excluded. Especially， two energy constraint-derived charging path planning strategies are taken into account， including the original route or a new route after charging. Intuitively， the advantage of the former is a kind of decoupling path planning in terms of energy supply， while the limition is linked with the duplication of charging path. The redundancy is derived of repetition rate and wastes part of energy. The pros of the latter is concerned that the charging route is not traversed again， while the cons is that complexity of the task map can be increased due to redundant routes. It may cause more energy supply.
Result
2
A Python-related simulation platform is built up based on the sea map of more than 15 000 square kilometers around Sansha city of China. Specifically， such configurable settings are listed： the physics simulation engine is Pymunk， the rendering tool is Pygame， and the numerical calculation tool is Numpy. We carry our three sorts of key experiments and get some following results. 1） The advantages and disadvantages of different traversal algorithms are analysed and compared under the conditions of energy constraints-included or excluded. In detail， we adopt breadth-first search algorithm in related to round-trip traversal algorithm or spiral traversal algorithm. For non-energy constraint， round-trip coverage method is generally better than spiral coverage method. It means that the repetition rate， the total number of steps and the total time of the round-trip traversal algorithm are lower than spiral algorithm under the same circumstances. 2） The effectiveness of the proposed task-equal region division strategy is validated. For example， under the setting of five unmanned ships for operation， the coverage rates of the coveraged areas are 20.8%， 20.4%， 20%， 19.8% and 19.0% in the total area. Similar sized task areas can ensure consistent task time for different ships to minimize total task time. 3） Compared to non-energy constraints， energy constraint-related setting is challenged much more， and the energy constraint-relevant setting can illustrate higher repetition rate， total steps and total time on the basis of the same number of unmanned ships and the same traversal algorithm. Energy constraint can be used to validate the potentials of routes replanning after charging beyond the original path after charging. Furthermore， ablation experiments are carried out in relevance to parameters-based number of ships， coverage rate and battery range of the unmanned ship. Ablation experimental results demonstrate that： 1） Increasing the number of unmanned ships will significantly reduce the total time to complete the task. There is an inverse relationship between the number of unmanned ships and the total task time. In practice， the increasment of the number of unmanned vessels can be as the most effective scheme to improve the efficiency within the range of purchase cost. 2） Appropriate reduction of the coverage requirement can reduce the repetition rate and the total task time. Actually， you can compensate the reduced coverage requirements to perform multiple tasks through changing the starting point. 3） Battery range of unmanned ships can be increased to improve task efficiency dramatically.
Conclusion
2
A solution of area coverage path planning is developed based on multiple unmanned surface vehicles cooperation for large-scale sea patrol tasks. The solution can deal with the problems of task division and energy supply of multiple unmanned surface vehicles， and be viewed as a certain reference for the practical application of multi-unmanned surface vehicles performing large-scale sea patrol tasks. Next， we will further study the relationship between charging equipment deployment strategy and algorithm efficiency in real sea environment， consider the problem of sudden collision avoidance during the navigation of unmanned ships， and expand the application scope of the proposed method， such as the seabed three-dimensional detection task.
海域巡逻无人船区域覆盖路径规划能源约束仿真
sea patrolunmanned surface vehiclearea coverage path planningenergy constraintsimulation
Balch T. 2000. The case for randomized search//Workshop on Sensors and Motion， IEEE International Conference on Robotics and Automation. San Francisco， USA： IEEE： 213-215
Bao X Y. 2018. Study on Cruise Route Planning of Unmanned Exploration Vessel Formation in Shallow Water Area. Guangzhou： South China University of Technology
包昕幼. 2018. 浅水区域无人探测艇编队巡航路径规划研究. 广州： 华南理工大学
Chang J Q， Pu J J， Zhuang Z Y， Cao L H and Zhang Y H. 2019. Application analysis of unmanned vehicle in the field of marine survey. Ship Engineering， 41（1）： 6-10， 78
常继强， 蒲进菁， 庄振业， 曹立华， 张永华. 2019. 无人船在海洋调查领域的应用分析. 船舶工程， 41（1）： 6-10， 78 ［DOI： 10.13788/j.cnki.cbgc.2019.01.02http://dx.doi.org/10.13788/j.cnki.cbgc.2019.01.02］
Chang S P， Shao L F， Zhou Z W and Liang X F. 2020. Research on application of USV to combat and support at border and coastal defence. Ship Engineering， 42（S1）： 10-13
常书平， 邵立福， 周自文， 梁晓锋. 2020. 无人艇在边海防作战保障中的应用研究. 船舶工程， 42（S1）： 10-13 ［DOI： 10.13788/j.cnki.cbgc.2020.S1.003http://dx.doi.org/10.13788/j.cnki.cbgc.2020.S1.003］
Chen J. 2013. The Research of Path Planning Algorithm for Unmanned Rescue Ship. Wuhan： Wuhan University of Technology
陈佳. 2013. 无人驾驶救助船路径规划算法的研究. 武汉： 武汉理工大学
Chen X， Yuan Y H and Rao D. 2021. Improved A* algorithm and its application in path planning of unmanned surface vehicle. Computer Simulation， 38（3）： 277-281
陈新， 袁宇浩， 饶丹. 2021. 一种改进A*算法在无人船路径规划中的应用. 计算机仿真， 38（3）： 277-281
Choset H and Pignon P. 1998. Coverage path planning： the boustrophedon cellular decomposition//Field and Service Robotics. London， UK： Springer： 203-209 ［DOI： 10.1007/978-1-4471-1273-0_32http://dx.doi.org/10.1007/978-1-4471-1273-0_32］
Choset H. 2001. Coverage for robotics —— A survey of recent results. Annals of Mathematics and Artificial Intelligence， 31（1/4）： 113-126 ［DOI： 10.1023/A：1016639210559http://dx.doi.org/10.1023/A：1016639210559］
Doucette A and Lu W. 2015. An intelligent robotic system for localization and path planning using depth first search//Proceedings of 2015 International Conference on Artificial Intelligence. The Steering Committee of the World Congress in Computer Science， Computer Engineering and Applied Computing （WorldComp）. Las Vegas， USA： IEEE： 401-402
Gabriely Y and Rimon E. 2001. Spanning-tree based coverage of continuous areas by a mobile robot//Proceedings of 2001 ICRA. IEEE International Conference on Robotics and Automation. Seoul， Korea （South）： IEEE： 1927-1933 ［DOI： 10.1109/robot.2001.932890http://dx.doi.org/10.1109/robot.2001.932890］
Hao Z B， Hong B R and Huang Q C. 2007. Study of coverage path planning based on grid-map. Application Research of Computers， 24（10）： 56-58
郝宗波， 洪炳镕， 黄庆成. 2007. 基于栅格地图的机器人覆盖路径规划研究. 计算机应用研究， 24（10）： 56-58 ［DOI： 10.3969/j.issn.1001-3695.2007.10.016http://dx.doi.org/10.3969/j.issn.1001-3695.2007.10.016］
Hong D F， Gao L R， Yao J， Zhang B， Plaza A and Chanussot J. 2021a. Graph convolutional networks for hyperspectral image classification. IEEE Transactions on Geoscience and Remote Sensing， 59（7）： 5966-5978 ［DOI： 10.1109/TGRS.2020.3015157http://dx.doi.org/10.1109/TGRS.2020.3015157］
Hong D F， He W， Yokoya N， Yao J， Gao L R， Zhang L P， Chanussot J and Zhu X X. 2021b. Interpretable hyperspectral artificial intelligence： when nonconvex modeling meets hyperspectral remote sensing. IEEE Geoscience and Remote Sensing Magazine， 9（2）： 52-87 ［DOI： 10.1109/MGRS.2021.3064051http://dx.doi.org/10.1109/MGRS.2021.3064051］
Lazarowska A. 2015. Ship’s trajectory planning for collision avoidance at sea based on ant colony optimisation. The Journal of Navigation， 68（2）： 291-307 ［DOI： 10.1017/S0373463314000708http://dx.doi.org/10.1017/S0373463314000708］
Liu J H， Yang J G， Liu H P， Tian X J and Gao M. 2017. An improved ant colony algorithm for robot path planning. Soft Computing， 21（19）： 5829-5839 ［DOI： 10.1007/s00500-016-2161-7http://dx.doi.org/10.1007/s00500-016-2161-7］
Liu S， Li Z S and Li Q. 2009. Improved Genetic Algorithms optimal area covering path planning for family robot. Computer Engineering and Applications， 45（31）： 245-248
刘松， 李志蜀， 李奇. 2009. 机器人全覆盖最优路径规划的改进遗传算法. 计算机工程与应用， 45（31）： 245-248 ［DOI： 10.3778/j.issn.1002-8331.2009.31.073http://dx.doi.org/10.3778/j.issn.1002-8331.2009.31.073］
Luo D C. 2019. Research on Collaborative Area Search Strategy for Multiple Unmanned Surface Vehicles. Harbin： Harbin Engineering University
罗代超. 2019. 多水面无人艇协同区域搜索策略研究. 哈尔滨： 哈尔滨工程大学 ［DOI： 10.27060/d.cnki.ghbcu.2019.000121http://dx.doi.org/10.27060/d.cnki.ghbcu.2019.000121］
Lyu X F， Cheng Q Z， Li S H and Lin Z. 2019. Unmanned surface vehicle full traversal path planning based on improved A* algorithm. Journal of Unmanned Undersea Systems， 27（6）： 695-703
吕霞付， 程啟忠， 李森浩， 林政. 2019. 基于改进A*算法的无人船完全遍历路径规划. 水下无人系统学报， 27（6）： 695-703
Lyu Y M， Lu K L and Wang Z. 2019. Research on path planning method of water quality monitoring USV. Intelligent Computer and Applications， 9（1）： 14-18， 23
吕扬民， 陆康丽， 王梓. 2019. 水质监测无人船路径规划方法研究. 智能计算机与应用， 9（1）： 14-18， 23 ［DOI： 10.3969/j.issn.2095-2163.2019.01.003http://dx.doi.org/10.3969/j.issn.2095-2163.2019.01.003］
Ma W T and Shi C L. 2020. Xi Jinping’s discussion on China’s maritime security governance： logic， basic requirements and capacity building. Journal of Fujian Provincial Committee Party School of CPC（FuJian Academy of Governance）， （6）： 23-31
马文婷， 史春林. 2020. 习近平关于中国海洋安全治理论述： 逻辑理路、基本要求与能力建设. 中共福建省委党校（福建行政学院）学报， （6）： 23-31 ［DOI： 10.15993/j.cnki.cn35-1198/c.2020.06.012http://dx.doi.org/10.15993/j.cnki.cn35-1198/c.2020.06.012］
Moravec H and Elfes A. 1985. High resolution maps from wide angle sonar//Proceedings of 1985 IEEE International Conference on Robotics and Automation. St. Louis， USA： IEEE： 116-121 ［DOI： 10.1109/robot.1985.1087316http://dx.doi.org/10.1109/robot.1985.1087316］
Pal A， Tiwari R and Shukla A. 2012. Modified A* algorithm for mobile robot path planning//Soft Computing Techniques in Vision Science. Berlin， Heidelberg， Germany： Springer： 183-193 ［DOI： 10.1007/978-3-642-25507-6_16http://dx.doi.org/10.1007/978-3-642-25507-6_16］
Tripathy H K， Mishra S， Thakkar H K and Rai D. 2021. CARE： a collision-aware mobile robot navigation in grid environment using improved breadth first search. Computers and Electrical Engineering， 94： #107327 ［DOI： 10.1016/j.compeleceng.2021.107327http://dx.doi.org/10.1016/j.compeleceng.2021.107327］
Wang D， Li C H， Guo N， Gao T T and Liu G M. 2021. Local path planning for mobile robot based on improved artificial potential field method. Journal of Shandong University of Technology （Natural Science Edition）， 35（3）： 1-6
王迪， 李彩虹， 郭娜， 高腾腾， 刘国名. 2021. 改进人工势场法的移动机器人局部路径规划. 山东理工大学学报（自然科学版）， 35（3）： 1-6 ［DOI： 10.13367/j.cnki.sdgc.2021.03.001http://dx.doi.org/10.13367/j.cnki.sdgc.2021.03.001］
Wang S， Zhang J Q， Yang S H and Zhang B L. 2019. Research on development status and combat applications of USVs in worldwide. Fire Control and Command Control， 44（2）： 11-15
王石， 张建强， 杨舒卉， 张博伦. 2019. 国内外无人艇发展现状及典型作战应用研究. 火力与指挥控制， 44（2）： 11-15 ［DOI： 10.3969/j.issn.1002-0640.2019.02.003http://dx.doi.org/10.3969/j.issn.1002-0640.2019.02.003］
Weng L， Yang Y and Zhong Y X. 2020. Collaborative traversal path planning algorithm of for multiple unmanned survey vessels. Journal of Unmanned Undersea Systems， 28（6）： 634-641
翁磊， 杨扬， 钟雨轩. 2020. 多无人艇协同遍历路径规划算法. 水下无人系统学报， 28（6）： 634-641 ［DOI： 10.11993/j.issn.2096-3920.2020.06.007http://dx.doi.org/10.11993/j.issn.2096-3920.2020.06.007］
Yakoubi M A and Laskri M T. 2016. The path planning of cleaner robot for coverage region using genetic algorithms. Journal of Innovation in Digital Ecosystems， 3（1）： 37-43 ［DOI： 10.1016/j.jides.2016.05.004http://dx.doi.org/10.1016/j.jides.2016.05.004］
Yang S X and Luo C. 2004. A neural network approach to complete coverage path planning. IEEE Transactions on Systems， Man， and Cybernetics， Part B （Cybernetics）， 34（1）： 718-724 ［DOI： 10.1109/TSMCB.2003.811769http://dx.doi.org/10.1109/TSMCB.2003.811769］
Ye C， Lu T Y， Xiao Y H， Lu H and Yang Q H. 2022. Maritime surveillance videos based ships detection algorithms： a survey. Journal of Image and Graphics， 27（7）： 2078-2093
叶晨， 逯天洋， 肖潏灏， 陆海， 杨群慧. 2022. 海事监控视频舰船目标检测研究现状与展望. 中国图象图形学报， 27（7）： 2078-2093 ［DOI： 10.11834/jig.200674http://dx.doi.org/10.11834/jig.200674］
Zhang D F and Liu F. 2013. Research and development trend of path planning based on artificial potential field method. Computer Engineering and Science， 35（6）： 88-95
张殿富， 刘福. 2013. 基于人工势场法的路径规划方法研究及展望. 计算机工程与科学， 35（6）： 88-95 ［DOI： 10.3969/j.issn.1007-130X.2013.06.015http://dx.doi.org/10.3969/j.issn.1007-130X.2013.06.015］
Zhang Q. 2019. Research on Complete Coverage Path Planning for Unmanned Surface Vessel. Wuhan： Wuhan University of Technology
张琪. 2019. 全区域覆盖自主移动无人船路径规划研究. 武汉： 武汉理工大学 ［DOI： 10.27381/d.cnki.gwlgu.2019.001453http://dx.doi.org/10.27381/d.cnki.gwlgu.2019.001453］
Zhang X H， Yao L B， Lyu Y F， Jian T， Zhao Z W and Zang J. 2020. Data-adaptive single-shot ship detector with a bidirectional feature fusion module for SAR images. Journal of Image and Graphics， 25（9）： 1943-1952
张筱晗， 姚力波， 吕亚飞， 简涛， 赵志伟， 藏洁. 2020. 双向特征融合的数据自适应SAR图像舰船目标检测模型. 中国图象图形学报， 25（9）： 1943-1952 ［DOI： 10.11834/jig.190558http://dx.doi.org/10.11834/jig.190558］
Zhao D R. 2020. Research on Full Coverage Path Planning and Tracking Technology for USV. Dalian： Dalian Maritime University
赵德润. 2020. 无人船区域全覆盖路径规划与跟踪技术的研究. 大连： 大连海事大学 ［DOI： 10.26989/d.cnki.gdlhu.2020.000514http://dx.doi.org/10.26989/d.cnki.gdlhu.2020.000514］
Zhao H， Zhao D R， Wang N and Guo C. 2020. Research on improved BINN algorithm for coverage of prioritized area in path planning of unmanned surface vessel. Shipbuilding of China， 61（2）： 91-102
赵红， 赵德润， 王宁， 郭晨. 2020. 改进型BINN算法应用在无人船优先区域覆盖路径规划的研究. 中国造船， 61（2）： 91-102 ［DOI： 10.3969/j.issn.1000-4882.2020.02.009http://dx.doi.org/10.3969/j.issn.1000-4882.2020.02.009］
Zuo L， Yan W S， Cui R X and Gao J. 2016. A coverage algorithm for multiple autonomous surface vehicles in flowing environments. International Journal of Control， Automation and Systems， 14（2）： 540-548 ［DOI： 10.1007/s12555-014-0454-0http://dx.doi.org/10.1007/s12555-014-0454-0］
相关作者
相关机构
京公网安备11010802024621