Intelligent navigation device and method

• US 20090157301A1
• Filed: 05/06/2008
• Published: 06/18/2009
• Est. Priority Date: 12/14/2007
• Status: Active Grant

• Current Assignee: Quanta Computer
• Original Assignee: Quanta Computer
• Inventors: Chen, Jie-Min, Tien, Kai-Wen
• Granted Patent: US 8,543,327 B2
• Time in Patent Office: Days
• US Class Current: 701/204
• CPC Class Codes: G01C 21/3492 employing speed data or traffic data, e.g. real-time or historical traffic control systems for road vehicles involving transmission of navigation instructions to the vehicle G08G1/0968

Abstract

The invention discloses an intelligent navigation method comprising the following steps of: (a) defining a system circle based on a current position and a target position; (b) searching a plurality of paths between the current position and the target position from the system circle; (c) for each path, calculating a total of directional paths and a total of path-influenced factors; (d) summing up the total of directional paths and the total of path-influenced factors for each path to obtain a plurality of summations; and (e) selecting a path corresponding to the minimum of all summations to be the optimal path.

Claims

1. An intelligent navigation method comprising steps of:

(a) defining a system circle according to a current position and a target position;

(b) searching a plurality of paths between the current position and the target position from the system circle;

(c) calculating a total of directional paths and a total of path-influenced factors for each path;

(d) summing up the total of directional paths and the total of path-influenced factors for each path to obtain a plurality of summations; and

(e) selecting one path corresponding to a minimum of all summations as an optimal path.

2. The method of claim 1, wherein the system circle is defined by steps of:

connecting the current position with the target position to be a first line segment;

selecting a middle point between the current position and the target position;

moving the middle point toward the target position along the first line segment; and

taking the middle point as a center of a circle, taking a second line segment between the current position and the middle point as a radius of the circle, and once the circle covers at least one street around the target position, assuming that the middle point is a center of the system circle, and the second line segment is a radius of the system circle.

3. The method of claim 1, wherein the system circle is defined by steps of:

selecting a plurality of paths between the current position and the target position;

defining a polygon according to the paths;

connecting the current position with a plurality of vertexes of the polygon around the target position, so as to obtain a plurality of triangles;

calculating a circumcenter coordinate of each triangle; and

averaging the circumcenter coordinates of the triangles to obtain an averaged coordinate as a center of the system circle, and a line segment between the averaged coordinate and the current position as a radius of the system circle.

4. The method of claim 1, wherein for one of the paths in step (c), the total of directional paths is calculated by steps of:

dividing the path into a plurality of sections; and

respectively calculating a directional path for each section, and summing up the directional paths to obtain the total of directional paths.

5. The method of claim 1, wherein in step (c), the total of path-influenced factors is calculated by steps of:

obtaining a plurality of peripheral roads according to the system circle; and

respectively calculating a path-influenced factor for each peripheral road, and summing up the path-influenced factors to obtain the total of path-influenced factors.

6. The method of claim 5, wherein the path-influenced factor is calculated by following formula:

$\mathrm{\Delta <br><br>}<br><br><br><br>{\stackrel{\mathrm{\varpi <br><br>}}{A}}^{\mathrm{\prime <br><br>}}=\left(\frac{\stackrel{\mathrm{\varpi <br><br>}}{M}}{t}<br><br>\stackrel{\_}{C}+\frac{{\stackrel{\mathrm{\varpi <br><br>}}{M}}^{\mathrm{\prime <br><br>}}}{t}<br><br>{\stackrel{\_}{C}}^{\mathrm{\prime <br><br>}}<br><br>P\right)<br><br>\mathrm{\Delta <br><br>}<br><br><br><br>t_s+\frac{\stackrel{\mathrm{\varpi <br><br>}}{M}}{t}<br><br>\stackrel{\_}{C}<br><br>\mathrm{\Delta <br><br>}<br><br><br><br>t_f$

wherein M/t represents a vehicle flow rate (per unit time) in one section of the current position;

C represents an averaged vehicle length in the section of the current position;

M ′

/t represents a vehicle flow rate (per unit time) in the peripheral road;

C ′

represents an averaged vehicle length in the peripheral road;

Δ

t_s represents a time obtained by dividing a path length by an averaged vehicle speed in the section of the current position;

Δ

t_f represents a time between unallowable and allowable passing controlled by a traffic light in the section of the current position;

P represents a probability that one vehicle drives to a certain section in the peripheral road.

7. The method of claim 1, further comprising steps of:

calculating a comparison factor a;

$a=\frac{W}{K}<br><br>\stackrel{\_}{C},$

 

wherein W represents an amount of vehicles between the current position and a traffic light ahead, K represents an amount of lanes in the section of the current position, and C represents an averaged vehicle length in the section of the current position;

calculating a distance d, the distance d being between the current position and the traffic light ahead or a path length of a certain section;

if d>

a, and d is far from a, according to d−

a=V×

T′

, calculating a first estimative time T′

, wherein V represents an averaged vehicle speed in the section;

if d≦

a, or d is close to a, and the traffic light ahead allows vehicles to pass

$\frac{d}{V}=T^{\mathrm{″<br><br>}},$

 

through, according to calculating a second estimative time T″

; and

if d≦

a, or d is close to a, and the traffic light ahead unallowing vehicles to pass through, according to T″

