Route guidance generation apparatus and method

• US 20020103599A1
• Filed: 01/29/2002
• Published: 08/01/2002
• Est. Priority Date: 01/30/2001
• Status: Active Grant

• Current Assignee: Fujitsu Mobile Communications Limited (Fujitsu Limited)
• Original Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Inventors: Sugiyama, Hiroshi, Doi, Miwako
• Granted Patent: US 6,490,522 B2
• Time in Patent Office: Days
• US Class Current: 701/211
• CPC Class Codes: G01C 21/20 Instruments for performing navigational calculations G01C21/24, G01C21/26 take precedence
• CPC Class Codes: G01C 21/3453 Special cost functions, i.e. other than distance or default speed limit of road segments

Abstract

An input unit indicates a departure point and a destination point on map information. A calculation unit extracts a plurality of routes each connected from the departure point to the destination point from the map information, and calculates a guidance demand degree of arbitrary points along each of the plurality of routes. A guidance demand degree is an evaluation value of the point based on a linearity of route, a complexity of route junction, and a change of route width. A route selection unit selects one route from the plurality of routes based on the guidance demand degree of each route. A guidance generation unit generates guidance information of the point decided to guide based on the guidance demand degree along the one route. A presentation unit presents the guidance information to a user.

Claims

1. A route guidance generation apparatus, comprising:

an input unit configured to indicate a departure point and a destination point on map information;

a calculation unit configured to extract a plurality of routes each connecting the departure point to the destination point from the map information, and to calculate a guidance demand degree for a plurality of guide points along each of the plurality of routes, the guidance demand degree reflecting an evaluation of the guide points based on linearity, complexity, and route width;

a route selection unit configured to select one route from the plurality of routes based on the guidance demand degree of each route;

a guidance generation unit configured to generate guidance information of each guide point along the selected route based on the guidance demand degree along the selected route; and

a presentation unit configured to present the guidance information to a user.

2. The route guidance generation apparatus according to claim 1,

further comprising a map information management unit configured to store the map information including a route network and landmark data, the route network including a plurality of nodes each arbitrarily located, each route line being connected between two nodes, and the landmark data including an attribute of each landmark used for guidance.

3. The route guidance generation apparatus according to claim 2,

wherein said calculation unit selects a first node neighboring the departure point and a second node neighboring the destination point from the plurality of nodes, extracts the plurality of routes each consisting of a plurality of route lines connected from the first node to the second node, and searches at least one intermediate node along each of the plurality of routes from said map information management unit.

4. The route guidance generation apparatus according to claim 3,

wherein said calculation unit recursively calculates a cost from a present node to the next node along each route, the cost including the guidance demand degree of the next node, a distance between the present node and the next node, and an existence degree of the landmark neighboring the next node, and calculates the sum of costs of all next nodes as the intermediate node along each route.

5. The route guidance generation apparatus according to claim 4,

wherein said route selection unit selects a route having the minimum sum of costs from the plurality of routes.

6. The route guidance generation apparatus according to claim 1,

wherein the linearity at a point is represented as a change angle between a first route line and a second route line along the route, and

wherein the guidance demand degree for the linearity is high in proportion to the change angle.

7. The route guidance generation apparatus according to claim 6, wherein

if a first branch line and a second branch line each not along the route cross at the point,

the complexity at the point is represented as a junction angle between the second route line and the first branch line or the second branch line, and

the guidance demand degree for the complexity is high in inverse proportion to the junction angle.

8. The route guidance generation apparatus according to claim 7, wherein

if the first route line and the second route line are wider than the first branch line and the second branch line,

the guidance demand degree for the route width is low.

9. The route guidance generation apparatus according to claim 8, wherein

if the width of one of the first route line and the second route line is the same as the width of one of the first branch line and the second branch line,

the guidance demand degree for the route width is high.

10. The route guidance generation apparatus according to claim 9, wherein

in case of calculating the guidance demand degree at a point having a low degree of complexity,

the guidance demand degree for the linearity is low.

11. The route guidance generation apparatus according to claim 10, wherein

if the first route line and the second route line are wider than the first branch line and the second branch line,

the guidance demand degree for the complexity and linearity are low.

12. The route guidance generation apparatus according to claim 5,

wherein said guidance generation unit selects at least one node having a cost above a threshold from a plurality of intermediate nodes along the one route, and generates the guidance information of the selected node.

13. The route guidance generation apparatus according to claim 12,

wherein the guidance information is one of a simplified map, a guidance sentence, a rally map, and a combination of the simplified map and the guidance sentence.

