ENPM 661 Project 5: Highway Hierarchies
Rene Jacques and Zachary Zimits
Abstract—This paper is an attempt to implement
Highway Hierarchy optimization on a Dijkstra search
algorithm. Two different methods of neighborhood
generation were attempted with the authors choosing to
go forward with the method that defined neighborhoods
based on geometry instead of the amount of nodes like
in previous papers. While this method did not return
the optimal path it was able to decrease the calculation
time 20 times. The testing for this project utilizes Open
Street Map (OSM) data from around the Washington
DC area (DMV). This data was initially accessed and
processed with the OSMnx python library.
Keywords—planning, highway hierarchy, Open Source
Map, OSM, road network, graph, route planning, dijk-
stra, neighborhoods
I. INTRODUCTION
There are many levels of planning used when creating
autonomous vehicles, from the trajectory of the vehicle in
its lane to the higher-level planning from the departure point
(A) to the destination point (B). This higher-level planning
will be referred to as route planning for the remainder of this
paper. In route planning nodes represent intersections and
the paths between them are edges. This can pose a problem
for certain search algorithms. When trying to find the path
between two points in a road network the search complexity
can expand exponentially with the distance between the two
points when using Dijkstra algorithm. to combat this issue
several techniques have been developed to simplify the plan-
ning problem and to speed up computation times. [3] One
such algorithm is Highway Hierarchies (HH). The purpose of
the Highway Hierarchy optimization is to recompute certain
portions of the map so they can be generalized as a single
node. This way the algorithm only has to do a classical
heuristic search in close proximity to the start and end nodes.
[1]
II. METHOD
A. Highway Hierarchy Structure
Highway hierarchies serve to abstract a map composed of
nodes and edges into a smaller map with less nodes where
each nodes represents a set of nodes from the original map.
As many new maps as are needed or desired can be created
to abstract the map further, resulting in several layers of
maps that can be searched to find optimal paths. Each of
these layers has less nodes than the layer preceding it,
meaning that higher level maps can be searched faster than
any lower level map.
The edges between each node in each map are composed
of the roads that form the shortest path with the least cost
between the entrance points of each node. This is shown in
(1) where the path between the small red and blue nodes
represents the edges between the larger nodes (shown as
the shaded red and blue regions). Two nodes are connected
Fig. 1. Representation of HH search process. [6]
through their shared edge by entrances (sometimes refereed
to as exits the terms are interchangeable), which are nodes
from the original map that link the roads that form the
shared edge. The larger nodes may have any number of
entrances. The larger nodes also contain the shortest paths
between each entrance and the other entrances within
the node, enabling fast pathing once any search has been
completed.
B. OpenStreetMap Map Processing
The data used to construct the base map is obtained from
OpenStreetMap (OSM), an open set of map data that is
community built. The map data can be accessed directly
from the OSM website or by using their API. The python
library we used to access the OSM data is OSMnx[7], a
custom module designed to make accessing and plotting
OSM data easy and efficient. OSMnx allows the user to
access map data through either longitude and latitude or
by using street addresses and place names. We specified a
bounding box defined by the two points in table I to obtain
(2) from OSM using OSMnx. The nodes and edges as
TABLE I
BOUNDING BOX POINTS
Longitude Latitude (deg)
39.05 -76.96
38.92 -77.05
defined by OSMnx were then extracted in order to create a
下载后可阅读完整内容，剩余7页未读，立即下载
toly_23
- 粉丝: 0
- 资源: 4
我的内容管理
展开
最新资源
- 李兴华Java基础教程：从入门到精通
- U盘与硬盘启动安装教程：从菜鸟到专家
- C++面试宝典：动态内存管理与继承解析
- C++ STL源码深度解析：专家级剖析与关键技术
- C/C++调用DOS命令实战指南
- 神经网络补偿的多传感器航迹融合技术
- GIS中的大地坐标系与椭球体解析
- 海思Hi3515 H.264编解码处理器用户手册
- Oracle基础练习题与解答
- 谷歌地球3D建筑筛选新流程详解
- CFO与CIO携手：数据管理与企业增值的战略
- Eclipse IDE基础教程：从入门到精通
- Shell脚本专家宝典：全面学习与资源指南
- Tomcat安装指南：附带JDK配置步骤
- NA3003A电子水准仪数据格式解析与转换研究
- 自动化专业英语词汇精华：必备术语集锦
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
