CN101608926B - 多层次多模态寻径导航方法 - Google Patents
多层次多模态寻径导航方法 Download PDFInfo
- Publication number
- CN101608926B CN101608926B CN2009101122541A CN200910112254A CN101608926B CN 101608926 B CN101608926 B CN 101608926B CN 2009101122541 A CN2009101122541 A CN 2009101122541A CN 200910112254 A CN200910112254 A CN 200910112254A CN 101608926 B CN101608926 B CN 101608926B
- Authority
- CN
- China
- Prior art keywords
- runway
- crossing
- track
- file
- actual track
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Fee Related
Links
- 238000000034 method Methods 0.000 title claims abstract description 32
- 230000000007 visual effect Effects 0.000 claims description 20
- 238000012800 visualization Methods 0.000 claims description 10
- 238000012545 processing Methods 0.000 claims description 6
- 239000000284 extract Substances 0.000 claims description 5
- 230000003068 static effect Effects 0.000 claims description 3
- 230000006399 behavior Effects 0.000 description 9
- 238000004458 analytical method Methods 0.000 description 8
- 238000010586 diagram Methods 0.000 description 8
- 238000013499 data model Methods 0.000 description 4
- 238000005516 engineering process Methods 0.000 description 4
- 238000005457 optimization Methods 0.000 description 4
- 238000011160 research Methods 0.000 description 4
- 238000004364 calculation method Methods 0.000 description 3
- 230000006870 function Effects 0.000 description 3
- VYMDGNCVAMGZFE-UHFFFAOYSA-N phenylbutazonum Chemical compound O=C1C(CCCC)C(=O)N(C=2C=CC=CC=2)N1C1=CC=CC=C1 VYMDGNCVAMGZFE-UHFFFAOYSA-N 0.000 description 3
- 241001156002 Anthonomus pomorum Species 0.000 description 2
- 241000239290 Araneae Species 0.000 description 2
- 241000611421 Elia Species 0.000 description 2
- 238000011960 computer-aided design Methods 0.000 description 2
- 238000011161 development Methods 0.000 description 2
- 230000018109 developmental process Effects 0.000 description 2
- 230000000694 effects Effects 0.000 description 2
- 238000013507 mapping Methods 0.000 description 2
- 230000000903 blocking effect Effects 0.000 description 1
- 230000001413 cellular effect Effects 0.000 description 1
- 238000012512 characterization method Methods 0.000 description 1
- 238000006243 chemical reaction Methods 0.000 description 1
- 230000019771 cognition Effects 0.000 description 1
- 238000004891 communication Methods 0.000 description 1
- 239000012141 concentrate Substances 0.000 description 1
- 238000000354 decomposition reaction Methods 0.000 description 1
- 238000012217 deletion Methods 0.000 description 1
- 230000037430 deletion Effects 0.000 description 1
- 238000013461 design Methods 0.000 description 1
- 230000009977 dual effect Effects 0.000 description 1
- 230000007613 environmental effect Effects 0.000 description 1
- 238000005206 flow analysis Methods 0.000 description 1
- 230000003993 interaction Effects 0.000 description 1
- 238000007726 management method Methods 0.000 description 1
- 239000003550 marker Substances 0.000 description 1
- 238000009401 outcrossing Methods 0.000 description 1
- 238000007430 reference method Methods 0.000 description 1
- 238000012216 screening Methods 0.000 description 1
- 230000011218 segmentation Effects 0.000 description 1
- 238000000926 separation method Methods 0.000 description 1
- 238000012732 spatial analysis Methods 0.000 description 1
- 238000003786 synthesis reaction Methods 0.000 description 1
Images
Landscapes
- Traffic Control Systems (AREA)
Abstract
多层次多模态寻径导航方法，涉及一种寻径导航。建立道路中心线结点表和弧段表，生成拓扑文件T1和T2，输入起点S和终点D，读取道路中心线和行车道属性数据，计算基于T1和T2的最优路径R1和R2；建立实际车道拓扑结构T3，记录物理车道ID、虚拟车道ID以及关联的起点ID和终点ID；读取实际车道属性数据，计算基于T3的最优路径R3；依据R1动态生成一定范围d1的缓冲区B1，选出B1内的建筑集L1，在2D可视化窗口表达L1，选出L1中的地标建筑集L2，在2.5D可视化窗口中表达L2，依据行驶者的坐标位置、动态调度d2的缓冲区B2，选B2内的包含L2的实时可视化地标L3，在B2内动态调入道路交通相关设施。
Description
技术领域
本发明涉及一种寻径导航，特别是涉及一种用于各种车辆出行时的多层次多模态寻径导航方法。
背景技术
寻径导航是基于位置的服务、智能交通、应急反应等诸多重要应用领域中的一项关键技术。随着城市的快速发展，大城市出现了复杂的道路网络系统和交通设施，比如高架路、地下通道、辅道、立交桥等，均呈现典型的三维特征。伴随而来的是交通管制的动态性、多样性和专门化，例如转向限制、单向通行、应急车道、限速车道等。面对如此复杂的交通环境，寻径导航的服务质量有了新的要求，特别体现为个性化和语境(personalized & contextual)。
首先，满足个性化的不同道路网络层次的路径查询。对于熟悉当地道路交通环境的用户，需要了解具体哪条车道可通行；而对于不太熟悉当地交通环境的用户，关心如何到达目的地，只需要了解哪几条街道允许通行。即多层次寻径问题。
其次，导航信息的可视化因人而异，因景而异。比如，个别用户需要逼真的三维导航场景来身临其境地感受局部环境，而其他用户需要提供整体路线指示，还有用户需要不同模式之间的切换，全面最大化场景体验。另外，不同状态下的导航内容不尽相同，比如灾害应急状况下的导航服务需要提供灾害相关的信息。即多模态导航问题。
目前，制约多层次多模态寻径导航发展的主要因素有：道路网模型表达不当、多层次寻径算法不妥、导航思路不配套。以下就上述问题作简单的分析。
(1)道路网络模型表达不当
传统寻径导航方法大多是基于二维的道路中心线，将复杂的立体交通抽象为简单的结点，用单一的弧段表达整条街道。这种描述方法显然不能够表达复杂的立体交通，特别是表达单个车道间的拓扑关系和交叉口处的复杂转向关系。近年来有相关改进方法，主要是通过非平面网络方法表达立体交通，或用转向表方法或对偶图体现交叉口处的转向限制，或用线性参考方法记录单个车道拓扑。综合看来，相关的改进方法依存的几何实体依旧是道路中心线或综合车道，可视化表达上仍停留在二维。相关的文献有：1、Fohl，Curtin，Goodchild et al.ANon-Planar，Lane-Based Navigable Data Model for ITS.7th International Symposium on SpatialData Handling，1996；2、陆锋，周成虎，万庆.基于特征的城市交通网络非平面数据模型.测绘学报，2000，29(4)：334-341；3、何桂平，赵鸿铎，姚祖康.基于线性参照系统的面向对象的立交模型.公路交通科技，2001，6：86-89；4、Jiang，Han and Chen.Modelling Turning Restrictionsin Traffic Network for Vehicle Navigation System.Symposium on geospatial theory，processing andapplications，2002；5、Winter.Modeling Costs of Turns in Route Planning.GeoInformatica，2002，6(4)：345-361；6、韩刚，蒋捷，陈军待等，车载导航系统中顾及道路转向限制的弧段Dijkstra算法.测绘学报，2002，31(4)：366-368；7、Cova and Johnson.A Network Flow Model for Lane-basedEvacuation Routing.Transportation Research Part A：Policy and Practice，2003，37(7)：579-604；8、左小清，李清泉，谢智颖.基于车道的道路数据模型.长安大学学报(自然科学版)，2004，24(2)：73-76；9、任刚，王炜，邓卫.带转向延误和限制的最短路径问题及其求解方法.东南大学学报(自然科学版)，2004，34(1)：104-108；10、Malaikrisanachalee and Adams.Lane-based Networkfor Transportation Network Flow Analysis and Inventory Management.TRR Journal of theTransportation Research Board，2005，1935：101-110；11、Li and Lin.A Trajectory-OrientedCarriageway-Based Road Network Data Model，Part 1：Background.Geo-spatiaI InformationScience，2006，9(1)：65-70。
(2)多层次寻径算法不妥
目前的多层次寻径算法主要有两种类型，一种是利用道路网固有的属性层次信息(国道、主干道、次干道和支路等)，优先选择道路等级高的路段。另一种是利用多尺度数据源自然的构建金字塔似的多级道路网结构(1∶50000，1∶10000和1∶5000等)，优先选择小比例尺路网来优化寻径效率。综合分析可以看到，这两种多层次寻径算法均不能解决“道路中心线-行车道-实际车道”这类考虑空间认知规律和推理规律的多层次寻径问题。相关文献有：12、Quek and Srikanthan.A hierarchical representation of roadway networks 7th World Congress onIntelligent Transportation Systems，2000；13、Park，Sung，Doh et al.Finding a path in thehierarchical road networks.Proceedings of 2001 IEEE Intelligent Transportation Systems，2001，936-942；14、Jagadeesh，Srikanthan and Quek.Heuristic Techniques for Accelerating HierarchicalRouting on Road Networks.IEEE Transactions on intelligent transportation system 2002，3(4)：301-309；15、陈则王，袁信.基于分层分解的一种实时车辆路径规划算法.南京航空航天大学学报，2003，35(2)：193-197；16、付梦印，李杰，邓志红.基于分层道路网络的新型路径规划算法.计算机辅助设计与图形学学报，2005，17(4)：719-722；17、陈玉敏，龚健雅，史文中.多级道路网的最优路径算法研究.武汉大学学报信息科学版，2006，31(1)：70-73)。
(3)导航思路不配套
从导航可视化角度来看，过去人们关注的焦点往往集中在两个方面：其一是满足不同交通出行方式(比如火车、公交、公路、行人等)或不同信息交互方式(语音，图像，触摸等)的导航可视化服务，即所谓的多模式导航；另一种是利用恰当的地标建筑增强导航可视化效果，即所谓的地标导航。这两种导航思路在某种程度上满足了导航服务的完整性和逼真性，但还不能解决个性化问题，特别是因人而异、因景而异的多模态导航问题。相关文献有：18、Goodchild.GIS and Transportation：Status and Challenges.GeoInformatica，2000，4(2)：127-139；19、Timpf and Heye.Complexity of routes in multi-modal wayfinding.Second InternationalConference on Geographic Information Science，2002；20、Brenner and Elias.Extracting landmarksfor car navigation systems using existing GIS databases and laser scanning.ISPRS Archives，2003，XXXIV(Part 3/W8)：17-19；21、Elias and Brenner.Automatic Generation and Application ofLandmarks in Navigation Data Sets.11th International Symposium on Spatial Data Handling，2004；22、李渊.基于语义信息的建筑尺度多模式应急路径规划.华中建筑，2007，25(3)：109-111；24、熊丽音，陆锋，陈传彬.城市多模式交通网络特征连通关系表达模型.武汉大学学报信息科学版，2008，33(4)：393-396。
国内相关专利申请，比如公开号为CN101191730的发明专利申请公开一种在汽车导航系统中检索用户兴趣点(points of interest)数据库的方法及其装置。汽车导航系统的信息检索方法包括以下步骤：为检索兴趣点数据库内必要的信息，生成有关数值型数据的通用索引和没有排序的名称的倒置文件索引的全处理步骤；判别输入的检索条件，在名称单独检索的情况下，以对上述名称的倒置文件索引为基础进行检索和输出有关信息的步骤；判别输入的检索条件，在名称单独检索以外的情况下，以上述数值型数据的通用索引为基础，进行检索和输出有关信息的步骤。
公开号为CN1724976的发明专利申请提供了导航系统的画面上按用户的要求分步骤显示画面处理状况。
尽管上述专利文献提升了寻径导航服务的个性化水平，但并不配套不同尺度应用环境(比如宏观2D、中观2.5D和微观3D)。到目前为止，还未见完整的多层次多模态寻径导航专利文献。
发明内容
本发明的目的在于提供一种主要用于各种车辆出行时的多层次多模态寻径导航方法。
本发明包括以下步骤：
1)根据道路中心线几何数据，建立道路中心线结点表和弧段表，生成拓扑文件T1，记录每个弧段ID、起始结点ID和终止结点ID；
2)根据行车道中心线几何数据和交叉口区域几何数据，生成拓扑文件T2，记录每个行车道以及交叉口区域内的连通关系；
3)输入起点S和终点D，读取道路中心线属性数据和行车道属性数据，利用Dijkstra算法分别计算基于拓扑文件T1和拓扑文件T2的最优路径R1和R2；
4)依据最优路径R2，读取与之关联的行车道数据集，建立实际车道拓扑结构T3，记录物理车道ID和虚拟车道ID，以及关联的起点ID和终点ID；
5)读取实际车道属性数据，利用Dijkstra算法计算基于实际车道拓扑结构T3的最优路径R3；
6)依据最优路径R1，动态生成一定范围d1的缓冲区B1，筛选出缓冲区B1范围内的建筑集L1，在2D可视化窗口以图示方式表达建筑集L1，提供全局导航环境；
7)调用建筑属性信息，进一步筛选出满足要求的建筑集L1中的地标建筑集L2，在2.5D可视化窗口中以轴测图模型表达地标建筑集L2，提供中观导航环境；
8)依据行驶者的坐标位置，动态调度一定范围d2的缓冲区B2，进一步筛选缓冲区B2范围内的包含地标建筑集L2的实时可视化地标建筑集L3，赋予相应纹理，并在缓冲区B2范围内动态调入道路交通相关设施，提供3D微观导航环境。
在步骤3)中，所述道路中心线属性数据包括距离、平均车速等，所述行车道属性包括距离、单向车速、交叉口延迟时间等数据。
在步骤4)中，所述实际车道属性数据包括车道通行观测时间和交叉口通行等待时间等。
在步骤7)中，所述建筑属性信息包括性质、高度等。
在步骤8)中，所述道路交通相关设施包括路灯、交通指示牌等。
所述步骤2)中，根据行车道中心线几何数据和交叉口区域几何数据，生成拓扑文件T2，记录每个行车道以及交叉口区域内的连通关系的方法包括以下步骤：
1)根据行车道几何数据，建立行车道结点表和弧段表，生成行车道局部拓扑文件T2*，记录每个行车道ID、起始结点ID和终止结点ID；
2)利用交叉口几何数据，提取其几何质心，建立交叉口处结点表，并记录交叉口关键属性信息，所述交叉口关键属性信息包括入行车道ID和出行车道ID等；
3)根据交叉口结点表和行车道局部拓扑文件T2*，新建交叉口区域拓扑文件T2#，记录交叉口区域内的连接弧段ID、起始结点ID和终止结点ID；
4)合并行车道局部拓扑文件T2*和交叉口区域拓扑文件T2#，生成拓扑文件T2，记录完整的行车道连通关系。
所述步骤4)中，依据最优路径R2，读取与之关联的行车道数据集，建立实际车道拓扑结构T3，记录物理车道ID和虚拟车道ID，以及关联的起点ID和终点ID的方法包括以下步骤：
1)读取与最优路径R2关联的行车道ID数据集，根据各个行车道ID对应的属性数据生成实际车道拓扑的基本要素，构建实际车道局部拓扑文件T3*，记录每个物理车道ID、起始结点ID和终止结点ID，所述各个行车道ID对应的属性数据包括实际车道数目等，所述实际车道拓扑的基本要素包括按行车道方向从左至右顺序编号表示实际车道属性；
2)利用实际车道的编号信息和交叉口处的转弯限制条件，补充交叉口处的虚拟车道ID，构建交叉口处的局部拓扑文件T3#，记录每个虚拟车道ID、起始结点ID和终止结点ID，所述交叉口处的转弯限制条件包括直行、左转、右转控制等；
3)合并实际车道局部拓扑文件T3*和交叉口处的局部拓扑文件T3#，生成拓扑文件T3^，记录完整的静态实际车道连通关系；
4)检测是否有存在事件及其事件性质，鼠标交互点击进行车道离散化处理，动态增加实际车道结点和实际车道弧段，在拓扑文件T3^基础上生成动态拓扑T3。
本发明以多层次道路网络模型和多尺度建筑模型为基础，依托三维GIS系统，通过语义关系自动构建实际车道、行车道和道路中心线三层网络拓扑结构，提供多层次路径优化算法，建立2D、2.5D和3D三种模态的可视化导航窗口，分别对应宏观、中观和微观的路线引导，满足个性化的语境自适应导航需求。
本发明实现的基本途径是根据给定的出发地和目的地，首先，分析道路中心线的拓扑网络，满足宏观分析和可视化需要，特别是图标模型的动态调度的需要；进而分析中观层次的行车道拓扑网络，综合考虑流向和交叉口转弯限制，为实际车道的选择提供最优路径的最小初始数据集。最后，根据关联的实际车道拓扑信息以及实际车道属性信息等，在微观层次确定实际可行的车道。在导航信息输出上，考虑到两层模态的控制：其一是应用语境模态，通过定义的“角色”(role)和“环境”(situation)来控制可视化输出的内容；其二是可视化窗口模态，通过设定的“二维地图视图”、“2.5维导航视图”和“三维行为视图”来分解导航信息，最大化输入导航的全局和局部信息。
附图说明
图1为本发明的原理示意图。
图2为本发明多层次寻径流程图。
图3为本发明多模态导航流程图。
图4为本发明道路中心线网络拓扑构建图。
图5为本发明行车道网络拓扑构建图。
图6为本发明实际车道网络拓扑构建图。
图7为本发明2D地图模态数据组织。
图8为本发明2.5D导航模态数据组织。
图9为本发明3D行为模态数据组织。
具体实施方式
以下实施例将结合附图对本发明作进一步的说明。
参见图1，本发明的技术方案原理是基于多层次三维数字地图数据库，包含多层次三维道路网络模型和多尺度三维建筑模型，在高精度车辆定位技术的支撑下，利用三维GIS系统操作平台，提供多层次路径优化和多模态路径导航，满足复杂城市环境中的个性化导航服务。针对其中的关键模块作如下说明：
1)多层次三维道路网络模型：将同一条道路，按照细节层次不同，组织为“道路中心线-行车道-实际车道”三个层次的几何与网络拓扑结构，并构建其内部关系。其中，道路中心线结构以单线抽象描述道路的几何形态，其空间位置置于道路中央；行车道以双线描述道路的几何形态，双线空间位置分别置于流向的中心；实际车道以多线描述道路的几何形态，根据功能差异细分为物理车道和虚拟车道(物理车道对应现实道路网络中的车道几何条带，虚拟车道实现物理车道在横向和交叉口区域内的连接)。
2)高精度车辆定位：以高精度车辆定位技术为支撑，提供厘米级车辆实时动态三维坐标信息，配合多层次三维道路网络模型中的车道带几何信息，能够推算出车辆在实际车道上的具体位置。
3)3DGIS人机界面：三维GIS提供数据处理和可视化的平台，特别是提供三维的空间分析功能如三维缓冲区分析和带纹理三维多尺度表达控制。利用3DGIS人机界面，能够在三维空间实时查询三维地上地下对象，提供全局和局部的可视化环境。
4)多层次路径优化：该功能是在多层次三维道路网络模型基础上，分别设计相应的路径计算方法，提供基于道路中心线的路径、行车道的路径和实际车道的路径。
5)多模态路径导航：以多层次路径优化的结果为基础，考虑多层次三维数字地图数据库，在3DGIS平台上开发2D、2.5D和3D导航可视化窗口，分别对应宏观地图模态导航、中观模型模态导航和微观行为模态导航。
6)个性化应用环境：整个寻径导航服务的外部需求，体现为导航内容的个性化选配、导航模态的选择。
参见图2，多层次寻径的算法流程包括构建三层网络拓扑结构T1，T2和T3。其中，T1和T2是独立构建，T3是在R2基础上进一步构建。多层次寻径算法流程的输入内容为三维场景、查询起点和终点，输出内容为R1，R2和R3。首先，按照预定义进程(拓扑构建1和拓扑构建2)分析道路中心线的拓扑网络(拓扑T1)和行车道拓扑网络(拓扑T2)，用预定义进程(Dijkstra寻径算法)计算道路中心线路径(路径R1)和行车道路径(路径R2)。然后，利用路径R2读取关联的局部行车道信息，按照预定义进程(拓扑构建3)分析实际车道拓扑网络(拓扑T3)，用预定义进程(Dijkstra寻径算法)计算实际车道路径(路径R3)。
参见图3，多模态导航的算法流程以R1，R2和R3为基础，通过层层数据筛选的方法，分别以2D地图视图、2.5D导航视图和3D行为视图加以表达。其中，多尺度模型数据库是本发明的重要基础，包括建筑的2D图示、2.5D轴测图和3D模型。针对路径R1，利用缓冲区分析1调用2D图示，产生分析数据(图示集L1)，并提供给2D地图视图。同时，基于L1和轴测图数据库，调入预定义进程(语义分析)，读取建筑高度属性和性质属性，筛选出地标集L2，并提供给2.5D导航视图。接着，基于L2和3D模型库，调入预定义进程(缓冲区分析2)，计算视线范围内的3D建筑集L3，并提供给3D行为视图。
本发明的实现过程采用计算机自动化处理，包括以下步骤：
步骤1，参见图4。根据道路中心线几何数据，建立道路中心线结点表和弧段表，生成拓扑文件T1，记录每个弧段ID、起始结点ID和终止结点ID。本发明中的道路中心线网络拓扑结构采用弧段-结点表存储连通的道路中心线连接关系。首先，依次读取每条道路中心线点集，建立弧段表。接着，获取中心线点集内所有点，提取首尾结点，并检查有无重复，去掉重复结点，建立结点表。然后，由结点表中结点ID和弧段表中弧段ID根据坐标位置，建立连接关系表。数据结构要求道路中心线几何连通，交叉口处是否断开根据实际情况而定。
步骤2，参见图5。根据行车道中心线几何数据和交叉口区域几何数据，生成拓扑文件T2，记录每个行车道以及交叉口区域内的连通关系。本发明的行车道几何网络并非几何连通，是通过交叉口区域实现逻辑连通。在具体实现方式上，通过引入交叉口结点的方式，在交叉口区域内建立虚拟连接弧段，建立交叉口区域内的连接关系，使整个行车道网络逻辑连通。
为了便于实施，本发明提供了步骤2的具体方式，包括以下步骤：
步骤2.1，根据行车道几何数据，建立行车道结点表和弧段表，生成行车道局部拓扑文件T2*。本发明根据行车道几何数据，依次读取每条行车道点集，建立弧段表。接着，获取行车道点集内所有点，提取首尾结点，并检查有无重复，去掉重复结点，建立行车道结点表。然后，由结点表中结点ID和弧段表中弧段ID根据坐标位置，建立连接关系表，生成行车道局部拓扑文件T2*，记录每个行车道ID、起始结点ID和终止结点ID。
步骤2.2，利用交叉口几何数据，提取其几何质心，建立交叉口处结点表，并记录交叉口关键属性信息(入行车道ID和出行车道ID)。本发明单独存储每个交叉口，以交叉口为对象组织交叉口处的行车道连通关系。在实现方式上，首先选取交叉口几何对象，然后依次点选入交叉口的行车道几何对象，确认后再依次点选出交叉口的车行道几何对象。默认情况下，系统根据行车道的数字化方向自动确认入行车道和出行车道。然后，根据交叉口对象的顶点坐标集，计算出质心坐标并记录质心ID号，生成交叉口结点表。交叉口结点表记录入行车道ID集和出行车道ID集。
步骤2.3，根据交叉口结点表和T2*，新建交叉口区域拓扑文件T2#，记录交叉口区域内的连接弧段ID、起始结点ID和终止结点ID。本发明中，交叉口内部的拓扑关系是通过自动建立行车道结点和交叉口结点之间的弧段来实现。首先，利用交叉口结点表中的入行车道ID集和出行车道ID集，找到每个行车道ID，并在T2*中增加两项记录“入交叉口ID”和“出交叉口ID”，将交叉口ID信息记录到每个行车道ID。然后，利用更新的T2*中的每个行车道ID的起点号(F_Node)和终点号(T_Node)，以及入交叉口号(In_Node)和出交叉口号(Out_Node)，新建交叉口区域内部弧段ID，弧段起点和终点分别由行车道起点号和出交叉口号，或者行车道终点和入交叉口号构成，完成交叉口区域拓扑文件T2#建立。
步骤2.4，合并T2*和T2#，生成拓扑文件T2，记录完整的行车道连通关系。该步骤是将新建交叉口区域内部弧段ID表，增加到行车道ID表中，构成一个完整的弧段-结点表。
步骤3，输入起点S和终点D，读取道路中心线属性数据(距离、平均车速)和行车道属性(距离、单向车速、交叉口延迟时间)数据，利用Dijkstra算法分别计算基于T1和T2的最优路径R1和R2。本发明利用传统Dijkstra寻径算法，计算车辆位置到目的地的最优路径。由于道路中心线网络和行车道网络数据量并不是很大，可以遍历计算的结点数目并不是很多，在算法效率上可以满足要求。在实现方式上，创建两个表(Open表和Close表)，分别保存所有已生成而未考察的结点和已访问过的结点。首先访问网络中离起始点最近且没有被检查过的点，这个点放入Open表待查。然后从Open表找出距起始点最近的点，找出这个点所有子结点，把改点放入Close表。遍历考察这个点的子结点，计算这些结点距起始点的权重值，放子结点到Open表中。最后，重复前面步骤，直到Open表为空，或找到目标点。本发明中，对于道路中心线网络，考虑的权重是距离，而对于行车道网络，由于具有交通流方向性，考虑的权重是通行时间。
步骤4，参见图6。依据R2，读取与之关联的行车道数据集，建立实际车道拓扑结构T3，记录物理车道ID和虚拟车道ID，以及关联的起点ID和终点ID。本发明中，采用启发式局部构建实际车道拓扑的方法，大大减少网络搜索空间和实际车道网络计算效率。在实现方式上，通过建立物理车道表达路段上的实际车道拓扑元素，通过建立虚拟车道表达交叉口区域内的实际车道连通关系。同时，本研究进一步考虑到实际车道的离散化处理，即在提示换车道处或当检测到临时事件(比如车道封锁)，更新实际车道拓扑。
为了便于实施，本发明提供了步骤4的具体方式，包括以下步骤：
步骤4.1，读取与R2关联的行车道ID数据集，根据各个行车道ID对应的属性数据(实际车道数目)生成实际车道拓扑的基本要素(按行车道方向从左至右顺序编号表示实际车道属性)，构建实际车道局部拓扑文件T3*，记录每个物理车道ID、起始结点ID和终止结点ID。本发明中，实际车道拓扑由行车道几何网络衍生，根据行车道属性表中记录的实际车道数目衍生出具体的实际车道拓扑要素，并按照行车道的方向自动对衍生出的行车道拓扑元素写入实际车道编号。
步骤4.2，利用实际车道的编号信息和交叉口处的转弯限制条件(直行、左转、右转控制)，补充交叉口处的虚拟车道ID，构建交叉口处的局部拓扑文件T3#，记录每个虚拟车道ID、起始结点ID和终止结点ID。本发明利用相应规则来控制交叉口处的虚拟车道自动化构建。在实现方式上，规则定义如下：
1)同一路段行车道，编号最小的实际车道之间建立虚拟车道，用为U型掉头虚拟车道
2)交叉口处入行车道的中间实际车道，与其他出行车道(除去同一路段出行车道)的中间实际车道建立虚拟车道，用为直行车道。
3)交叉口处入行车道的编号最大的实际车道，与其他出行车道(除去同一路段出行车道)的编号最大的实际车道建立虚拟车道，用为右转车道。
其中，由于每个行车道记录的实际车道数目有变化，如上规则可能产生重复虚拟车道，需要自动删除重复数据；另外，每个地区实际交通规划有特例，需要根据实际转向限制更改交通规则来自动建立虚拟车道。
步骤4.3，合并T3*和T3#，生成拓扑文件T3^，记录完整的静态实际车道连通关系。该步骤是将新建交叉口区域内部虚拟车道弧段ID表，增加到物理车道ID表中，构成一个完整的实际车道弧段-结点表。
步骤4.4，检测是否有存在事件及其事件性质，鼠标交互点击进行车道离散化处理，动态增加实际车道结点和实际车道弧段，在T3^基础上生成动态拓扑T3。本发明考虑到两种交通行为，一种是实际车道之间的换道行为，还一种是临时事件下的实际车道封闭行为。在实现方式上，第一种通过电脑自动处理，即根据行车道方向，选取2/3处为换道点，将实际车道分为提速区和换道区。第二种通过人工点击行车道几何网络，交互指定实际车道封闭的位置。两种处理方式，均在原物理车道弧段上，增加中间结点，并自动增加中间结点之间的虚拟弧段，更新为动态实际车道拓扑T3。
步骤5，读取实际车道属性数据(车道通行观测时间和交叉口通行等待时间)，利用Dijkstra算法计算基于T3最优路径R3。本发明在基于实际车道的路径计算中，考虑的权重包含了三种，其一是物理车道上的通行距离与速度，计算物理车道上通行时间；其二是物理车道之间换道行为的时间，默认设定为2s；其三是交叉口处的通行时间，根据左转，直行和右转红绿灯时间定，默认设定为30S。同样，利用Dijkstra算法计算车辆位置到目的地的最优路径，该路径的可视化表达由车道带体现。具体实现方式为：每条车道带记录行车道ID和所在车道序号，当进行车道离散化处理时，根据车道变换点和临时事件的位置，自动切分对应的车道带。然后，根据分析结果R3，读取关联的实际车道ID和序列号，再渲染对应的车道带。
步骤6，参见图7。依据R1，动态生成一定范围d1的缓冲区B1，筛选出B1范围内的建筑集L1，在2D可视化窗口以图示方式表达L1，提供全局导航环境。本发明在宏观导航可视化中采用局部二维图示方式，最大特点是图示具有明确的特征和意义，比如酒店、商场、停车道、收费站等。采用ISO19117作为图示表达的参考国际标准，按照建筑和地物类型预先设定二维图示集，通过建筑性质关联和对路径R1作缓冲区分析筛选出R1一定范围内的图示建筑。在实现方式上，R1缓冲区的半径d1默认设定为50m，整个导航环境即提供了沿着路径所有的建筑符号化表示场景。对于缓冲区范围外的建筑，仍以建筑二维几何形状作为可视化背景。
步骤7，参见图8。调用建筑属性信息(性质、高度)，进一步筛选出满足要求的L1中的地标建筑集L2，在2.5D可视化窗口中以轴测图模型表达L2，提供中观导航环境。本发明在中观导航可视化中采用局部2.5维立体模型方式，最大特点是凸显建筑高度和建筑性质。在具体实现上，采用属性数据读取的方式，即读取L1中地标建筑关联的建筑ID的高度信息和建筑性质信息，筛选出视觉突出、意义重要的建筑作为地标建筑。然后，利用高度属性拉升地标建筑并赋予特定颜色增强可视化效果。颜色定义的默认规则如下：{居住建筑：黄色；商业建筑：橙色；行政办公建筑：红色；其他建筑：蓝色}。
步骤8，参见图9。依据行驶者的坐标位置，动态调度一定范围d2的缓冲区B2，进一步筛选B2范围内的包含L2的实时三维可视化建筑集L3，赋予相应纹理，并在B2范围内动态调入道路交通相关设施(路灯、交通指示牌等)，提供3D微观导航环境。本发明在微观导航可视化中采用局部三维纹理模型方式，提供实时的环境信息，包括车辆一定视线范围内的交通标识和交通配套设施可视化。在实现方式上，以驾驶者为原点，动态计算一定范围d2的圆形缓冲区B2(默认d2取值设定为100米)，并筛选出L2内的动态可视化建筑集L3。同样，采用属性数据读取的方式，读取L3中建筑ID，从多层次建筑模型中动态调出相应的富含纹理的三维建筑模型和配套设施模型。
Claims (5)
1.多层次多模态寻径导航方法，其特征在于包括以下步骤：
1)根据道路中心线几何数据，建立道路中心线结点表和弧段表，生成拓扑文件T1，记录每个弧段ID、起始结点ID和终止结点ID；
2)根据行车道中心线几何数据和交叉口区域几何数据，生成拓扑文件T2，记录每个行车道以及交叉口区域内的连通关系，具体步骤如下：
(1)根据行车道几何数据，建立行车道结点表和弧段表，生成行车道局部拓扑文件T2*，记录每个行车道ID、起始结点ID和终止结点ID；
(2)利用交叉口几何数据，提取其几何质心，建立交叉口处结点表，并记录交叉口关键属性信息，所述交叉口关键属性信息包括入行车道ID和出行车道ID；
(3)根据交叉口结点表和行车道局部拓扑文件T2*，新建交叉口区域拓扑文件T2#，记录交叉口区域内的连接弧段ID、起始结点ID和终止结点ID；
(4)合并行车道局部拓扑文件T2*和交叉口区域拓扑文件T2#，生成拓扑文件T2，记录完整的行车道连通关系；
3)输入起点S和终点D，读取道路中心线属性数据和行车道属性数据，利用Dijkstra算法分别计算基于拓扑文件T1和拓扑文件T2的最优路径R1和R2；
4)依据最优路径R2，读取与之关联的行车道数据集，建立实际车道拓扑结构T3，记录物理车道ID和虚拟车道ID，以及关联的起点ID和终点ID，具体步骤如下：
(1)读取与最优路径R2关联的行车道ID数据集，根据各个行车道ID对应的属性数据生成实际车道拓扑的基本要素，构建实际车道局部拓扑文件T3*，记录每个物理车道ID、起始结点ID和终止结点ID，所述各个行车道ID对应的属性数据包括实际车道数目，所述实际车道拓扑的基本要素包括按行车道方向从左至右顺序编号表示实际车道属性；
(2)利用实际车道的编号信息和交叉口处的转弯限制条件，补充交叉口处的虚拟车道ID，构建交叉口处的局部拓扑文件T3#，记录每个虚拟车道ID、起始结点ID和终止结点ID，所述交叉口处的转弯限制条件包括直行、左转、右转控制；
(3)合并实际车道局部拓扑文件T3*和交叉口处的局部拓扑文件T3#，生成拓扑文件T3^，记录完整的静态实际车道连通关系；
(4)检测是否有存在事件及其事件性质，鼠标交互点击进行车道离散化处理，动态增加实际车道结点和实际车道弧段，在拓扑文件T3^基础上生成动态拓扑T3；
5)读取实际车道属性数据，利用Dijkstra算法计算基于实际车道拓扑结构T3的最优路径R3；
6)依据最优路径R1，动态生成一定范围d1的缓冲区B1，筛选出缓冲区B1范围内的建筑集L1，在2D可视化窗口以图示方式表达建筑集L1，提供全局导航环境；
7)调用建筑属性信息，进一步筛选出满足要求的建筑集L1中的地标建筑集L2，在2.5D可视化窗口中以轴测图模型表达地标建筑集L2，提供中观导航环境；
8)依据行驶者的坐标位置，动态调度一定范围d2的缓冲区B2，进一步筛选缓冲区B2范围内的包含地标建筑集L2的实时可视化地标建筑集L3，赋予相应纹理，并在缓冲区B2范围内动态调入道路交通相关设施，提供3D微观导航环境。
2.如权利要求1所述的多层次多模态寻径导航方法，其特征在于在步骤3)中，所述道路中心线属性数据包括距离、平均车速，所述行车道属性包括距离、单向车速、交叉口延迟时间。
3.如权利要求1所述的多层次多模态寻径导航方法，其特征在于在步骤4)中，所述实际车道属性数据包括车道通行观测时间和交叉口通行等待时间。
4.如权利要求1所述的多层次多模态寻径导航方法，其特征在于在步骤7)中，所述建筑属性信息包括性质、高度。
5.如权利要求1所述的多层次多模态寻径导航方法，其特征在于在步骤8)中，所述道路交通相关设施包括路灯、交通指示牌。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN2009101122541A CN101608926B (zh) | 2009-07-24 | 2009-07-24 | 多层次多模态寻径导航方法 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN2009101122541A CN101608926B (zh) | 2009-07-24 | 2009-07-24 | 多层次多模态寻径导航方法 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN101608926A CN101608926A (zh) | 2009-12-23 |
| CN101608926B true CN101608926B (zh) | 2012-02-01 |
Family
ID=41482761
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN2009101122541A Expired - Fee Related CN101608926B (zh) | 2009-07-24 | 2009-07-24 | 多层次多模态寻径导航方法 |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN101608926B (zh) |
Families Citing this family (29)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN102999646B (zh) * | 2011-09-14 | 2015-03-04 | 中国科学技术大学 | 一种微观交通仿真中车辆跟驰换道方法及系统 |
| CN103245342A (zh) * | 2012-02-06 | 2013-08-14 | 北京四维图新科技股份有限公司 | 导航实现方法及装置 |
| CN104573140A (zh) * | 2013-10-09 | 2015-04-29 | 北京军区军事训练模拟仿真研发服务中心 | 一种应用于虚拟仿真的分层动态路径规划方法 |
| CN104183016B (zh) * | 2014-09-05 | 2017-08-15 | 山东省国土测绘院 | 一种快速的2.5维建筑物模型的构建方法 |
| EP3195001B1 (en) * | 2014-11-26 | 2018-11-07 | Kone Corporation | Local navigation system |
| MX376402B (es) * | 2015-07-27 | 2025-03-07 | Nissan Motor | Dispositivo de recuperacion de ruta y metodo de recuperacion de ruta. |
| TWI584224B (zh) * | 2015-12-14 | 2017-05-21 | 台灣國際航電股份有限公司 | 三維地圖產生方法 |
| US10048688B2 (en) * | 2016-06-24 | 2018-08-14 | Qualcomm Incorporated | Dynamic lane definition |
| EP3467800B1 (en) | 2016-06-30 | 2023-10-04 | Huawei Technologies Co., Ltd. | Lane scheduling method, lane information acquisition method, vehicle and management device |
| JP7016214B2 (ja) * | 2016-11-29 | 2022-02-04 | アルパイン株式会社 | 走行可能領域設定装置および走行可能領域設定方法 |
| CN108663059A (zh) * | 2017-03-29 | 2018-10-16 | 高德信息技术有限公司 | 一种导航路径规划方法和装置 |
| CN107389079B (zh) * | 2017-07-04 | 2020-07-28 | 广州海格星航信息科技有限公司 | 高精度路径规划方法和系统 |
| CN109242230B (zh) * | 2017-07-10 | 2021-09-03 | 中国科学院沈阳自动化研究所 | 一种解决wbs排序问题的调度方法 |
| CN107817000B (zh) * | 2017-10-25 | 2020-09-08 | 广州汽车集团股份有限公司 | 无人驾驶车辆的路径规划方法、装置及计算机设备 |
| CN110110019B (zh) * | 2018-01-31 | 2021-10-29 | 北京四维图新科技股份有限公司 | 一种道路网拓扑数据更新的方法及装置 |
| CN110440818B (zh) * | 2018-05-04 | 2021-11-19 | 沈阳美行科技有限公司 | 车道矩阵模型及其构建方法、读取方法和装置 |
| CN108921943B (zh) * | 2018-06-29 | 2022-08-09 | 广东星舆科技有限公司 | 一种基于车道级高精度地图的道路三维模型建模方法 |
| CN108898862A (zh) * | 2018-07-03 | 2018-11-27 | 北京百度网讯科技有限公司 | 红绿灯路口的确定方法、装置及电子设备 |
| US10761535B2 (en) * | 2018-08-21 | 2020-09-01 | GM Global Technology Operations LLC | Intelligent vehicle navigation systems, methods, and control logic for multi-lane separation and trajectory extraction of roadway segments |
| CN111121793B (zh) * | 2018-10-31 | 2022-07-01 | 百度在线网络技术（北京）有限公司 | 用于无人驾驶的地图生成方法、装置及存储介质 |
| CN111383450B (zh) * | 2018-12-29 | 2022-06-03 | 阿里巴巴集团控股有限公司 | 一种交通路网的描述方法及装置 |
| CN111912424A (zh) * | 2019-05-09 | 2020-11-10 | 上海博泰悦臻电子设备制造有限公司 | 切换导航视角的方法、导航装置及车辆 |
| CN111846288B (zh) * | 2020-07-30 | 2021-09-24 | 北京理工大学 | 不确定环境中的小天体软着陆微分博弈控制方法 |
| CN112129306B (zh) * | 2020-09-24 | 2024-05-28 | 腾讯科技（深圳）有限公司 | 路线生成方法、装置、计算机设备和存储介质 |
| CN112216130B (zh) * | 2020-09-30 | 2022-07-26 | 长沙理工大学 | 一种车路协同环境下的应急车辆诱导方法 |
| CN112683286A (zh) * | 2021-03-16 | 2021-04-20 | 季华实验室 | 拓扑路网地图的建立方法、系统、存储介质及电子设备 |
| CN114526753B (zh) * | 2022-04-24 | 2022-07-15 | 深圳依时货拉拉科技有限公司 | 跨路口交规的关联方法及装置、计算机设备及可读存储介质 |
| CN114913144A (zh) * | 2022-05-06 | 2022-08-16 | 国交空间信息技术（北京）有限公司 | 道路中心线确定方法、装置、系统、计算设备及存储介质 |
| CN117928559B (zh) * | 2024-01-26 | 2024-08-30 | 兰州理工大学 | 一种基于强化学习的威胁规避下无人机路径规划方法 |
-
2009
- 2009-07-24 CN CN2009101122541A patent/CN101608926B/zh not_active Expired - Fee Related
Also Published As
| Publication number | Publication date |
|---|---|
| CN101608926A (zh) | 2009-12-23 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN101608926B (zh) | 多层次多模态寻径导航方法 | |
| JP3370555B2 (ja) | 歩行者情報提供システム | |
| CN104899357B (zh) | 一种基于AutoCAD平面交叉口工程图的拓扑数据提取方法 | |
| Beil et al. | CityGML and the streets of New York-A proposal for detailed street space modelling | |
| US8442767B2 (en) | Method of operating a navigation system to provide route guidance | |
| CN109976332A (zh) | 一种用于无人驾驶的高精度地图模型及自主导航系统 | |
| JP2005515513A (ja) | 概略図の生成 | |
| CN102169637A (zh) | 面向城市交通的动态路径诱导方法 | |
| US8301641B2 (en) | Method of collecting information for a geographic database for use with a navigation system | |
| Labetski et al. | A proposal for an improved transportation model in CityGML | |
| Chen et al. | Multi-scale and multi-modal GIS-T data model | |
| CN106780739A (zh) | 一种变电站智能巡检三维gis系统建立方法 | |
| Beil et al. | Combined modelling of multiple transportation infrastructure within 3D city models and its implementation in CityGML 3.0 | |
| CN116127786B (zh) | 基于城市慢行交通仿真的慢行群体安全状态测算系统和方法 | |
| CN114580796B (zh) | 一种旅游属性路径规划方法及系统 | |
| Puusepp et al. | Simulating pedestrian movement | |
| Boersma | Modelling different levels of detail of roads and intersections in 3D city models | |
| Bartelme | Geographic information systems | |
| Eldeeb et al. | Investigating walkability and bikeability in compact vs. new extensions: the case of Greater Cairo | |
| JP2002333828A (ja) | 電子地図データ | |
| Wang et al. | Low-carbon mixed traffic route recommendation for community residents based on multilayer complex traffic network | |
| Noyman et al. | TravelAgent: Generative Agents in the Built Environment | |
| Golledge | Human wayfinding | |
| Gong | Generalization of road network for an embedded car navigation system | |
| Mina et al. | Deployment model for urban guide signs based on road network topology |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| C06 | Publication | ||
| PB01 | Publication | ||
| C10 | Entry into substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| C14 | Grant of patent or utility model | ||
| GR01 | Patent grant | ||
| CF01 | Termination of patent right due to non-payment of annual fee |
Granted publication date: 20120201 Termination date: 20150724 |
|
| EXPY | Termination of patent right or utility model |