Apparatus and method for guiding vehicle occupant to travel from present position of vehicle to set destination through display unit

• US 5,557,522 A
• Filed: 09/09/1994
• Issued: 09/17/1996
• Est. Priority Date: 09/10/1993
• Status: Expired due to Term

• Current Assignee: Nissan Motor Co., Ltd.
• Original Assignee: Nissan Motor Co., Ltd.
• Inventors: Grom, Brian R., Tsuda, Hiroshi, Nakayama, Okihiko, Iwasaki, Masayasu
• Primary Examiner(s): Teska, Kevin J.
• Assistant Examiner(s): NOT, DEFINED
• Application Number:
  US08/302,028
• Time in Patent Office: 739 Days
• Field of Search: 364/424.02, 364/449, 364/424.01, 364/436, 364/443, 364/444
• US Class Current: 701/200
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes

Abstract

In an apparatus and method for guiding a vehicle occupant from a present position of the vehicle to a destination to which the vehicle occupant desires to reach, optimum routes of travel from the present position to respective intersections surrounding the present position of the vehicle are already searched and stored when the vehicle stops at the present position of the vehicle with a vehicular ignition switch turned off. Then, when the ignition switch is turned on and the vehicle occupant sets the destination, the optimum routes from the set destination toward the present position are searched on the basis of the road map data and result of search of the optimum routes of the respective intersections surrounding the present position of the vehicle. When the optimum route from the set destination to the present position of the vehicle is searched, the display unit superimposes and displays the present position of the vehicle and the optimum route to the destination on the road map so as to quickly start the guidance of the route from the present position to the destination. In the embodiment, if the set destination corresponds to one of registered points of locations, the present position and the optimum route to the destination are immediately displayed on the road map after the destination is set.

Claims

1. An apparatus for guiding a vehicle occupant toward a destination at which the vehicle occupant desires to arrive through a display unit, comprising:

a) road map storing means for storing a road map therein;

b) setting means through which the vehicle occupant sets the destination;

c) first detecting means for detecting a present position of the vehicle and outputting a signal indicative of the present position of the vehicle;

d) display control means for reading the road map from said road map storing means, displaying the road map on the display unit, and simultaneously displaying the detected present position of the vehicle and an optimum route of travel of the vehicle to the set destination from the present position of the vehicle;

e) second detecting means for detecting whether a vehicular ignition key switch is placed at an OFF position or at an ON position to determine whether or not the vehicle is stopped;

f) first route searching means for previously searching the optimum routes of the vehicle to respective intersections from the detected present position of the vehicle when said second detecting means detects that the vehicular ignition key switch is placed at the OFF position with the vehicle stopped before the display control means is effective, said respective intersections falling in a region other than the destination set by the occupant through the setting means and surrounding the detected present position of the vehicle; and

g) second route searching means operating for immediately displaying one of the optimum routes from the present position of the vehicle to the set destination if the set destination set through the setting means corresponds to one of the respective intersections falling in the region and whose optimum route is searched by the first route searching means when the ignition key switch is placed at the ON position and the vehicle occupant sets the destination through the setting means and otherwise operating for retrieving the result of search by the first route search means and the read road map data so as to derive the optimum route from the set destination toward the present position of the vehicle via one of the optimum routes searched by the first route searching means when the ignition key switch is placed at the ON position when the destination is set, and for immediately displaying the derived optimum route from the set destination through the setting means toward the present position of the vehicle via the searched optimum route by said first route searching means through one of the respective intersections in the region on the display unit through the display control means.

2. An apparatus for guiding a vehicle occupant toward a destination at which the vehicle occupant is desired to arrive via a display unit as claimed in claim 1, wherein said first route searching means searches any one of the routes which has a least value of a road distance from the present position to each intersection falling in the region surrounding the present position of the vehicle.

3. An apparatus for guiding a vehicle occupant toward a destination at which the vehicle occupant is desired to arrive via a display unit as claimed in claim 1, which further includes:

