Data processing: vehicles – navigation – and relative location – Navigation – Employing way point navigation
Reexamination Certificate
2001-11-01
2003-05-20
Black, Thomas G. (Department: 3663)
Data processing: vehicles, navigation, and relative location
Navigation
Employing way point navigation
C701S200000, C701S207000, C701S209000, C340S988000, C340S989000, C340S991000, C342S357490, C342S357490, C342S357490, C342S357490
Reexamination Certificate
active
06567741
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to the navigation of a moving vehicle. In particular, this invention relates to a method and system for decreasing the number of shape points to increase effectiveness and response time of a server-based navigation system.
BACKGROUND OF THE INVENTION
Onboard vehicle navigation technology has come a long way in the recent years. Existing computer capabilities coupled with wireless and Global Positioning Satellite technology is making huge advances in taking some of the high cost out of “real time” vehicle navigation. There are different systems to make this technology work (for example, onboard autonomous systems vs. server-based navigation systems). There are also a number of different methods to support this technology. On server-based navigation systems, the client is placed onboard the vehicle while the server, communicated with through wireless and often satellite technology, plays host to most of the source applications and databases.
Within onboard vehicle navigation systems, there is a predetermined list of location points where a vehicle is instructed to proceed in a certain direction (i.e., turn right, turn left, etc.) This list is known as a maneuver list and the points on this list are known as maneuver points. The maneuver list is processed from a server based database to a client processor onboard the vehicle. Within each maneuver point are geodesic points (hereafter known as shape points). Each shape point has a latitudinal and longitudinal value identifying its location with respect to its physical location on the surface of the earth. The number of shape points and the position of shape points, determines the geographic condition of the path being navigated (e.g., curvy line vs. straight line).
The processing of this information is necessary to determine vehicle location and to generate correct navigation instructions. The server based processing for this is time consuming and this processing time is dependent on the amount of data input into the server. Navigation instructions must be generated and transmitted to the vehicle in a timely fashion to provide a useful navigation system. For example, if a vehicle has passed a maneuver point on a route it will need instructions on the next maneuver at an acceptable time before it reaches or exceeds that next maneuver point. Receiving maneuver information after passing the maneuver point is useless and compromises the need for the navigation system.
The number of shape points to be processed has a direct correlation to the amount of processing time and the amount of physical processor based memory needed for the navigation system to operate effectively and generate timely and accurate instructions. Navigating on extremely curvy routes, which require numerous shape points, could potentially warrant the design and installation of onboard vehicle navigation systems that are cost prohibitive.
It would be desirable, therefore, to provide a method to reduce shape points to provide more effective and timely navigation instructions to a moving vehicle that overcomes the above.
SUMMARY OF THE INVENTION
One aspect of the present invention provides a method for generating navigation instructions for a vehicle. A number of shape points between a set of primary maneuver points may be determined. A determination may be made as to whether the number of shape points exceeds a cardinal threshold. A bearing between a first shape point and a second shape point may be determined if the number of shape points exceeds the cardinal threshold. It may be determined whether the bearing exceeds an angular threshold. The second shape point may be eliminated if associated bearings exceed the angular threshold. In one embodiment, the angular threshold may be predetermined. In still another embodiment, the cardinal threshold may be predetermined.
Another aspect of the present invention provides a system for generating navigation instructions for a vehicle. The system may include means for determining a number of shape points between a set of primary maneuver points, means for determining whether the number of shape points exceeds a cardinal threshold and means for determining a bearing between a first shape point and a second shape point, if it is determined that the number of shape points exceeds the cardinal threshold. It may also include means for determining whether the bearing exceeds an angular threshold and means for eliminating the second shape point if it is determined that associated bearings exceed the angular threshold.
Another aspect of the system provides a computer usable medium including a program for generating navigation instructions for a vehicle. The program may include computer readable program code that determines a number of shape points between a set of primary maneuver points and computer readable program code that determines whether the number of shape points exceeds a cardinal threshold. It may also include computer readable program code that determines a great circle distance and a bearing between a first shape point and a second shape point, if it is determined that the number of shape points exceeds the cardinal threshold. The program may also include computer readable program code that determines whether the bearing exceeds an angular threshold and computer readable program code that eliminates the second shape point if it is determined that the bearing exceeds the angular threshold.
The foregoing and other features and advantages of the invention will become further apparent from the following detailed description of the presently preferred embodiments, read in conjunction with the accompanying drawings. The detailed description and drawings are merely illustrative of the invention rather than limiting, the scope of the invention being defined by the appended claims and equivalents thereof.
REFERENCES:
patent: 5828571 (1998-10-01), Bessacini et al.
patent: 6029111 (2000-02-01), Croyle
patent: 6281807 (2001-08-01), Kynast et al.
patent: 6330858 (2001-12-01), McDonough et al.
patent: 6366851 (2002-04-01), Chojnacki et al.
patent: 6366927 (2002-04-01), Meek et al.
patent: 2002/0062193 (2002-05-01), Lin
patent: 2002/0087262 (2002-07-01), Bullock et al.
patent: 2002/0161513 (2002-10-01), Bechtolsheim et al.
Aloi Daniel N.
Kacel Richard J.
Stefan Jeffrey M.
General Motors Corporation
Mancho Ronnie
Simon Anthony Luke
LandOfFree
Method and system for reducing shape points for a navigation... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for reducing shape points for a navigation..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for reducing shape points for a navigation... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3029618