基于全向路口模型的非结构化道路重复节点路径规划

doi:10.11896/jsjkx.201200193

Computer Science ›› 2021, Vol. 48 ›› Issue (11A): 77-80.doi: 10.11896/jsjkx.201200193

• Intelligent Computing • Previous Articles Next Articles

Route Planning of Unstructured Road Including Repeat Node Based on Bidirectional Search

CAO Bo¹, CHEN Feng¹, CHENG Jing¹, LI Hua², LI Yong-le²

1 Zhenjiang Campus,Army Military Transportation University,Zhenjiang,Jiangsu 212003,China
2 Military Transportation Research Institute,Army Military Transportation University,Tianjin 300161,China

Online:2021-11-10 Published:2021-11-12
About author:CAO Bo,born in 1994,master.His main research interests include construction and application of high precision map.
LI Yong-le,born in 1984,Ph.D supervisor.His main research interests include omnidirectional vision,virtual reality and computer vision.

Abstract

Abstract: Aiming at high-precision navigation route planning around unstructured environment with repeat node,firstly,we propose a map model construction method based on all-direction intersection structure,taking the turn constraint into account.Based on the traditional navigation map,the intersection structure is refined more detailed with the navigation node set based on turn,and the turning constraint is processed to ensure that the turning constraint are met when topology relation is formed between different nodes.Then,A^* algorithm based on bidirectional search is designed according to the model to solve the route planning problem of unstructured road with repeated node,which expands the route search from the origin and the destination meanwhile until the optimal route is obtained.Finally,a comparative experiment is carried out around a field environment.Results show that route obtained based on the map model in this paper can satisfy the restriction of turning constraint and effectively solve the problem of repeat node route planning.

Key words: All-direction intersection structure, Bidirectional search A^* algorithm, Repeat node, Route planning, Turning constraint, Unstructured road

CLC Number:

TP391

CAO Bo, CHEN Feng, CHENG Jing, LI Hua, LI Yong-le. Route Planning of Unstructured Road Including Repeat Node Based on Bidirectional Search[J].Computer Science, 2021, 48(11A): 77-80.

References

[1]LIU Q,HOU P L,WANG G J,et al.Intelligent route planning on large road networks with efficiency and privacy[J].Journal of Parallel and Distributed Computing,2019,133(11):93-106.
[2]UTAMIMA A,REINERS T,ANSARIPOOR A H,et al.Op-timisation of agricultural routing planning in field logistics with evolutionary hybrid neighbourhood search[J].Biosystems Engineering,2019,184(8):166-180.
[3]YU H Z,LU F.A multi-modal multi-criteria route planningmethod based on genetic algorithm[J].Acta Geodaetica et Cartographica Sinica,2014,43(1):89-96.
[4]GUO C Z,MEGURO J,KOJIMA Y,et al.Automatic lane-level map generation for advanced driver assistance systems using low-cost sensors[C]//2014 IEEE International Conference on Robotics and Automation.Hong Kong,2014:3975-3982.
[5]JIANG K,YANG D G,LIU C R,et al.A flexible multi-layer map model designed for lane-level route planning in autonomous vehicles[J].Engineering,2019,5(2):305-318.
[6]DENG Y,CHEN Y X,ZHANG Y J,et al.Fuzzy Dijkstra algorithm for shortest path problem under uncertain environment[J].Applied Soft Computing,2012,12(3):1231-1237.
[7]ZHENG N B,LU G,LI Q Q,et al.The adaption of A^* algorithm for least-time paths in time-dependent transportation networks with turn delays[J].Acta Geodaetica et Cartographica Sinica,2019,5(2):93-100.
[8]QIN F,WU J,ZHANG X F,et al.Improved Search Algorithm Based on A^* for Bidirectional Preprocessing[J].Computer Systems & Applications,2019,28(5):95-101.
[9]XIAO P,ZHOU Z F,ZHAO Y.Discussion on uninterruptednavigation of agricultural machinery based on SINS/GNSS[J].Journal of Navigation and Positioning,2019,7(1):33-37.
[10]CHEN H Y,ZHANG Y.An Overview of Research on Military Unmanned Ground Vehicles[J].Acta Armamentarii,2014,35(10):1696-1706.
[11]LI Z F,YANG Y J,WANG X.Rule based shortest path query algorithm[J].Journal of Software,2019,30(3):515-536.
[12]GUO X Y,LUO X.Global Path Search based on A^* Algorithm[C]//International Conference on Transportation & Logistics,Information & Communication,Smart City (TLICSC 2018).Chengdu,China,2018:369-374.
[13]REN T Z,ZHOU R,XIA J,et al.Three-dimensional path planning of UAV based on an improved A^* algorithm[C]//2016 IEEE Chinese Guidance,Navigation and Control Conference.Nanjing,China,2016:140-145.
[14]ARTIGUES C,HUGUET M J,GUEYE F,et al.State-based accelerations and bidirectional search for bi-objective multi-modal shortest paths[J].Transportation Research Part C:Emerging Technologies,2013,27(1):233-259.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

Comments

Recommended 0

No Suggested Reading articles found!

Route Planning of Unstructured Road Including Repeat Node Based on Bidirectional Search

PDF (PC)

Abstract

Cite this article

share this article

References

Related Articles 6

Metrics

Comments

Recommended 0

[1]	YANG Hao-xiong, GAO Jing, SHAO En-lu. Vehicle Routing Problem with Time Window of Takeaway Food ConsideringOne-order-multi-product Order Delivery [J]. Computer Science, 2022, 49(6A): 191-198.
[2]	SHEN Biao, SHEN Li-wei, LI Yi. Dynamic Task Scheduling Method for Space Crowdsourcing [J]. Computer Science, 2022, 49(2): 231-240.
[3]	HU Jie, LAN Yu-bin, OUYANG Fan. Anti-collision Route Planning of UAVs for Charging Ground WSN [J]. Computer Science, 2019, 46(1): 162-168.
[4]	WANG Yan-qing,XIN Ke-jun,CHEN De-yun and WU Jian. Road Edge Detection Based on Heuristic Probabilistic Hough Transform [J]. Computer Science, 2013, 40(9): 279-283.
[5]	YU Ling-li,JIAO Ji-le,CAI Zi-xing. Multi-robot Mission Planning Algorithm and its System Implementation [J]. Computer Science, 2010, 37(6): 252-255.
[6]	GUO Jin-chao,HUANG Xin-han,WANG Yan-feng,CUI Guang-zhao. Online Route Planning Based on Quantum Particle Swarm Optimization [J]. Computer Science, 2009, 36(7): 237-239.