Research And Implementation Of Multi-UAV Real-time Path Planning Based On Multi-agent System

With the rapid development of modern warfare, the sky has become one of themain battlefields of the war, different functions of UAVs have become the protagonistof the battlefield, and a huge number of UAVs collaboration to complete the complexmilitary task will become a necessity.In recent years, with the application of distributed systems become more and morewidely, the Generalized Assignment Problem applied to distributed systems to solve theproblem has become a necessity. The Rapidly-Exploring Random Tree has recentlyshown promising results in trajectory design and path planning problems.Targeted this background, this thesis takes in-depth research of multi-UAVreal-time path planning technology, combined with Multi-Agent technology, solve thepath planning problem as a distributed generalized assignment problem, and optimizethe generates path of the RRT algorithm with this idea, in order to quickly generate thepath that is conflict-free with the constraints such as obstacles and the threats to achievemulti-UAV real-time path planning.The thesis first describes the issues related to UAV path planning, then analysis thesignificance of the multi-UAV path planning and the key technologies and researchstatus of path planning, and the thesis analysis the Generalized Assignment Problemwithin the distributed systems.Then, according to the needs of multi-UAV real-time path planning, the thesisproposed the multi-UAV real-time path planning framework within the D-GAP-basedMulti-Agent systems that combines the classic RRT search algorithm. In the thesis, theUAVs and the environmental constraints are abstracted to the agents, with theframework based on the D-GAP model; we use a set of distributed networked constraintagents to detect the paths which are generated by RRT algorithm. When constraint agentreceived the path from the UAV agent, it will make the path traverse all constraintagents according to some delivery order as soon as possible. If the path cannot satisfyone of the constraint agents, this constraint agent will terminate the path detection, markthe waypoint which is not satisfying the constraint, and reply it to the UAV agent, then the UAV agent will take another waypoint to stand of the marked one. Then, theconstraint agent will pass the marked waypoint to other constraint agents for learningand establishing the decision-making model. In this way, we can select the paths thatgenerated by RRT algorithm which can quick path through the multi-agent network.And send the optimal one to the team agent to detect. If the path does not satisfy theconstraints between the teams, the priority to select the path to be modified based on thedefinition of the UAV task. If the constraint conflict between UAVs cannot beeliminated, then there is no solution. If all UAV’s flight paths to meet the constraintsbetween the teams, produce the group flight path feasible solution vector pathList, andcomplete the path planning process.The framework gives full play to the parallel features of Multi-Agent Systems,D-GAP framework loaded Multi-Agent Systems Network can quickly detect the pathgenerated by the RRT and each agent backtracking learning, to accelerate the speed ofthe future path of the detection.Finally, we make simulation and analysis of the above method, and the simulationresults show the correctness and feasibility of the proposed method.