Path Planning with Adaptive Autonomy Based on an Improved A∗ Algorithm and Dynamic Programming for Mobile Robots

Sustainable path-planning algorithms are essential for executing complex user-defined missions by mobile robots. Addressing various scenarios with a unified criterion during the design phase is often impractical due to the potential for unforeseen situations. Therefore, it is important to incorporate the concept of adaptive autonomy for path planning. This approach allows the system to autonomously select the best path-planning strategy. The technique utilizes dynamic programming with an adaptive memory size, leveraging a cellular decomposition technique to divide the map into convex cells. The path is divided into three segments: the first segment connects the starting point to the center of the starting cell, the second segment connects the center of the goal cell to the goal point, and the third segment connects the center of the starting cell to the center of the goal cell. Since each cell is convex, internal path planning simply requires a straight line between two points within a cell. Path planning uses an improved A∗ (I-A∗) algorithm, which evaluates the feasibility of a direct path to the goal from the current position during execution. When a direct path is discovered, the algorithm promptly returns and saves it in memory. The memory size is proportional to the square of the total number of cells, and it stores paths between the centers of cells. By storing and reusing previously calculated paths, this method significantly reduces redundant computation and supports long-term sustainability in mobile robot deployments. The final phase of the path-planning process involves pruning, which eliminates unnecessary waypoints. This approach obviates the need for repetitive path planning across different scenarios thanks to its compact memory size. As a result, paths can be swiftly retrieved from memory when needed, enabling efficient and prompt navigation. Simulation results indicate that this algorithm consistently outperforms other algorithms in finding the shortest path quickly.