This thesis discusses the use of a cooperative multiple robot system as applied to distributed tracking and sampling of a boundary edge. Within this system the boundary edge is partitioned into subsegments, each allocated to a particular robot such that workload is balanced across the robots. Also, to minimize the time between sampling local areas of the boundary edge, it is desirable to minimize the difference between each robot’s progression (i.e. phase) along its allocated sub segment of the edge. The paper introduces a new distributed controller that handles both workload and phase balancing. Simulation results are used to illustrate the effectiveness of the controller in an Autonomous Underwater Vehicle (AUV) under ice edge sampling application. Successful results from experimentation with three iRobot(R) Creates are also presented.

The classical n-bugs problem has attracted considerable attention from researchers. This problem stems from the study of movement of a group of animals. In the context of multi- agent systems the problem has been modelled as cyclic pursuit. Under this paradigm, every agent, indexed i, chases its unique leader, agent i + 1 (modulo n), with n being the total number of agents. In the existing literature, cyclic pursuit has been studied for homogeneous agents where each agent’s velocity is proportional to the distance separating it from its leader and is directed along the line joining it to its leader. The constant of proportionality, initially chosen to be the same for all the agents, resulted in consensus in position, without the need for any centralized controller. Later, the constant of proportionality, alternately called the gain, was allowed to be heterogeneous and positional consensus was still achieved. Moreover, it was shown that the point of convergence, where the agents rendezvous, could be chosen at will, except for some diagnostic cases. In this thesis, besides admitting heterogeneous gains, the agents are assumed to pursue their respective leaders with an angle of deviation from the line joining them to their corresponding leaders. This expands the reachability set (set of points where the agents can rendezvous) for the system of agents to include points that were hitherto unreachable. Sufficient conditions for stability of such systems have been derived in this thesis. Detailed analysis of the reachability set has also been carried out. Some researchers have also investigated hierarchical cyclic pursuit, where there are multiple levels of pursuit. For instance, in the two level hierarchical pursuit, the agents are divided into m groups of n agents each, where each agent in a group chases its leader within the group as well as a similarly indexed agent in its leading group. Thus, groups of agents are also in cyclic pursuit. So far, only homogeneous gains were considered under this paradigm. The present thesis admits heterogeneous gains and establishes necessary and sufficient conditions for the stability of heterogeneous hierarchical cyclic pursuit, that generalize existing results. Reachable sets are also derived for this case. It is proved that the existing results can be derived as special cases of the ones considered in this thesis. As an extension to a realistic application, the importance of expansion in reachable set vis-a`-vis capturing a moving target is highlighted in this thesis. It has been shown that if the target’s initial position is reachable, then using a control law proposed in the thesis, the target can be captured. This control law is essentially an augmented cyclic pursuit law with the target’s velocity information fed to each agent in addition to the conventional cyclic pursuit command. Analysis has been carried out for agents with double integrator dynamics as well. A control law in conjunction with an algorithm is proposed that helps ensure global reachability of agents, with double integrator dynamics, in cyclic pursuit. Another application, in which cyclic pursuit and a closely related topology called platooning have been coupled together to track the boundaries of unknown regions and constantly monitor them, is addressed in this thesis. This problem is especially important in monitoring forest fire, marine contamination, volcanic ash eruptions, etc., and can protect human life by cordoning off unsafe regions using multiple autonomous agents. Lastly, discrete time cyclic pursuit laws are analyzed to obtain results similar to the continuous time counterparts that exist in the literature. Moreover, heterogeneous gains and deviations are admitted similar to the continuous time version considered in this thesis. Gershgorin’s theorem is used extensively to arrive at sufficient conditions for the stability of such discrete time deviated cyclic pursuit systems. Reachability sets are also derived. In case of discrete time systems, loss of synchronization due to no common clock for autonomous agents is a very realistic scenario. This thesis obtains some results on the stability of such asynchronous cyclic pursuit systems and indicates that special precautions are needed for dealing with heterogeneous cyclic pursuit systems even when one gain is negative, since the system may not converge, depending on the initial positions of the agents and the sequence of updates.

A segmentação de imagens é um problema muito importante em visão computacional, no qual uma imagem é dividida em regiões relevantes, tal como para isolar objetos de interesse de uma dada aplicação. Métodos de segmentação baseados na transformada imagem-floresta (IFT, Image Foresting Transform), com funções de conexidade monotonicamente incrementais (MI) têm alcançado um grande sucesso em vários contextos. Na segmentação interativa de imagens, na qual o usuário pode especificar o objeto desejado, novas sementes podem ser adicionadas e/ou removidas para corrigir a rotulação até conseguir a segmentação esperada. Este processo gera uma sequência de IFTs que podem ser calculadas de modo mais eficiente pela DIFT (Differential Image Foresting Transform). Recentemente, funções de conexidade não monotonicamente incrementais (NMI) têm sido usadas com sucesso no arcabouço da IFT no contexto de segmentação de imagens, permitindo incorporar informações de alto nível, tais como, restrições de forma, polaridade de borda e restrição de conexidade, a fim de customizar a segmentação para um dado objeto desejado. Funções não monotonicamente incrementais foram também exploradas com sucesso na geração de superpixels, via sequências de execuções da IFT. Neste trabalho, apresentamos um estudo sobre a Transformada Imagem-Floresta Diferencial no caso de funções NMI. Nossos estudos indicam que o algoritmo da DIFT original apresenta uma série de inconsistências para funções não monotonicamente incrementais. Este trabalho estende a DIFT, visando incorporar um subconjunto das funções NMI em grafos dirigidos e mostrar sua aplicação no contexto da geração de superpixels. Outra aplicação que é apresentada para difundir a relevância das funções NMI é o algoritmo Bandeirantes para perseguição de bordas e rastreamento de curvas. / Image segmentation is a problem of great relevance in computer vision, in which an image is divided into relevant regions, such as to isolate an object of interest for a given application. Segmentation methods with monotonically incremental connectivity functions (MI) based on the Image Foresting Transform (IFT) have achieved great success in several contexts. In interactive segmentation of images, in which the user is allowed to specify the desired object, new seeds can be added and/or removed to correct the labeling until achieving the expected segmentation. This process generates a sequence of IFTs that can be calculated more efficiently by the Differential Image Foresting Trans- form (DIFT). Recently, non-monotonically incremental connectivity functions (NMI) have been used successfully in the IFT framework in the context of image segmentation, allowing the incorporation of shape, boundary polarity, and connectivity constraints, in order to customize the segmentation for a given target object. Non-monotonically incremental functions were also successfully exploited in the generation of superpixels, via sequences of IFT executions. In this work, we present a study of the Differential Image Foresting Transform in the case of NMI functions. Our research indicates that the original DIFT algorithm presents a series of inconsistencies for non-monotonically incremental functions. This work extends the DIFT algorithm to NMI functions in directed graphs, and shows its application in the context of the generation of superpixels. Another application that is presented to spread the relevance of NMI functions is the Bandeirantes algorithm for curve tracing and boundary tracking.

A segmentação de imagens é um problema muito importante em visão computacional, no qual uma imagem é dividida em regiões relevantes, tal como para isolar objetos de interesse de uma dada aplicação. Métodos de segmentação baseados na transformada imagem-floresta (IFT, Image Foresting Transform), com funções de conexidade monotonicamente incrementais (MI) têm alcançado um grande sucesso em vários contextos. Na segmentação interativa de imagens, na qual o usuário pode especificar o objeto desejado, novas sementes podem ser adicionadas e/ou removidas para corrigir a rotulação até conseguir a segmentação esperada. Este processo gera uma sequência de IFTs que podem ser calculadas de modo mais eficiente pela DIFT (Differential Image Foresting Transform). Recentemente, funções de conexidade não monotonicamente incrementais (NMI) têm sido usadas com sucesso no arcabouço da IFT no contexto de segmentação de imagens, permitindo incorporar informações de alto nível, tais como, restrições de forma, polaridade de borda e restrição de conexidade, a fim de customizar a segmentação para um dado objeto desejado. Funções não monotonicamente incrementais foram também exploradas com sucesso na geração de superpixels, via sequências de execuções da IFT. Neste trabalho, apresentamos um estudo sobre a Transformada Imagem-Floresta Diferencial no caso de funções NMI. Nossos estudos indicam que o algoritmo da DIFT original apresenta uma série de inconsistências para funções não monotonicamente incrementais. Este trabalho estende a DIFT, visando incorporar um subconjunto das funções NMI em grafos dirigidos e mostrar sua aplicação no contexto da geração de superpixels. Outra aplicação que é apresentada para difundir a relevância das funções NMI é o algoritmo Bandeirantes para perseguição de bordas e rastreamento de curvas. / Image segmentation is a problem of great relevance in computer vision, in which an image is divided into relevant regions, such as to isolate an object of interest for a given application. Segmentation methods with monotonically incremental connectivity functions (MI) based on the Image Foresting Transform (IFT) have achieved great success in several contexts. In interactive segmentation of images, in which the user is allowed to specify the desired object, new seeds can be added and/or removed to correct the labeling until achieving the expected segmentation. This process generates a sequence of IFTs that can be calculated more efficiently by the Differential Image Foresting Trans- form (DIFT). Recently, non-monotonically incremental connectivity functions (NMI) have been used successfully in the IFT framework in the context of image segmentation, allowing the incorporation of shape, boundary polarity, and connectivity constraints, in order to customize the segmentation for a given target object. Non-monotonically incremental functions were also successfully exploited in the generation of superpixels, via sequences of IFT executions. In this work, we present a study of the Differential Image Foresting Transform in the case of NMI functions. Our research indicates that the original DIFT algorithm presents a series of inconsistencies for non-monotonically incremental functions. This work extends the DIFT algorithm to NMI functions in directed graphs, and shows its application in the context of the generation of superpixels. Another application that is presented to spread the relevance of NMI functions is the Bandeirantes algorithm for curve tracing and boundary tracking.