Determining a patrol path

• US 9,285,232 B2
• Filed: 05/16/2013
• Issued: 03/15/2016
• Est. Priority Date: 05/30/2012
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Dong, Wei Shan, Duan, Ning, Fellows, Ronald, Li, Li, Sun, Wei, Wang, Zhi Hu, Zhou, Chang Jin
• Primary Examiner(s): Black, Thomas G
• Assistant Examiner(s): Lewandroski, Sara
• Application Number:
  US13/895,627
• Publication Number:
  US 20130325336A1
• Time in Patent Office: 1,034 Days
• Field of Search: 701/25, 701/26, 701/209, 701/210, 701/411, 701/533, 701/201, 701/202, 700/250, 700/253
• US Class Current: 1/1
• CPC Class Codes: G01C 21/3453 Special cost functions, i.e. other than distance or default speed limit of road segments
• CPC Class Codes: G01C 21/3461 Preferred or disfavoured areas, e.g. dangerous zones, toll or emission zones, intersections, manoeuvre types, segments such as motorways, toll roads, ferries

Abstract

A method of determining a path comprises obtaining a path in a road net, the road net comprising a plurality of nodes; calculating, with a processing device, an event displacement probability within coverage of the path, wherein the event displacement probability is used to describe a possibility of displacement of an event that could have occurred within the coverage of the path, to outside the coverage of the path to occur; and changing the path based on the event displacement probability.

Claims

1. A method of determining a path for an individual to patrol, the method comprising:

receiving, via a receiving device, a request from the individual for an initial patrol path to patrol within a road net, the road net comprising a plurality of nodes, the request including a start point of the individual within the road net;

determining the initial patrol path using the start point, and transmitting the initial patrol path to the individual;

calculating, with a processing device, an event displacement probability within coverage of the initial path, wherein the event displacement probability is used to determine a likelihood of a relocation of an event that occurs within the coverage of the initial patrol path, in the absence of the individual on patrol in the initial patrol path, to occur at a location outside the coverage of the initial patrol path;

changing the initial patrol path to a modified patrol path based on the event displacement probability; and

transmitting, via a transmitting device, the modified patrol path to the individual.

2. The method according to claim 1, wherein the coverage of the initial patrol path comprises at least one of:

a maximum range enclosed by all points having a straight-line distance A with each node in the initial patrol path; and

a maximum range enclosed by all points having a path distance B with each node in the initial patrol path, wherein the path distance is a length of progressing along a road in the road net.

3. The method according to claim 2, wherein the location outside the coverage of the initial patrol path comprises an extended area, wherein the extended area comprises one of:

a maximum range enclosed by all points having a straight-line distance C with a border of the coverage of the initial patrol path;

a maximum range enclosed by all points having a path distance D with a border of the coverage of the initial patrol path;

a part which is the maximum range enclosed by all points having a straight-line distance C with a border of the coverage of the initial patrol path subtracted by the coverage of the initial patrol path; and

a part which is the maximum range enclosed by all points having a path distance D with a border of the coverage of the initial patrol path subtracted by the coverage of the initial patrol path.

4. The method according to claim 3, wherein calculating the event displacement probability within coverage of the initial patrol path is based on historical data of an event occurring probability within the coverage of the initial patrol path during a period, and historical data of an event occurring probability within the extended area during the same period.

5. The method according to claim 4, wherein the calculating an event displacement probability within coverage of the initial patrol path further comprises:

taking historical data of an area other than the extended area during the same period as a basis for the calculating.

6. The method according to claim 1, further comprising calculating event occurring probabilities between adjacent nodes in the road net, and wherein the changing the initial patrol path to a modified patrol path based on the event displacement probability comprises changing, based on the event displacement probability, an event occurring probability between at least one node within the coverage of the path and nodes adjacent to the at least one node, and obtaining the modified patrol path based on the changed event occurring probability.

7. The method according to claim 1, wherein the method further comprises:

obtaining a number, X, of paths in the road net, an end node of each of the X paths being a node whose path distance from a start node is closest to E, and E being a set distance;

calculating event occurring probabilities between adjacent nodes in the road net;

obtaining another number, Y, of paths having the highest event occurring probability in the X paths based on the event occurring probabilities between adjacent nodes in the road net;

calculating a probability for a given one of the start, end and adjacent nodes to be present on the Y paths; and

the changing the initial patrol path based on the event displacement probability comprises changing, based on the event displacement probability, a probability for at least one node within the coverage of the path to be present on the Y paths, and obtaining the modified patrol path based on the changed probability for the at least one node to be present on the Y paths.

8. The method according to claim 1, wherein the method further comprises:

obtaining a number, P, paths in the road net, an end node of each of the P paths being a node whose path distance from a start node is closest to F, and F being a set distance;

calculating event occurring probabilities between adjacent nodes in the road net;

obtaining another number, Q, of paths having the highest event occurring probability in the P paths based on the event occurring probabilities between adjacent nodes in the road net;

calculating a probability for a given one of the start, end and adjacent nodes to be present on the Q paths;

generating a transformation matrix based on a probability for a node to be present on the Q paths, wherein if a first node is adjacent to a second node, at least one value corresponding to the second node in the transformation matrix is a ratio of the probability for the second node to be present on the Q paths to a sum of probabilities for each node adjacent to the first node to be present on the Q paths; and

wherein the changing the initial patrol path based on the event displacement probability comprises updating, based on the event displacement probability, at least one value corresponding to at least one node within the coverage of the initial patrol path in the transformation matrix, and obtaining the modified patrol path based on the updated transformation matrix.

9. The method according to claim 1, wherein:

the request further comprises information indicating a direction of the initial patrol path; and

the modified patrol path based on the event displacement probability takes the indicated start point of the patrol path as a start point and is along the indicated direction of the initial patrol path.