Patrol device and patrol path planning method for the same

• US 8,396,620 B2
• Filed: 07/22/2009
• Issued: 03/12/2013
• Est. Priority Date: 11/28/2008
• Status: Active Grant

• Current Assignee: National Taiwan University (Government of The Republic of China)
• Original Assignee: National Taiwan University (Government of The Republic of China)
• Inventors: Hung, Wei-Han, Kang, Shih-Chung, Liu, Peter
• Primary Examiner(s): Black, Thomas
• Assistant Examiner(s): PAYNE, ROBERT T
• Application Number:
  US12/507,747
• Publication Number:
  US 20100138096A1
• Time in Patent Office: 1,329 Days
• Field of Search: 701/25, 702/187, 700/245, 700/248, 340/10.6, 340/3.3, 318/568.12, 318/568.19
• US Class Current: 701/25
• CPC Class Codes: G05D 1/0214 in accordance with safety or protection criteria, e.g. avoiding hazardous areas monitoring the location of vehicles within a certain area, e.g. forbidden or allowed areas, in traffic control systems for road vehicles G08G1/13
• CPC Class Codes: G05D 1/0274 using mapping information stored in a memory device navigation using map-matching G01C21/30

Abstract

The present invention relates to a patrol device and a patrol path planning method. The patrol device includes an operating unit configured to establish a plurality of patrol paths, each of which has an Average Patrol Omission (APO) value and an Average Patrol Quality (APQ) value, and to determine an optimum patrol path from the plurality of patrol paths according to the APO value and the APQ value; and a moving unit configured to move along the optimum patrol path. The method includes providing a plurality of patrol paths, each of which has an Average Patrol Omission (APO) value and an Average Patrol Quality (APQ) value; and evaluating the plurality of patrol paths according to the respective APO values and the respective APQ values so as to select an optimum patrol path therefrom.

Claims

1. A patrol path planning method, comprising the steps of:

setting an Allowed Vacant Time (AVT);

providing a plurality of patrol paths, each of which passes through a plurality of patrol regions, each of which has a Patrol Omission (PO) value determined by whether the respective passed patrol region is patrolled or not within the AVT and a Patrol Quality (PQ) value determined by a ratio of an average time per patrol for the respective passed patrol region to the AVT;

obtaining an Average Patrol Omission (APO) value and an Average Patrol Quality (APQ) value for each of the plurality of patrol paths; and

evaluating the plurality of patrol paths according to the respective APO values and the respective APQ values so as to select an optimum patrol path therefrom.

2. A planning method as claimed in claim 1 further comprising the steps of:

providing the plurality of patrol regions; and

providing a plurality of possible paths each of which connects all of the plurality of patrol regions.

3. A planning method as claimed in claim 2 further comprising the steps of:

determining the plurality of patrol paths according to the plurality of possible paths by an algorithm based on a directed graph; and

calculating all the APO values and all the APQ values of the plurality of patrol paths to select the optimum patrol path.

4. A planning method as claimed in claim 3, wherein the directed graph having the plurality of patrol regions and a plurality of passages for an operation of the algorithm.

5. A planning method as claimed in claim 3, wherein the plurality of possible paths have a plurality of path combinations to be the plurality of patrol paths.

6. A planning method as claimed in claim 3, wherein the algorithm is one of a Shortest Path Permutation Method (SPPM) and a Locally Optimum Repetitious Method (LORM).

7. A planning method as claimed in claim 6, wherein the SPPM is performed by a Dijkstra algorithm.

8. A planning method as claimed in claim 6, wherein the LORM is performed by a Patrol Depth First Search (P-DFS) algorithm.

9. A planning method as claimed in claim 8, wherein the P-DFS algorithm uses at least one of a Patrol Time (PT) and a Repeat Limit (RL) as an operating limitation.

10. A planning method as claimed in claim 1, wherein the APO value and the APQ value are respectively an average of the respective Patrol Omission values and an average of the respective Patrol Quality values of the plurality of passed patrol regions of the corresponding patrol path.

11. A planning method as claimed in claim 1, wherein the optimum patrol path is provided to a robot for moving accordingly.

12. A route planning method, comprising the steps of:

providing a plurality of patrol paths and a plurality of selected patrol regions each of which has a Patrol Omission (PO) value and a Patrol Quality (PQ) value, wherein the PO value is determined based on whether the respective selected patrol region is patrolled or not within an Allowed Vacant Time (AVT) and the PQ value is determined based on a ratio of an average time per patrol for the respective selected patrol region to the AVT; and

selecting an optimum patrol path from the plurality of patrol paths according to one set of values selected from a group consisting of the respective PO values, the respective PQ values and a combination thereof.

13. A planning method as claimed in claim 12, wherein the plurality of patrol paths are provided by a Patrol Depth First Search (P-DFS) method.

14. A planning method as claimed in claim 13 further comprising using at least one of a Patrol Time (PT) and a Repeat Limit (RL) as an operating limitation of the P-DFS method.

15. A planning method as claimed in claim 12 further comprising a step of establishing a patrol model having a plurality of patrol regions and a plurality of possible patrol paths each of which connects at least two of the plurality of patrol regions.

16. A planning method as claimed in claim 15 further comprising the steps of:

providing the plurality of patrol paths according to the plurality of possible patrol paths by an algorithm; and

calculating the respective PO values and the respective PQ values to select the optimum patrol path.

17. A patrol device, comprising:

an operating unit configured to establish a plurality of patrol paths, each of which has an Average Patrol Omission (APO) value and an Average Patrol Quality (APQ) value, and to determine an optimum patrol path from the plurality of patrol paths according to the APO value and the APQ value, wherein each of the plurality of patrol paths passes through a plurality of regions, each of which has a Patrol Omission (PO) value determined based on whether the respective region is patrolled or not within an Allowed Vacant Time (AVT) and a Patrol Quality (PQ) value determined based on a ratio of an average time per patrol for the respective region to the AVT; and

a moving unit configured to move along the optimum patrol path.

18. A patrol device as claimed in claim 17, wherein the operating unit is one selected from a group consisting of a desktop computer, a notebook computer, an industrial computer and an electrical device having an operating processor, the APO value and the APQ are calculated by the operating unit, and the moving unit is a vehicle.

19. A patrol device as claimed in claim 17 further configured in a robot.

20. A patrol device as claimed in claim 17, wherein the operating unit establishes a patrol model having the plurality of patrol paths, and the moving unit receives a moving command from the operating unit so as to move along the optimum patrol path.