14. The route guidance generation apparatus according to claim 13,

wherein said guidance generation unit adds an explanation of feature of route as a principal reason of the guidance demand degree to the guidance information.

15. The route guidance generation apparatus according to 12,

wherein said guidance generation unit selects a presentation method of the guidance information based on the guidance demand degree of each selected node and the existence degree of the landmark neighboring each selected node, and

wherein said presentation unit proposes the presentation method to the user.

16. The route guidance generation apparatus according to claim 12, wherein

when said route selection unit cannot select a route, or decides that the route guidance is difficult based on the guidance demand degree of each selected node and the existence degree of the landmark neighboring each selected node,

said guidance generation unit generates a message representing that the route guidance is impossible instead of the guidance information.

17. The route guidance generation apparatus according to claim 1,

wherein said presentation unit interactively presents the guidance information of each guide point along the selected route in response to an inquiry from the user or a present location of the user.

18. The route guidance generation apparatus according to claim 17,

further comprising a guidance demand degree adjustment unit configured to detect the point of which the guidance demand degree is corrected based on an inquiry from the user, and to correct the user'"'"'s parameter of at least one of the linearity, complexity, and route width based on the guidance demand degree of the detected point.

19. A server apparatus, comprising:

a receiving unit configured to receive a route guidance request transmitted from a client terminal, the route guidance request including a departure point and a destination point;

a calculation unit configured to extract a plurality of routes each connecting the departure point to the destination point from map information, and to calculate a guidance demand degree for a plurality of guide points along each of the plurality of routes, the guidance demand degree reflecting an evaluation of the point based on linearity, complexity, and route width;

a route selection unit configured to select one route from the plurality of routes based on the guidance demand degree of each route;

a guidance generation unit configured to generate guidance information of each guide point along the selected route based on the guidance demand degree along the selected route; and

a transmitting unit configured to transmit the guidance information to the client'"'"'s terminal.

20. A route guidance generation method, comprising:

indicating a departure point and a destination point on map information;

extracting a plurality of routes each connecting the departure point to the destination point from the map information;

calculating a guidance demand degree for a plurality of guide points along each of the plurality of routes, the guidance demand degree reflecting an evaluation of the guide points based on linearity, complexity, and route width;

selecting one route from the plurality of routes based on the guidance demand degree of each route;

generating guidance information of each guide point along the selected route based on the guidance demand degree along the selected route; and

presenting the guidance information to a user.

21. A computer program product, comprising:

a computer readable program code embodied in said product for causing a computer to generate guidance information, said computer readable program code having;

a first program code to indicate a departure point and a destination point on map information;

a second program code to extract a plurality of routes each connecting the departure point to the destination point from the map information;

a third program code to calculate a guidance demand degree for a plurality of guide points along each of the plurality of routes, the guidance demand degree reflecting an evaluation of the guide points based on linearity, complexity, and route width;

a fourth program code to select one route from the plurality of routes based on the guidance demand degree of each route;

a fifth program code to generate guidance information of each guide point along the selected route based on the guidance demand degree along the selected route; and

a sixth program code to present the guidance information to a user.

22. An apparatus for supporting editing of map information used for generation of guidance information to guide a route from a departure point to a destination point, comprising:

an extraction unit configured to extract at least one point having a guidance demand degree above a threshold as an investigation needed point from a plurality of points, the guidance demand degree being calculated based on linearity, complexity, and route width on the map information, and to extract investigation contents of the investigation needed point by referring to the map information neighboring the investigation needed point; and

an output unit configured to output a list including the investigation needed point and the investigation contents.

23. A method for supporting editing of map information used for generation of guidance information to guide a route from a departure point to a destination point, comprising;

extracting at least one point having a guidance demand degree above a threshold as an investigation needed point from a plurality of points, the guidance demand degree being calculated based on linearity, complexity, and route width on the map information;

extracting investigation contents of the investigation needed point by referring to the map information neighboring the investigation needed point; and

outputting a list including the investigation needed point and the investigation contents.

24. A computer program product, comprising:

a computer readable program code embodied in said product for causing a computer to support editing of map information used for generation of guidance information to guide a route from a departure point to a destination point, said computer readable program code having;

a first program code to extract at least one point having a guidance demand degree above a threshold as an investigation needed point from a plurality of points, the guidance demand degree being calculated based on linearity, complexity, and route width on the map information;

a second program code to extract investigation contents of the investigation needed point by referring to the map information neighboring the investigation needed point; and

a third program code to output a list including the investigation needed point and the investigation contents.