Preview

PDF, English Download (44MB) | Terms of use

Abstract

Robotic applications like search and rescue missions, surveillance, police missions, patrolling, and warfare can all be modeled as a Pursuit-Evasion Game (PEG). Most of these tasks are multi-agent problems, often including a cooperation between team members and a conflict between adversarial teams. In order to realize such a situation with robots, two major problems have to be solved. Initially, a decomposition of the PEG has to be performed for getting results in reasonable time. Present embedded computers lack the computational power enabling them to process the highly complex solution algorithm of the non-decomposed game fast enough. Secondly, a framework has to be defined, enabling the computation of optimal actions for both the pursuers and the evaders when a cooperation within the teams is possible. It is intended to develop strategies, that allow the team of pursuers to capture a faster evader in a visibility-based PEG setup due to cooperation. For tackling the first problem a game structure is sought, aiming to considerably reduce the time complexity of the solution process. The first step is the decomposition of the action space, and the second is the change of the game structure itself. The latter is reached by defining a two-pursuer one-evader PEG with three different game structures, which are the Non-Decomposed Game, the Multiple Two-Player Game Decomposition (MTPGD) game, and the Team-Subsumption Two-Player Game (TSTPG). Several simulation results demonstrate, that both methods yield close results in respect to the full game. With increasing cardinality of each player’s strategy space, the MTPGD yields a relevant decrease of the run-time. Otherwise, the TSTPG does not minimize the time complexity, but enables the use of more sophisticated algorithms for two-player games, resulting in a decreased runtime. The cooperation within a team is enabled by introducing a hierarchical decomposition of the game. On a superordinate collaboration level, the pursuers choose their optimal behavioral strategy (e.g. pursuit and battue) resulting in the case of a two-pursuer one-evader PEG in a three-player noncooperative dynamic game, which is solved in a subordinate level of the overall game. This structure enables an intelligent behavior change for the pursuers based on game-theoretical solution methods. Depending on the state of the game, which behavioral strategy yields the best results for the pursuers within a predefined time horizon has to be evaluated. It is shown that the pursuer’s outcome can be improved by using a superordinate cooperation. Moreover, conditions are presented under which a capture of a faster evader by a group of two pursuers is possible in a visibility-based PEG with imperfect information. Since Unmanned Aerial Vehicles (UAVs) are increasingly a common platform used in the aforementioned applications, this work focuses only on PEGs with multi-rotor UAVs. Furthermore, the realization of the concepts in this thesis are applied on a real hex rotor. The feasibility of the approach is proven in experiments, while all implementations on the UAV are running in real-time. This framework provides a solution concept for all types of dynamic games with an 1-M or N-1 setup, that have a non-cooperative and cooperative nature. At this stage a N-M dynamic game is not applicable. Nevertheless, an approach to extend this framework to the N-M case is proposed in the last chapter of this work.