Updating road maps

Patent metadata

Field	Value
Publication number	US-9816823-B2
Application number	US-201313842318-A
Country	US
Kind code	B2
Filing date	Mar 15, 2013
Priority date	Mar 15, 2013
Publication date	Nov 14, 2017
Grant date	Nov 14, 2017

Abstract

A technique for updating road maps is disclosed. A number of GPS traces can be matched with a number of roads in a map. Matched GPS traces may be processed by a matched segment module to produce proposed changes to the map. The map can be updated using a map updating module based on the proposed changes from the matched segment module. Unmatched GPS traces may be processed by an unmatched segment module to produce proposed changes to the map. The map can be updated using a map updating module based on the proposed changes from the unmatched segment module. The proposed changes to the map may include metadata defining new roads in the map, new intersections in the map, updates to turn restrictions in the map, updates to the allowable directional traffic flow on the roads within the map, updates to road closures in the map.

First claim

What is claimed is:

1. A system for updating road maps, comprising:
a processor;
a database, comprising data describing a number of roads;
a map matching module configured to match a number of GPS traces with a number of roads;
a matched segment module configured to process GPS traces that are matched to a subset of the number of roads;
an unmatched segment module configured to process GPS traces that are unmatched with a road among the number of roads; and
a map updating module configured to update a number of roads based on proposed changes presented by the matched segment module and the unmatched segment module;
in which the map matching module is further configured to:
partition the number of roads into a number of disjoint sections with the map matching module treating each of the number of roads as bi-directional;
determine, based on a percentage of GPS traces in each direction along a disjoint section among the number of disjoint sections, the possible directional flow of traffic; and
propose a change to the metadata in the database describing the allowable directional flow of traffic;
in which, where it has been determined that a section within the number of sections is a one-way directional flow of traffic, the system is configured to imply one-way directional flow of traffic constraints on other sections within the number of sections.

2. The system of claim 1 , in which the unmatched segment module is further configured to:
cluster the unmatched GPS traces;
select a cluster of unmatched GPS traces having at least a threshold number of GPS traces;
produce a single road geometry for a cluster of unmatched GPS traces using a centerline fitting procedure, the single road geometry describing a new road not described in the database;
determine a connection point for the single road geometry with an existing road within the database; and
provide a proposed update to the map updating module.

3. The system of claim 1 , in which the map updating module is further configured to notify a user of the system when the proposed change from the matched segment module, the unmatched segment module, or a combination thereof is produced and request confirmation from the user to update the database.

4. The system of claim 1 , in which the map matching module is further configured to:
receive a GPS trace that traverses a first and second road among the number of roads in which the first and second roads are not connected in the database and the traversal from the first to the second road indicates a divergence from the first road;
in which the divergence is resolved by matching subsequent GPS points to the second road and ignoring the connectivity to the first road after a first distance threshold has been exceeded from a last known matched GPS point on the first road;
determine that a discontinuity resulting from the divergence in the map matching process exists based on whether the first of the subsequent GPS points to the second road being matched with the second road is within a second threshold distance from the last known matched GPS point on the first road;
create metadata describing a missing intersection; and
provide a proposed update to the map updating module describing the missing intersection after at least a threshold number of discontinuities have been determined to exist.

5. The system of claim 4 , in which the geometry of the missing intersection is determined by either:
selecting the point of intersection of the first and second roads if the road geometries intersect within a threshold distance to the discontinuity; or
selecting the point of intersection as being the closest point between the first and second road within a threshold distance to the discontinuity if the geometry defining the first and second roads does not intersect.

6. The system of claim 4 , in which the map matching module is configured to observe metadata defining turn restrictions in the database and in which the metadata defining turn restrictions is updated after a threshold number of discontinuities are determined to exist in the metadata.

7. The system of claim 1 , in which the partitioning the number of roads into a number of disjointed sections further comprises maintaining a number of road sections as joined together to form a single section where the intersections between the road sections provide no other path for traffic to travel.

8. The system of claim 1 , in which the matched segment module is further configured to produce metadata associated with a road describing whether the road is closed for traffic by:
partitioning each road into disjointed, single-direction paths with each path describing an allowed directional traffic flow for that road;
setting each path to a training mode and receiving GPS traces describing travel along that path;
updating usage metadata associated with each path until a threshold number of GPS traces are received to determine usual traffic flow of any path; and
providing a proposed update to the map updating module describing the metadata associated with a path as indicating the path as closed when the number of GPS traces within a period of time falls below a threshold.

9. The system of claim 8 , in which the metadata associated with a road further describes roads that are closed to a type of vehicle based on:
whether, during the training mode, the GPS traces describing travel along that path indicates that a threshold number of GPS traces have not been received for that type of vehicle; and
in which the road is marked closed to that type of vehicle when it is determined that the threshold is not met.

10. The system of claim 1 , in which the matched segment module is further configured to produce metadata associated with a road describing turn restrictions at a traffic intersection by:
partitioning the number of roads into disjointed, single-direction sections with each section describing turn options available at the intersection of multiple sections;
setting each intersection to a training mode and receiving GPS traces describing travel through the intersection;
updating usage metadata associated with each intersection until a threshold number of GPS traces are received to determine usual traffic flow of any section;
proposing a change to the metadata to the map updating module describing turn restrictions at a traffic intersection based on the updated usage data; and
providing a proposed update to the map updating module describing the metadata associated with a section as indicating the section is closed when the number of GPS traces within a period of time falls below a threshold.

11. A method of updating a road map on a GPS device comprising:
with a processor:
matching a number of GPS traces to a number of roads within a map database with a map matching module;
processing GPS traces that are matched to a subset of the number of roads with a matched segment module;
processing GPS traces that are unmatched with the roads with an unmatched segment module; and
providing, at a map updating module, a proposed change based on processed GPS traces received from the matched and unmatched segment modules;
receiving a GPS trace that traverses a first and second road among the number of roads in which the first and second roads are not connected in the map database and the traversal from the first to the second road indicates a divergence from the first road;

in which the divergence is resolved by matching subsequent GPS points to the second road and ignoring the connectivity to the first road after a first distance threshold has been exceeded from a last known matched GPS point on the first road.

12. The met

Assignees

• Hewlett Packard Development Co Lp
• Hewlett Packard Entpr Dev Lp

Inventors

• Wang Yin
• Forman George
• Liu Xuemei

Classifications

• G01C21/32 Primary

  Structuring or formatting of map data · CPC title

• G06F19/10

  Physics · mapped topic

• G06F17/30

  Physics · mapped topic

• G01C21/3617

  using user history, behaviour, conditions or preferences, e.g. predicted or inferred from previous use or current movement · CPC title

• G16B99/00

  Subject matter not provided for in other groups of this subclass · CPC title