没有合适的资源?快使用搜索试试~ 我知道了~
首页Matching GPS observations to locations on a digital map
Matching GPS observations to locations on a digital map
需积分: 9 17 下载量 89 浏览量
更新于2023-06-01
评论
收藏 513KB PDF 举报
GREENFELDJS.Matching GPS Observations to Locations on a Digital Map [C] //Transportation Research Board 81st Annual Meeting .Washington D.C:[s.n],2002.
资源详情
资源评论
资源推荐
Matching GPS Observations to Locations on a Digital Map.
Joshua S. Greenfeld
Department of Civil and Environmental Engineering
New Jersey Institute of Technology
Newark, NJ 07102
Greenfeld@adm.njit.edu
ABSTRACT
GPS based navigation and route guidance systems are becoming increasingly popular among bus operators,
fleet managers and travelers. To provide this functionality, one has to have a GPS receiver, a digital map of
the traveled network and software that can associate (match) the user’s position with a location on the
digital map. Matching the user’s location has to be done even when the GPS location and the underlying
digital map have inaccuracies and errors.
There are several approaches for solving this map matching task. Some only match the user’s location to
the nearest street node while others are able to locate the user at specific location on the traveled street
segment. In this paper a topologically based matching procedure is presented. The procedure was tested
with low quality GPS data to assess its robustness. The performance of the algorithms was found to
produce outstanding results.
Keywords: Global Positioning System (GPS), Map Matching, Route Guidance, and Navigation.
INTRODUCTION
The proliferation of handheld and dashboard mounted traveler guidance systems with navigation software
and map databases are changing the way people travel to and arrive at their desired destinations.
Contemporary navigation systems provide not only a visual map and a current location of the travelers, but
also directions for the quickest route to user selected destinations. These navigation systems, sometimes
referred to as Personal Navigation Assistants (PNAs), are installed in rental cars and delivery fleets, and are
now available as an optional accessory in several new car models. Other PNAs are portable systems that
are based on either a notebook computer or on a handheld Personal Digital Assistants (PDA) computer.
PNAs are also available for off-the-road activities such as hiking, treasure hunting and other recreational
endeavors. Location aspects of this type of application will not be discussed in this paper.
To provide route guidance it is necessary to have two essential components: a digital map and a device to
locate the user. In essence, there are three different ways to determine the user’s location (1). The first is to
use some form of dead reckoning (DR) system in which the user’s speed and direction of movement are
continuously used to update her/his location (2). Many DR systems use a compass and/or a gyro system to
augment the determination of the absolute heading. The biggest problem with dead reckoning is that it is a
relative positioning scheme. This means that the absolute positioning error grows proportionally with the
distance traveled. Therefore, in lengthy trips DR will produce poor positioning.
The second method to determine the user’s location is to use some form of ground-based (Terrestrial)
Radio Frequency or beacon that broadcasts its location to nearby users (3). The received signals are used to
triangulate the position of the user. This system is an absolute scheme, thus the accuracy does not degrade
with time. However, the usage of such a system is limited to areas that are within visibility of the radio
towers emitting the broadcast signals. Usage of such a system is not commonly available to the general
public.
The third method to determine the user’s location is to use some form of radio/satellite positioning system
such as the Global Positioning System (GPS) (4). GPS signals and other transmitted information are
received by the PNA and are used to compute the user’s location. GPS based location devices are by far the
most popular and least expensive system for determining the user’s location. Therefore, henceforth, GPS
will be referred to as the default locating device. GPS can provide not only a position in terms of
coordinates but also speed and direction. In this paper only GPS derived coordinates will be considered to
make the algorithm applicable to other locating devices that do not provide speed and heading information.
The second element necessary to provide route guidance is a digital map. The map offers the users a spatial
reference for their location. It allows users to associate their observed position with a physical location in
the real world. For a PNA to be effective, the location indicated on the digital map should correspond to the
actual position of the user. If both the digital map and the GPS location were perfectly accurate this would
have been a straightforward task. All one has to do is to snap the location obtained from the GPS to the
street network. However, GPS can have locational errors and the digital map can have not only positional
error but suffers from incomplete information such as missing street segments, etc. To make the PNA
function effectively one should improve the accuracies of the map (see (5) and (6)) and develop algorithms
that are capable of determining the correct user location even with inaccurate map/network data.
Map-matching algorithms are used to reconcile inaccurate locational data with an inaccurate map/network
data. The necessary sophistication of the map-matching algorithms depends on the nature of the application
and the available data. There are three complexity levels that a map-matching algorithm has to resolve. The
most straightforward algorithm is needed when the user travels on a fixed network. For example, a bus
traveling on known street segments, thus, all that is needed is to locate the bus on one of the street segments
that makes up the bus route. That is, the search domain for a street segment as a match candidate is very
limited.
A second level of map-matching algorithms is needed when the user inputs a destination and the PNA
determines a suggested traveling route. In this application, the algorithm assumes that the user follows the
suggested route and matching is performed to that route. If the user deviates from the suggested route, the
system detects a large discrepancy between the GPS location and the matched location. Normally in such
cases, a new route and subsequently a new match are computed. The main drawback of using “known
route” information is that it can result in an incorrect match if the user deviates only slightly from his/her
“known route”. For example, if the user elects to travel on a nearby parallel street, most of these algorithms
will determine that the user is traveling on the “known route”. Detecting this type of a mistake could be
very difficult.
The third and most general map-matching algorithm does not assume any knowledge or any other
information regarding the expected location of the user. It uses only coordinates such as x,y or Latitude,
Longitude, and the relevant street network to locate the user. In this paper only the general map-matching
algorithm will be discussed.
In the next section, a formal definition of the map-matching problem is given. Next, some prior approaches
for solving the map-matching problem are reviewed and discussed. Some of these approaches are based
only on geometric information (e.g. nearest node) while others are based on statistical (e.g. (8)) and
topological analysis (e.g. consistency with prior matches). In the given review only algorithms that use
geometric and topological are discussed. Our approach/algorithm for solving the problem is subsequently
described. Finally, conclusions and possible future research directions are outlined.
PROBLEM STATEMENT (FOLLOWING (1))
A vehicle (or a person) is moving along a finite system (or set) of streets,
N . A location device such as
GPS provides an estimate for the vehicle’s location at a finite number of points in time, denoted by
{0,1,…,t }. The vehicle’s actual location at time t is denoted by
t
P
and the estimate is denoted by
t
P
. The
goal is to determine the street in N that contains
t
P
. That is, to determine the street that the vehicle is on
at time, t. In addition, the location of the vehicle relative to the end points of the street is also to be
determined
The street system,
N , is virtually never known exactly. Instead, a network representation, N, of N is
constructed using various mapping techniques. As illustrated in Figure 1, N, consists of a set of curves in
R
2
, each of which is called an arc. Each arc is assumed to be piecewise linear. Hence, arc A
∈
N can be
completely characterized by a finite sequence of points (A
0
, A
1
,…, A
n
). A
0
and A
n
, the endpoints the of the
line segment A, are referred to as nodes while A
1
, A
2
,…, A
n-1
are referred to as vertices or shape points. A
node is an end point at which an arc terminates or begins while a shape point is used to show the geometry
of the arc. A node can be a transition point from one arc to another (e.g., corresponding to an intersection in
the street system) or a terminal (e.g., corresponding to a dead-end in the street system) point in the network.
The Person’s Actual Location
The Estimated Location
The Map-Matched Location
The Set of (Actual) Streets The Set of (Estimated) Arcs
Figure 1: The Map-Matching Problem
The goal of the map matching problem is to match the estimated location, P
t
, with an arc, A in the “map”,
N, and then to determine the street, A
i
N∈ , that corresponds to the vehicle’s actual location. In some
applications such as matching the location of the bus to a bus stop, it is necessary to determine the position
on A
i
that best corresponds to
t
P
. An assumption that we have to make here is that there is a one-to-one
correspondence between the actual street network
N and the map network N, otherwise
t
P
cannot be
correctly mapped into N.
MAP MATCHING ALGORITHMS
It is worthy to distinguish between map-matching methods that use some known facts about the expected
route of the user and methods that use no such information. Knowing the user’s route can make the map-
matching task easier since the search for the arc A
i
is very much constrained by the known route. For
example, matching the location of a bus along its route is a relatively easy task since the bus is expected to
follow a fixed set of arcs in a predetermined sequence. Similarly, PNDs that compute the users route to
his/her destination can use this information to narrow the matchable search space to the suggested route.
However, confining the search space to only “expected to be traveled” arcs is not always a good idea,
especially in the latter case. The bus or the PND user could intentionally or unintentionally deviate from
their routes. Various circumstances such as bad traffic conditions or inaccessibility of a given street
segment could force them to travel on an alternative route. Therefore, a more general map-matching
algorithm has to be developed to augment such circumstances.
It is also customary to distinguish between map-matching methods that use only geometric information (7)
and those using topological information as well (1). When using only geometric information, one makes
use only of the “shape” of the arcs and not of the way in which they are “connected”. When using
剩余12页未读,继续阅读
河柚
- 粉丝: 2
- 资源: 14
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- zigbee-cluster-library-specification
- JSBSim Reference Manual
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0