h) power supply means for continuing a power supply to the vehicle guidance apparatus for a predetermined period of time after the vehicle ignition key switch is placed at the OFF position so as to operate the first route searching means;

i) an auxiliary power supply which is independent of a vehicular battery; and

j) search result storing means for holding its memory content by receiving the power supply from the auxiliary power supply when the supply of power from the power supply means is halted, and wherein said first route search means carries out the optimum routes while the power supply means continues to supply the power to the vehicle guidance apparatus for the predetermined period of time and for storing the result of route search thereby into the search result storing means.

4. An apparatus for guiding a vehicle occupant toward a destination at which the vehicle occupant is desired to arrive via a display unit as claimed in claim 3, wherein said second route searching means searches any one of the routes from the set destination toward the present position of the vehicle, retrieving the intersections falling another region surrounding the set destination in such an order that sums of a road distance from the set destination to any one of the intersections falling in the other region surrounding the set destination and an estimated road distance from its any one intersection to the present position of the vehicle becomes smaller so as to derive the optimum route from the set destination toward the present position of the vehicle.

5. An apparatus for guiding a vehicle occupant toward a destination at which the vehicle occupant is desired to arrive via a display unit as claimed in claim 4, wherein said second route searching means ends the corresponding route search when the intersection to be searched thereby has reached to a start intersection, said start intersection being defined as an intersection present outside of a circle having a predetermined radius with the present position as a center of the circle and which is nearest to the present position of the vehicle.

6. An apparatus for guiding a vehicle occupant toward a destination at which the vehicle occupant is desired to arrive via a display unit as claimed in claim 4, wherein said second route searching means ends the corresponding route search when the intersection to be searched thereby has reached to one of the intersections at which the route search by the first route searching means has been ended.

7. An apparatus for guiding a vehicle occupant toward a destination at which the vehicle occupant is desired to arrive via a display unit as claimed in claim 3, which further includes:

k) data selecting means for selecting data which satisfies a previously set condition from among the route search searched by said first route searching means, and wherein said route search result storing means stores the route search data selected by said data selecting means and wherein said second route searching means retrieves the selected route search data stored in said route search result storing means and the road map data stored in said road map storing means so as to search the optimum route from the set destination toward the present position of the vehicle.

8. An apparatus for guiding a vehicle occupant toward a destination at which the vehicle occupant is desired to arrive via a display unit as claimed in claim 7, wherein said first route searching means searches one of the routes from the present position to the respective intersections falling in the region surrounding the present position of the vehicle which has a least value of a road distance from the present position of the vehicle to the intersection to be searched and wherein said data selecting means selects the route search data related to the intersections, each of the intersections, to which the road distance from the present position of the vehicle have reached to a previously set value of a boundary radius.

9. An apparatus for guiding a vehicle occupant toward a destination at which the vehicle occupant is desired to arrive via a display unit as claimed in claim 7, wherein said first route searching means searches one of the routes from the present position to the respective intersections falling in the region surrounding the present position of the vehicle and wherein said data selecting means selects the route search data related to the respective intersections falling in the region surrounding the present position of the vehicle, each of said respective intersections being the intersection having a road distance from the present position of the vehicle thereto, said road distance being reached to a first previously set value of a first boundary radius and being reached to a second previously set value of a second boundary radius, said second previously set value of the second boundary radius being larger than the first previously set value of the first boundary radius.

10. An apparatus for guiding a vehicle occupant toward a destination at which the vehicle occupant is desired to arrive via a display unit as claimed in claim 9, wherein said route search result storing means stores the route searched data related to all intersections until the road distance from the present position of the vehicle to each of the intersections to be searched thereby and stores the route search data related to the intersections selected by the data selecting means to which the road distances from the present position of the vehicle have at least reached to the second previously set value of the second boundary radius when the road distance from the present position of the vehicle to the intersection to be searched has exceeded the first previously set value of the first boundary.

