Real-time adaptive multi-robot exploration with application to underwater map construction

This paper deals with the problem of autonomous exploration of unknown areas using teams of Autonomous X Vehicles (AXVs)—with X standing for Aerial, Underwater or Sea-surface—where the AXVs have to autonomously navigate themselves so as to construct an accurate map of the unknown area. Such a problem can be transformed into a dynamic optimization problem which, however, is NP-complete and thus infeasible to be solved. A usual attempt is to relax this problem by employing greedy (optimal one-step-ahead) solutions which may end-up quite problematic. In this paper, we first show that optimal one-step-ahead exploration schemes that are based on a transformed optimization criterion can lead to highly efficient solutions to the multi-AXV exploration. Such a transformed optimization criterion is constructed using both theoretical analysis and experimental investigations and attempts to minimize the “disturbing” effect of deadlocks and nonlinearities to the overall exploration scheme. As, however, optimal one-step-ahead solutions to the transformed optimization criterion cannot be practically obtained using conventional optimization schemes, the second step in our approach is to combine the use of the transformed optimization criterion with the cognitive adaptive optimization (CAO): CAO is a practicably feasible computational methodology which adaptively provides an accurate approximation of the optimal one-step-ahead solutions. The combination of the transformed optimization criterion with CAO results in a multi-AXV exploration scheme which is both practically implementable and provides with quite efficient solutions as it is shown both by theoretical analysis and, most importantly, by extensive simulation experiments and real-life underwater sea-floor mapping experiments in the Leixes port, Portugal.