Determining a patrol path

• US 9,322,662 B2
• Filed: 06/24/2013
• Issued: 04/26/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): LI, CE LI
• Application Number:
  US13/925,132
• Publication Number:
  US 20130325338A1
• Time in Patent Office: 1,037 Days
• Field of Search: 701/23, 701/26, 701/202, 701/209, 701/411, 701/533
• 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. An apparatus for determining a path, the apparatus comprising:

a first path module configured to receive, 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;

a path device configured to determine the initial patrol path using the start point, and transmit, via a transmitting device, the initial patrol path to the individual;

a processor-implemented probability calculating module configured to calculate an event displacement probability within coverage of the initial path obtained by the first path module, wherein the event displacement probability is used to determine a likelihood of a relocation of an event from within the coverage of the initial patrol path to a location outside the coverage of the initial patrol path in the absence of the individual on patrol in the initial patrol path; and

a second path module configured to change the initial patrol path to a modified patrol path based on the event displacement probability;

wherein the transmitting device is further configured to transmit the modified patrol path to the individual.

2. The apparatus 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 apparatus according to claim 2, wherein the location outside the coverage of the initial patrol path comprises an extended area, and 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 apparatus according to claim 3, wherein the probability calculating module is specifically configured to calculate the event displacement probability within coverage of the initial patrol path 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 apparatus according to claim 4, wherein the probability calculating module is specifically configured to take historical data of an area other than the extended area during the same period as a basis for the calculating, and to calculate an event displacement probability within coverage of the initial patrol path 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.

6. The apparatus according to claim 1, further comprising a first calculating module configured to calculate event occurring probabilities between adjacent nodes in the road net, and wherein the second path module comprises:

a first updating sub-module configured to change, based on the event displacement probability, event occurring probabilities between at least one node within the coverage of the path and nodes adjacent to the at least one node; and

a first determining sub-module configured to obtain the modified patrol path based on the changed event occurring probability.

7. The apparatus according to claim 1, further comprising:

a first obtaining module configured to obtain 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;

a second calculating module configured to calculate event occurring probabilities between adjacent nodes in the road net;

a first selecting module configured to obtain 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;

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

the second path module comprising a second updating sub-module configured to change, 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, a second determining sub-module configured to obtain the modified patrol path based on the probability for the at least one node to be present on the Y paths.

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

a second obtaining module configured to obtain a number, P, of 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;

a fourth calculating module configured to calculate event occurring probabilities between adjacent nodes in the road net;

a second selecting module configured to obtain 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;

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

a matrix generating module configured to generate 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;

wherein the second path module comprises a third updating sub-module configured to update, 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 a third determining sub-module configured to obtain the modified patrol path based on the updated transformation matrix.

9. The apparatus 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.

10. An apparatus for determining a path, the apparatus comprising:

a first path module configured to receive, 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;

a path device configured to determine the initial patrol path using the start point, and transmit, via a transmitting device, the initial patrol path to the individual;

a processor-implemented probability calculating module configured to calculate an event displacement probability within coverage of the initial path obtained by the first path module, wherein the event displacement probability is used to determine a likelihood of a relocation of an event from within the coverage of the initial patrol path to a location outside the coverage of the initial patrol path;

a first obtaining module configured to obtain 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;

a second calculating module configured to calculate event occurring probabilities between adjacent nodes in the road net;

a first selecting module configured to obtain 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;

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

a second path module configured to change the initial patrol path to a modified patrol path based on the event displacement probability, the second path module comprising a second updating sub-module configured to change, 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, a second determining sub-module configured to obtain the modified patrol path based on the probability for the at least one node to be present on the Y paths;

wherein the transmitting device is further configured to transmit the modified patrol path to the individual.

11. The apparatus according to claim 10, 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.

12. The apparatus according to claim 11, wherein the location outside the coverage of the initial patrol path comprises an extended area, and 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.

13. The apparatus according to claim 12, wherein the probability calculating module is specifically configured to calculate the event displacement probability within coverage of the initial patrol path 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.

14. The apparatus according to claim 10, 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.

15. An apparatus for determining a path, the apparatus comprising:

a first path module configured to receive, 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;

a path device configured to determine the initial patrol path using the start point, and transmit, via a transmitting device, the initial patrol path to the individual;

a processor-implemented probability calculating module configured to calculate an event displacement probability within coverage of the initial path obtained by the first path module, wherein the event displacement probability is used to determine a likelihood of a relocation of an event from within the coverage of the initial patrol path to a location outside the coverage of the initial patrol path;

a first obtaining module configured to obtain a number, P, of 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;

a second calculating module configured to calculate event occurring probabilities between adjacent nodes in the road net;

a first selecting module configured to obtain 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;

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

a matrix generating module configured to generate 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

a second path module configured to change the initial patrol path to a modified patrol path based on the event displacement probability wherein the second path module comprises a second updating sub-module configured to update, 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 a second determining sub-module configured to obtain the modified patrol path based on the updated transformation matrix;

wherein the transmitting device is further configured to transmit the modified patrol path to the individual.

16. The apparatus according to claim 15, 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.

17. The apparatus according to claim 16, wherein the location outside the coverage of the initial patrol path comprises an extended area, and 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.

18. The apparatus according to claim 17, wherein the probability calculating module is specifically configured to calculate the event displacement probability within coverage of the initial patrol path 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.

19. The apparatus according to claim 15, 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.