The task of the multi-agent based planner is to decide the most optimal spot and route for a parking car as soon as receives the “Park” command from the user.
Modified A* Algorithm Inputs
- Available Spots: The algorithm can use one spot and provide the best route to the spot, or can choose the best spot from a list of spots and the best route to that spot. The option for providing only one spot allows a) the user to choose a spot for the vehicle when adding a Virtual Vehicle to the GUI or b) when the vehicle is exiting, it must be destined for the exit “spot”.
- Motion of Vehicles: One of the characteristics of this modified A* algorithm is that it plans a route to the spot that avoids the paths of other spots. Thus, it needs to know the waypoints of all moving vehicles in order to avoid their paths.
Modified A* Algorithm Implementation
- H-Cost: Rather than the traditional h-cost of the distance between the current location and the parking spot (goal), this modified A* uses the distance between the current location and the exit. This is implemented so that parking spots closer to the exit will have lower f-scores.
- G-Cost: The modified A* algorithm uses the g-cost as the sum of the distance traveled to reach the current location and an additional +2 cost for any place in the current path that overlaps the path of any other vehicle. This is to encourage the A* planner to choose a path that has minimal overlap with other vehicles to avoid congestion.
- Corner Cost: A +1 cost is added to each turn in the path. This is because the Oculus Prime is prone to drift and performs better in straight line paths. To optimize the navigation, a corner cost is added for each turn the vehicle makes to avoid paths with multiple turns.
- Way-point Extraction: When the planner has completed the path, the way-points are extracted. A way-point is the start location, end location, and the location of any turn the vehicle takes.
- Choosing Best Spot: If a list of spots is sent to the planner, it will run the modified A* algorithm on the 10 spots closest to the exit. The algorithm will return the f-score of the path and the way-points of the path. The spot with the lowest f-score is chosen as the best spot and the way-points are then passed to the navigation stack to follow to the parking spot.
Parking Lot with Spot Numbers