IP Library › Granted Patent US 9,791,280
Granted Patent B2
US 9,791,280 · App. 13/723,478 · Granted Oct 17, 2017

Determining a route

Inventor: Krzysztof Duleba (Pfaffikon SZ, CH)
Assignee: Google Inc.
G01C21/20G01C21/3484G01C21/3492
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 9,791,280
App. No.
13/723,478
Filed
Dec 21, 2012
Granted
Oct 17, 2017
Kind
B2
Art Unit
3662
USPC
701/533
Abstract

A method, system and apparatus for determining a route between start and finish locations by searching journey tracks shared by users and using tracks identified in the search to determine the route between the start and finish locations.

Claims (49)

1. A computer implemented method of determining a route, comprising:

searching, by one or more computing devices, journey tracks shared by users to identify at least one journey track which is located within a predetermined area of a defined route start location, wherein the journey tracks comprise the locations of a mobile user device during a journey made by a user;

searching, by the one or more computing devices, journey tracks shared by users to identify at least one journey track which is located within a predetermined area of a defined route finish location;

performing, by the one or more computing devices, a security check associated with the identified journey tracks to determine if the identified journey tracks are available for sharing with a requesting user, wherein performing the security check comprises:

determining, by the one or more computing devices for each identified journey track, whether at least a predetermined number of other journey tracks shared by users pass within a predetermined distance of at least a portion of such identified journey track; and

designating as available for sharing, by the one or more computing devices, each identified journey track for which it is determined that at least the predetermined number of other journey tracks shared by users pass within the predetermined distance of at least the portion of such identified journey track; and

using a plurality of the identified journey tracks to determine, by the one or more computing devices, a route between the defined start and finish locations based at least in pan on the security check, wherein determining the route comprises forming the route from intersecting journey tracks identified from the plurality of journey tracks and available for sharing, wherein the route consists of journey tracks, wherein at least one of the identified journey tracks from the plurality of the identified journey tracks comprises a journey track that does not follow an existing mapped road.

2. The method of claim 1 , wherein the journey tracks comprise a series of locations at which the user was located during the journey.

3. The method of claim 2 , wherein the series of locations were determined as the journey was made by the user.

4. The method of claim 1 , wherein a first of the identified journey tracks is located within the predetermined area of the start location and a second of the identified journey tracks intersects the first identified journey track and is located within the predetermined area of the finish location.

5. The method of claim 1 , comprising connecting the plurality of identified journey tracks at intersections between them to create a continuous route and determining the route as the created continuous route.

6. The method of claim 1 , wherein searching the shared journey tracks comprises determining a geographical proximity of each shared journey track to the start location and/or finish location in order to identify tracks which pass through the predetermined areas of the start location, finish location, or combinations thereof.

7. The method of claim 6 , wherein determining the geographical proximity comprises determining a distance between each shared journey track and the start and/or finish locations.

8. The method of claim 6 , wherein determining the geographical proximity of each shared journey track to the start and/or finish locations comprises reading a geographical location identifier associated with each shared journey track and comparing it with a geographical location identifier associated with the start location, finish location, or combinations thereof.

9. The method of claim 8 , wherein each geographical location identifier indicates a cell of a cellular grid overlaid on a map.

10. The method of claim 1 , wherein one or more of the journey tracks are associated with privacy information which restricts their availability for use in the route determination.

11. The method of claim 1 , comprising determining the route in response to receipt of a route request defining the start and finish locations.

12. The method of claim 1 , comprising causing the route to be provided to a user.

13. A computer implemented method of determining a route, comprising:

identifying, by one or more computing devices, at least a first shared GPS track which is available for sharing and which passes through a geographical area specified in a route request, wherein identifying the first shared GPS track comprises:

searching, by the one or more computing devices, GPS tracks shared by users to identify at least one GPS track which is located within a predetermined area of the geographical area;

performing, by the one or more computing devices, a security check associated with the identified GPS tracks to determine if the identified GPS tracks are available for sharing with a requesting user, wherein performing the security check comprises:

determined, by the one or more computing devices for each identified GPS track, whether at least a predetermined number of other GPS tracks shared by users pass within a predetermined distance of at least a portion of such identified GPS track; and

designating as available for sharing, by the one or more computing devices, each GPS track for which it is determined that at least the predetermined number of other GPS tracks shared by users pass within the predetermined distance of at least the portion of such identified GPS track; and

