System, method and computer program product for path computing based on unpleasant data

• US 10,215,578 B2
• Filed: 08/29/2016
• Issued: 02/26/2019
• Est. Priority Date: 08/29/2016
• Status: Active Grant

• Current Assignee: AirBNB Incorporated
• Original Assignee: International Business Machines Corporation
• Inventors: Chakraborty, Supriyo, Crawford, Catherine Helen, Raghavendra, Ramya
• Primary Examiner(s): Melton, Todd M
• Application Number:
  US15/249,721
• Publication Number:
  US 20180058869A1
• Time in Patent Office: 911 Days
• 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
• CPC Class Codes: G01C 21/3484 Personalized, e.g. from learned user behaviour or user-defined profiles
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem

Abstract

A path computing method, system, and computer program product, include extracting unpleasant data from a database to create a multi-variate spatio-temporal density function, collecting a tolerance level of a user, and computing a path for the user based on the tolerance level and the density function.

Claims

1. A computer-implemented path computing method, the method comprising:

extracting unpleasant data from a database to create a plurality of multi-variate spatio-temporal density functions;

collecting a tolerance level of a user; and

computing a path for the user based on the tolerance level and the plurality of density functions,

wherein, around a geolocation of centroids defining an incident in the unpleasant data for each of the plurality of density functions, a decay function is created with decay rates that are weighted based on a type of the incident and a time of day associated with the incident, the decay being in relation to a distance from a location having a highest value risk of the unpleasant data,

wherein a geofence is created around the centroids,

wherein the computing determines a path between the geofences that does not overlap with the geofences to maximize a distance to the incidents in the centroids,

wherein the computing entirely avoids the incident in the unpleasant data and maximizes a distance between each of the geolocation of centroids of the plurality of density functions, and

wherein the path is computed based on a constrained optimization problem over a graph where locations are nodes in the geofence and the locations are connected using streets as edges in which an association between the tolerance level and the plurality of density functions are used to compute the path such that;

each edge of the geofence of the unpleasant data is less than the tolerance level;

a sum of the edge weights is minimized; and

a total time for the oath is less than a user time constraint.

2. The computer-implemented method of claim 1, wherein the unpleasant data comprises a relationship between a type of incident and a location of the type of the incident.

3. The computer-implemented method of claim 1, wherein the unpleasant data is semantically combined in the database from multiple data sources selected from a group consisting of;

a government-provided crime database;

a social network;

crowd sourcing data; and

a city planning map.

4. The computer-implemented method of claim 1, wherein the plurality of density functions are created by running k-means and finding the centroids based on a location associated with an incident in the unpleasant data to obtain the geolocation of the centroids.

5. The computer-implemented method of claim 4, wherein the k-means are weighted based on a predetermined weighting for each type of incident.

6. The computer-implemented method of claim 1, further comprising learning a safety score based on a user'"'"'s safely tolerance while on the computed path and based on prior data about the tolerance level.

7. The computer-implemented method of claim 1, wherein a plurality of paths are computed by the computing, the method further comprising:

learning a safety score to update the tolerance level of the user based on a path of the plurality of paths selected by the user.

8. The computer-implemented method of claim 1, embodied in a cloud-computing environment.

9. The computer-implemented method of claim 1, further comprises generating the path by weighting edges of the decay function based on the geolocation with a cumulative risk function from all centroids and decays such that a variety of routes are generated for avoiding areas that are within a factor of probability of incident occurrences using the overall cumulative risk function.

10. The computer-implemented method of claim 1, wherein the computing avoids an area that is within a factor of a probability of an incident occurrence greater than the tolerance level using the density functions.

11. A computer program product for path computing, the computer program product comprising a computer-readable storage medium having program instructions embodied therewith, the program instructions executable by a computer to cause the computer to perform:

extracting unpleasant data from a database to create a plurality of multi-variate spatio-temporal density functions;

collecting a tolerance level of a user; and

computing a path for the user based on the tolerance level and the plurality of density functions,

wherein, around a geolocation of centroids defining an incident in the unpleasant data for each of the plurality density functions, a decay function is created with decay rates that are weighted based on a type of the incident and a time of day associated with the incident, the decay being in relation to a distance from a location having a highest value risk of the unpleasant data,

wherein a geofence is created around the centroids,

wherein the computing determines a path between the geofences that does not overlap with the geofences to maximize a distance to the incidents in the centroids,

wherein the computing entirely avoids the incident in the unpleasant data and maximizes a distance between each of the geolocation of centroids of the plurality of density functions, and

wherein the path is computed based on a constrained optimization problem over a graph where locations are nodes in the geofence and the locations are connected using streets as edges in which an association between the tolerance level and the plurality of density functions are used to compute the path such that;

each edge of the geofence of the unpleasant data is less than the tolerance level;

a sum of the edge weights is minimized; and

a total time for the path is less than a user time constraint.

12. The computer program product of claim 11, wherein the unpleasant data comprises a relationship between a type of incident and a location of the type of the incident.

13. The computer program product of claim 11, wherein the unpleasant data is semantically combined in the database from multiple data sources selected from a group consisting of:

a government-provided crime database;

a social network;

crowd sourcing data; and

a city planning map.

14. The computer program product of claim 11, wherein the plurality of density functions are created by running k-means and finding the centroids based on a location associated with an incident in the unpleasant data to obtain the geolocation of the centroids.

15. The computer program product of claim 14, wherein the k-means are weighted based on a predetermined weighting for each type of the incident.

16. A path computing system, said system comprising:

a processor; and

a memory, the memory storing instructions to cause the processor to;

extract unpleasant data from a database to create a plurality of multi-variate spatio-temporal density functions;

collect a tolerance level of a user; and

compute a path for the user based on the tolerance level and the plurality of density functions,

wherein, around a geolocation of centroids defining an incident in the unpleasant data for each of the plurality of density functions, a decay function is created with decay rates that are weighted based on a type of the incident and a time of day associated with the incident, the decay being in relation to a distance from a location having a highest value risk of the unpleasant data,

wherein a geofence is created around the centroids,

wherein the computing determines a path between the geofences that does not overlap with the geofences to maximize a distance to the incidents in the centroids,

wherein the computing entirely avoids the incident in the unpleasant data and maximizes a distance between each of the geolocation of centroids of the plurality of density functions, and

wherein the path is computed based on a constrained optimization problem over a graph where locations are nodes in the geofence and the locations are connected using streets as edges in which an association between the tolerance level and the plurality of density functions are used to compute the path such that;

each edge of the geofence of the unpleasant data is less than the tolerance level;

a sum of the edge weights is minimized; and

a total time for the path is less than a user time constraint.

17. The system of claim 16, embodied in a cloud-computing environment.