System and method for selecting and presenting a route to a user

• US 20070073480A1
• Filed: 09/23/2005
• Published: 03/29/2007
• Est. Priority Date: 09/23/2005
• Status: Active Grant

• Current Assignee: Jolly Seven, Series 70 of Allied Security Trust I (Allied Security Trust)
• Original Assignee: Scenera Technologies LLC (Scenera Research LLC)
• Inventors: Singh, Mona
• Granted Patent: US 7,698,061 B2
• Time in Patent Office: Days
• US Class Current: 701/211
• CPC Class Codes: G01C 21/20 Instruments for performing navigational calculations G01C21/24, G01C21/26 take precedence
• CPC Class Codes: G01C 21/3484 Personalized, e.g. from learned user behaviour or user-defined profiles
• CPC Class Codes: G08G 1/096805 where the transmitted instructions are used to compute a route
• CPC Class Codes: G08G 1/096833 where different aspects are considered when computing the route
• CPC Class Codes: G08G 1/096838 where the user preferences are taken into account or the user selects one route out of a plurality
• CPC Class Codes: G08G 1/096844 where the complete route is dynamically recomputed based on new data

Abstract

A method and system are provided for selecting and presenting a route to a user. An exemplary embodiment includes storing at least a portion of routes taken by a plurality of users; receiving from a particular user a request for at least one recommended route from an origination point to a destination point; formulating a query based on user specified parameters to obtain routes taken by other users, wherein the specified parameters include the origination point, the destination point and characteristics of other users of other users; retrieving a plurality of the stored routes taken by other users in response to the query; and presenting the at least one recommended route to the particular user using at least one of the received routes that most closely matches the specified parameters.

Claims

1. A method for selecting and presenting a route to a user, comprising:

storing at least a portion of routes taken by a plurality of users;

receiving from a particular user a request for at least one recommended route from an origination point to a destination point;

formulating a query based on user specified parameters to obtain routes taken by other users, wherein the specified parameters include the origination point, the destination point, and characteristics of other users;

retrieving a plurality of the stored routes taken by other users in response to the query; and

presenting the at least one recommended route to the particular user using at least one of the received routes that most closely matches the specified parameters.

2. The method of claim 1 wherein retrieving a plurality of the stored routes further comprises:

retrieving a plurality of the stored routes taken by other users having at least some of the characteristics of other users and related to at least one of the origination and destination points.

3. The method of claim 2 wherein the characteristics of other users include demographic parameters including any combination of a name, address, sex, age, driving experience, and number of children.

4. The method of claim 3 wherein formulating the query further comprises:

formulating the query based on route parameters, wherein the route parameters include any combination of quickness, personal safety, traffic safety, road conditions, and police activity.

5. The method of claim 1 further comprising:

allowing each of the plurality of users to specify a group of users with whom the user'"'"'s routes may be shared and from whom the routes may be requested.

6. The method of claim 5 wherein the specified group of users comprises a buddy list.

7. The method of claim 1 wherein receiving the plurality of routes in response to the query further comprises:

generating one or more candidate routes from the origination point to the destination point; and

assigning weights to the generated candidate routes based in part on how much the retrieved routes overlap the candidate routes.

8. The method of claim 7 wherein the weight assigned to a particular one of the generated candidate routes is proportional to the distance at least one of the retrieved routes overlaps the particular one the generated candidate routes.

9. The method of claim 7 wherein the weight assigned to the particular one of the generated candidate routes is proportional to a number of street segments the at least one of the retrieved routes overlaps the particular one of the generated candidate routes.

10. The method of claim 7 wherein the weight assigned to the particular one of the generated candidate routes is determined by:

calculating a total distance of the candidate route;

calculating a total distance that at least one segment of the at least one of the retrieved routes overlaps with a corresponding segment of the candidate route; and

assigning a value to the weight that is equal to either of the total distance of overlapping segments, or the total distance of overlapping segments divided by the total distance of the candidate route.

11. The method of claim 7 wherein presenting to the particular user the at least one recommended route further comprises:

selecting at least one of the generated candidate routes having a highest weight.

12. The method of claim 1 further comprising responding to the query by:

generating an origin region around the origination point and generating a destination region around the destination point; and

retrieving stored routes having at least one of a beginning segment falling within the origin region and an ending segment falling within destination region.

13. The method of claim 12 wherein responding to the query further comprises:

calculating a radius r based on a predetermined percentage of a distance between the origination point and the destination point;

calculating the origin region by generating a circle centered around the origination point having the radius r; and

calculating the destination region by generating a circle centered around the destination point having the radius r.

14. The method of claim 13 wherein responding to the query further comprises:

determining a radius R having a length less than the distance from the origination point to the destination point;

drawing a first arc of the radius R through the origin region that is centered at the destination point;

drawing an arc of the radius R through the destination region that is centered at the origination point; and

retrieving saved routes that have an ending segment falling within a region bounded by the origin region and the first arc, and that have an ending segment falling with a region bounded by the destination region and the second arc.

15. The method of claim 1 wherein storing the routes further comprises:

storing the routes of each of the users locally on respective ones of a plurality of user devices.

16. The method of claim 1 wherein storing the routes further comprises:

storing route data recorded by a plurality of user devices in a route database on a network server.

17. A system for selecting and presenting a route to a user, comprising:

at least one route database for storing at least a portion of routes taken by at least one user;

a routing module coupled to the route database for receiving from a particular user a request for at least one recommended route from an origination point to a destination point, wherein in response to the request, the routing module is further functional for,