11. An apparatus for guiding a vehicle occupant toward a destination at which the vehicle occupant is desired to arrive via a display unit as claimed in claim 3, which further comprises:

k) registering means for previously registering arbitrary points of locations; and

     1) selecting means for selecting one of the registered points of locations as the destination of the vehicle, and wherein said first and second route searching means are integrated as the route searching means for searching the optimum routes from the detected present position of the vehicle to the registered points of locations registered by said registering means after the ignition key switch has been placed at the OFF position said route storing means stores the optimum routes as the result of the route search by said route searching means, and said display control means reads one of the optimum routes from the detected present position of the vehicle to the selected registered point of location as the set destination and immediately displays the read optimum route on the display unit when said selecting means selects one of the registered points of locations as the destination of the vehicle and the ignition key switch is again placed at the ON position after the ignition key switch is placed at the OFF position.

12. An apparatus for guiding a vehicle occupant toward a destination at which the vehicle occupant is desired to arrive via a display unit as claimed in claim 11, wherein said route, storing means comprises a non-volatile memory.

13. An apparatus for guiding a vehicle occupant toward a destination at which the vehicle occupant is desired to arrive via a display unit as claimed in claim 12, wherein said non-volatile memory comprises a S-RAM.

14. An apparatus for guiding a vehicle occupant toward a destination at which the vehicle occupant is desired to arrive via a display unit as claimed in claim 11, which further comprises:

m) memory control means for controlling the storage of the contents of the route storing means such that, when an information quantity of the result of route search by said route searching means is greater than a predetermined quantity, parts of routes corresponding to the predetermining quantity near to the present position of the vehicle are stored in the route storing means.

15. An apparatus for guiding a vehicle occupant toward a destination at which the vehicle occupant is desired to arrive via a display unit as claimed in claim 14, wherein said route searching means searches the optimum route from the detected present position of the vehicle to a predetermined distance.

16. An apparatus for guiding a vehicle occupant toward a destination at which the vehicle occupant is desired to arrive via a display unit as claimed in claim 15, wherein said route searching means sets one of intersections adjacent to a point of location which is present on a straight line from the detected present position of the vehicle to the registered point of location and which is present at the predetermined distance from the detected present position of the vehicle as an intervened point of location and searches the optimum route from the detected present position of the vehicle to the intervened point of location.

17. An apparatus for guiding a vehicle occupant toward a destination at which the vehicle occupant is desired to arrive via a display unit as claimed in claim 16, wherein, when the optimum route stored in the route storing means is a part from the present position to the registered point of location, said route searching means searches the optimum route of the remaining part of the optimum route to the registered point of location after the display control means display the part of the optimum route on the road map displayed on the display unit.

18. An apparatus for guiding a vehicle occupant toward a destination at which the vehicle occupant is desired to arrive via a display unit as claimed in claim 1, wherein said first route searching means searches for any one of the routes to be traveled from the present position of the vehicle to the respective intersections falling in the region surrounding the present position of the vehicle, the searched route having a least value of a required time it takes for the vehicle to reach the searched intersection from the present position of the vehicle.

19. An apparatus for guiding a vehicle occupant toward a destination at which the vehicle occupant is desired to arrive via a display unit as claimed in claim 18, wherein said second route searching means searches for any one of the routes as the optimum route from the set destination toward the present position of the vehicle in such an order of intersections that a sum between the required time it takes for the vehicle to reach to the searched intersection from the destination and an estimated required time it would take for the vehicle to reach to the present position from the searched intersection becomes small so as to derive the optimum route from the destination to the present position of the vehicle after the destination is set.

21. An apparatus for guiding a vehicle occupant toward a destination as received in claim 1, further comprising a timer for continuing, for a predetermined time duration, supply of power from a vehicular battery to the first route searching means after detection by the second detecting means that the vehicular ignition key switch is at the OFF position,

thereby to activate the first route searching means for the predetermined time duration to search the optimum routes of the vehicle to the respective intersections after detection that the vehicular ignition key switch is at the OFF position and before the vehicular ignition key switch is placed in the ON condition and the second route searching means is activated.

