一種針對(duì)大型凹型障礙物的組合導(dǎo)航算法
doi: 10.11999/JEIT190179 cstr: 32379.14.JEIT190179
-
1.
齊魯工業(yè)大學(xué)(山東省科學(xué)院)電子信息工程學(xué)院(大學(xué)物理教學(xué)部) 濟(jì)南 250353
-
2.
齊魯工業(yè)大學(xué)(山東省科學(xué)院)電氣工程與自動(dòng)化學(xué)院 濟(jì)南 250353
-
3.
齊魯工業(yè)大學(xué)(山東省科學(xué)院)山東省科學(xué)院自動(dòng)化研究所 濟(jì)南 250101
-
4.
濟(jì)南市人機(jī)智能協(xié)同工程實(shí)驗(yàn)室 濟(jì)南 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
-
摘要:
針對(duì)移動(dòng)機(jī)器人導(dǎo)航過程中無法規(guī)避大型凹型障礙物問題，該文提出一種多狀態(tài)的組合導(dǎo)航算法。算法按照不同的運(yùn)動(dòng)環(huán)境，將移動(dòng)機(jī)器人的運(yùn)行狀態(tài)分類為運(yùn)行態(tài)、切換態(tài)、避障態(tài)，同時(shí)定義了基于移動(dòng)機(jī)器人運(yùn)行速度和運(yùn)行時(shí)間的狀態(tài)雙切換條件。當(dāng)移動(dòng)機(jī)器人處于運(yùn)行態(tài)時(shí)，采用人工勢(shì)場(chǎng)法(APFM)進(jìn)行導(dǎo)航，并實(shí)時(shí)觀測(cè)毗鄰障礙物的幾何構(gòu)型。在遭遇障礙物時(shí)，切換態(tài)用于判斷是否滿足狀態(tài)切換條件，以進(jìn)入避障態(tài)執(zhí)行避障算法。避障完成后，狀態(tài)自動(dòng)切換回運(yùn)行態(tài)繼續(xù)執(zhí)行導(dǎo)航任務(wù)。多狀態(tài)的提出，可有效解決傳統(tǒng)人工勢(shì)場(chǎng)法在大型凹形障礙物的避障過程中存在局部震蕩的問題?；谶\(yùn)行速度和運(yùn)行時(shí)間的雙切換條件判定算法，可實(shí)現(xiàn)多狀態(tài)間的平滑切換。實(shí)驗(yàn)結(jié)果表明，該算法在解決局部震蕩問題的同時(shí)，還可降低避障時(shí)間，提升導(dǎo)航算法效率。
-
關(guān)鍵詞:
- 組合導(dǎo)航算法 /
- 人工勢(shì)場(chǎng)法 /
- A*算法 /
- 大型凹形障礙物
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 人工勢(shì)場(chǎng)法符號(hào)含義
符號(hào) 符號(hào)含義 符號(hào) 符號(hào)含義 ${\rm{obs}}$ 障礙物 ${\bf{X}}{\rmq7j3ldu95}$ 目標(biāo)位置 ${U_{{\rm{Xd}}}}(x)$ 引力勢(shì)能 ${U_{{\rm{obs}}}}(x)$ 斥力勢(shì)能 ${U_{{\rm{art}}}}(x)$ 總勢(shì)能 ${{F}}$ 合力 ${{{F}}_{{\rm{Xd}}}}$ 吸引力 ${{F}}_{\rm{obs}}$ 排斥力 $j$ 移動(dòng)機(jī)器人感知到的
周邊障礙物的個(gè)數(shù)
下載: 導(dǎo)出CSV
表 2 A*算法符號(hào)含義
符號(hào) 符號(hào)含義 符號(hào) 符號(hào)含義 $g(\cdot )$ 從初始節(jié)點(diǎn)到當(dāng)前移動(dòng)機(jī)器人
所在節(jié)點(diǎn)node的啟發(fā)式評(píng)估代價(jià)$h(\cdot )$ 從當(dāng)前移動(dòng)機(jī)器人所在節(jié)點(diǎn)node到
目標(biāo)節(jié)點(diǎn)的啟發(fā)式評(píng)估代價(jià)$(x_{\rm{start}},y_{\rm{start}})$ 初始節(jié)點(diǎn)坐標(biāo) $(x_{\rm{goal}},y_{\rm{goal}})$ 目標(biāo)節(jié)點(diǎn)坐標(biāo) $(x,y)$ 移動(dòng)機(jī)器人實(shí)時(shí)位置坐標(biāo)
下載: 導(dǎo)出CSV
表 3 模型描述符號(hào)含義
符號(hào) 符號(hào)含義 符號(hào) 符號(hào)含義 $O_1$ 障礙物的左端點(diǎn) $O_2$ 障礙物的右端點(diǎn) $2\alpha $ 障礙物的長(zhǎng) $\beta $ 障礙物的寬 $v_t$ 移動(dòng)機(jī)器人的實(shí)時(shí)線速度 $a$ 移動(dòng)機(jī)器人在運(yùn)行態(tài)時(shí)的最大速度 $\Delta d$ 移動(dòng)機(jī)器人在某段時(shí)間內(nèi)的移動(dòng)距離 $S_{\rm{obs}}$ 所有障礙物總面積 $S_{\rm{map}}$ 地圖面積 $\rho $ 障礙物密度
下載: 導(dǎo)出CSV
表 4 算法性能比較
算法 時(shí)間(s) 路徑長(zhǎng)度(m) A*算法 22.40 1040.69 改進(jìn)人工勢(shì)場(chǎng)法[15] 無窮大 無窮大 本文組合算法 10.62 707.09
下載: 導(dǎo)出CSV
-
王勇臻, 陳燕, 于瑩瑩. 求解多旅行商問題的改進(jìn)分組遺傳算法[J]. 電子與信息學(xué)報(bào), 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 黃長(zhǎng)強(qiáng), 趙克新. 基于改進(jìn)蟻獅算法的無人機(jī)三維航跡規(guī)劃[J]. 電子與信息學(xué)報(bào), 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. 況菲, 王耀南. 基于混合人工勢(shì)場(chǎng)-遺傳算法的移動(dòng)機(jī)器人路徑規(guī)劃仿真研究[J]. 系統(tǒng)仿真學(xué)報(bào), 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ìn)混合算法[J]. 計(jì)算機(jī)工程與應(yīng)用, 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 胡中華, 潘洲, 王凱凱. 基于混合算法的動(dòng)態(tài)路徑規(guī)劃[J]. 煤礦機(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 唐志榮, 冀杰, 吳明陽, 等. 基于改進(jìn)人工勢(shì)場(chǎng)法的車輛路徑規(guī)劃與跟蹤[J]. 西南大學(xué)學(xué)報(bào): 自然科學(xué)版, 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]. 電子與信息學(xué)報(bào), 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 沈文君. 基于改進(jìn)人工勢(shì)場(chǎng)法的機(jī)器人路徑規(guī)劃算法研究[D]. [碩士論文], 暨南大學(xué), 2009.SHEN Wenjun. Algorithm research of path planning for robot based on improved artifical potential field[D]. [Master dissertation], Jinan University, 2009. -
計(jì)量
- 文章訪問數(shù): 2652
- HTML全文瀏覽量: 1325
- PDF下載量: 88
- 被引次數(shù): 0
下載:
