In recent years, the rapid growth of urban vehicle ownership has exacerbated the challenge of “difficult parking,” making efficient parking solutions a critical focus in smart city development. As a key component of smart infrastructure, robot technology plays a pivotal role in addressing this issue through automated systems. Smart parking garages, which utilize automated guided vehicles (AGVs) based on advanced robot technology, offer a promising approach by enabling automated vehicle storage and retrieval, thus enhancing space utilization and reducing human intervention. However, path planning for AGVs in these environments remains a complex task due to constraints like narrow pathways and obstacles. Traditional path planning algorithms, such as the A* algorithm, often result in suboptimal paths with excessive turns and longer distances, which can impede efficiency and increase operational costs. This paper proposes an improved A* algorithm tailored for smart parking garages, incorporating modifications to the search strategy, dynamic weight adjustment, and a turning penalty function to optimize path length, reduce turning frequency, and improve overall performance. Through simulations and analyses, we demonstrate how these enhancements leverage robot technology to achieve more efficient and practical path planning, contributing to the advancement of intelligent transportation systems.
The foundation of path planning in robot technology involves modeling the environment to facilitate navigation. In smart parking garages, the grid-based method is commonly employed due to its simplicity and effectiveness in representing obstacles and free spaces. This method discretizes the environment into uniform cells, where each cell corresponds to a traversable area or an obstacle. For instance, parked vehicles are marked as obstacles (black cells), while pathways remain free (white cells). This representation allows AGVs to navigate efficiently using algorithms that compute optimal paths from start to goal points. The A* algorithm, a widely used heuristic search method in robot technology, combines the cost from the start node and an estimated cost to the goal, expressed as: $$F(n) = G(n) + H(n)$$ where \(F(n)\) is the total estimated cost, \(G(n)\) is the actual cost from the start node to node \(n\), and \(H(n)\) is the heuristic estimate from node \(n\) to the goal. Common heuristic functions include the Manhattan distance, Euclidean distance, and Chebyshev distance, each with distinct applications depending on the movement constraints. In our context, the Manhattan distance is preferred for its alignment with grid-based movements, calculated as: $$H_{\text{MD}} = |x_n – x_m| + |y_n – y_m|$$ where \((x_n, y_n)\) and \((x_m, y_m)\) are the coordinates of the current and goal nodes, respectively. Despite its popularity, the traditional A* algorithm often generates paths with unnecessary turns and inefficiencies in crowded environments like parking garages, highlighting the need for improvements tailored to real-world robot technology applications.
To address the limitations of the traditional A* algorithm in smart parking garages, we introduce several key modifications that enhance its suitability for AGV path planning. First, we change the search strategy from an 8-neighborhood search to a 4-neighborhood search. In an 8-neighborhood search, the algorithm explores all eight surrounding cells, allowing diagonal movements, which can lead to paths that are shorter in distance but impractical for AGVs with specific kinematic constraints, such as those using Mecanum wheels. These wheels enable movements like forward, backward, lateral shifts, and in-place rotations, but not diagonal travel, making the 4-neighborhood search—which only permits horizontal and vertical movements—more realistic. This adjustment reduces the risk of collisions and aligns with the actual capabilities of robot technology in confined spaces. The 4-neighborhood search restricts the expansion to adjacent cells in the four cardinal directions, ensuring that paths are feasible for AGV navigation. This change not only improves safety but also simplifies the path structure, making it easier to implement in real-time systems.
Second, we incorporate a dynamic weight coefficient into the heuristic function to balance search efficiency and path optimality. In the standard A* algorithm, the weight on the heuristic function is often fixed, which can lead to either excessive node exploration or suboptimal paths. By dynamically adjusting the weight based on the proximity to the goal, we achieve a more adaptive search process. The modified formula becomes: $$F(n) = G(n) + c \times H(n)$$ where \(c\) is the dynamic weight coefficient defined as: $$c = \frac{|x_w – x_v| + |y_w – y_v|}{|x_w – x_u| + |y_w – y_u|}$$ Here, \((x_u, y_u)\) represents the start point, \((x_v, y_v)\) is the current node, and \((x_w, y_w)\) is the goal point. This formulation ensures that when the AGV is far from the goal, \(c\) increases, speeding up the search by reducing the exploration range. Conversely, as the AGV approaches the goal, \(c\) decreases, allowing for more precise pathfinding. This dynamic adjustment enhances the scalability of robot technology in large environments like parking garages, where computational efficiency is crucial.
Third, we introduce a turning penalty function to minimize the number of turns in the path, which is critical for AGVs using Mecanum wheels. While traditional AGVs may require straight segments before turns, Mecanum wheel-based AGVs can execute in-place rotations of 90 degrees, allowing for more flexible movements. However, excessive turns still lead to increased time and energy consumption due to acceleration and deceleration cycles. To mitigate this, we add a turning penalty term to the A* algorithm: $$F(n) = G(n) + c \times H(n) + k \alpha$$ where \(k\) is a factor derived from the movement pattern, and \(\alpha\) is the turning penalty factor. For Mecanum wheel AGVs, the turning condition is determined based on consecutive node transitions. Specifically, a turn occurs when the AGV changes direction between moves, and \(k\) is set to the maximum difference in coordinates between previous and current nodes to quantify the turn magnitude. By penalizing turns, the algorithm prioritizes straighter paths, reducing the overall number of direction changes and improving operational efficiency in robot technology applications. This approach is particularly beneficial in parking garages with narrow aisles, where frequent turns can cause delays and increase the risk of errors.
To validate our improved A* algorithm, we conducted simulations using MATLAB software in a grid-based environment representing a smart parking garage. The environment was modeled as a 30×30 grid with 25% of cells randomly designated as obstacles to simulate parked vehicles. The AGV’s start point was set at the top-left corner, and the goal point at the bottom-right corner. We evaluated the algorithm under different configurations, including varying weight coefficients and turning penalty factors, to assess its performance in terms of path length, number of turns, traversal nodes, and travel time. Each grid cell was assumed to represent 1 meter, with a travel time of 0.5 seconds per cell for straight movement and 1 second per turn to account for acceleration and deceleration in real-world robot technology scenarios.
The results demonstrated significant improvements with our modifications. For instance, when testing different weight coefficients, the dynamic weight approach (\(c = c_1\)) achieved a balance between path length and computational effort. The table below summarizes the outcomes for various weight values, showing that dynamic weighting reduced the number of traversed nodes while maintaining an optimal path distance of 52 meters, compared to fixed weights that either increased path length or exploration effort.
| Weight Coefficient \(c\) | Traversed Nodes | Path Distance (m) |
|---|---|---|
| 0.5 | 636 | 52 |
| 0.75 | 587 | 52 |
| 1 | 399 | 52 |
| 2 | 114 | 56 |
| 3 | 112 | 56 |
| \(c_1\) (dynamic) | 146 | 52 |
Furthermore, the introduction of the turning penalty function led to a notable reduction in turns and travel time. By testing different penalty factors \(\alpha\), we observed that a value of 0.4 optimized the trade-off between path length and turning frequency. The following table illustrates how increasing \(\alpha\) decreased the number of turns from 28 to 22, reduced path distance by 5.41%, and cut travel time by 12.3%, highlighting the effectiveness of our approach in enhancing robot technology efficiency.
| Penalty Factor \(\alpha\) | Traversed Nodes | Path Distance (m) | Number of Turns | Travel Time (s) |
|---|---|---|---|---|
| 0 | 190 | 74 | 28 | 65 |
| 0.2 | 195 | 74 | 28 | 65 |
| 0.4 | 247 | 70 | 22 | 57 |
| 0.5 | 313 | 70 | 22 | 57 |
These simulations confirm that our improved A* algorithm outperforms the traditional version by producing paths that are not only shorter but also more practical for AGV operations in smart parking garages. The reduction in turns and travel time translates to lower energy consumption and faster service, which are essential for scalable robot technology implementations. Additionally, the dynamic weight adjustment ensures that the algorithm remains efficient across varying environmental conditions, making it a robust solution for real-world applications. The integration of these elements demonstrates how advanced algorithms can drive innovation in robot technology, particularly in automated systems where precision and efficiency are paramount.
In conclusion, our improved A* algorithm addresses key challenges in path planning for smart parking garages by modifying the search strategy, incorporating dynamic weighting, and adding a turning penalty function. These enhancements result in paths that are shorter, have fewer turns, and require less travel time, thereby optimizing the performance of AGVs based on Mecanum wheel robot technology. The simulations validate the practicality of our approach, showing significant improvements over traditional methods. This work underscores the importance of tailoring algorithms to specific robotic constraints and environments, paving the way for more efficient and intelligent parking solutions. Future research could explore the integration of multiple algorithms, such as combining A* with machine learning techniques, to further enhance obstacle avoidance and adaptability in dynamic settings. As robot technology continues to evolve, such advancements will play a crucial role in realizing fully automated urban infrastructure, ultimately contributing to smarter and more sustainable cities.
The implications of this study extend beyond parking garages to other domains where mobile robot technology is applied, such as warehouses, hospitals, and manufacturing facilities. By refining path planning algorithms, we can unlock new levels of autonomy and efficiency in robotic systems. For example, the dynamic weight adjustment method could be adapted for use in multi-robot coordination, where real-time path optimization is critical to avoid collisions and maximize throughput. Similarly, the turning penalty function might be customized for different types of robots with varying kinematic properties, ensuring broad applicability across diverse robot technology platforms. Moreover, the grid-based modeling approach used here can be extended to three-dimensional environments or combined with sensor data for more accurate representations, enabling robots to navigate complex spaces with greater precision.
In terms of computational complexity, our improved A* algorithm maintains a balance between performance and resource usage. The 4-neighborhood search reduces the number of nodes evaluated during each iteration, which can lower memory requirements and processing time in large-scale deployments. This is particularly beneficial in embedded systems common in robot technology, where computational resources are often limited. The dynamic weight coefficient further optimizes this by focusing the search on promising regions, reducing unnecessary computations. Empirical tests in our simulations showed that the algorithm could handle grids of up to 40×40 cells with obstacle densities of 25% without significant slowdowns, demonstrating its scalability. Future work could involve testing in even larger environments or with real-time data streams to assess robustness under practical conditions.
Another aspect worth considering is the integration of our algorithm with other components of robot technology, such as localization and control systems. For instance, in smart parking garages, AGVs must accurately perceive their position using sensors like LiDAR or cameras, and then execute the planned path with high precision. By coupling our improved A* algorithm with robust localization techniques, we can ensure that paths are not only optimal but also executable in the presence of uncertainties. This holistic approach aligns with the broader trends in robot technology, where algorithms are designed to work seamlessly with hardware and sensory inputs. Additionally, the turning penalty function could be extended to account for other factors, such as energy consumption or wear and tear on robotic components, further enhancing the longevity and reliability of automated systems.
From a practical standpoint, the adoption of our improved path planning method could lead to tangible benefits in smart parking garage operations. For example, reduced travel times and fewer turns mean that AGVs can complete more tasks per hour, increasing the overall throughput of the system. This efficiency gain is crucial in high-demand urban areas where parking space is scarce. Moreover, the smoother paths generated by our algorithm can improve passenger comfort in cases where AGVs transport vehicles with occupants, as abrupt turns and stops are minimized. These improvements highlight how incremental advances in robot technology can have a significant impact on user experience and operational economics.
In summary, this paper presents a comprehensive approach to enhancing the A* algorithm for mobile robot path planning in smart parking garages. Through strategic modifications, we have shown that it is possible to achieve better performance in terms of path quality, efficiency, and practicality. The results underscore the value of continuous innovation in robot technology and its applications in solving real-world problems. As we move forward, it is essential to keep exploring new ways to integrate algorithmic improvements with emerging technologies, such as artificial intelligence and the Internet of Things, to create even more intelligent and adaptive robotic systems. This journey not only advances the field of robot technology but also contributes to the broader goal of building smarter, more efficient urban environments for future generations.