# US 2010/0138096 A1 · Patrol Device And Patrol Path Planning Method For The Same

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2010/0138096 A1
- Document ID: US20100138096A1
- Status: Published application
- Kind: A1
- Application number: 12/507,747
- Filed: 2009-07-22
- Published: 2010-06-03
- Earliest claimed: 2008-11-28
- Assignees: National Taiwan University
- Inventors: Wei-Han Hung; Shih-Chung Kang; Peter Liu
- Web page: https://patentgrep.com/patent/US20100138096A1

## CPC

- G05D 1/648: Performing a task within a working area or space, e.g. cleaning
- G05D 1/0274: {using mapping information stored in a memory device (navigation using map-matching G01C21/30)}
- G05D: SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES

## 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

### Claim 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.

### Claim 2 (depends on 1)

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.

### Claim 3 (depends on 2)

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.

### Claim 4 (depends on 3)

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.

### Claim 5 (depends on 3)

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.

### Claim 6 (depends on 3)

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).

### Claim 7 (depends on 6)

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

### Claim 8 (depends on 6)

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

### Claim 9 (depends on 8)

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.

### Claim 10 (depends on 1)

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.

### Claim 11 (depends on 1)

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

### Claim 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.

### Claim 13 (depends on 12)

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.

### Claim 14 (depends on 13)

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.

### Claim 15 (depends on 12)

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.

### Claim 16 (depends on 15)

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.

### Claim 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.

### Claim 18 (depends on 17)

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.

### Claim 19 (depends on 17)

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

### Claim 20 (depends on 17)

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.
