Abstract:In the research and practice of multi-agent systems, formation path planning is particularly crucial, as it not only ensures the safe operation of agents but also enhances the efficiency of the system in task execution. This study introduces a multi-agent formation path planning method adapted for dynamic and complex environments, ensuring the system's real-time responsiveness in dynamic obstacle avoidance and formation shape maintenance. The paper develops two core algorithms: one dedicated to local motion planning and the other focused on global path planning. The local motion planning algorithm iteratively applies semidefinite programming and quadratic programming to identify obstacle-free convex regions around agents and optimizes formation parameters through continuous convex optimization techniques. This approach effectively addresses the issue of multi-agent formation avoiding dynamic obstacles, ensuring the stability of the formation while adhering to environmental constraints. In the global path planning phase, this concept is further utilized by sampling obstacle-free convex regions in free space, combined with constraint optimization to calculate transitional formations between the initial and target formations, and employing graph search algorithms to find the optimal path to the target formation. The paper utilizes MATLAB to build a complex warehouse environment with both dynamic and static obstacles to verify the effectiveness of the method. It also compares the approach with the virtual structure method and Probabilistic Roadmap (PRM), demonstrating its superiority in terms of efficiency and accuracy.