Optimal Multi-Robot Exploration For Static Environment

Abstract

Persistent surveillance or exploration of any static environment requires the agent to cover the entire mission space in a fixed amount of time. In this thesis, a similar problem is addressed by deploying multiple agents and controlling their movement and direction by parameterizing their trajectories. It has been proven that in a one dimensional space, the best solution is to move the agent at maximum speed in a direction and then switch directions when points of interest are reached, after collecting information from those points. But in two dimensional spaces, such conclusions can no longer be drawn. In this thesis, the agent trajectories are represented by a parametric function which can be optimized. The points are associated with a time-varying uncertainty function which increases if the points are not within the sensing range of the agent. First, a single agent is considered and its trajectory is optimized by using different cost functions and initial conditions. Infinitesimal Perturbation Analysis(IPA) is used to calculate the cost function with respect to the trajectory parameters. A major part of this thesis is devoted to find an appropriate cost function which solves the persistent surveillance problem. This thesis also concentrates on providing a solution for obstacle avoidance. The problem considered here is highly non-convex and therefore global optimizing techniques must be used. Stochastic Comparison Algorithm is used to find a global optimal solution. The simulation results shows the comparison between all the methods used