Intelligent dynamic parking for autonomous vehicles

Patent metadata

Field	Value
Publication number	US-11938969-B2
Application number	US-201816198935-A
Country	US
Kind code	B2
Filing date	Nov 23, 2018
Priority date	Nov 23, 2018
Publication date	Mar 26, 2024
Grant date	Mar 26, 2024

Abstract

Embodiments for intelligent dynamic parking for autonomous vehicles by a processor. A dynamic parking plan may be determined for an autonomous vehicle to travel from a selected location and returning to the selected location within a selected time window according to a transportation network and one or more a variable parking functions in lieu of waiting at the selected location.

First claim

The invention claimed is:

1. A method, by a processor, for dynamic parking for autonomous vehicles, comprising:
receiving input, by an autonomous vehicle, instructing the autonomous vehicle to travel from an initial location to a selected location, wherein the autonomous vehicle carries at least one passenger from the initial location to the selected location;
determining a dynamic parking plan for the autonomous vehicle to travel from the selected location at a first time and return to the selected location at a second time according to a transportation network and one or more variable parking functions, wherein the at least one passenger is unloaded at the selected location such that, subsequent to unloading the at least one passenger at the selected location at the first time, the autonomous vehicle autonomously travels from the selected location at the first time, on a determined route of a sequence of vehicle movements computed prior to departing the selected location at the first time, and back to the selected location at the second time in lieu of waiting at the selected location;
in conjunction with the determining of the dynamic parking plan according to the one or more variable parking functions, defining the one or more variable parking functions according to a congestion cost function that minimizes a total congestion cost by the autonomous vehicle, wherein the total congestion costs is a sum of a plurality of congestion costs respectively associated with each of a plurality of trip segments of the determined route;
determining, for the dynamic parking plan, a transition plan of one or more transitions equal to traversing one or more edges of the transportation network on the determined route according to a search space built containing all possible combinations of trip segments, including the plurality of trip segments, able to be used to return to the selected location at the second time, wherein the determined route is identified by relaxing an admissible estimation of an acceptable heuristic of the search space, and, commencing with the selected location, pruning those trip segments of all possible combinations of trips segments that do not comply with the acceptable heuristic as compared to the relaxed admissible estimation, wherein determining the transition plan for the dynamic parking plan includes causing the autonomous vehicle to perform one or more actions on the determined route, and wherein the one or more actions include traversing the one or more edges and waiting at one of the one or more transitions of one or more of the plurality of trip segments for one time step according to the congestion cost associated therewith and the total congestion cost.

2. The method of claim 1 , further including determining one or more actions to perform within the dynamic plan, wherein the one or more actions include traversing the one or more edges of the transportation network, waiting at selected alternative locations, or a combination thereof.

3. The method of claim 1 , further including defining the one or more variable parking functions according to a travel time function that determines an amount of time for the autonomous vehicle to travel.

4. The method of claim 1 , further including restricting the autonomous vehicle to be within at least a defined amount of time from the selected location.

5. The method of claim 1 , further including dynamically adjusting the dynamic parking plan according to one or more contextual factors.

6. The method of claim 1 , further including:
dynamically building a graph of the transportation network having one or more nodes and the one or more edges;
performing a heuristic search according to a congestion cost function, a travel time function, or a combination thereof, and
traversing the one or more edges according to the heuristic search for traveling from the selected location and returning to the selected location.

7. A system for dynamic parking for autonomous vehicles, comprising:
one or more computers with executable instructions that when executed cause the system to:
receive input, by an autonomous vehicle, instructing the autonomous vehicle to travel from an initial location to a selected location, wherein the autonomous vehicle carries at least one passenger from the initial location to the selected location;
determine a dynamic parking plan for the autonomous vehicle to travel from the selected location at a first time and return to the selected location at a second time according to a transportation network and one or more variable parking functions, wherein the at least one passenger is unloaded at the selected location such that, subsequent to unloading the at least one passenger at the selected location at the first time, the autonomous vehicle autonomously travels from the selected location at the first time, on a determined route of a sequence of vehicle movements computed prior to departing the selected location at the first time, and back to the selected location at the second time in lieu of waiting at the selected location;
in conjunction with the determining of the dynamic parking plan according to the one or more variable parking functions, define the one or more variable parking functions according to a congestion cost function that minimizes a total congestion cost by the autonomous vehicle, wherein the total congestion costs is a sum of a plurality of congestion costs respectively associated with each of a plurality of trip segments of the determined route; and
determine, for the dynamic parking plan, a transition plan of one or more transitions equal to traversing one or more edges of the transportation network on the determined route according to a search space built containing all possible combinations of trip segments, including the plurality of trip segments, able to be used to return to the selected location at the second time, wherein the determined route is identified by relaxing an admissible estimation of an acceptable heuristic of the search space, and, commencing with the selected location, pruning those trip segments of all possible combinations of trips segments that do not comply with the acceptable heuristic as compared to the relaxed admissible estimation, wherein determining the transition plan for the dynamic parking plan includes causing the autonomous vehicle to perform one or more actions on the determined route, and wherein the one or more actions include traversing the one or more edges and waiting at one of the one or more transitions of one or more of the plurality of trip segments for one time step according to the congestion cost associated therewith and the total congestion cost.

8. The system of claim 7 , wherein the executable instructions further determine one or more actions to perform within the dynamic plan, wherein the one or more actions include traversing the one or more edges of the transportation network, waiting at selected alternative locations, or a combination thereof.

9. The system of claim 7 , wherein the executable instructions further define the one or more variable parking functions according to a travel time function that determines an amount of time for the autonomous vehicle to travel.

10. The system of claim 7 , wherein the executable instructions further restrict the autonomous vehicle to be within at least a defined amount of time from the selected location.

11. The system of claim 7 , wherein the executable instructions further dynamically adjust the dynamic parking plan according to one or more contextual factors.

12. The system of claim 7 , wherein the executable instructions further:
dynamically build a graph of the transportation network having one

Assignees

• IBM

Inventors

• Botea Adi
• Buesser Beat
• Chen Bei
• Kishimoto Akihiro

Classifications

• B60W60/0025 Primary

  specially adapted for specific operations · CPC title

• G06N5/01

  Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound · CPC title

• G06Q30/0284 Primary

  Time or distance, e.g. usage of parking meters or taximeters · CPC title

• G06Q50/30

  Physics · mapped topic

• B60W2554/406

  Traffic density · CPC title