Entropy-based Optimization via A* Algorithm for Parking Space Recommendation

Xin Wei, Runqi Qiu, Houyu Yu, Yurun Yang, Haoyu Tian, Xiang XiangFifth 2021 · DOI · OpenReview

Abstract

This paper addresses the path planning problems for recommending parking spaces, given the difficulties of identifying the most optimal route to vacant parking spaces and the shortest time to leave the parking space. Our optimization approach is based on the entropy method and realized by the A algorithm. Experiments have shown that the combination of A and the entropy value induces the optimal parking solution with the shortest route while being robust to environmental factors.

Introduction

Finding the "best" parking spot in a crowded urban environment is a multi-faceted challenge. Most current intelligent parking systems are one-dimensional, typically guiding drivers to the nearest vacant spot while ignoring the "total cost" of the choice, such as walking distance to the destination or the difficulty of maneuvering into a tight space. This paper proposes an Optimized Parking Space Recommendation (OPSR) system that dynamically balances these factors using a combination of pathfinding algorithms and information theory.

Methodology

The OPSR system utilizes a three-stage pipeline to evaluate and rank vacant parking spaces based on driving distance, walking distance, and parking difficulty.

Pathfinding and Graph Modeling

The parking lot is first modeled as an undirected graph where intersections and parking spaces are represented as nodes. This simplification significantly reduces computational overhead, making the system suitable for real-time deployment. The A* algorithm is then employed to calculate two critical metrics: the vehicle driving distance ($X$) from the entrance to the spot and the pedestrian walking distance ($L$) from the spot to the exit.

Figure 1: The parking lot layout (a) is mapped to an undirected graph (b) to facilitate efficient pathfinding using the A* algorithm.

Quantifying Parking Difficulty

A key innovation of this approach is the quantification of parking "hassle" or difficulty ($S$). The authors assign numerical values based on the surrounding vehicle situation: 3 for a spot with cars on both sides, 2 for one side, and 1 for an isolated spot. This turns a subjective feeling into a computable metric.

Figure 4: Visual representation of parking difficulty levels based on adjacent vehicles, ranging from high difficulty (a) to low difficulty (c).

Entropy-based Weighting and Standardization

To combine disparate metrics—meters for distance versus categorical scores for difficulty—the system uses fuzzy set standardization to map all values onto a [0, 1] interval. The Information Entropy method then calculates dynamic weights ($W_1, W_2, W_3$) based on the dispersion of the data. If distances are similar across all spots but difficulty levels vary widely, the system automatically assigns more weight to the difficulty factor. The final recommendation is based on a comprehensive index $H = W_1 \times X + W_2 \times L + W_3 \times S$.

Results and Discussion

The algorithm was evaluated using a simulated parking lot model with standard 2.4m x 5.3m spaces. In experimental trials, the OPSR system consistently identified optimal spots that balanced driving time, walking distance, and ease of parking. For instance, it might recommend a spot slightly further from the entrance if it offers a significantly easier parking maneuver and a shorter walk to the exit.

Compared to fixed-weighting schemes and existing baselines, OPSR achieved the lowest total time consumption across various scenarios, including vacant, surrounded, and distance-constrained environments. The system proved robust across different lot configurations, whereas fixed-weight models often failed when the environment did not match their hard-coded priorities.

Conclusion

By combining the A* algorithm with entropy-based weighting, the OPSR system provides a robust and adaptive solution for parking space recommendation. It successfully moves beyond simple distance-based metrics to include the practicalities of maneuvering and pedestrian access. Future work will focus on integrating real-time sensor data, such as camera feeds, to update environmental factors and difficulty scores dynamically.

Summary updated

Abstract

This paper addresses the path planning problems for recommending parking spaces, given the difficulties of identifying the most optimal route to vacant parking spaces and the shortest time to leave the parking space. Our optimization approach is based on the entropy method and realized by the A* algorithm. Experiments have shown that the combination of A* and the entropy value induces the optimal parking solution with the shortest route while being robust to environmental factors.
BibTeX
@inproceedings{wei2021entropy,
  author = {Xin Wei and Runqi Qiu and Houyu Yu and Yurun Yang and Haoyu Tian and Xiang Xiang},
  title = {{Entropy-based Optimization via A* Algorithm for Parking Space Recommendation}},
  booktitle = {Fifth},
  year = {2021},
  doi = {10.1117/12.2619645},
}
Figure