20. A method for guiding a vehicle occupant toward a destination at which the vehicle occupant desires to arrive via a display unit, comprising the steps of:

a) storing a road map at least including a present position of the vehicle on the road map;

b) setting the destination;

c) detecting the present position of the vehicle and outputting a signal indicative of the present position of the vehicle;

d) reading the road map, displaying the read road map on the display unit, and simultaneously displaying the detected present position of the vehicle and an optimum route of travel of the vehicle to reach to the set destination from the present position of the vehicle;

e) detecting whether a vehicular ignition key switch is placed at an ON position to determine whether or not the vehicle is stopped;

f) previously searching the optimum routes of travel of the vehicle to respective intersections from the detected present position of the vehicle when the vehicular ignition key switch is placed at an OFF position with the vehicle stopped, said respective intersections falling in a region other than the destination set by the occupant and surrounding the detected present position of the vehicle; and

g) immediately displaying one of the optimum routes from the present position of the vehicle to the set destination if the set destination corresponds to one of the respective intersections falling in the region when the ignition key switch is placed at the ON position and the vehicle occupant sets the destination and otherwise retrieving the result of search at said step f) and the read road map data so as to derive the optimum route from the set destination toward the present position of the vehicle via one of the optimum routes when the ignition key switch is placed at the ON position when the destination is set, and for immediately displaying the derived optimum route from the set destination toward the present position of the vehicle via the searched optimum route through one of the respective intersections in the region on the display unit.

22. A method for guiding a vehicle occupant toward a destination at which the vehicle occupant desires to arrive through a display unit, comprising the steps of:

a) storing a road map;

b) detecting a present position of the vehicle and outputting a signal indicative of the present position of the vehicle;

c) reading the road map stored at step a) from road map storing means, displaying the road map on the display unit, and displaying the detected present position of the vehicle and, simultaneously, an optimum route of travel of the vehicle to a set destination from the present position of the vehicle if the destination is set;

d) detecting whether a vehicular ignition key switch is placed at an OFF position or at an ON position to determine whether the vehicle is stopped or not;

e) previously searching the optimum routes of the vehicle to respective intersections from the detected present position of the vehicle when the vehicular ignition key switch is placed at the OFF position with the vehicle stopped before said step c), said respective intersections falling in a region other than the destination set by the occupant at the step c) and surrounding the present position of the vehicle; and

f) immediately displaying one of the optimum routes from the present position of the vehicle to the set destination if the set destination set at the step c) corresponds to one of the respective intersections falling in the region and whose optimum route is searched at the step e) when the ignition key switch is placed at the ON position and the vehicle occupant sets the destination and otherwise for retrieving the result of the search at the step e) and the read road map data so as to derive the optimum route from the set destination toward the present position of the vehicle via one of the optimum routes searched at the step e) when the ignition key switch is placed at the ON position and when the destination is set, and for immediately displaying the derived optimum route from the set destination toward the present position of the vehicle via the searched optimum route searched at the step e) through one of the respective intersections in the region on the display unit.

23. A system for a vehicular travel route guidance to a destination to which a vehicle occupant desires to reach from a present position of the vehicle, comprising:

a) road map storing means for storing a road map data therein;

b) first detecting means for detecting the present position of the vehicle using a vehicle forward direction sensor and GPS satellites wave receiver;

c) second detecting means for detecting whether a key switch of an ignition key is closed or open;

d) setting means through which the vehicle occupant sets the destination when the key switch is closed;

e) display means for reading and displaying the road map data from the road map storing means on a display unit image screen and for superimposing the detected present position of the vehicle and an optimum route from the detected present position of the vehicle to the set destination on the displayed road map after the destination is set with the key switch closed;

f) first route searching means for previously searching for one of the routes along which the vehicle is to travel at optimum, said optimum route being present in a road segment from the detected present position of the vehicle to each of a plurality of intersections falling in a first region surrounding the detected present position of the vehicle, when the key switch is open so that the vehicle stops;

