一種針對大型凹型障礙物的組合導航算法
doi: 10.11999/JEIT190179
-
1.
齊魯工業(yè)大學(山東省科學院)電子信息工程學院(大學物理教學部) 濟南 250353
-
2.
齊魯工業(yè)大學(山東省科學院)電氣工程與自動化學院 濟南 250353
-
3.
齊魯工業(yè)大學(山東省科學院)山東省科學院自動化研究所 濟南 250101
-
4.
濟南市人機智能協(xié)同工程實驗室 濟南 250353
Integrated Navigation Algorithm for Large Concave Obstacles
-
1.
School of Electronic and Information Engineering (Department of Physics), Qilu University of Technology (Shandong Academy of Sciences), Jinan 250353, China)
-
2.
School of Electrical Engineering and Automation, Qilu University of Technology (Shandong Academy of Sciences), Jinan 250353, China
-
3.
Institute of Automation, Qilu University of Technology (Shandong Academy of Sciences), Jinan 250101, China
-
4.
Jinan Engineering Laboratory of Human-machine Intelligent Cooperation, Jinan 250353, China
-
摘要:
針對移動機器人導航過程中無法規(guī)避大型凹型障礙物問題,該文提出一種多狀態(tài)的組合導航算法。算法按照不同的運動環(huán)境,將移動機器人的運行狀態(tài)分類為運行態(tài)、切換態(tài)、避障態(tài),同時定義了基于移動機器人運行速度和運行時間的狀態(tài)雙切換條件。當移動機器人處于運行態(tài)時,采用人工勢場法(APFM)進行導航,并實時觀測毗鄰障礙物的幾何構(gòu)型。在遭遇障礙物時,切換態(tài)用于判斷是否滿足狀態(tài)切換條件,以進入避障態(tài)執(zhí)行避障算法。避障完成后,狀態(tài)自動切換回運行態(tài)繼續(xù)執(zhí)行導航任務。多狀態(tài)的提出,可有效解決傳統(tǒng)人工勢場法在大型凹形障礙物的避障過程中存在局部震蕩的問題。基于運行速度和運行時間的雙切換條件判定算法,可實現(xiàn)多狀態(tài)間的平滑切換。實驗結(jié)果表明,該算法在解決局部震蕩問題的同時,還可降低避障時間,提升導航算法效率。
Abstract:For the problem that mobile robot can not avoid large concave obstacles during navigation, this paper proposes a multi-state integrated navigation algorithm. The algorithm classifies the running state of mobile robot into running state, switching state and obstacle avoidance state according to different moving environment, and defines the state double switching conditions based on the running speed and running time of the mobile robot. The Artificial Potential Field Method (APFM) is used to navigate and observe the geometric configuration of adjacent obstacles in real time. When encountering an obstacle, the switching state is used to determine whether the state switching condition is satisfied, and the obstacle avoidance algorithm is executed to enter the obstacle avoidance state and enter the obstacle avoidance state to implement the obstacle avoidance algorithm. After the obstacle avoidance is completed, the state automatically switches back to the running state to continue the navigation task. The proposal of multi-state can solve the problem of local oscillation of traditional artificial potential field method in the process of avoiding large concave obstacles. Furthermore, the double-switching condition determination algorithm based on running speed and running time can realize smooth switching between states and optimize the path. The experimental results show that the algorithm can not only solve the local oscillation problem, but also reduce the obstacle avoidance time and improve the efficiency of the navigation algorithm.
-
表 1 人工勢場法符號含義
符號 符號含義 符號 符號含義 ${\rm{obs}}$ 障礙物 ${\bf{X}}{\rmq7j3ldu95}$ 目標位置 ${U_{{\rm{Xd}}}}(x)$ 引力勢能 ${U_{{\rm{obs}}}}(x)$ 斥力勢能 ${U_{{\rm{art}}}}(x)$ 總勢能 ${{F}}$ 合力 ${{{F}}_{{\rm{Xd}}}}$ 吸引力 ${{F}}_{\rm{obs}}$ 排斥力 $j$ 移動機器人感知到的
周邊障礙物的個數(shù)下載: 導出CSV
表 2 A*算法符號含義
符號 符號含義 符號 符號含義 $g(\cdot )$ 從初始節(jié)點到當前移動機器人
所在節(jié)點node的啟發(fā)式評估代價$h(\cdot )$ 從當前移動機器人所在節(jié)點node到
目標節(jié)點的啟發(fā)式評估代價$(x_{\rm{start}},y_{\rm{start}})$ 初始節(jié)點坐標 $(x_{\rm{goal}},y_{\rm{goal}})$ 目標節(jié)點坐標 $(x,y)$ 移動機器人實時位置坐標 下載: 導出CSV
表 3 模型描述符號含義
符號 符號含義 符號 符號含義 $O_1$ 障礙物的左端點 $O_2$ 障礙物的右端點 $2\alpha $ 障礙物的長 $\beta $ 障礙物的寬 $v_t$ 移動機器人的實時線速度 $a$ 移動機器人在運行態(tài)時的最大速度 $\Delta d$ 移動機器人在某段時間內(nèi)的移動距離 $S_{\rm{obs}}$ 所有障礙物總面積 $S_{\rm{map}}$ 地圖面積 $\rho $ 障礙物密度 下載: 導出CSV
-
王勇臻, 陳燕, 于瑩瑩. 求解多旅行商問題的改進分組遺傳算法[J]. 電子與信息學報, 2017, 39(1): 198–205. doi: 10.11999/JEIT160211WANG Yongzhen, CHEN Yan, and YU Yingying. Improved grouping genetic algorithm for solving multiple traveling salesman problem[J]. Journal of Electronics &Information Technology, 2017, 39(1): 198–205. doi: 10.11999/JEIT160211 黃長強, 趙克新. 基于改進蟻獅算法的無人機三維航跡規(guī)劃[J]. 電子與信息學報, 2018, 40(7): 1532–1538. doi: 10.11999/JEIT170961HUANG Changqiang and ZHAO Kexin. Three dimensional path planning of UAV with improved ant lion optimizer[J]. Journal of Electronics &Information Technology, 2018, 40(7): 1532–1538. doi: 10.11999/JEIT170961 KHATIB O. Real-time obstacle avoidance for manipulators and mobile robots[J]. The International Journal of Robotics Research, 1986, 5(1): 90–98. doi: 10.1177/027836498600500106 PARK M G, JEON J H, and LEE M C. Obstacle avoidance for mobile robots using artificial potential field approach with simulated annealing[C]. 2001 IEEE International Symposium on Industrial Electronics, Pusan, South Korea, 2001: 1530–1535. doi: 10.1109/ISIE.2001.931933. 況菲, 王耀南. 基于混合人工勢場-遺傳算法的移動機器人路徑規(guī)劃仿真研究[J]. 系統(tǒng)仿真學報, 2006, 18(3): 774–777. doi: 10.16182/j.cnki.joss.2006.03.061KUANG Fei and WANG Yaonan. Robot path planning based on hybrid artificial potential field/genetic algorithm[J]. Journal of System Simulation, 2006, 18(3): 774–777. doi: 10.16182/j.cnki.joss.2006.03.061 LEE D, JEONG J, KIM Y H, et al. An improved artificial potential field method with a new point of attractive force for a mobile robot[C]. The 2nd International Conference on Robotics and Automation Engineering, Shanghai, China, 2017: 63–67. doi: 10.1109/ICRAE.2017.8291354. ROSTAMI S M H, SANGAIAH A K, WANG Jin, et al. Obstacle avoidance of mobile robots using modified artificial potential field algorithm[J]. EURASIP Journal on Wireless Communications and Networking, 2019(1): No. 70, 1–19. doi: 10.1186/s13638-019-1396-2 HART P E, NILSSON N J, and RAPHAEL B. A formal basis for the heuristic determination of minimum cost paths[J]. IEEE Transactions on Systems Science and Cybernetics, 1968, 4(2): 100–107. doi: 10.1109/TSSC.1968.300136 DECHTER R and PEARL J. Generalized best-first search strategies and the optimality of A*[J]. Journal of the ACM, 1985, 32(3): 505–536. doi: 10.1145/3828.3830 田景文, 孔垂超, 高美娟. 一種車輛路徑規(guī)劃的改進混合算法[J]. 計算機工程與應用, 2014, 50(14): 58–63. doi: 10.3778/j.issn.1002-8331.1208-0319TIAN Jingwen, KONG Chuichao, and GAO Meijuan. Improved hybrid algorithm of vehicle path planning[J]. Computer Engineering and Applications, 2014, 50(14): 58–63. doi: 10.3778/j.issn.1002-8331.1208-0319 胡中華, 潘洲, 王凱凱. 基于混合算法的動態(tài)路徑規(guī)劃[J]. 煤礦機械, 2015, 36(12): 243–245. doi: 10.13436/j.mkjx.201512103HU Zhonghua, PAN Zhou, and WANG Kaikai. Dynamic path planning based on hybrid algorithm[J]. Coal Mine Machinery, 2015, 36(12): 243–245. doi: 10.13436/j.mkjx.201512103 唐志榮, 冀杰, 吳明陽, 等. 基于改進人工勢場法的車輛路徑規(guī)劃與跟蹤[J]. 西南大學學報: 自然科學版, 2018, 40(6): 174–182. doi: 10.13718/j.cnki.xdzk.2018.06.025TANG Zhirong, JI Jie, WU Mingyang, et al. Vehicles path planning and tracking based on an improved artificial potential field method[J]. Journal of Southwest University:Natural Science Edition, 2018, 40(6): 174–182. doi: 10.13718/j.cnki.xdzk.2018.06.025 趙奇, 趙阿群. 一種基于A*算法的多徑尋由算法[J]. 電子與信息學報, 2013, 35(4): 952–957. doi: 10.3724/SP.J.1146.2012.00983ZHAO Qi and ZHAO Aqun. A multi-path routing algorithm base on A* algorithm[J]. Journal of Electronics &Information Technology, 2013, 35(4): 952–957. doi: 10.3724/SP.J.1146.2012.00983 DIJKSTRA E W. A note on two problems in connexion with graphs[J]. Numerische Mathematik, 1959, 1(1): 269–271. doi: 10.1007/BF01386390 沈文君. 基于改進人工勢場法的機器人路徑規(guī)劃算法研究[D]. [碩士論文], 暨南大學, 2009.SHEN Wenjun. Algorithm research of path planning for robot based on improved artifical potential field[D]. [Master dissertation], Jinan University, 2009. -