Patrol Device And Patrol Path Planning Method For The Same

• US 20100138096A1
• Filed: 07/22/2009
• Published: 06/03/2010
• 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, Liu, Peter, Kang, Shih-Chung
• Granted Patent: US 8,396,620 B2
• Time in Patent Office: Days
• 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:

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.

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

providing a 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 each of the plurality of patrol paths passes through a plurality of passed patrol regions each of which has a Patrol Omission value and a Patrol Quality value, and 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; 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; 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.