Identifying significant locations based on vehicle probe data

• US 10,120,381 B2
• Filed: 12/21/2015
• Issued: 11/06/2018
• Est. Priority Date: 03/13/2015
• Status: Active Grant

• Current Assignee: Nissan Motor Co., Ltd.
• Original Assignee: Nissan North America Incorporated (Nissan Motor Co., Ltd.)
• Inventors: Thakur, Siddharth
• Primary Examiner(s): Black, Thomas G
• Assistant Examiner(s): Kong, Sze-Hon
• Application Number:
  US14/976,405
• Publication Number:
  US 20160265930A1
• Time in Patent Office: 1,051 Days
• CPC Class Codes: G01C 21/3617 using user history, behaviour, conditions or preferences, e.g. predicted or inferred from previous use or current movement
• CPC Class Codes: G05D 1/0088 characterized by the autonomous decision making process, e.g. artificial intelligence, predefined behaviours using knowledge based models G06N5/00

Abstract

A method, a vehicle and a system that identify and use a location significant to a person associated with a vehicle based on vehicle probe data are described. Vehicle transportation network information representing a vehicle transportation network is identified, the vehicle transportation network information including destinations of a vehicle obtained from vehicle probe data. For at least some of the destinations, density-based clustering is performed using temporal data associated with the at least some of the destinations to form at least two spatio-temporal clusters. A contextual label is assigned to a location associated with a first spatio-temporal cluster of the at least two spatial-temporal clusters based on the temporal data associated with the first spatio-temporal cluster, the location being a labeled location, and the labeled location is used for vehicle operation. The labeled location may be used for navigation or service, for example.

Claims

1. A vehicle, comprising:

a processor configured to execute instructions stored on a non-transitory computer readable medium to;

identify vehicle transportation network information representing a vehicle transportation network, the vehicle transportation network information including destinations of a vehicle obtained by spatially clustering vehicle probe data;

for at least some of the destinations, perform density-based clustering using temporal data associated with the at least some of the destinations to form at least two spatio-temporal clusters; and

assign a contextual label to a location associated with a first spatio-temporal cluster of the at least two spatio-temporal clusters based on the temporal data associated with the first spatio-temporal cluster, the location being a labeled location; and

a vehicle operation device configured to operate the vehicle using the labeled location.

2. The vehicle of claim 1, wherein the processor is configured to execute instructions stored on the non-transitory computer readable medium to perform density-based clustering by:

performing two-dimensional density-based clustering using an arrival time of day and a stay time of trip data associated with the at least some of the destinations.

3. The vehicle of claim 2, wherein the processor is configured to execute instructions stored on the non-transitory computer readable medium to perform density-based clustering by:

grouping trip data associated with each destination of the at least some of the destinations by stay type; and

performing the two-dimensional density-based clustering by the stay type.

4. The vehicle of claim 3, wherein the stay type comprises at least two of:

a weekday stay type having an arrival day of a week and a departure day of the week both falling on a weekday;

a weekend stay type having an arrival day of the week and a departure day of the week both falling on a weekend;

or

a mixed stay type having an arrival day of the week falling on a weekday and a departure day of the week falling on a weekend or having an arrival day of the week falling on a weekend and a departure day of the week falling on a weekday.

5. The vehicle of claim 1, wherein the processor is configured to execute instructions stored on the non-transitory computer readable medium to identify vehicle transportation network information representing a vehicle transportation network by, before the density-based clustering:

transforming point data from the vehicle probe data into trip data, each trip forming the trip data comprising a start point with a start timestamp and a stop point with a stop timestamp; and

performing the spatial clustering using the trip data to form spatial clusters to identify the destinations of the vehicle.

6. The vehicle of claim 5, wherein the processor is configured to execute instructions stored on the non-transitory computer readable medium to identify vehicle transportation network information representing a vehicle transportation network by, before the density-based clustering:

storing the trip data to form stored trip data;

assigning a cluster identifier to each unique vehicle transportation network location resulting from performing the spatial clustering; and

appending the cluster identifier to any of the start points and any of the stop points forming a respective one of the spatial clusters within the stored trip data.

7. The vehicle of claim 6, wherein the processor is configured to execute instructions stored on the non-transitory computer readable medium to identify vehicle transportation network information representing a vehicle transportation network by, before the density-based clustering:

determining a stay time for a trip of the trip data as a difference between a stop timestamp of the trip and a start timestamp of a subsequent trip;

filtering continuous records by comparing a cluster identifier of the trip with a cluster identifier of the subsequent trip to generate a location record for the unique vehicle transportation network location; and

adding an arrival timestamp at the unique vehicle transportation network location and a departure timestamp from the unique vehicle transportation network location to the location record.

8. The vehicle of claim 5, wherein the processor is configured to execute instructions stored on the non-transitory computer readable medium to identify vehicle transportation network information representing a vehicle transportation network by, before the density-based clustering:

sorting each entry within the vehicle probe data based on a measurement timestamp to form a sequence of records;

determining a time difference of consecutive records within the sequence;

