Method and system for navigation using bounded geographic regions

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.

We claim: 
     
       1. A method and system of navigation guidance, containing, at a minimum: an end-user device with means for using bounded geographic regions (“BGRs”) comprising the steps of inputting destinations and receiving routing guidance or routing with an end-user device;
 geo-locating the end-user device using a global-positioning system (“GPS”) chip-set capable of transmitting and receiving location data; 
 identifying the position of the end-user device with reference to a map database, containing roads and, optionally, points of interest (“POIs”); 
 a device and method for determining vehicle position; 
 a server or otherusing an assemblage of memory and, processing elements;, and associated circuitry, referred to as a server and a computer-readable instruction set, called the navigation software core, resident on the non-transitory, computer-readable memory elements of the server, 
 a means for communicating between the end-user device and the server; and 
 accessing 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”) BGR of interest to the end user, each BGR being an area bounded by a defined perimeter, all areas of interest to the end user are included in a BGR; and a node is the point at which a road segment intersects with the defined perimeter of a BGR; each BGR having at least two nodes, wherein a BGR can be entered at any node and exited at any other node, and a Node Pair is an entry node to and exit node from a BGR 
 and a using the 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 at least one dependent variable provided by the user and the independent variables which are inherently part of a solution database in the NPLUT. 
 
     
     
       2. The invention method of navigation guidance using BGRs in  claim 1 , in which further comprising the step of calculating with the navigation software contains core an error function calculator and performing a feedback routine to correct dependent variable values stored in the NPLUT database. 
     
     
       3. The invention method of navigation guidance using BGRs in  claim 1 , in which further comprising the step of communicating to and storing in the NPLUT each end-user's actual value for each Node Pair solution for dependent variables, including, but not limited to, at least one of 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 method of navigation guidance using BGRs in  claim 1 , in which further comprising the step of capturing and storing in the NPLUT 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 analysis of variance (“ANOVA”) and MANOVA multivariate analysis of variance (“MANOVA”) calculations of the dependent variables stored in the NPLUT, in order to give more accurate estimates during future navigation. 
     
     
       5. The invention method of navigation guidance using BGRs in  claim 4 , in which further comprising the step of compressing 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 method of navigation guidance using BGRs in  claim 1 , in which further comprising the step of creating 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 method of navigation guidance using BGRs in  claim 6 , in which further comprising the step of varying the tessellation pattern on the cube, which is comprised of squares and rectangles, by reducing geometrically the area of which is reduced geometrically as the rectangles vary with the rectangles distance from the center of the cube face, and by increasing the aspect ratio of which increases with of the rectangles with the rectangles distance from the center of the cube face. 
     
     
       8. The invention method of navigation guidance using BGRs in  claim 1 , in which further comprising the step of calculating solutions for each Node Pair are calculated using different processors in a multi-processor configuration. 
     
     
       9. The invention method of navigation guidance using BGRs in  claim 1 , in which further comprising the step of calculating, iteratively, with 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 method of navigation guidance using BGRs in  claim 1 , further comprising the step of storing in which the end-user's device memory only stores detail from Active BGRs. 
     
     
       11. The invention method of navigation guidance using BGRs in  claim 1 , in which the communication further comprising the step of communicating with the server is made via at least one of a cellular wireless or network and a satellite network connection to from at least one of a vehicle, mobile telephone, mobile data terminal, or and remote electronic device. 
     
     
       12. The invention method of navigation guidance using BGRs in  claim 1 , in which the server can also collect further comprising the step of collecting data, with the server, 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. 
     
     
       13. A system of navigation guidance using bounded geographic regions (“BGRs”), comprising
 an end-user device with means for inputting destinations and receiving routing guidance; 
 a map database, containing roads and, optionally, points of interest (“POIs”); 
 a device for geo-locating the end-user device using a global-positioning system (“GPS”) chip-set capable of transmitting and receiving location data, and a software method, embodied in non-transitory, computer readable medium, which is used by the device for determining vehicle position; 
 an assemblage of memory, processing elements, and associated circuitry, referred to as a server; 
 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 of interest to the end user, each BGR being an area bounded by a defined perimeter, all areas of interest to the end user are included in a BGR, and a node is the point at which a road segment intersects with a defined perimeter of a BGR; 
 and a navigation software core, resident on the server, to identify Node Pairs for each BGR which might be part of a potential solution, and to optimize a navigation solution based on at least one dependent variable provided by the user and independent variables in the NPLUT. 
 
     
     
       14. The system of navigation guidance using BGRs in claim 13, in which the software contains an error function calculator and a feedback routine to correct dependent variable values stored in the NPLUT database. 
     
     
       15. The system of navigation guidance using BGRs in claim 13, 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. 
     
     
       16. The system of navigation guidance using BGRs in claim 13, 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. 
     
     
       17. The system of navigation guidance using BGRs in claim 16, 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. 
     
     
       18. The system of navigation guidance using BGRs in claim 13, 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. 
     
     
       19. The system of navigation guidance using BGRs in claim 18, 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. 
     
     
       20. The system of navigation guidance using BGRs in claim 13, in which solutions for each Node Pair are calculated using different processors in a multi-processor configuration. 
     
     
       21. The system of navigation guidance using BGRs in claim 13, 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. 
     
     
       22. The system of navigation guidance using BGRs in claim 13, in which the end-user's device memory only stores detail from Active BGRs. 
     
     
       23. The system of navigation guidance using BGRs in claim 13, 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. 
     
     
       24. The system of navigation guidance using BGRs in claim 13, 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.