-
摘要: 礦區廢棄地為室外大型非結構化環境，包含多種類型的障礙物且存在諸多不確定性因素，給移動機器人全覆蓋路徑規劃造成了極大的困難。本文使用牛耕式單元分解法結合生物激勵神經網絡算法完成移動機器人對礦區廢棄地的全覆蓋路徑規劃。首先，針對礦區廢棄地已知環境，采用牛耕式單元分解法對復雜環境做出區域分解，將具有綜合復雜性的地圖分解為多個不含障礙物的子區域；然后，根據子區域的鄰接關系構建無向圖，采用深度優先搜索算法確定子區域間的轉移順序；最后，采用生物激勵神經網絡算法確定子區域內部行走方式以及子區域間路徑轉移。仿真結果表明，生物激勵神經網絡算法在解決機器人路徑轉移問題方面比其他路徑規劃算法更高效，所得的方法能夠處理復雜的非結構化環境，完成廢棄礦區移動機器人的覆蓋路徑規劃。
-
關鍵詞:
- 礦區廢棄地 /
- 路徑規劃 /
- 牛耕式單元分解法 /
- 區域分解 /
- 生物激勵神經網絡算法
Abstract: Land resources are the fundamental and basic requirements for human survival and development as well as for the agricultural production and industrial construction. In recent years, due to the impact of industrial construction and chemical pollution, the cultivable land area is gradually decreasing, and the available agricultural land may be gravely insufficient for food production in the future. In China, the amount of abandoned mine land has increased significantly because of China’s national supply-side structural reform program. The abandoned mine land can be transformed into agricultural land to effectively alleviate food crisis and the contradictory relationship existing between people and land, and improve the ecological environment of mining area. Abandoned mine land refers to the land that has lost its economic value due to a series of production operations and also the land that has not been artificially restored to original conditions after mining. Abandoned mine land is a large, external, and unstructured environment with multiple obstacles and uncertainties and cannot be accessed by humans. Therefore, mobile robots are used to access those areas, and even for mobile robots, planning their coverage path in those areas is difficult. In this paper, the boustrophedon cellular decomposition (BCD) method and biologically inspired neural network (BINN) algorithm were combined to complete the coverage path planning of mobile robots on abandoned mine land. First, for the known environment of the abandoned mine land, the BCD method was used to make regional decomposition of the complex environment. The map with comprehensive complexity was decomposed into several subregions without any obstacles. Second, an undirected graph (i.e., a set of objects called vertices or nodes that are connected together, where all the edges are bidirectional) was constructed according to the adjacency relationship of the subregions, and the depth first search algorithm was used to determine the transfer order between subregions. Finally, the BINN algorithm was used to determine the internal walking mode of and the regional transfer path between the subregions. Simulation results show that the BINN algorithm is of higher efficiency than any other path planning algorithms used to solve the robot path transfer problem. Moreover, the proposed method in this paper could work in complex, unstructured environments to complete the coverage path planning of mobile robots. -
圖 2 廢棄礦區復雜環境。（a）積水區；（b）廢棄廠區；（c）尾礦、煤矸石的堆占；（d）周邊土壤現狀
Figure 2. Complex environment of abandoned mine land: (a) pools zone; (b) abandoned factory; (c) heap of tailings and gangue; (d) status of surrounding soil
圖 4 礦區廢棄地仿真圖。（a）仿真環境；（b）區域分解圖
Figure 4. Simulation map of abandoned mine land: (a) simulation environment; (b) regional decomposition map
圖 5 子區域連接圖。（a）鄰接圖；（b）轉移序列圖
Figure 5. Connection diagram of subregions: (a) adjacency map; (b) transfer order map
圖 7 子區域遍歷結果。（a）全覆蓋結果；（b）路徑轉移結果
Figure 7. Coverage results of subregions: (a) complete coverage result; (b) path transition result
圖 8 實驗結果對比。（a）BINN算法；（b）A*算法；（c）Dijkstra算法；（d）RRT算法
Figure 8. Comparison of experimental results: (a) BINN algorithm; (b) A* algorithm; (c) Dijkstra algorithm; (d) RRT algorithm
圖 9 算法性能評價結果圖。（a）距離對比結果；（b）時間對比結果
Figure 9. Performance evaluation results of algorithms: (a) distance comparison result; (b) time comparison result
表 1 BCD方法步驟
Table 1. BCD method steps
Step Content Input Original map Step 1 Image preprocessing: erode the map Step 2 Traverse the array columns to determine the connectivity of slices, and return the number of connectivity and connected regions Step 3 If the slice connectivity changes, determine it is IN event or OUT event, and return the store data of current sub-region Step 4 Represent partition information on a map Output Regional decomposition map 
下載: 導出CSV
表 2 DFS算法步驟
Table 2. DFS algorithm steps
Step Content Input Sub-region adjacency graph G Step 1 Choose the starting cell $v$. Insert it into the path list. Mark it as visited Step 2 Visit an adjacent cell ${w_{\rm{1}}}$. Insert this cell into the path list. Mark it as visited Step 3 Start from ${w_1}$, go to the unvisited cell ${w_2}$ in the neighbor list of the ${w_1}$, insert this cell into the path list and mark it as visited. Repeat this procedure until all cells in G are visited Step 4 Back track from the last cell and insert each element that is visited to the front of the path list, until an element with an unvisited neighbor is encountered. Insert this element to the front of the path list Step 5 Repeat the above procedure until all cells in the adjacency graph have been visited Output Sub-region path list
下載: 導出CSV
表 3 路徑轉移距離對比
Table 3. Distance comparison of path transition
Algorithm Distance of path transition Total distance J—I I—F F—C RRT algorithm 8.30 11.30 12.86 32.46 Dijkstra algorithm 7.83 9.41 11.41 28.65 A* algorithm 7.83 9.41 11.41 28.65 BINN algorithm 7.83 9.41 10.83 28.07
下載: 導出CSV
表 4 路徑轉移時間對比
Table 4. Time comparison of path transition
Algorithm Time of path transition Total time/s J—I I—F F—C RRT algorithm 4.14 4.65 6.20 14.99 Dijkstra algorithm 1.07 1.31 1.77 4.15 A* algorithm 1.07 1.33 1.76 4.16 BINN algorithm 0.80 0.89 0.95 2.64
下載: 導出CSV
259luxu-164<th id="5nh9l"></th> <strike id="5nh9l"></strike> <th id="5nh9l"><noframes id="5nh9l"><th id="5nh9l"></th> <strike id="5nh9l"></strike> <th id="5nh9l"><noframes id="5nh9l"> <th id="5nh9l"></th> <strike id="5nh9l"><noframes id="5nh9l"><span id="5nh9l"></span> <span id="5nh9l"><noframes id="5nh9l"><span id="5nh9l"></span> <strike id="5nh9l"><noframes id="5nh9l"><strike id="5nh9l"></strike> <span id="5nh9l"><noframes id="5nh9l"> <span id="5nh9l"><noframes id="5nh9l"> <span id="5nh9l"></span> <span id="5nh9l"><video id="5nh9l"></video></span> <th id="5nh9l"><noframes id="5nh9l"><th id="5nh9l"></th> -
參考文獻
[1] Sang L H, Fu M C, Feng Y H. Progress and prospect of research on land reclamation planning and design in mining area. <italic>Coal Sci Technol</italic>, 2018, 46(2): 243桑李紅, 付梅臣, 馮洋歡. 煤礦區土地復墾規劃設計研究進展及展望. 煤炭科學技術, 2018, 46(2):243 [2] Xu B, Xu M, Chen L P, et al. Review on coverage path planning algorithm for intelligent machinery. <italic>Comput Meas Control</italic>, 2016, 24(10): 1徐博, 徐旻, 陳立平, 等. 智能機械全覆蓋路徑規劃算法綜述. 計算機測量與控制, 2016, 24(10):1 [3] Hsu P M, Lin C L, Yang M Y. On the complete coverage path planning for mobile robots. <italic>J Intell Robot Syst</italic>, 2014, 74(3-4): 945 doi: 10.1007/s10846-013-9856-0 [4] Mac T T, Copot C, Tran D T, et al. Heuristic approaches in robot path planning: a survey. <italic>Rob Autonom Syst</italic>, 2016, 86: 13 doi: 10.1016/j.robot.2016.08.001 [5] Wang Z L, Li H, Zhang X L. Construction waste recycling robot for nails and screws: computer vision technology and neural network approach. <italic>Autom Construct</italic>, 2019, 97: 220 doi: 10.1016/j.autcon.2018.11.009 [6] Wang Y N, Pan Q, Chen Y J. Path planning method based on improved biologically inspired neural network. <italic>Control Eng China</italic>, 2018, 25(4): 541王耀南, 潘琪, 陳彥杰. 改進型生物激勵神經網絡的路徑規劃方法. 控制工程, 2018, 25(4):541 [7] Zhu D Q, Cao X, Sun B, et al. Biologically inspired self-organizing map applied to task assignment and path planning of an AUV system. <italic>IEEE Trans Cognitive Dev Syst</italic>, 2018, 10(2): 304 doi: 10.1109/TCDS.2017.2727678 [8] Zhu D Q, Yan M Z. Survey on technology of mobile robot path planning. <italic>Control Des</italic>, 2010, 25(7): 961朱大奇, 顏明重. 移動機器人路徑規劃技術綜述. 控制與決策, 2010, 25(7):961 [9] 劉剛, 李笑, 康熙, 等. 基于GNSS的農田平整自動導航路徑規劃方法. 農業機械學報, 2016, 47(增刊1):21)Liu G, Li X, Kang X, et al. Automatic navigation path planning method for land leveling based on GNSS. <italic>Trans Chin Soc Agric Mach</italic>, 2016, 47(增刊1): 21 [10] Sucan I A, Moll M, Kaveraki L E. The open motion planning library. <italic>IEEE Rob Autom Mag</italic>, 2012, 19(4): 72 doi: 10.1109/MRA.2012.2205651 [11] Oksanen T, Visala A. Coverage path planning algorithms for agricultural field machines. <italic>J Field Rob</italic>, 2009, 26(8): 651 doi: 10.1002/rob.20300 [12] Palleja T, Tresanchez M, Teixido M, et al. Modeling floor-cleaning coverage performances of some domestic mobile robots in a reduced scenario. <italic>Rob Autonom Syst</italic>, 2010, 58(1): 37 doi: 10.1016/j.robot.2009.07.030 [13] Bircher A, Kamel M, Alexis K, et al. Receding horizon path planning for 3D exploration and surface inspection. <italic>Autonom Robots</italic>, 2018, 42(2): 291 doi: 10.1007/s10514-016-9610-0 [14] Wang H J, Yu Y, Yuan Q B. Application of Dijkstra algorithm in robot path-planning // Second International Conference on Mechanic Automation & Control Engineering. Hohhot, 2011: 1067 [15] Fu B, Chen L, Zhou Y T, et al. An improved A* algorithm for the industrial robot path planning with high success rate and short length. <italic>Rob Autonomous Syst</italic>, 2018, 106: 26 doi: 10.1016/j.robot.2018.04.007 [16] Wei K, Ren B Y. A method on dynamic path planning for robotic manipulator autonomous obstacle avoidance based on an improved RRT algorithm. <italic>Sensors</italic>, 2018, 18(2): 571 doi: 10.3390/s18020571 [17] Rashid R, Perumal N, Elamvazuthi I, et al. Mobile robot path planning using Ant Colony Optimization// 2016 2nd IEEE International Symposium on Robotics and Manufacturing Automation (ROMA). Ipoh, 2016: 1 [18] Zhang C, Li Q, Chen P, et al. Improved ant colony optimization based on particle swarm optimization and its application. <italic>J Univ Sci Technol Beijing</italic>, 2013, 35(7): 955張超, 李擎, 陳鵬, 等. 一種基于粒子群參數優化的改進蟻群算法及其應用. 北京科技大學學報, 2013, 35(7):955 [19] Tian Z J, Gao X H, Zhang M X. Path planning based on the improved artificial potential field of coal mine dynamic target navigation. J China Coal Soc, 2016, 41(Suppl 2): 589田子建, 高學浩, 張夢霞. 基于改進人工勢場的礦井導航裝置路徑規劃. 煤炭學報, 2016, 41(增刊2): 589 [20] Chen E K, Wu M H, Zhang Y J. Path planning for coal mine rescue robot in complex environment. <italic>Coal Technol</italic>, 2018, 37(10): 301陳爾奎, 吳梅花, 張英杰. 復雜環境下煤礦救災機器人路徑規劃. 煤炭技術, 2018, 37(10):301 [21] Sun J, Chen Z H, Wang P, et al. Multi-region coverage method based on cost map and minimal tree for mobile robot. <italic>Robot</italic>, 2015, 37(4): 435孫建, 陳宗海, 王鵬, 等. 基于代價地圖和最小樹的移動機器人多區域覆蓋方法. 機器人, 2015, 37(4):435 [22] Hameed I A, Bochtis D, S?rensen C A. An optimized field coverage planning approach for navigation of agricultural robots in fields involving obstacle areas. <italic>Int J Adv Rob Syst</italic>, 2013, 10(5): 1 [23] Tang Q S. Application and research on tree structure based on depth-first algorithm. <italic>Comput Technol Dev</italic>, 2014, 24(9): 226唐青松. 深度優先算法在創建樹形結構中的應用研究. 計算機技術與發展, 2014, 24(9):226 [24] Luo C M, Yang S X, Li X D, et al. Neural-dynamics-driven complete area coverage navigation through cooperation of multiple mobile robots. <italic>IEEE Trans Ind Electron</italic>, 2017, 64(1): 750 doi: 10.1109/TIE.2016.2609838 [25] Yang S X, Meng M. An efficient neural network approach to dynamic robot motion planning. <italic>Neural Networks</italic>, 2000, 13(2): 143 doi: 10.1016/S0893-6080(99)00103-3 -
點擊查看大圖
圖(9) / 表(4)
計量
- 文章訪問數: 1996
- HTML全文瀏覽量: 1121
- PDF下載量: 123
- 被引次數: 0
