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

doi:10.11896/jsjkx.201200193

计算机科学 ›› 2021, Vol. 48 ›› Issue (11A): 77-80.doi: 10.11896/jsjkx.201200193

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

曹波¹, 陈锋¹, 成静¹, 李华², 李永乐²

1 陆军军事交通学院镇江校区江苏镇江212003
2 陆军军事交通学院军事交通运输研究所天津300161

出版日期:2021-11-10 发布日期:2021-11-12
通讯作者: 李永乐(liyongle1984@163.com)
作者简介:1509968341@qq.com
基金资助:
军队重点学科专业建设项目-智能无人系统关键技术前沿跟踪研究

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

摘要： 针对非结构化道路重复节点的全局导航路径规划问题,首先提出了一种基于全向路口结构并满足转向约束的地图模型构建方法,在传统导航地图的基础上对路口结构进行细化,以转向为基本单元设置导航节点,并进行转向约束处理,确保不同节点形成拓扑关系时满足转向约束;然后,根据所构建的模型设计了基于双向搜索的A^*算法,分别从起点和终点展开路径搜索,直至获取最优路径;最后,在某野外实验场环境中展开对比实验,结果表明,基于所提地图模型所得的全局路径满足转向约束要求,且能够有效解决重复节点的路径规划问题。

关键词: 非结构化道路, 全局路径规划, 全向路口结构, 双向搜索A^*算法, 重复节点, 转向约束

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

中图分类号:

TP391

曹波, 陈锋, 成静, 李华, 李永乐. 基于全向路口模型的非结构化道路重复节点路径规划[J]. 计算机科学, 2021, 48(11A): 77-80. https://doi.org/10.11896/jsjkx.201200193

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. https://doi.org/10.11896/jsjkx.201200193

参考文献

[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

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

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

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 4

Metrics

本文评价

推荐阅读 0

[1]	王梓强, 胡晓光, 李晓筱, 杜卓群. 移动机器人全局路径规划算法综述 Overview of Global Path Planning Algorithms for Mobile Robots 计算机科学, 2021, 48(10): 19-29. https://doi.org/10.11896/jsjkx.200700114
[2]	王燕清,辛柯俊,陈德运,吴剑. 基于启发式概率Hough变换的道路边缘检测方法 Road Edge Detection Based on Heuristic Probabilistic Hough Transform 计算机科学, 2013, 40(9): 279-283.
[3]	庄佳园,万磊,廖煌雷,孙寒冰. 基于电子海图的水面无人艇全局路径规划研究 Global Path Planning of Unmanned Surface Vehicle Based on Electronic Chart 计算机科学, 2011, 38(9): 211-214.
[4]	周菁,戴冠中,蔡晓妍. 基于蚁群系统的机器人全局最优路径规划的研究与仿真 Research and Simulating of Global Optimal Path Planning of Mobile Robot Based on Ant Colony System 计算机科学, 2010, 37(5): 171-174.