g) second route searching means for searching for one of the routes along which the vehicle is to travel at optimum on the basis of the result of route search by said first route searching means and read road map data, said optimum route being present in a road segment from the set destination to each of a plurality of intersections falling in a second region surrounding the set destination, when the key switch is closed and the destination is set; and

h) display control means, responsive to the set of the destination with the key switch closed, for combining the optimum route searched by the first route searching means and that searched by the second route searching means so as to derive and display the optimum route from the present position to the set destination on the road map of the display unit image screen,

a timer by means of which a power supply from a vehicular battery to the vehicular travel route guidance system is continued for a predetermined time duration so as to activate the first route searching means when the timer is started in response to the open of the key switch,

wherein said first searching means searches for the optimum route from the detected present position of the vehicle to each of the intersections falling in the first region, the optimum route therein having a road distance h from the detected present position to any one of the intersections falling in the first region which gives a minimum value from among the searched plurality of the routes from the detected present position of the vehicle to the one intersection,

wherein said first route searching means searches for the optimum route from the present position to each of the plurality of intersections falling in the first region in such a way that the first route searching means comprises a road map data base including an intersection network and a memory which stores the result of route search by the first route searching means, the result of route search memory means storing the road distance h from a start intersection to each of the intersections falling in the first region and a preceding intersection A placed in front of each intersection falling in the first region and each intersection therein being present on the optimum route from the start intersection to each intersection therein for each intersection falling therein, said start intersection being defined as an intersection which is present outside of a circle with the present position as a center of the circle and which is nearest to the present position of the vehicle, said first route searching means starts the route search by setting the road distance h of a center intersection to zero (h=0) and by setting the road distances h of the other intersection except the center intersection to an infinity (h=+∞

), the center intersection being defined as the intersection to be searched to calculate the route and intersections adjacent to the center intersection being defined as the adjacent intersections, adds the road distance hO of the center intersection from the start intersection stored in the road distance portion of the route result storing means and the road distance from the center intersection to the selected adjacent intersection to derive the road distance h1 from the start intersection to the selected adjacent intersection, compares the derived road distance h1 with the road distance h2 from the start intersection to the selected adjacent intersection stored as the road distance of the selected adjacent intersection in the route result storing means, changes the road distance h2 of the selected adjacent intersection to the road distance h1 when the derived road distance h1 is smaller than the road distance h2, sets the preceding intersection to the selected adjacent intersection as the new center intersection, sets the next new center intersection which has the least value of road distance h from the start intersection from among all of the intersections except the center intersections already selected as the center intersections when the above-described series of processing are ended for all adjacent intersections to the center intersection, and repeats the above-described series of processing for all intersections adjacent to the next new center intersection, so that the first route searching means sets sequentially the new center intersection in the order that the road distances from the start intersection give smaller values.

24. A system for a vehicular travel route guidance to a destination to which the vehicle occupant desires to reach from a present position of the vehicle as claimed in claim 23, wherein said first route searching means sequentially traces the preceding intersections A of the selected adjacent intersections to reach to the start intersection, the traced routes from the start intersection to the selected adjacent intersections providing the optimum route from the start intersection to the selected adjacent intersection when the route search by the first route searching means at the finally selected adjacent intersection is ended.

