Method and system for navigation using bounded geograhic regions

• US 8,868,332 B2
• Filed: 10/25/2012
• Issued: 10/21/2014
• Est. Priority Date: 10/26/2011
• Status: Expired

• Current Assignee: Rightthereware Llc
• Original Assignee: Right There Ware LLC
• Inventors: Heed, John Culver, Heed, Thomas Paul
• Primary Examiner(s): Cheung, Mary
• Assistant Examiner(s): MAZZARA, ANNE MARIE
• Application Number:
  US13/660,985
• Publication Number:
  US 20130110393A1
• Time in Patent Office: 726 Days
• Field of Search: 701/430
• US Class Current: 701/430
• CPC Class Codes: G01C 21/3415 Dynamic re-routing, e.g. recalculating the route when the user deviates from calculated route or after detecting real-time traffic data or accidents
• CPC Class Codes: G01C 21/3484 Personalized, e.g. from learned user behaviour or user-defined profiles
• CPC Class Codes: G08G 1/096816 where the complete route is transmitted to the vehicle at once
• 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
• CPC Class Codes: G16Z 99/00 Subject matter not provided for in other main groups of this subclass
• CPC Class Codes: H04W 4/021 Services related to particular areas, e.g. point of interest [POI] services, venue services or geofences
• CPC Class Codes: H04W 4/024 Guidance services

Abstract

A navigation system containing a software core, which uses bounded geographic regions (“BGRs”) and Node Pairs to explicitly optimize, in two dimensions, for user desired dependent variables, by analyzing variance due to standard and user-defined independent variables. The invention stores Node Pair data, and can use error function, feedback, and ANOVA/MANOVA to create a tightly convergent navigation solution.

Claims

1. A method and system of navigation guidance, containing, at a minimum:

an end-user device with means for inputting destinations and receiving guidance or routing;

a map database, containing roads and, optionally, points of interest (“

POIs”

);

a device and method for determining vehicle position;

a server or other assemblage of memory and processing elements;

a means for communicating between the end-user device and the server;

a Node Pair Look-up Table (“

NPLUT”

) database which is initially, either partially or fully, loaded with explicit solutions for each Node Pair, and which contains explicit solutions between each potential entry node and each potential exit node of every Bounded Geographic Region (“

BGR”

) of interest to the end user; and

a navigation software core, resident on the server, having the capability to create BGRs of such a size that explicit navigation solutions are possible within the boundaries of the BGR, to identify Node Pairs for each BGR which might be part of a potential solution, and to optimize a navigation solution based on the dependent variable provided by the user and the independent variables which are inherently part of a solution database.

2. The invention in claim 1, in which the software contains an error function calculator and a feedback routine to correct dependent variable values stored in the NPLUT database.

3. The invention in claim 1, in which each end-user'"'"'s actual value for each Node Pair solution for dependent variables, including, but not limited to, time, distance, fuel usage, cost, and any user defined dependent variables, as well as independent variables, are communicated to and stored in NPLUT, either while or after the end-user arrives at the destination.

4. The invention in claim 1, in which for each dependent Node Pair value in the NPLUT, associated independent variable factors are captured and stored, both variable and attribute, including, but not limited to, time of day, date, day of the week, temperature, construction, precipitation, driver'"'"'s age, driver'"'"'s profession, driver'"'"'s gender, vehicle type, vehicle age, vehicle mileage, and special event, which can be used to create ANOVA and MANOVA calculations of the dependent variables stored in the NPLUT, in order to give more accurate estimates during future navigation.

5. The invention in claim 4, in which the NPLUT database is compressed by storing only the necessary ANOVA or MANOVA sums and products from prior navigation iterations, and deleting the underlying data off of which the sums and products are calculated.

6. The invention in claim 1, in which the BGRs are created by Virtual Tessellation, by inscribing the Earth in a tessellated cube or partitioned cube, and projecting the tessellation or partition from the cube onto the surface of the Earth.

7. The invention in claim 6, in which the tessellation pattern on the cube is comprised of squares and rectangles, the area of which is reduced geometrically as the rectangles vary from the center of the cube face, and the aspect ratio of which increases with distance from the center of the cube face.

8. The invention in claim 1, in which solutions for each Node Pair are calculated using different processors in a multi-processor configuration.

9. The invention in claim 1, in which the navigation software core will iteratively calculate routes using more and more BGRs, until the solutions become sufficiently divergent, or until the last BGR layer exceeds, orthogonally to a line from the origin to the destination, the distance that a vehicle can travel at the maximum posted speed limit in the amount of time defined by the current best solution.

10. The invention in claim 1, in which the end-user'"'"'s device memory only stores detail from Active BGRs.

11. The invention in claim 1, in which the communication with the server is made via a wireless or satellite connection to a vehicle, mobile telephone, mobile data terminal, or remote electronic device.

12. The invention in claim 1, in which the server can also collect data from other data sources, including, but not limited to, NHTSA traffic sensor information, police report, local traffic reports, and construction reports, for inclusion in the NPLUT as either variable or attribute data associated with a Node Pair.