Abstract
In this thesis we deal with the problem of navigating a team of robots in both known and unknown environments, so as the mission's objectives to be fulfilled. The structure of this thesis is divided into two main pillars. In the first pillar we deal with the problem of determining an optimal path involving all points of a given area of interest (offline), while avoiding sub-areas with specific characteristics (e.g. obstacles, no-fly zones, etc.). This problem, which is usually referred as multi-robot coverage path planning (mCPP), has been proven to be NP-hard. Currently, existing approaches produce polynomial algorithms that are able to only approximate the minimum covering time. In chapter 3, a novel methodology is proposed, capable of producing such optimal paths in approximately polynomial time. In the heart of the proposed approach lies the DARP algorithm, which divides the terrain into a number of equal areas each corresponding to a specific robot, in such a way to guarantee: com ...
In this thesis we deal with the problem of navigating a team of robots in both known and unknown environments, so as the mission's objectives to be fulfilled. The structure of this thesis is divided into two main pillars. In the first pillar we deal with the problem of determining an optimal path involving all points of a given area of interest (offline), while avoiding sub-areas with specific characteristics (e.g. obstacles, no-fly zones, etc.). This problem, which is usually referred as multi-robot coverage path planning (mCPP), has been proven to be NP-hard. Currently, existing approaches produce polynomial algorithms that are able to only approximate the minimum covering time. In chapter 3, a novel methodology is proposed, capable of producing such optimal paths in approximately polynomial time. In the heart of the proposed approach lies the DARP algorithm, which divides the terrain into a number of equal areas each corresponding to a specific robot, in such a way to guarantee: complete coverage, non-backtracking solution, minimum coverage path, while at the same time does not need any preparatory stage. In the second pillar of this thesis, we design algorithms capable of navigating team of robots without any prior knowledge. More specifically, we deal with problems where the objectives of the multi-robot system can be transformed to the optimization of a specifically defined cost-function. Due to the unknown environment, unknown robots' dynamics, sensor nonlinearities, etc., the analytic form of the cost-function is not available a priori. Therefore, standard gradient descent-like algorithms are not applicable to these problems. In chapter 4, 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-robot exploration. 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. This combination results in a multi-robot 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 Leixoes port, Portugal. Finally, in chapter 5, we propose a distributed algorithm applicable to a quite large class of practical multi-robot applications. In such multi-robot applications, the user-defined objectives of the mission can be casted as a general optimization problem, without explicit guidelines of the sub-tasks per different robot. A novel distributed methodology is proposed, based on the CAO algorithm (as proposed on the previous chapter) that carefully designs a cost-function for each operational robot, where the joined optimization of which can accomplish the overall team objectives. The latter can be achieved by online learning (on each robot), only the problem-specific characteristics that affect the accomplishment of the overall mission objectives. The overall, low-complexity algorithm, can straightforwardly incorporate any kind of operational constraint, is fault tolerant and can appropriately tackle time-varying cost-functions. A cornerstone of this approach is that it shares the same convergence characteristics as those of block coordinate descent algorithms. The proposed algorithm is evaluated in four heterogeneous simulation set-ups under multiple scenarios, against both general purpose (centralized) and specifically-tailored to the problem in hand, algorithms.
show more
