SPATIAL CLUSTERING OF VEHICLE PROBE DATA

• US 20160225255A1
• Filed: 03/13/2015
• Published: 08/04/2016
• Est. Priority Date: 01/30/2015
• Status: Active Grant

• Current Assignee: Nissan Motor Co., Ltd.
• Original Assignee: Nissan North America Incorporated (Nissan Motor Co., Ltd.)
• Inventors: THAKUR, SIDDHARTH, SAITO, DAISUKE
• Granted Patent: US 9,697,730 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: B62D 15/0285 Parking performed automatically
• CPC Class Codes: G01C 21/3841 Data obtained from two or more sources, e.g. probe vehicles
• CPC Class Codes: G01S 19/42 Determining position
• CPC Class Codes: G05D 1/0274 using mapping information stored in a memory device navigation using map-matching G01C21/30
• CPC Class Codes: G05D 1/0278 using satellite positioning signals, e.g. GPS
• CPC Class Codes: G08G 1/0112 from the vehicle, e.g. floating car data [FCD]
• CPC Class Codes: G08G 1/0137 for specific applications

Abstract

A method and apparatus for identifying parking areas may include identifying a plurality of coordinates representing vehicle spatial data, partitioning the plurality of coordinates into at least two groups of vehicle locations based on at least one condition existing when the plurality of coordinates was identified, clustering the vehicle spatial data for a first group of the at least two groups of vehicle locations based on proximity, comparing dimensions of the clustered vehicle spatial data for the first group with other location data within the vehicle transportation network information, and defining a respective location of the clustered vehicle spatial data as a parking area of a plurality of parking areas. Each parking area is associated with a respective location in a vehicle transportation network. The parking area information may be used in the identification of a route from an origin to a primary destination.

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 including a primary destination, wherein identifying the vehicle transportation network information includes identifying the vehicle transportation network information such that the vehicle transportation network information includes parking area information representing a plurality of parking areas, wherein each parking area from the plurality of parking areas is associated with a respective location in the vehicle transportation network by;

identifying a plurality of coordinates representing vehicle spatial data;

partitioning the plurality of coordinates into at least two groups of vehicle locations based on at least one condition existing when the plurality of coordinates was identified;

clustering the vehicle spatial data for a first group of the at least two groups of vehicle locations based on proximity;

comparing dimensions of the clustered vehicle spatial data for the first group with other location data within the vehicle transportation network information; and

defining a respective location of the clustered vehicle spatial data as a parking area of the plurality of parking areas; and

determine a target parking area from the plurality of parking areas as the primary destination based on the vehicle transportation network information,

identify a route from an origin to the primary destination in the vehicle transportation network using the vehicle transportation network information; and

a trajectory controller configured to route the vehicle to travel from the origin to the primary destination using the route.

2. The vehicle of claim 1, wherein clustering the vehicle spatial data for the first group of the at least two groups of vehicle locations based on proximity comprises:

performing a Delaunay triangulation of the plurality of coordinates within the first group;

calculating a respective edge length for edges of the Delauney triangulation; and

identifying at least one group of points of the vehicle spatial data connected by those of the edges having an edge length below a distance threshold as at least one cluster of the clustered vehicle data, the dimensions of the clustered vehicle spatial data obtained from each cluster.

3. The vehicle of claim 2, wherein each parking area from the plurality of parking areas is associated with a respective location in the vehicle transportation network by calculating the dimensions of the clustered vehicle spatial data obtained from the at least one group of points by:

calculating a first difference between maximum and minimum coordinates in a first direction of an orthogonal coordinate system for each group of points; and

calculating a second difference between maximum and minimum coordinates in a second direction of an orthogonal coordinate system for each group of points.

4. The vehicle of claim 3, wherein the first difference and the second difference for each group of points defines a discovered parking lot size for a cluster of the clustered vehicle spatial data, and wherein comparing the dimensions of the clustered vehicle spatial data for the first group with other location data within the vehicle transportation network information comprises:

comparing a distribution of the discovered parking lot sizes to a distribution of known parking lot sizes for locations of each cluster relative to map data of the vehicle transportation network information; and

wherein defining a respective location of the clustered vehicle spatial data as a parking area of the plurality of parking areas comprises;

identifying each cluster as a parking area of the plurality of parking areas when the distribution of the discovered parking lot sizes matches the distribution of known parking lot sizes.

5. The vehicle of claim 2, wherein comparing the dimensions of the clustered vehicle spatial data for the first group with other location data within the vehicle transportation network information comprises:

comparing the dimensions of each cluster of the clustered vehicle spatial data to a maximum allowable parking lot size for locations of each cluster relative to map data of the vehicle transportation network information; and

wherein defining a respective location of the clustered vehicle spatial data as a parking area of the plurality of parking areas comprises;

identifying each cluster as a parking area of the plurality of parking areas when a respective size of each cluster is at or below the maximum allowable parking lot size.

6. The vehicle of claim 5, wherein clustering the vehicle spatial data for the first group of the at least two groups of vehicle locations based on proximity comprises, when a respective size of each cluster is above the maximum allowable parking lot size:

reducing the distance threshold to an updated distance threshold;

identifying at least one group of points of the vehicle spatial data connected by those of the edges having an edge length below the updated distance threshold as at least one updated cluster of the clustered vehicle data, the dimensions of the clustered vehicle spatial data obtained from each updated cluster;

wherein comparing the dimensions of the clustered vehicle spatial data for the first group with other location data within the vehicle transportation network information comprises;

comparing the dimensions of each updated cluster of the clustered vehicle spatial data to the maximum allowable parking lot size for locations of each updated cluster relative to the map data of the vehicle transportation network information; and

wherein defining a respective location of the clustered vehicle spatial data as a parking area of the plurality of parking areas comprises;

identifying each updated cluster as a parking area of the plurality of parking areas when a respective size of each updated cluster is at or below the maximum allowable parking lot size.

7. The vehicle of claim 2, wherein comparing the dimensions of the clustered vehicle spatial data for the first group with other location data within the vehicle transportation network information comprises:

comparing a distribution of the dimensions of each cluster of the clustered vehicle spatial data to a distribution of known parking lot sizes for locations of each cluster relative to map data of the vehicle transportation network information; and

wherein defining a respective location of the clustered vehicle spatial data as a parking area of the plurality of parking areas comprises;

identifying each cluster as a parking area of the plurality of parking areas when the distribution of the dimensions of each cluster matches the distribution of known parking lot sizes.

8. The vehicle of claim 7, wherein clustering the vehicle spatial data for the first group of the at least two groups of vehicle locations based on proximity comprises, when the distribution of the dimensions of each cluster does not match the distribution of known parking lot sizes:

reducing the distance threshold to an updated distance threshold;

identifying at least one group of points of the vehicle spatial data connected by those of the edges having an edge length below the updated distance threshold as at least one updated cluster of the clustered vehicle data, the dimensions of the clustered vehicle spatial data obtained from each updated cluster;

wherein comparing the dimensions of the clustered vehicle spatial data for the first group with other location data within the vehicle transportation network information comprises;

comparing a distribution of the dimensions of each updated cluster of the clustered vehicle spatial data to the distribution of known parking lot sizes for locations of each cluster relative to map data of the vehicle transportation network information; and

wherein defining a respective location of the clustered vehicle spatial data as a parking area of the plurality of parking areas comprises;

identifying each updated cluster as a parking area of the plurality of parking areas when the distribution of the dimensions of each updated cluster matches the distribution of known parking lot sizes.

9. The vehicle of claim 1, wherein identifying the plurality of coordinates representing vehicle spatial data comprises sampling global positioning system (GPS) coordinates from a plurality of vehicles at defined intervals of time.

10. The vehicle of claim 9, wherein each parking area from the plurality of parking areas is associated with a respective location in the vehicle transportation network by:

converting the GPS coordinates to Universal Transverse Mercator (UTM) coordinates.

11. The vehicle of claim 1, wherein the vehicle is an autonomous vehicle.

12. The vehicle of claim 1, wherein partitioning the plurality of coordinates into at least two groups of vehicle locations based on at least one condition existing when the plurality of coordinates was identified comprises:

partitioning the plurality of coordinates into the at least two groups such that each group includes coordinates of the plurality of coordinates obtained at different time windows.

13. 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 including a primary destination, wherein identifying the vehicle transportation network information includes identifying the vehicle transportation network information such that the vehicle transportation network information includes parking area information representing a plurality of parking areas, wherein each parking area from the plurality of parking areas is associated with a respective location in the vehicle transportation network by;

identifying a plurality of coordinates representing vehicle spatial data from a plurality of vehicles;

partitioning the plurality of coordinates into at least two groups of vehicle locations based on at least one condition existing when the plurality of coordinates was identified, wherein the at least one condition comprises a time of day;