determining, by the one or more computing devices, a route between two geographical locations which includes at least a part of the first shared GPS track.

14. The method of claim 13 , comprising identifying at least two shared GPS tracks which pass through the geographical area and connecting the at least two tracks together to form the route.

15. A route provider apparatus for determining a route, comprising at least one computer processor and at least one computer-readable memory storing instructions which when executed by the at least one processor cause the at least one processor to:

search journey tracks shared by users to identify at least one journey track which is located within a predetermined area of a defined route start location, wherein the journey tracks comprise the locations of a mobile user device during a journey made by a user;

search journey tracks shared by users to identify at least one journey track which is located within a predetermined area of a defined route finish location;

perform a security check associated with the identified journey tracks to determine if the identified journey tracks are available for sharing with a requesting user, wherein the instructions that cause the at least one processor to perform the security check cause the at least one processor to:

determine whether at least a predetermined number of other journey tracks shared by users pass within a predetermined distance of at least a portion of such identified journey track; and

designate as available for sharing each identified journey track for which it is determined that at least the predetermined number of other journey tracks shared by users pass within the predetermined distance of at least the portion of such identified journey tracks; and

use a plurality of the identified journey tracks to determine a route between the defined start and finish locations based at least in part on the security check, wherein determining the route comprises forming the route from intersecting journey tracks identified from the plurality of journey tracks and available for sharing, wherein the route consists of journey tracks, wherein at least one of the identified journey tracks from the plurality of the identified journey tracks comprises a journey track that does not follow an existing mapped road.

16. A route provider apparatus for determining a route, comprising at least one computer processor and at least one computer-readable memory storing instructions which when executed by the at least one processor cause the at least one processor to:

identify at least a first shared GPS track which is available for sharing and which passes through a geographical area specified in a route request, wherein the instructions that cause the at least one processor to identify at least the first GPS track cause the at least one processor to:

search GPS tracks shared by users to identify at least one GPS track which is located within a predetermined area of the geographical area; and

perform a security check associated with the identified GPS tracks to determine if the identified GPS tracks are available for sharing with a requesting user, wherein the instructions that cause the at least one processor to perform the security check cause the at least one processor to:

determine, for each identified GPS track, whether at least a predetermined number of other GPS tracks shared by users pass within a predetermined distance of at least a portion of such identified GPS track; and

designate as available for sharing each GPS track for which it is determined that at least the predetermined number of other GPS tracks shared by users pass within the predetermined distance of at least the portion of such identified GPS track; and

determine a route between two geographical locations which includes at least a part of the at least one identified GPS track.

17. The apparatus of claim 16 , wherein the instructions when executed by the at least one processor cause the at least one processor to identify at least two shared GPS tracks which pass through the geographical area and connect the at least two tracks together to form the route.

18. A system for requesting and determining a route for providing to a user, comprising at least one computer processor and at least one computer-readable memory storing instructions which when executed by the at least one processor cause the at least one processor to:

generate a route request in response to a user input;

respond to the route request by identifying a route start location and a route finish location from the route request;

search journey tracks shared by users to identify tracks which form at least part of a route between the start and finish locations; and

perform a security check associated with the identified journey tracks to determine if the identified journey tracks are available for sharing with a requesting user, wherein the instructions that cause the at least one processor to perform the security check cause the at least one processor to:

determine whether at least a predetermined number of other journey tracks shared by users pass within a predetermined distance of at least a portion of such identified journey track; and

designate as available for sharing each identified journey track for which it is determined that at least the predetermined number of other journey tracks shared by users pass within the predetermined distance of at least the portion of such identified journey tracks.

19. The computer implemented method of claim 1 , wherein searching, by the one or more computing devices, journey tracks shared by users to identify at least one journey track which is located within the predetermined area of the defined route finish location comprises incrementally increasing, by the one or more computing devices, an acceptable distance between the journey tracks and the route finish location until the at least one journey track is identified.

Assignments (2)
CHANGE OF NAME Recorded Oct 5, 2017
From: GOOGLE INC.
To: GOOGLE LLC
Reel/Frame 044129/0001 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Dec 21, 2012
From: DULEBA, KRZYSZTOF
To: GOOGLE INC.
Reel/Frame 029516/0150 →
Continuity (1)
Related Publication 20150168147A1 · Jun 18, 2015