identifying the start of a trip when the time difference exceeds a threshold value; and

identifying the start point, the start timestamp, the stop point, and the stop timestamp for the trip.

9. The vehicle of claim 1, wherein the processor is configured to execute instructions stored on the non-transitory computer readable medium to identify vehicle transportation network information representing a vehicle transportation network by, before the density-based clustering:

performing the spatially clustering using a plurality of trips comprising GPS coordinates associated with each of a start location and an end location from the vehicle probe data to form spatial clusters; and

assigning a cluster identifier to each location associated with a spatial cluster; and

wherein the processor is configured to execute instructions stored on the non-transitory computer readable medium to perform density-based clustering by;

for each location assigned to a cluster identifier, performing two-dimensional density-based clustering of arrival time of day at location versus a stay time at the location to form temporal clusters; and

forming the at least two spatio-temporal clusters by combining the spatial clusters with the temporal clusters.

10. The vehicle of claim 1, wherein the processor is configured to execute instructions stored on the non-transitory computer readable medium to assign a contextual label to a location by:

selecting records from the first spatio-temporal cluster within a defined time window that have an overnight stay;

identifying the location that is the most common within the records; and

assigning the contextual label of home to the location.

11. The vehicle of claim 1, wherein the processor is configured to execute instructions stored on the non-transitory computer readable medium to assign a contextual label to a location by:

selecting records from the first spatio-temporal cluster within a defined time window that have no overnight stay;

identifying the location that is the most common within the records; and

assigning the contextual label of work to the location.

12. The vehicle of claim 1, wherein the vehicle operation device is a navigation system;

and wherein the processor is configured to execute instructions stored on the non-transitory computer readable medium to;

generate a route to the labeled location using the navigation system.

13. The vehicle of claim 12, wherein the vehicle is an autonomous vehicle;

and wherein the processor is configured to execute instructions stored on the non-transitory computer readable medium to;

operate the vehicle to traverse the route.

14. A system for identifying and using a location significant to a person associated with a vehicle based on vehicle probe data, the system including:

a memory including a non-transitory computer readable medium; and

a processor configured to execute instructions stored on the non-transitory computer readable medium to;

identify vehicle transportation network information representing a vehicle transportation network, the vehicle transportation network information including destinations of a vehicle obtained by spatially clustering vehicle probe data;

for at least some of the destinations, perform density-based clustering using temporal data associated with the at least some of the destinations to form at least two spatio-temporal clusters;

assign a contextual label to a location associated with a first spatio-temporal cluster of the at least two spatio-temporal clusters based on the temporal data associated with the first spatio-temporal cluster, the location being a labeled location; and

use the labeled location for vehicle operation.

15. The system of claim 14, wherein the processor is configured to execute instructions stored on the non-transitory computer readable medium to use the labeled location for vehicle operation by:

performing density-based clustering using temporal data associated with destinations determined over a period of time subsequent to the assigning the contextual label to form at least two updated spatio-temporal clusters;

assigning the contextual label to an updated location associated with a first updated spatio-temporal cluster;

comparing the location with the updated location; and

changing the labeled location to the updated location when the updated location is different from the location.

16. The system of claim 14, wherein the processor is configured to execute instructions stored on the non-transitory computer readable medium to perform density-based clustering using temporal data by:

performing two-dimensional density-based clustering using an arrival time of day and a stay time of trip data associated with those of the destinations having a same stay type based on an arrival day of a week and a departure day of the week.

17. The system of claim 16, wherein the processor is configured to execute instructions stored on the non-transitory computer readable medium to identify vehicle transportation network information by, before the density-based clustering:

performing the spatially clustering using location data within the vehicle probe data to identify the destinations.

18. A system for identifying and using a location significant to a person associated with a vehicle based on vehicle probe data, the system including:

a memory including a non-transitory computer readable medium; and

a processor configured to execute instructions stored on the non-transitory computer readable medium to;

identify vehicle transportation network information representing a vehicle transportation network by performing spatial clustering of vehicle location information obtained from vehicle probe data of a vehicle, the vehicle transportation network information including destinations of the vehicle;

perform two-dimensional density-based clustering using an arrival time of day and a stay time associated with at least some of the destinations to form a spatio-temporal cluster;

assign a contextual label to a location associated with the spatio-temporal cluster based on temporal data associated with the spatio-temporal cluster, the location being a labeled location; and

use the labeled location for vehicle operation.

19. The system of claim 18, wherein the processor is configured to execute instructions stored on the non-transitory computer readable medium to:

group trip data associated with the destinations by stay type; and

wherein the processor is configured to execute instructions stored on the non-transitory computer readable medium to perform two-dimensional density-based clustering by;

performing the two-dimensional density-based clustering for the at least some of the destinations associated with a single stay type.

20. The system of claim 19, wherein the single stay type comprises one of:

a weekday stay type having an arrival day of a week and a departure day of the week both falling on a weekday;

or

a weekend stay type having an arrival day of the week and a departure day of the week both falling on a weekend.