clustering the vehicle spatial data for a first group of the at least two groups of vehicle locations based on proximity;

comparing dimensions of the clustered vehicle spatial data for the first group with other location data within the vehicle transportation network information; and

defining a respective location of the clustered vehicle spatial data as a parking area of the plurality of parking areas; and

determine a target parking area from the plurality of parking areas as the primary destination based on the vehicle transportation network information,

identify a route from an origin to the primary destination in the vehicle transportation network using the vehicle transportation network information; and

a trajectory controller configured to route the vehicle to travel from the origin to the primary destination using the route.

14. The vehicle of claim 13, wherein the vehicle transportation network includes a plurality of destinations that includes the primary destination and wherein the processor is configured to execute instructions stored on the non-transitory computer readable medium to identify the vehicle transportation network information such that at least some of the plurality of coordinates are associated with a respective destination from the plurality of destinations and such that at least one parking area from the plurality of parking areas is associated with the primary destination.

15. The vehicle of claim 14, wherein the processor is configured to execute instructions stored on the non-transitory computer readable medium to associate the at least one parking area from the plurality of parking areas with the primary destination by:

comparing destinations associated with the plurality of coordinates defining each parking area of the plurality of parking areas with the primary destination; and

associating the at least one parking area from the plurality of parking areas with the primary destination when the primary destination is among the destinations associated with the plurality of coordinates defining the at least one parking area.

16. The vehicle of claim 13, wherein the time of day comprises a time window.

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

18. A system for generating vehicle transportation network information, 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;

automatically associate each parking area of a plurality of parking areas with a respective location in the vehicle transportation network by;

identifying a plurality of coordinates representing vehicle spatial data;

partitioning the plurality of coordinates into at least two groups of vehicle locations based on at least one condition existing when the plurality of coordinates was identified;

clustering the vehicle spatial data for a first group of the at least two groups of vehicle locations based on proximity;

comparing dimensions of the clustered vehicle spatial data for the first group with other location data within the vehicle transportation network information; and

defining a respective location of the clustered vehicle spatial data as a parking area of the plurality of parking areas; and

update the vehicle transportation network information based on the automatically identified associations between the parking areas and the respective locations.

19. The system of claim 18, wherein the processor is configured to execute instructions stored on the non-transitory computer readable medium to partition the plurality of coordinates into at least two groups of vehicle locations based on at least one condition existing when the plurality of coordinates was identified by at least one of:

partitioning the plurality of coordinates into the at least two groups such that each group includes coordinates of the plurality of coordinates obtained at different time windows;

or

partitioning the plurality of coordinates into the at least two groups such that each group includes coordinates of the plurality of coordinates associated with only a single vehicle of a plurality of vehicles.

20. The system of claim 18, wherein the processor is configured to execute instructions stored on the non-transitory computer readable medium to cluster the vehicle spatial data for the first group of the at least two groups of vehicle locations based on proximity by:

performing a Delaunay triangulation of the plurality of coordinates within the first group;

calculating a respective edge length for edges of the Delauney triangulation; and

identifying at least one group of points of the vehicle spatial data connected by those of the edges having an edge length below a distance threshold as at least one cluster of the clustered vehicle data, the dimensions of the clustered vehicle spatial data obtained from each cluster;

wherein the processor is configured to execute instructions stored on the non-transitory computer readable medium to compare the dimensions of the clustered vehicle spatial data for the first group with other location data within the vehicle transportation network information by;

comparing the dimensions of each cluster of the clustered vehicle spatial data to a maximum allowable parking lot size for locations of each cluster relative to map data of the vehicle transportation network information when the map data does not include known parking lot sizes for the locations;

comparing a distribution of the dimensions of each cluster of the clustered vehicle spatial data to a distribution of the known parking lot sizes for locations of each cluster relative to the map data of the vehicle transportation network information when the map data includes known parking lot sizes for the locations; and

wherein the processor is configured to execute instructions stored on the non-transitory computer readable medium to define a respective location of the clustered vehicle spatial data as a parking area of the plurality of parking areas by one of;

identifying each cluster as a parking area of the plurality of parking areas when the distribution of the dimensions of each cluster matches the distribution of known parking lot sizes;

or

identifying each cluster as a parking area of the plurality of parking areas when a respective size of each cluster is at or below the maximum allowable parking lot size.

21. The system of claim 18, wherein the processor is configured to execute instructions stored on the non-transitory computer readable medium to identify the plurality of coordinates representing the vehicle spatial data from a source other than the vehicle.