• Equitable Power Diagrams
• autonomous underwater vehicles
• Renyi’s entropy

This Thesis investigates innovative exploration methods for marine area search with teams of autonomous underwater vehicles (AUVs). In particular, methods for cooperative adaptive motion planning have been developed, general in nature, but in our case applied to the field of marine archaeological search, where the goal is to find remnants or objects resting on, or buried in, the seabed.

The exploration and motion planning problem is divided in two main lines of investigation. The first consists in defining a map of a priori detection probability in accordance with the available information and data over the survey area. Therefore, a refined mathematical method, that uses Parzen windows theory with Gaussian kernels, is developed for building the a priori map. The Renyi's entropy is used as the metric indicating relative information gain.
The second line of investigation instead defines how to compute the optimal waypoints for each AUV when the search mission is in progress. It can be seen as a classical problem of motion planning, which in marine environment usually involves preplanning paths offline before the exploration, either zig-zag or regular lawn-mower transects. The lawn-mower patterns have some failings:
• The AUV may not be able to search in marine areas where the a priori probability is optimum. Hence, the AUV does not move in areas with higher density of objects resting on or buried in the seabed.
• If during the mission some objects are discovered the pre-specified path does not change. Instead, these objects may have influence on a priori information used at the beginning of the mission and therefore a new planning path may be requested.
• The map of a priori detection probability is not updated dynamically with the exploration in progress.
• The AUVs are not able to establish a cooperative communication and localization procedure. Hence, once the vehicle submerges, its location estimate will drift, eventually deviating from the pre-specified paths.
These failures are ridden out using a new online and adaptive approach to define the AUVs' paths. Therefore, a cooperative distributed algorithm is developed defining the AUVs' waypoints by the minimization of the information entropy over the a priori map.
Note that the a-priori map built as previously indicated is naturally suited to this approach. The algorithm is implemented by partitioning the marine area through the Equitable Power Diagrams theory, by potential functions for motion planning and taking into account communication constraints.

The benefits of the proposed algorithms are evaluated within the application field of underwater archaeology. In particular, a performance metric has been defined in terms of relicts found in a fixed time, time to complete the mission, number of relicts found and area explored for relicts found. The Tuscan Archipelago database, kindly made available to us by the Tuscan Superintendence on Cultural Heritage, has given the ground information to apply the investigated algorithms. Simulations results are summarized to show the effectiveness of the novel proposed exploration method. While the performance results are tied to the application domain chosen, it is clear that the methodology and approaches proposed can also be used for other search and rescue applications.