25. A system for a vehicular travel route guidance to a destination to which the vehicle occupant desires to reach from a present position of the vehicle as claimed in claim 24, wherein said second route searching means comprises another result of route storing means for storing road distances g of road segments from a target intersection to the respective intersections falling in the second region, preceding intersections B placed in front of the respective intersections on the optimum route from the target intersection to the respective intersections falling the second region, and estimated road distances h'"'"' from the respective intersections falling in the second region to the start intersection, said target intersection being defined as an intersection which is present outside of a circle having a predetermined radius and with the set destination as a center of the circle and which is nearest to the set destination, the estimated road distance h'"'"' being defined as a straight line distance from the start intersection to each intersection falling in the second region, and wherein said second route searching means first sets the road distance g of the target intersection to zero (0) and the road distances g of the other intersections except the target intersection to an infinity (+∞

), and starts the route search form the set destination, with the target intersection set as the center intersection, adds the road distance g0 from the target intersection to the center intersection to the road distance from the center intersection to the selected adjacent intersection, one of the intersections adjacent to the center intersection being selected as the adjacent intersection, to derive the road distance g1 from the target intersection to the selected adjacent intersection compares the road distance g1 with the road distance g2 stored as the road distance of the selected adjacent intersection in the route search result storing means, changes the road distance g2 of the adjacent intersection to the road distance g1 when the road distance g1 is smaller than the road distance g2, sets the center intersection as the preceding intersection B of the selected adjacent intersection, calculates and stores the estimated road distance h'"'"' from the selected adjacent intersection to the start intersection, sets one of the intersections falling in the second region which has a least value of a sum (g+h'"'"') between the road distance g from the target intersection thereto and the estimated road distance h'"'"' from the one intersection to the start intersection as the next new center intersection when the above-described series of the processing for all of the adjacent intersections to the center intersection are ended, executes the above-described series of processing for the next new center intersection, so that the second route searching means searches for the optimum routes from the set destination to the respective intersections falling in the second region, sequentially sets the new center intersections in the order such that the sum (g+h'"'"') becomes smaller, derives a sum (g+h) between the road distance g of the selected adjacent intersection from the target intersection and the road distance h of the selected adjacent intersection from the start intersection when the selected adjacent intersection has reached to the intersection at which the optimum route search from the start intersection is ended by the first route searching means, compares the sum (g+h) with the road distance g3 from the start intersection to the start intersection, changes the road distance g3 of the start intersection to (g+h) when the road distance (g+h) is smaller than the road distance g3, and sets the finally selected adjacent intersection as the preceding intersection B to the start intersection, the preceding intersection B is defined as a contacting intersection between the first region and second region, and ends the optimum route search when the start intersection gives the center intersection the optimum route connecting between the start intersection and the target intersection having the least value of the road distance from the target intersection to the start intersection via the preceding intersections B.

26. A system for a vehicular travel route guidance to a destination to which the vehicle occupant desires to reach from a present position of the vehicle as claimed in claim 25, wherein said second route searching means ends the optimum route search when the selected center intersection has reached to the contacting intersection.

27. A system for a vehicular travel route guidance to a destination to which the vehicle occupant desires to reach from a present position of the vehicle as claimed in claim 26, wherein said first route searching means searches the optimum route from the start intersection to the respective intersections falling in the first region, said first region being within a first layer having a boundary radius of H1 previously set and first route searching means searches the optimum route until the selected center intersection has reached within an n-th layer (n denotes arbitrary integer), the preceding intersection to the selected adjacent intersection being defined as a parent intersection.

28. A system for a vehicular travel route guidance to a destination to which the vehicle occupant desires to reach from a present position of the vehicle as claimed in claim 27, wherein said first route searching means searches the optimum routes from the start intersection to the selected adjacent intersection until the selected adjacent intersection has reached to the center intersection falling in the n-th layer and the predetermined time set by the time has passed.

29. A system For a vehicular travel route guidance to a destination to which the vehicle occupant desires to reach from a present position of the vehicle as claimed in claim 28, wherein said second route searching means ends the optimum route search from the set destination to the respective intersections surrounding the target intersection when the searched intersection has reached to the selected center intersection in the n-th layer at which the route search carried out by the first route searching means is ended.

30. A system for a vehicular travel route guidance to a destination to which the vehicle occupant desires to reach from a present position of the vehicle as claimed in claim 29, wherein if the set destination corresponds to one of registered points of locations stored in points of locations registering means, the optimum route from the present position of the vehicle which has been registered in the points of locations registering means to the set destination is immediately displayed on the display unit image screen.