+Δ

t_f′

=T′

″

, calculating a third estimative time T′

″

, wherein Δ

t_f′

represents a time between unallowable and allowable passing controlled by a traffic light in the section.

8. The method of claim 7, further comprising steps of:

receiving a dynamic information; and

examining whether the dynamic information influences the optimal path or not;

if yes, re-estimating the optimal path.

9. An intelligent navigation comprising steps of:

(a) defining a system circle according to a current position and a target position;

(b) searching a plurality of paths between the current position and the target position in the system circle;

(c) dividing each path into a plurality of sections;

(d) respectively calculating an estimative time for each section;

(e) according to the estimative time, calculating a driving time corresponding to each path; and

(f) selecting one path corresponding to a minimum of the driving time as an optimal path.

10. The method of claim 9, wherein the system circle is defined by steps of:

connecting the current position with the target position to be a first line segment;

selecting a middle point between the current position and the target position;

moving the middle point toward the target position along the first line segment; and

taking the middle point as a center of a circle, taking a second line segment between the current position and the middle point as a radius of the circle, and once the circle covers at least one street around the target position, assuming that the middle point is a center of the system circle and the second line segment is a radius of the system circle.

11. The method of claim 9, wherein the system circle is defined by steps of:

selecting a plurality of paths between the current position and the target position;

defining a polygon according to the paths;

connecting the current position with a plurality of vertexes of the polygon around the target position, so as to obtain a plurality of triangles;

calculating a circumcenter coordinate of each triangle; and

averaging the circumcenter coordinates of the triangles to obtain an averaged coordinate as a center of the system circle, and a line segment between the averaged coordinate and the current position as a radius of the system circle.

12. The method of claim 9, wherein step (d) further comprises steps of:

calculating a comparison factor a;

$a=\frac{W}{K}<br><br>\stackrel{\_}{C},$

 

wherein W represents an amount of vehicles between the current position and a traffic light ahead, K represents an amount of lanes in the section of the current position, C represents an averaged vehicle length in the section of the current position;

calculating a distance d, the distance d being between the current position and the traffic light ahead or a path length of a certain section;

if d>

a, and d is far from a, according to d−

a=V×

T′

, calculating a first estimative time T′

, wherein V represents an averaged vehicle speed in the section;

if d≦

a, or d is close to a, and the traffic light ahead allowing vehicles to pass through, then according to

$\frac{d}{V}=T^{\mathrm{″<br><br>}},$

 

calculating a second estimative time T″

; and

if d≦

a, or d is close to a, and the traffic light ahead unallowing vehicles to pass through, according to T″

+Δ

t_f′

=T′

″

, calculating a third estimative time T′

″

, wherein Δ

t_f′

represents a time between unallowable and allowable passing controlled by a traffic light in the section.

13. The method of claim 12, further comprising steps of:

receiving a dynamic information; and

examining whether the dynamic information influences the optimal path or not;

if yes, re-estimating the optimal path.

14. An intelligent navigation device comprising:

an input module for inputting a target position;

a wireless communication module for receiving a vehicle flow rate;

a position module for determining a current position;

a control module, according to the current position and the target position, for defining a system circle, so as to determine an optimal path; and

a display module for displaying the optimal path.

15. The intelligent navigation device of claim 14, wherein the control module further searches a plurality of paths between the current position and the target position, the control module calculates a total of directional paths and a total of path-influenced factors for each of the paths, the control module sums up the total of directional paths and the total of path-influenced factors corresponding to each path, so as to obtain a plurality of summations, and the control module selects one path corresponding to a minimum of all summations to be the optimal path.

16. The intelligent navigation device of claim 14, wherein the control module searches a plurality of paths between the current position and the target position in the system circle, the control module divides each path into a plurality of sections, the control module respectively calculates an estimative time for each section, the control module, according to the estimative time, calculates a driving time corresponding to each path and selects one path corresponding to a minimum of the driving time to be the optimal path.

17. The intelligent navigation device of claim 14, wherein the control module defines the system circle by steps of:

connecting the current position with the target position to be a first line segment;

selecting a middle point between the current position and the target position;

moving the middle point toward the target position along the first line segment; and

taking the middle point as a center of a circle, taking a second line segment between the current position and the middle point as a radius of the circle, and once the circle covers at least one street around the target position, assuming that the middle point is a center of the system circle, and the second line segment is a radius of the system circle.

18. The intelligent navigation device of claim 14, wherein the control module defines the system circle by steps of:

selecting a plurality of paths between the current position and the target position;

defining a polygon according to the paths;

connecting the current position with a plurality of vertexes of the polygon around the target position, so as to obtain a plurality of triangles;

calculating a circumcenter coordinate of each triangle; and

averaging the circumcenter coordinates of the triangles to obtain an averaged coordinate as a center of the system circle, and a line segment between the averaged coordinate and the current position being as a radius of the system circle.

19. The intelligent navigation device of claim 14, wherein the wireless communication module receives a dynamic information, the control module examines whether the dynamic information influences the optimal path or not;

if yes, the control module re-estimate the optimal path.

20. The intelligent navigation device of claim 14, communicating with an information-shared system via a wireless communication network, wherein the information-shared system provides the vehicle flow rate for the intelligent navigation device.