Improved A* multirobot path planning method based on spatiotemporal expansion and directional guidance

Abstract

In view of the problems of frequent path conflicts and low planning efficiency in collaborative operations of multiple robots in dense environments such as warehousing and logistics, an improved A* path planning method that integrates spatiotemporal extension and directional guidance is proposed. Based on the traditional A* algorithm, this method introduces the time dimension into a two-dimensional planar grid map to construct a three-dimensional spatiotemporal coordinate system, achieving time-domain separation of multiple robot trajectories and fundamentally avoiding node conflicts. Simultaneously, it introduces a directional vector from the starting point to the target point as a heuristic guidance, designs an angle threshold and probability relaxation mechanism, optimizes the node selection strategy in the Open list, and reduces the expansion of invalid nodes. The adoptability and time complexity of the improved algorithm are theoretically analyzed. The theoretical analysis clarifies the admissibility boundary of the improved algorithm, pointing out that although the introduction of the probabilistic relaxation mechanism prevents the algorithm from guaranteeing strict global optimality in the mathematical sense, the path quality loss can be limited to an engineering-acceptable range through threshold constraints and probability control. Simulation experiments in a Gazebo-based warehouse scenario with dynamic pedestrians and communication bandwidth constraints show that the improved algorithm reduces the average number of node visits by 32.6% and the path planning time by 27.4%, while the pathlength increase does not exceed 2.3%, achieving a favorable balance between planning efficiency and path quality.