Abstract

In this dissertation, the cooperative multi agent search and coverage problem in uncertain environments is investigated. Each agent individually plans its desired trajectory. The agents exchange their positions and their sensors’ measurement with their neighbouring agents through a communication channel in order to maintain the cooperation objective.
Different aspects of multi agent search and coverage problem are investigated. Several models for uncertain environments are proposed and the updating rules for the probability maps are provided. Each of this models is appropriate for a specific type of problems. The cooperative search mission is first converted to a decentralized multi agent optimal path planning problem, using rolling horizon dynamic programming approach which is a mid-level controller. To make cooperation between agents possible, two approximation methods are proposed to modify the objective function of agents and to take into the account the decision of other agents. The simulation results show the proposed methods can considerably increase the performance of mission without significantly increasing the computation burden. This approach is then extended for the case with known communication delay between mobile agents. The simulation results show the proposed methods can compensate for the effect of known communication delay between mobile agents. A Voronoi-based search strategy for a team of mobile agents with limited range sensors is also proposed which combines both mid-level and low-level controllers. The strategy includes the short-term objective of maximizing the uncertainty reduction in the next step, the long-term objective of distributing the agents in the environment with minimum overlap in their sensory domain, and the collision avoidance constraint. The simulation results show the proposed control law can reduce the value of uncertainty in the environment below any desired threshold.
For the search and coverage problem, we first introduce a framework that includes two types of agents; search agents and coverage agents. The problem is formulated such that the information about the position of the targets is updated by the search agents. The coverage agents use this information to concentrate around the more important areas in the environment. The proposed cooperative search method, along with a well-known Centroidal Voronoi Configuration method for coverage, is used to solve the problem. The effectiveness of the proposed algorithm is demonstrated by simulation and experiment. We then introduce the “limited turn rate Voronoi diagram” and formulate the search and coverage problem as a multi-objective optimization problem with different constraints which is able to consider practical issues like minimum fuel consumption, refueling, obstacle avoidance, and collision avoidance. In this approach, there is only one type of agents which performs both search and coverage tasks. The “multi agent search and coverage problem” is formulated such that the “multi agent search problem” and “multi agent coverage problem” are special cases of this problem. The simulation results show the effectiveness of the proposed method.