DETERMINING A PATROL PATH

• US 20130325338A1
• Filed: 06/24/2013
• Published: 12/05/2013
• 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
• Granted Patent: US 9,322,662 B2
• Time in Patent Office: Days
• US Class Current: 701/527
• 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 obtain a path in a road net, the road net comprising a plurality of nodes;

a processor-implemented probability calculating module configured to calculate an event displacement probability within coverage of the path obtained by the first path module, 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

a second path module configured to change the path based on the event displacement probability.

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

a range reachable by eyesight when one is progressing along the path;

a range reachable by sound produced when one is progressing along the path;

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

a maximum range enclosed by all points having a path distance B with each node in the 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 an event displacement probability within coverage of the path is specifically used to describe a possibility of displacement of an event that could have occurred within the coverage of the path, to an extended area and occur outside the coverage of the path, 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 path;

a maximum range enclosed by all points having a path distance D with a border of the coverage of the 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 path subtracted by the coverage of the path;

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

4. The apparatus according to claim 3, wherein the probability calculating module is specifically configured to calculate an event displacement probability within coverage of the path based on historical data of an event occurring probability within the coverage of the 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 path based on historical data of an event occurring probability within the coverage of the 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 a new path based on the changed event occurring probability.

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

a first obtaining module configured to obtain X paths in the road net, an end node of every path 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 Y 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 node to 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 present on the Y paths, a second determining sub-module configured to obtain a new path based on the probability for the changed node to present on the Y paths.

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

a second obtaining module configured to obtain P paths in the road net, an end node of every path 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 Q 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 node to present on the Q paths;

a matrix generating module configured to generate a transformation matrix based on a probability for a node to 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 present on the Q paths to a sum of probabilities for each node adjacent to the first node to 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 path in the transformation matrix, and a third determining sub-module configured to obtain a new path based on the updated transformation matrix.

9. An apparatus for indicating a patrol path, the apparatus comprising:

a receiving device configured to receive a request which comprises information indicating a start point of the patrol path;

a path device configured to comprise an apparatus for determining a path according to claim 1, wherein the path changed based on an event displacement probability and obtained by the apparatus for determining a path takes the indicated start point of the patrol path as a start point; and

a sending device configured to send an indication of a patrol path based on the path changed based on the event displacement probability.