Map-matching by dual-level heuristic search

Patent metadata

Field	Value
Publication number	US-2016356608-A1
Application number	US-201514731529-A
Country	US
Kind code	A1
Filing date	Jun 5, 2015
Priority date	Jun 5, 2015
Publication date	Dec 8, 2016
Grant date	—

Abstract

In one embodiment, a computer-implemented method includes receiving a global positioning system (GPS) location of a mobile device. Two or more road locations are determined as possible locations corresponding to the GPS location in a physical network of a set of roads. A first portion of a virtual network is built, by a computer processor, by expanding the virtual network from a node representing a prior road location to the two or more candidate road locations. A first candidate road location is selected as a current road location from among the two or more candidate road locations. A route of the mobile device is identified as including the prior road location and the first candidate road location. At least one of the two or more candidate road locations not selected as the current road location is excluded from future building of the virtual network. The virtual network is built dynamically.

First claim

What is claimed is:

1 . A computer-implemented method, comprising:
receiving a global positioning system (GPS) location of a mobile device; determining two or more road locations as possible locations corresponding to the GPS location in a physical network of a set of roads; building, by a computer processor, a first portion of a virtual network by expanding the virtual network from a node representing a prior road location to the two or more candidate road locations; selecting as a current road location a first candidate road location from among the two or more candidate road locations; identifying a route of the mobile device as including the prior road location and the first candidate road location; and excluding from future building of the virtual network at least one of the two or more candidate road locations not selected as the current road location, wherein the virtual network is built dynamically.

2 . The method of claim 1 , wherein each node in the virtual network represents a corresponding candidate road location, and wherein a path through the virtual network represents the route of the mobile device through the physical network.

3 . The method of claim 1 , wherein selecting as the current road location the first candidate road location comprises applying a cost function to each of the two or more candidate road locations.

4 . The method of claim 3 , wherein the cost function considers one or more spatial constraints of the physical network of the set of roads.

5 . The method of claim 1 , wherein the building and the selecting comprise performing a dual-level heuristic search.

6 . The method of claim 1 , further comprising backtracking through the virtual network to change the selection of the first candidate road location, responsive to selection criteria not being met for a later set of candidate road locations.

7 . The method of claim 6 , wherein the selection criteria require that a value of the cost function exceed a selection threshold.

8 . A system comprising:
a memory; and one or more computer processors, communicatively coupled to the memory, the one or more processors configured to:
receive a global positioning system (GPS) location of a mobile device;
determine two or more road locations as possible locations corresponding to the GPS location in a physical network of a set of roads;
build a first portion of a virtual network by expanding the virtual network from a node representing a prior road location to the two or more candidate road locations;
select as a current road location a first candidate road location from among the two or more candidate road locations;
identify a route of the mobile device as including the prior road location and the first candidate road location; and
exclude from future building of the virtual network at least one of the two or more candidate road locations not selected as the current road location, wherein the virtual network is built dynamically.

9 . The system of claim 8 , wherein each node in the virtual network represents a corresponding candidate road location, and wherein a path through the virtual network represents the route of the mobile device through the physical network.

10 . The system of claim 8 , wherein, to select as the current road location the first candidate road location, the one or more computer processors are further configured to apply a cost function to each of the two or more candidate road locations.

11 . The system of claim 10 , wherein the cost function considers one or more spatial constraints of the physical network of the set of roads.

12 . The system of claim 8 , wherein, to perform the build and the select, the one or more computer processors are further configured to perform a dual-level heuristic search.

13 . The system of claim 8 , wherein the one or more computer processors are further configured to backtrack through the virtual network to change the selection of the first candidate road location, responsive to selection criteria not being met for a later set of candidate road locations.

14 . The system of claim 13 , wherein the selection criteria require that a value of the cost function exceed a selection threshold.

15 . A computer program product for map-matching, the computer program product comprising a computer readable storage medium having program instructions embodied therewith, the program instructions executable by a processor to cause the processor to perform a method comprising:
receiving a global positioning system (GPS) location of a mobile device; determining two or more road locations as possible locations corresponding to the GPS location in a physical network of a set of roads; building a first portion of a virtual network by expanding the virtual network from a node representing a prior road location to the two or more candidate road locations; selecting as a current road location a first candidate road location from among the two or more candidate road locations; identifying a route of the mobile device as including the prior road location and the first candidate road location; and excluding from future building of the virtual network at least one of the two or more candidate road locations not selected as the current road location, wherein the virtual network is built dynamically.

16 . The computer program product of claim 15 , wherein each node in the virtual network represents a corresponding candidate road location, and wherein a path through the virtual network represents a route of the mobile device through the physical network.

17 . The computer program product of claim 15 , wherein selecting as the current road location the first candidate road location comprises applying a cost function to each of the two or more candidate road locations, wherein the cost function considers one or more spatial constraints of the physical network of the set of roads.

18 . The computer program product of claim 15 , wherein the building and the selecting comprise performing a dual-level heuristic search.

19 . The computer program product of claim 15 , the method further comprising backtracking through the virtual network to change the selection of the first candidate road location, responsive to selection criteria not being met for a later set of candidate road locations.

20 . The computer program product of claim 19 , wherein the selection criteria require that a value of the cost function exceed a selection threshold.

Assignees

• IBM

Inventors

• Dong Wei Shan
• Duan Ning
• Gao Peng
• Ma Chun Yang
• Zhang Xin

Classifications

• G01C21/30 Primary

  Map- or contour-matching · CPC title

• G01S19/42

  Determining position · CPC title

• G01S19/50

  whereby the position solution is constrained to lie upon a particular curve or surface, e.g. for locomotives on railway tracks · CPC title