Vehicle navigation apparatus employing node selection, comparison and elimination techniques

• US 5,109,344 A
• Filed: 04/25/1989
• Issued: 04/28/1992
• Est. Priority Date: 04/28/1988
• Status: Expired due to Term

• Current Assignee: Mazda Motor Corporation
• Original Assignee: Mazda Motor Corporation
• Inventors: Sasaki, Masao, Kakihara, Masaki
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): AUCHTERLONIE, THOMAS
• Application Number:
  US07/342,951
• Time in Patent Office: 1,099 Days
• Field of Search: 364/443, 364/444, 364/449, 364/450, 340/988, 340/990, 340/995, 340/992, 342/451, 73/178 R
• US Class Current: 701/209
• CPC Class Codes: G01C 21/30 Map- or contour-matching

Abstract

A vehicle navigation apparatus which selects possible target nodes stored in memory based on the present position of the vehicle and then eliminates those nodes not possible to reach after comparing the bearing from the present position of the vehicle to each selected node with the present bearing of the vehicle. The navigation apparatus determines that the vehicle is traveling on a road-not-in-memory when the number of possible nodes is reduced to zero. The navigation apparatus repeatedly searches, after each predetermined travel distance, for possible nodes within a progressively widening search circle, the radius of which is related to the distance traveled. When a target is found which is stored in memory the apparatus determines that the vehicle has returned to travel on a road stored in memory.

Claims

1. An apparatus for navigating a vehicle, comprising:

direction detection means for detecting the direction in which the vehicle is traveling;

distance detection means for detecting the distance traveled from a start node;

vehicle position assuming means for assuming the present position of the vehicle relative to a reference position on the basis of data on the traveling direction and the traveled distance detected by said means;

map information storage means for previously storing map information including data, on the positions of a multiplicity of nodes set on roads and connections therebetween, said nodes including said start node;

node selection means for selecting nodes which are directly linked to the start node on the basis of the connection data from among said multiplicity of nodes set on roads;

node bearing calculating means for calculating the bearing from the present position of the vehicle obtained by said vehicle position assuming means to each of said nodes selected by said node selection means;

comparison means for comparing the bearing to each of said nodes selected by said node selection means with the vehicle traveling direction obtained by said direction detection means; and

node elimination means for eliminating nodes judged to be impossible to select as target nodes from among the nodes selected by said node selection means on the basis of the result of the comparison effected by said comparison means.

2. An apparatus according to claim 1, further comprising control means for controlling said node selection means so that said selection means can select nodes which are connected to the start node each time the vehicle is determined to have reached the start node and maintains the selected nodes until eliminated by said elimination means.

3. An apparatus according to claim 1, further comprising:

means for calculating the distance between a single remaining node after said node elimination means has eliminated all other nodes and the vehicle position assumed by said vehicle position assuming means, and means for comparing this distance with a predetermined first threshold value, and wherein it is determined that said single node remaining uneliminated is a node reached by the vehicle when said distance between said selected node and the present position becomes smaller than said first threshold value.

4. An apparatus according to claim 1, further comprising:

control means for activating said node bearing calculation means, said node selection means and said node elimination means each time the vehicle travels a predetermined distance.

5. An apparatus according to claim 1, wherein said comparison means further:

calculates the angles of said bearings calculated by said node bearing calculating means, with respect to the present direction of the vehicle detected by said direction detection means,

divides said angles with the traveled distance detected by said distance, and

compares the quotients of the division with a predetermined value, and

said node elimination means determines that, when said quotients are larger than said predetermined value, the corresponding nodes should be eliminated.

6. An apparatus according to claim 1, wherein said comparison means further:

calculates the angles of said bearings calculated by said node bearing calculating means with the present direction of the vehicle detected by said direction detection means,

divides said angles by the traveled distance detected by said distance detection means,

multiplies said angles by a weight function the value of which increases as said angle increases, and

compares the product of the multiplication with a predetermined value, and

said node elimination means determines that, when said products are larger than said predetermined value, the corresponding nodes should be eliminated.

7. An apparatus for navigating a vehicle, comprising:

direction detection means for detecting the direction in which the vehicle is traveling;

distance detection means for detecting the distance traveled;

vehicle position assuming means for assuming the present position of the vehicle relative to a reference position on the basis of data on the traveling direction and the traveled distance detected by said means;

map information storage means for previously storing map information including data, on the positions of a multiplicity of nodes set on roads and connections therebetween;

road-in-memory assuming means for assuming, on the basis of said present position of the vehicle and the connections between said nodes stored in said storage means, that the vehicle is traveling on a road-in-memory connecting nodes stored in said storage means;

distance calculation means for calculating the distance between the present position of the vehicle and the road-in-memory assumed by road-in-memory assuming means; and

determination means for determining when the calculated distance becomes larger than a predetermined second threshold value, that the vehicle is traveling a road-not-in-memory, said second threshold value increasing in response to the increase in the traveled distance.

8. An apparatus according to claim 7, further comprising:

node bearing calculating means for calculating the bearing from the present position of the vehicle obtained by said vehicle position assuming means to each of said nodes stored in said storage means;

node selection means for comparing the bearing to each of said nodes with the vehicle traveling direction obtained by said direction detection means, and for selecting, on the basis of the results of said comparison, one of said nodes toward which the vehicle is proceeding;

control means for controlling said node bearing calculation means and said node selection means so as to activate the same each time the vehicle travels a predetermined distance; and

elimination means, operating under the control of said control means, for eliminating nodes judged to be impossible to select as target nodes on the basis of the result of the comparison effected by said node selection means;

wherein, when the number of remaining nodes becomes naught, as a result of elimination effected by said node elimination means, it is determined that the vehicle is traveling along a road-not-in-memory.

9. An apparatus according to claim 7, further comprising:

means for storing the position of a point on a road-not-in-memory which the vehicle has entered after traveling along a road in memory, if said determination means determines that the vehicle is traveling along a road not in memory;

means for calculating the distance traveled from said point;

means for setting an area related to the distance traveled from said point;

means for seeking a node stored within said set area; and

means for calculating the distance between the vehicle position and the node found in said area and comparing this distance with a third threshold value;

whereby, when the distance to said node found in said area becomes smaller than said third threshold value, it is determined that the vehicle has proceeded from the road not in memory to a road in memory.

10. An apparatus according to claim 9, wherein said area corresponding to the traveled distance is a circular region proportional to the traveled distance.

11. An apparatus for navigating a vehicle, comprising:

direction detection means for detecting the direction in which the vehicle is traveling;

distance detection means for detecting the distance traveled;

vehicle position assuming means for assuming the present position of the vehicle relative to a reference position on the basis of data on the traveling direction and the traveled distance detected by said means;

map information storage means for previously storing map information data on the positions of a multiplicity of nodes set on roads;

bearing storage means for storing, as a first bearing, the direction detected by said direction detection means;

means for recognizing that the vehicle has started turning on the basis of the direction detected by said direction detection means;

means activated after said recognition of the start of turning to recognize that a portion of the road along which the vehicle is traveling is straight, and to calculate the average of bearings obtained from said direction detection means as the vehicle passes said portion of the road; and

means for comparing the difference between said average of bearings and said first bearing with a predetermined threshold value, and

for determining when the average of bearings is larger than said threshold value that the vehicle has passed a corner and for determining that the vehicle has passed a curve other than a corner when the difference between said first bearing and said average of bearings has exceeded a threshold value a predetermined number of times.