The Research On Multi-Robot Pursuit Strategy

The multi-player pursuit-evasion games is a hot issue in the field of artificialintelligence and distributed control, and also is an important way in investigation ofmulti-agent’s collaboration and coordination in multi-robot system.The complexity of pursuit-evasion games increases exponentially, and thehierarchical approach decompose the multi-player pursuit-evasion games involvingmulti-pursuers and multi-evaders into several games with one pursuer and oneevader, so the problem is become simple. The hierarchical approach can also ensurethe efficiency of pursuit. In multi-player pursuit-evasion games, some of pursuersunite as a pursuers-coalition, pursuers in coalition communicate and cooperate witheach other in order to achieve an efficient strategy of pursuit and evaders would becaught much faster. All of the pursuers in games divide into severalpursuers-coalitions and called a pursuers-coalition structure. Optimal coalitionstructure problem solving is to search a pursuers-coalition structure with themaximum pay in all of the possible pursuers-coalition structures. But the number ofpursuers-coalition structures increase exponentially as the number of robot increase,so the optimal coalition structure problem solving is very complex. In this thesis,we improved the coalition gain independence in pursuit-evasion games and got thenumber of coalition in the optimal pursuers-coalition structure, than algorithmSPGP (The Search of Pursuers-Coalition Structure based on Greedy Pay) is given.It gets the level in the coalition structure graph by the number of evaders, and theleader of every coalition is solved. The algorithm SPGP made the search volumemuch smaller. The efficient of the algorithm SPGP is validated by theory andsimulation experiment.Also in this thesis, a hierarchical approach to the multi-player pursuit-evasiongames based on fast marching method which provide a pursuit strategy is given.During pursuit, the number of pursuers is more than that of evaders. The pursuerswithout task can be incorporated into the game by constructing Active Regions byusing Fast Marching Method. So the constringent pursuit strategy is achieved.