formulating a query based on user specified parameters to obtain routes taken by other users, wherein the specified parameters include the origination point, the destination point, and characteristics of other users;

retrieving from the at least one route database a plurality of the stored routes taken by one or more other users in response to the query; and

presenting the at least one recommended route to the particular user using at least one of the received routes that most closely matches the specified parameters.

18. The system of claim 17 wherein routing module retrieves a plurality of the stored routes further comprises:

retrieving a plurality of the stored routes taken by other users having at least some of the characteristics of other users and related to at least one of the origination and destination points.

19. The system of claim 18 wherein the characteristics of other users include demographic parameters including any combination of a name, address, sex, age, driving experience, and number of children.

20. The system of claim 19 wherein the routing module formulates the query based on route parameters that include any combination of quickness, personal safety, traffic safety, road conditions, and police activity.

21. The system of claim 17 wherein the routing module allows the at least one user to specify a group of users with whom the user'"'"'s routes may be shared and from whom the routes may be requested.

22. The system of claim 21 wherein the specified group of users comprises a buddy list.

23. The system of claim 17 wherein the route module further generates one or more candidate routes from the origination point to the destination point, and assigns weights to the generated candidate routes based in part on how much the retrieved routes overlap the candidate routes.

24. The system of claim 23 wherein the weight assigned to a particular one of the generated candidate routes is proportional to the distance at least one of the retrieved routes overlaps the particular one the generated candidate routes.

25. The system of claim 23 wherein the weight assigned to the particular one of the generated candidate routes is proportional to a number of street segments the at least one of the retrieved routes overlaps the particular one of the generated candidate routes.

26. The system of claim 23 wherein the weight assigned to the particular one of the generated candidate routes is determined by:

calculating a total distance of the candidate route;

calculating a total distance that at least one segment of the at least one of the retrieved routes overlaps with a corresponding segment of the candidate route; and

assigning a value to the weight that is equal to either of the total distance of overlapping segments, or the total distance of overlapping segments divided by the total distance of the candidate route.

27. The system of claim 23 wherein the route module presents to the particular user at least one of the generated candidate routes having a highest weight.

28. The system of claim 17 wherein the route module for the functions for:

generating an origin region around the origination point and generating a destination region around the destination point; and

retrieving stored routes from the route database having at least one of a beginning segment falling within the origin region and an ending segment falling within destination region.

29. The system of claim 28 wherein the origin region and destination region are generated by:

calculating a radius r based on a predetermined percentage of a distance between the origination point and the destination point;

calculating the origin region by generating a circle centered around the origination point having the radius r; and

calculating the destination region by generating a circle centered around the destination point having the radius r.

30. The system of claim 29 wherein the routes are further retrieved by:

determining a radius R having a length less than the distance from the origination point to the destination point;

drawing a first arc of the radius R through the origin region that is centered at the destination point;

drawing an arc of the radius R through the destination region that is centered at the origination point; and

retrieving saved routes that have an ending segment falling within a region bounded by the origin region and the first arc, and that have an ending segment falling with a region bounded by the destination region and the second arc.

31. The system of claim 17 wherein the routes of each of the users are stored locally on respective ones of a plurality of user devices.

32. The system of claim 17 wherein route data recorded by a plurality of user devices is stored in a route database on a network server.

33. An executable software product stored on a computer-readable medium containing program instructions for selecting and presenting a route to a user, the program instructions for:

storing at least a portion of routes taken by a plurality of users;

receiving from a particular user a request for at least one recommended route from an origination point to a destination point;

formulating a query based on user specified parameters to obtain routes taken by other users, wherein the specified parameters include the origination point, the destination point, and characteristics of other users;

retrieving a plurality of the stored routes taken by other users in response to the query; and

presenting the at least one recommended route to the particular user using at least one of the received routes that most closely matches the specified parameters.

34. A server-based method for selecting and presenting a route to a user, comprising:

storing at least a portion of routes taken by a plurality of users in a route database on a network server;

receiving from a particular user a request for at least one recommended route from an origination point to a destination point, wherein the request further specifies characteristics of other users;

generating one or more candidate routes from the origination point to the destination point;

using the characteristics of other users specified in the request to filter which set of users should be queried for their routes;

generating an origin region around the origination point, and generating a destination region around the destination point;

querying the route database for the routes of the filter set of users having at least a beginning segment falling within the origin region or an ending segment falling within the destination region;

assigning weights to the candidate routes based in part on how much the routes retrieved in response to the query overlap the candidate routes; and

selecting one or more of the candidate routes having a highest assigned weight and presenting the selected routes to the user.

35. A peer-to-peer method for selecting and presenting a route to a user, comprising:

locally storing at least a portion of routes taken by each of a plurality of users in respective ones of a plurality of user devices, wherein each of the user devices are capable of communicating with the other user devices over a network;

on a particular one of the user devices, receiving a request for at least one recommended route from an origination point to a destination point, wherein the request further specifies characteristics of other users;

generating one or more candidate routes from the origination point to the destination point;

using the characteristics of other users specified in the request to filter which set of users should be queried for their routes;

querying the devices of the filter set of users for routes related to at least one of the origination point and the destination point, wherein in response, each one of the queried devices,

generates an origin region around the origination point and generates a destination region around the destination point,

retrieves the stored routes having at least a beginning segment falling within the origin region or an ending segment falling within the destination region, and

returns the retrieved routes;

assigning weights to the candidate routes based in part on how much the returned routes overlap the candidate routes; and

selecting one or more of the candidate routes having a highest assigned weight and presenting the selected routes to the user.