Navigation systems and route planning methods thereof

• US 8,396,666 B2
• Filed: 01/12/2009
• Issued: 03/12/2013
• Est. Priority Date: 08/07/2008
• Status: Active Grant

• Current Assignee: IP3 2017, Series 200 of Allied Security Trust I (Allied Security Trust)
• Original Assignee: MiTAC International Corporation (MiTAC Holdings Corp.)
• Inventors: Lee, Ai-Chieh
• Primary Examiner(s): ALMATRAHI, FARIS S
• Application Number:
  US12/352,558
• Publication Number:
  US 20100036602A1
• Time in Patent Office: 1,520 Days
• Field of Search: None
• US Class Current: 701/533
• CPC Class Codes: G01C 21/3415 Dynamic re-routing, e.g. recalculating the route when the user deviates from calculated route or after detecting real-time traffic data or accidents

Abstract

Route planning methods for navigating an electronic device having a navigation system from a starting point to a destination are disclosed. The method comprises the following steps. First, current position of the electronic device is acquired. Next, a decision point corresponding to the current position is obtained in a planned route in which the decision point has a dedicated moving direction which is planned by the planned route and a plurality of possible moving directions. Accordingly, pluralities of candidate routes, destined to the destination, corresponding to the possible moving directions are generated. Next, the electronic device is navigated to the destination using the planned route or one of the candidate routes.

Claims

1. A route planning method for use in an electronic device having a navigation system for navigating from a starting point to a destination, comprising:

acquiring current position of the electronic device;

obtaining a decision point corresponding to the current position in a planned route, wherein the decision point has a dedicated moving direction which is planned by the planned route and a plurality of possible moving directions;

generating a plurality of candidate routes, destined to the destination, corresponding to all of the possible moving directions; and

navigating the electronic device to the destination by utilizing the planned route or one of the candidate routes,

wherein the candidate routes to the destination corresponding to all of the possible moving directions are planned in advance so that one of the pre-planned candidate routes is used as a replacement route to immediately replace the originally planned route without any calculation for route re-planning when moving through the decision point and deviating from the dedicated moving direction planned by the planned route.

2. The route planning method of claim 1, wherein the candidate routes are generated when moving between the starting point and the decision point.

3. The route planning method of claim 1, wherein the step of navigating the electronic device to the destination by utilizing the planned route or one of the candidate routes further comprises:

proceeding to navigate the electronic device to the destination utilizing the planned route when moving through the decision point and following the dedicated moving direction planned by the planned route.

4. The route planning method of claim 3, further comprising:

generating a plurality of second candidate routes, destined to the destination, corresponding to possible moving directions of a next decision point that is located between the decision point and the destination; and

replacing the planned route with one of the second candidate routes and navigating the electronic device to the destination utilizing the replaced second candidate route when moving through the next decision point and deviating from the dedicated moving direction planned by the planned route.

5. A navigation system for use in an electronic device, comprising:

a display unit;

a processing unit, acquiring current position of the electronic device and obtaining a decision point corresponding to the current position in a planned route, wherein the decision point has a dedicated moving direction which is planned by the planned route and a plurality of possible moving directions; and

a route planning unit, generating a plurality of candidate routes, destined to the destination, corresponding to all of the possible moving directions,

wherein the processing unit navigates the electronic device to the destination by utilizing the planned route or one of the candidate routes when moving through the decision point and wherein the candidate routes to the destination corresponding to all of the possible moving directions are planned in advance so that the processing unit selects one of the pre-planned candidate routes as a replacement route to immediately replace the originally planned route without any calculation for route re-planning and navigates the electronic device to the destination utilizing the selected candidate route when moving through the decision point and deviating from the dedicated moving direction planned by the planned route.

6. The navigation system of claim 5, wherein the candidate routes are generated by the route planning unit while moving between the starting point and the decision point.

7. The navigation system of claim 5, wherein the processing unit deletes the candidate routes and proceeds to navigate the electronic device to the destination utilizing the planned route when moving through the decision point and following the dedicated moving direction planned by the planned route.

8. The navigation system of claim 7, wherein the route planning unit further generates a plurality of second candidate routes, destined to the destination, corresponding to possible moving directions of a next decision point that is located between the decision point and the destination and, when moving through the next decision point and deviating from the dedicated moving direction planned by the planned route, the processing unit replaces the planned route with one of the second candidate routes and navigates the electronic device to the destination utilizing the replaced second candidate route.

9. A route planning method for use in an electronic device having a navigation system for navigating from a starting point to a destination, comprising:

planning a first route according to the starting point and the destination, wherein the first route comprises at least one decision point, and the decision point has a dedicated moving direction which is planned by the first route and a plurality of possible moving directions;

pre-planning a plurality of second candidate routes, destined to the destination, corresponding to the possible moving directions when moving between the starting point and the decision point; and

selecting a replacement route from the second candidate routes to immediately replace the first route without any calculation for route re-planning and navigating the electronic device to the destination utilizing the replacement route when moving through the decision point and deviating from the dedicated moving direction planned by the first route.

10. The route planning method of claim 9, wherein the step of selecting a replacement route from the second candidate routes further comprises:

acquiring current position of the electronic device; and

obtaining the replacement route from the second candidate routes according to the current position of the electronic device.

11. The route planning method of claim 10, further comprising:

obtaining a first decision point corresponding to the current position, wherein the first decision point has a dedicated moving direction which is planned by the replacement route and a plurality of possible moving directions;

planning a plurality of third candidate routes, destined to the destination, corresponding to the possible moving directions; and

replacing the replacement route with one of the third candidate routes and navigating to the destination utilizing the replaced third candidate route when moving through the decision point and deviating from the dedicated moving direction planned by the replacement route.

12. The route planning method of claim 9, further comprising:

deleting the second candidate routes and proceeding to navigate to the destination utilizing the first route when moving through the decision point and following the dedicated moving direction planned by the first route.

13. The route planning method of claim 12, further comprising:

planning a plurality of third candidate routes, destined to the destination, corresponding to possible moving directions of a next decision point that is located between the decision point and the destination; and

replacing the first route with one of the third candidate routes and navigating to the destination utilizing the replaced third candidate route when moving through the next decision point and deviating from the dedicated moving direction planned by the first route.

14. A non-transitory machine-readable storage medium comprising a computer program, which, when executed, causes a device to perform a route planning method, and the method comprising:

generating a planned route, wherein the device performs a navigation process according to the planned route;

acquiring current position of the device;

obtaining a decision point corresponding to the current position in the planned route, wherein the decision point has a dedicated moving direction which is planned by the planned route and a plurality of possible moving directions;

generating a plurality of candidate routes, destined to the destination, corresponding to all of the possible moving directions; and

navigating the device to the destination by utilizing the planned route or one of the candidate routes,

wherein the candidate routes to the destination corresponding to all of the possible moving directions are planned in advance so that one of the pre-planned candidate routes is used as a replacement route to immediately replace the originally planned route without any calculation for route re-planning when moving through the decision point and deviating from the dedicated moving direction planned by the planned route.