Multi-Robot Cooperative Planning Under Road Network Constraints

Along with the booming development of intelligent robotics,multi-robot collaboration is also receiving increased attention.Compared with single robot,multi-robot system are more efficient,more environment-adaptive,more fault-tolerant,more task-adaptive,and more situational-aware than single robot.Multi-robot collaboration technology is the key to take advantage of multi-robot system,and multi-robot pursuit is a typical multirobot collaboration problem,which is a hot spot in current multi-robot system research.Multi-robot collaborative path planning is an important basic capability of multi-robot pursuit,which directly affects the execution result of the pursuit task.Multi-robot pursuit is a process in which allied robots pursuit the enemy through collaborative motion,which is a multi-robot collaborative path planning problem in a broad sense.In this thesis,for the practical application requirements of multi-robot system and for the road network environment,we study the multi-robot collaborative path planning and multi-robot pursuit in a narrow sense.The main work and research results of this thesis are as follows:1.For the online multi-robot collaborative path planning problem under road network constraints,a predictive planning algorithm and a dynamic road network addition algorithm are proposed.Conflict detection is the basis of collaborative path planning,and this thesis designs the collision detect method of swept volume interference based on geometric relations to realize the conflict detection of action sequences.In this thesis,a single-robot planning algorithm Safe Interval Path Planning with Turn(SIPPT)is designed to consider steering,which can set constraints and plan action sequences satisfying the constraints based on conflicts.The original Continuous-Time Conflict-Based Search(CCBS)can only solve the offline multi-robot collaborative path planning problem under the road network constraint,but in this thesis,we design the predictive planning algorithm and dynamic road network addition algorithm to solve the problem of execution error caused by the computation delay and message transmission delay in the online scenario and the possible failure of the robots to perform.This thesis extends the collaborative path planning algorithm to the online scenario by designing a predictive planning algorithm and a dynamic road network addition algorithm to solve the execution error problem caused by computational delay and message transmission delay in the online scenario and the problem that robots may not be able to plan at map nodes.Experiments show that the online multi-robot collaborative motion replanning using the algorithm in this thesis does not require robots to pause their motion and wait for replanning,which can effectively improve the system operation efficiency.2.Based on the game tree,we study the collaborative pursuit problem under road network constraints and propose an effective pursuit strategy.In this thesis,we first study the problem of pursuit under the assumption of sequential action: based on the actual situation of pursuit under road network constraints,we improve the representation of the pursuit state and the determination method of successful pursuit;we design an algorithm that can generate a uniform topological map from the road network with specified accuracy,which lays the foundation for applying the research results of sequential action pursuit game to the road network environment;we construct a decision tree model for pursuit planning,which unifies the design of the pursuit algorithm The decision tree model of pursuit planning is constructed to unify the design of the pursuit algorithm to the design of the state utility function;the Monte Carlo tree search algorithm is used to improve the decision quality of the backpropagation analysis of the pursuit strategy in the state where the success of the pursuit cannot be guaranteed.In addition,this thesis proposes a pursuit strategy based on the assumption of target stationarity,which can be applied to both sequential action pursuit and simultaneous action sequential pursuit under road network constraints.Based on the study of sequential action pursuit on uniform topological graphs,this thesis investigates the pursuit problem under road network constraints: a strategy migration method with state utility values as a bridge is proposed to migrate the backpropagation analysis strategy to the road network environment;the performance of the backpropagation analysis strategy and the target stationary hypothesis-based pursuit strategy are experimentally compared in the road network environment,and it is found that the backpropagation analysis strategy has better preplanning,while the target stationary hypothesis-based pursuit The performance of the backpropagation analysis strategy is found to be better in preplanning,while the target stationary hypothesis-based pursuit strategy is better in rounding up the final parking location;in order to take advantage of both strategies,a composite pursuit strategy is designed,and the performance advantages of the composite pursuit strategy are verified through experiments.