Spatial clustering of vehicle probe data

• US 9,697,730 B2
• Filed: 03/13/2015
• Issued: 07/04/2017
• 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
• Primary Examiner(s): Nguyen, Nga X
• Application Number:
  US14/657,082
• Publication Number:
  US 20160225255A1
• Time in Patent Office: 844 Days
• Field of Search: 701408, 701430, 701454
• 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 a parking area is associated with a 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, using a spatial clustering technique, the vehicle spatial data for a first group of the at least two groups of vehicle locations based on proximity of the plurality of coordinates forming the first group, the spatial clustering technique forming at least a first cluster of the vehicle spatial data;

comparing dimensions of the first cluster with location data within the vehicle transportation network information indicating dimensions of at least one parking area, the dimensions of the cluster representing an estimated size of a parking area encompassing the plurality of coordinates forming the first cluster; and

based on the comparing, defining a location of the first cluster as the parking area;

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.

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 the parking area is associated with the location in the vehicle transportation network by:

converting the GPS coordinates of the plurality of coordinates forming the first cluster 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.

2. 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, 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 Delaunay 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, dimensions of the clustered vehicle spatial data obtained from each cluster;

comparing the 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;

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

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.

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 the 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.

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 a parking area is associated with a 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;

forming at least a first cluster of coordinates by clustering the vehicle spatial data for a first group of the at least two groups of vehicle locations based on proximity of the plurality of coordinates forming the first group to each other;

comparing spatial dimensions of the first cluster with location data within the vehicle transportation network information indicating a candidate parking area; and

defining a location of the first cluster as the parking area responsive to the spatial dimensions of the first cluster conforming to the candidate parking area; 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. The vehicle of claim 13, wherein clustering the vehicle spatial data comprises:

performing a Delaunay triangulation of the plurality of coordinates within the first group to form at least the first cluster having an edge length below a distance threshold.

19. The vehicle of claim 13, wherein the location data comprises dimensions of a polygon forming the candidate parking area within the vehicle transportation network information.

20. The vehicle of claim 19, wherein the dimensions of the first cluster conform to the candidate parking area when the dimensions of the first cluster fit within the polygon.

21. The vehicle of claim 13, wherein the candidate parking area comprises a maximum allowable size of parking areas in a locality of the first cluster within the vehicle transportation network information.