PATH SEARCHING METHOD AND PATH SEARCH DEVICE

• US 20130245940A1
• Filed: 03/12/2013
• Published: 09/19/2013
• Est. Priority Date: 03/15/2012
• Status: Active Grant

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: SHINAGAWA, Akio, Tamai, Kyohei
• Granted Patent: US 9,482,543 B2
• Time in Patent Office: Days
• US Class Current: 701/527
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes
• CPC Class Codes: G06N 5/01 Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound

Abstract

A computer determines to which of a plurality of levels each of a plurality of road types for which a path search is performed corresponds, according to a distance between a departure point and a destination point. Next, the computer performs a first path search for the road type associated with a first level from the departure point to the destination point, and a second path search for the road type associated with the first level from the destination point to the departure point. Then, the computer performs a third path search for the road type associated with a second level according to a point obtained in the first path search and a point obtained in the second path search, and generates path information according to a result of the first path search, the second path search, and the third path search.

Claims

1. A path searching method performed by a computer, the method comprising:

determining to which of a plurality of levels each of a plurality of road types for which a path search is performed corresponds, according to a distance between a departure point and a destination point;

performing, by using a processor, a first path search for the road type associated with a first level among the plurality of levels from the departure point to the destination point, and a second path search for the road type associated with the first level from the destination point to the departure point;

performing, by using the processor, a third path search for the road type associated with a second level among the plurality of levels according to a point obtained in the first path search and a point obtained in the second path search; and

generating path information according to a result of the first path search, the second path search, and the third path search.

2. The path searching method according to claim 1, wherein

the determining to which of the plurality of levels each of the plurality of road types corresponds includes determining that a same road type belongs to a different level among the plurality of levels depending on which of a plurality of range scales the distance belongs to.

3. The path searching method according to claim 1, further comprising

when the distance belongs to a specific range scale among a plurality of classified range scales and a road associated with a level other than a specific level among the plurality of levels exists between two roads that are associated with the specific level, changing the level of the road associated with the level other than the specific level to the specific level.

4. A path search device comprising

a processor that:

determines to which of a plurality of levels each of a plurality of road types for which a path search is performed corresponds, according to a distance between a departure point and a destination point;

performs a first path search for the road type associated with a first level among the plurality of levels from the departure point to the destination point, and a second path search for the road type associated with the first level from the destination point to the departure point;

performs a third path search for the road type associated with a second level among the plurality of levels according to a point obtained in the first path search and a point obtained in the second path search; and

generates path information according to a result of the first path search, the second path search, and the third path search.

5. A computer-readable recording medium having stored therein a program for causing a computer to execute a process comprising:

determining to which of a plurality of levels each of a plurality of road types for which a path search is performed corresponds, according to a distance between a departure point and a destination point;

performing a first path search for the road type associated with a first level among the plurality of levels from the departure point to the destination point, and a second path search for the road type associated with the first level from the destination point to the departure point;

performing a third path search for the road type associated with a second level among the plurality of levels according to a point obtained in the first path search and a point obtained in the second path search; and

generating path information according to a result of the first path search, the second path search, and the third path search.