In this dissertation, we study multi-robot coordination in the context of multi-target tracking. Specifically, we are interested in the coordination achieved by means of submodular function optimization. Submodularity encodes the diminishing returns property that arises in multi-robot coordination. For example, the marginal gain of assigning an additional robot to track the same target diminishes as the number of robots assigned increases. The advantage of formulating coordination problems as submodular optimization is that a simple, greedy algorithm is guaranteed to give a good performance. However, often this comes at the expense of unrealistic models and assumptions. For example, the standard formulation does not take into account the fact that robots may fail, either randomly or due to adversarial attacks. When operating in uncertain conditions, we typically seek to optimize the expected performance. However, this does not give any flexibility for a user to seek conservative or aggressive behaviors from the team of robots. Furthermore, most coordination algorithms force robots to communicate at each time step, even though they may not need to. Our goal in this dissertation is to overcome these limitations by devising coordination algorithms that are parsimonious in communication, allow a user to manage the risk of the robot performance, and are resilient to worst-case robot failures and attacks. In the first part of this dissertation, we focus on designing parsimonious communication strategies for target tracking. Specifically, we investigate the problem of determining when to communicate and who to communicate with. When the robots use range sensors, the tracking performance is a function of the relative positions of the robots and the targets. We propose a self-triggered communication strategy in which a robot communicates its own position with its neighbors only when a certain set of conditions are violated. We prove that this strategy converges to the optimal robot positions for tracking a single target and in practice, reduces the number of communication messages by 30%. When tracking multiple targets, we can reduce the communication by forming subsets of robots and assigning one subset to track a target. We investigate a number of measures for tracking quality based on the observability matrix and show which ones are submodular and which ones are not. For non-submodular measures, we show a greedy algorithm gives a 1/(n+1) approximation, if we restrict the subset to n robots. In optimizing submodular functions, a common assumption is that the function value is deterministic, which may not hold in practice. For example, the sensor performance may depend on environmental conditions which are not known exactly. In the second part of the dissertation, we design an algorithm for stochastic submodular optimization. The standard formulation for stochastic optimization optimizes the expected performance. However, the expectation is a risk-neutral measure. Instead, we optimize the Conditional Value-at-Risk (CVaR), which allows the user the flexibility of choosing a risk level. We present an algorithm, based on the greedy algorithm, and prove that its performance has bounded suboptimality and improves with running time. We also present an online version of the algorithm to adapt to real-time scenarios. In the third part of this dissertation, we focus on scenarios where a set of robots may fail naturally or due to adversarial attacks. Our objective is to track as many targets as possible, a submodular measure, assuming worst-case robot failures. We present both centralized and distributed resilient tracking algorithms to cope with centralized and distributed communication settings. We prove these algorithms give a constant-factor approximation of the optimal in polynomial running time. / Doctor of Philosophy / Today, robotics and autonomous systems have been increasingly used in various areas such as manufacturing, military, agriculture, medical sciences, and environmental monitoring. However, most of these systems are fragile and vulnerable to adversarial attacks and uncertain environmental conditions. In most cases, even if a part of the system fails, the entire system performance can be significantly undermined. As robots start to coexist with humans, we need algorithms that can be trusted under real-world, not just ideal conditions. Thus, this dissertation focuses on enabling security, trustworthiness, and long-term autonomy in robotics and autonomous systems. In particular, we devise coordination algorithms that are resilient to attacks, trustworthy in the face of the uncertain conditions, and allow the long-term operation of multi-robot systems. We evaluate our algorithms through extensive simulations and proof-of-concept experiments. Generally speaking, multi-robot systems form the "physical" layer of Cyber-Physical Sytems (CPS), the Internet of Things (IoT), and Smart City. Thus, our research can find applications in the areas of connected and autonomous vehicles, intelligent transportation, communications and sensor networks, and environmental monitoring in smart cities.

Multi-robot task assignment (allocation) involves assigning robots to tasks in order to optimize the entire team’s performances. Until now, one of the most useful non-domain-specific ways to coordinate multi-robot systems is through task allocation mechanisms. This dissertation addresses the classic task assignment problems in which robots and tasks are eventually matched by forming a one-to-one mapping, and their overall performances (e.g., cost, utility, and risk) can be linearly summed. At a high level, this research emphasizes two facets of the multi-robot task assignment, including (1) novel extensions from classic assignment algorithms, and (2) completely newly designed task allocation methods with impressive new features. For the former, we first propose a strongly polynomial assignment sensitivity analysis algorithm as well as a means to measure the assignment uncertainties; after that we propose a novel method to address problems of multi-robot routing and formation morphing, the trajectories of which are obtained from projections of augmenting paths that reside in a new three-dimensional interpretation of embedded matching graphs. For the latter, we present two optimal assignment algorithms that are distributable and suitable for multi-robot task allocation problems: the first one is an anytime assignment algorithm that produces non-decreasing assignment solutions along a series of task-swapping operations, each of which updates the assignment configurations and thus can be interrupted at any moment; the second one is a new market-based algorithm with a novel pricing policy: in contrast to the buyers’ “selfish” bidding behaviors in conventional auction/market-based approaches, we employ a virtual merchant to strategically escalate market prices in order to reach a state of equilibrium that satisfies both the merchant and buyers. Both of these newly developed assignment algorithms have a strongly polynomial running time close to the benchmark algorithms but can be easily decentralized in terms of computation and communication.

Orientador: Prof. Dr. Luiz Henrique Bonani do Nascimento / Dissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Engenharia da Informação, 2016. / A crescente multiplicidade de serviços e a demanda por altas taxas de transmissão e de tráfego na rede fizeram das Redes Ópticas um recurso essencial no mundo contemporâneo. Recentemente, o advento das Redes Ópticas Elásticas (EON) permitiu que os dados sejam transportados em longas distâncias, fornecendo largura de banda e taxas de dados flexíveis, com base na tecnologia de Multiplexação por Divisão de Frequência Ortogonal (OFDM). Nos últimos anos, muitos esforços têm se concentrado na análise de desempenho dessas redes em vários cenários, entre os quais se destacam as variações de tipos de formato de modulação, de algoritmos de roteamento e alocação de espectro e de características nos tipos de serviços. A avaliação de tais cenários mostrou que diferentes tipos de serviço e diferentes estratégias de gerenciamentolevam a níveis muito díspares de desempenho entre serviços. Dessa forma, o objetivo desse trabalho é avaliar políticas híbridas de alocação de espectro, em termos de largura de faixa e taxa de bits, em cenários com compartilhamento dos recursos, de forma a analisar as diferenças de desempenho entre serviços e, assim, o nível de Qualidade de Serviço (QoS). As métricas adotadas para o trabalho são: (i) a probabilidade de bloqueio intraserviço e (ii) a probabilidade de bloqueio geral da rede e os resultados apresentados com a implantação de políticas híbridas permitiu obter fairness em EON. / The increasing amount of services and the demand for high transmission rates and network traffic, turn the Optical Networks as an essential resource in the contemporary world. Recently, the advent of Elastic Optical Networks (EON) allowed data transportation over long distances, providing flexible bandwidth and flexible data rates, based on Orthogonal Frequency Division Multiplexing (OFDM) technology. In recent years, many efforts have been made to analyse the performance of these networks in a great amount of scenarios, considering the variation of modulation formats, the variation of routing and spectrum assignment algorithms and the variation of service characteristics. The evaluation of such scenarios has shown that different kind of services and different management strategies lead to different levels of service performance. Therefore, the aim of this work is to evaluate hybrid policies for spectrum assignment, considering bandwidth and bit rate in a scenario where the network resources are shared, in order to analise the differences of performance among service types and than the level of Quality of Service (QoS). The adopted metrics are: (i) the intraservice blocking probability and (ii) the general blocking probability and the results presented to the deployment of hybrid policies yielded fairness in EON.

Submitted by bruna ortiz (brunaortiz.f@gmail.com) on 2016-07-04T15:34:48Z No. of bitstreams: 1 Dissertação-Laura Michaella Batista Ribeiro.pdf: 5196443 bytes, checksum: 44f8d0ba69aa5d5fb4454331819feaa4 (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2016-07-18T13:11:02Z (GMT) No. of bitstreams: 1 Dissertação-Laura Michaella Batista Ribeiro.pdf: 5196443 bytes, checksum: 44f8d0ba69aa5d5fb4454331819feaa4 (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2016-07-18T13:25:46Z (GMT) No. of bitstreams: 1 Dissertação-Laura Michaella Batista Ribeiro.pdf: 5196443 bytes, checksum: 44f8d0ba69aa5d5fb4454331819feaa4 (MD5) / Made available in DSpace on 2016-07-18T13:25:46Z (GMT). No. of bitstreams: 1 Dissertação-Laura Michaella Batista Ribeiro.pdf: 5196443 bytes, checksum: 44f8d0ba69aa5d5fb4454331819feaa4 (MD5) Previous issue date: 2014-04-07 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / With the significant utilization of the Wi-Fi networks as one of the main mass media and transmission of data, some problems of traffic reliability have been related and increasing day by day. The unplanned use of Access’ Points – AP, chained to the interferences resulting from coexistence of other technologies occupying the same frequency spectrum 2.4GHz, has constantly affected the performance of these networks. In order to propose a solution to interference’s problem between networks 802.11, this work describe an approach of attribution of channels based in many aspects such as received signal strength indicator, signal-to-noise ratio, link quality and channels overlap factor. This approach, named MFDCA (Multi-Factor Dynamic Channel Assignment) is composed by detection interferences modules, as well as selection and attribution of channels. The approach attributes in a dynamic way operation of channels in the networks 802.11, considering the characteristics noted in the spectral environment where which AP is inserted. The MFDCA was developed so that to operate in low cost of access points, as long as they withstand an installation of a firmware based in Linux. The results of the tests accomplished in a pilot network show that a MFDCA is able to benefit the network as a whole, including non-administered networks, by increasing its throughput and decreasing the rate losses of packages. / Com a utilização significativa das redes Wi-Fi como um dos principais meios de comunicação e transmissão de dados, problemas relacionados à confiabilidade no tráfego dessas redes foram surgindo. O uso não planejado de pontos de acesso (do inglês, Access Point - AP), aliado com as interferências decorrentes da coexistência de outras tecnologias compartilhando o mesmo espectro de frequências 2,4GHz, tem constantemente afetado o desempenho das redes sem fio. Com o intuito de propor uma solução para o problema de interferência entre redes sem fio 802.11, este trabalho descreve uma abordagem para atribuição de canais baseada em múltiplos fatores como a indicação da intensidade do sinal recebido, a relação sinal-ruído, a qualidade de link e o fator de sobreposição de canais. Esta abordagem, denominada de MFDCA (Multi-Factor Dynamic Channel Assignment) é composta pelos módulos de detecção de interferências e de seleção e atribuição de canais. A abordagem atribui de forma dinâmica canais de operação nas redes 802.11, considerando as características presentes no ambiente espectral onde cada AP está inserido. AMFDCA foi projetada para operar em pontos de acesso de baixo custo, desde que suportem a instalação de um firmware baseado em Linux. Os resultados dos testes realizados em uma rede piloto mostram que a MFDCA é capaz de beneficiar as redes como um todo, incluindo redes não administradas, proporcionando um aumento na vazão de dados e a diminuição das taxas de perdas de pacotes.

No description available.

Made available in DSpace on 2016-04-04T18:31:45Z (GMT). No. of bitstreams: 1 RICARDO VICENTE FAVERO.pdf: 1635235 bytes, checksum: d51f441103ff9f2ad94576b0bdd11b9f (MD5) Previous issue date: 2015-11-13 / The wavelength division multiplexing (WDM) optical network accommodates traffic load in 100, 50 and 25 GHz fixed-grid channel. This fixed-grid condition limits the number of lightpath for each optical fiber (80 channels in c-band) and doesn t allow bit rates with bandwidth over 50 GHz. To improve these factors, the flexibly grid elastic optical network (EON) was proposed, aiming accommodate adequately bit rates demand by customers. This proposal allows efficiency bandwidth and also expands bit rates supported by network. The EON bandwidth efficiency is obtained by routing and spectrum assignment (RSA) algorithm which acts to maximize the bandwidth utilization. Even with RSA, EON still show fragmentation rates substantial. In this context, this work proposes a new elastic optical network defragmentation strategy. This defragmentation strategy selects the lightpaths from the most fragmented link. The defragmentation process is based on RSA (DF-RSA). The DF-RSA determines the new position to reallocate the connection selected and performs. Using computer simulation of EON operation, were submitted several bit rates demands with different modulations format and traffic load between 45 and 100 erlang. Two simulation scenarios were proposed. The first one, compare the performance of RSA algorithm first-fit (FF) with and without defragmentation. It was considered as defragmentation process beginning point (trigger), the number of release connections. This scenario had until 48% of relative gain on minimizing blocking probability. The second scenario compared the performance of the follows RSA algorithms: FF, Maximize Path Spectrum Consecutiveness (MPSC) and Fragmentation Aware (FA). The FF was evaluated with and without defragmentation process and the others just with defragmentation process. The trigger employed was eventual connection blocked. The second scenario reached over the 80% blocking probability relative gain in 50 erlang traffic load. We conclude that the new elastic optical network defragmentation offers substantial gain bandwidth utilization and consequently blocking probability reduction. / As redes ?pticas de multiplexa??o por divis?o de comprimento de onda (WDM) acomodam o tr?fego em canais fixos de 100, 50 e 25 GHz. Esta condi??o de grade fixa limita o n?mero de conex?es por fibra ?ptica (80 canais na banda C), e n?o permite taxas de transmiss?o com ocupa??o espectral acima de 50 GHz. Para melhorar estes fatores, foram propostas as redes ?pticas el?sticas (EON) com canais flex?veis, visando acomodar adequadamente as taxas de transmiss?o demandas pelos usu?rios. Esta proposta possibilita maior efici?ncia espectral e tamb?m amplia as taxas de transmiss?o suportadas pela rede. A efici?ncia espectral nas EONs ? obtida com os algoritmos de roteamento e atribui??o espectral (Routing and Spectrum Assignment, RSA), que atuam para maximizar seu uso espectral. Mesmo com o uso de RSAs, as EONs ainda apresentam ?ndices de fragmenta??o consider?veis. Neste contexto, este trabalho prop?e uma nova estrat?gia de desfragmenta??o espectral para EONs. Esta proposta de desfragmenta??o seleciona as conex?es do enlace mais fragmentado, para o processo de desfragmenta??o. A desfragmenta??o baseia seu processo de realoca??o de conex?es por RSA, denominado DF-RSA. O DF-RSA determina a nova posi??o e realiza a realoca??o das conex?es. Com o uso de simula??o computacional da opera??o de funcionamento da EON, foram submetidas v?rias demandas de taxas de transmiss?o com diferentes modula??es e cargas de tr?fego entre 45 e 100 erlang. Foram propostos dois cen?rios de simula??o. No primeiro, foi comparado o desempenho do algoritmo RSA First-Fit (FF) com e sem o processo de desfragmenta??o. Considerou-se como ponto de inicio das desfragmenta??es (gatilho), o n?mero de conex?es liberadas da rede. Neste cen?rio obteve-se at? 48% de ganho relativo na minimiza??o da probabilidade de bloqueio. No segundo cen?rio, foram comparados os desempenhos dos seguintes algoritmos RSAs: FF, Maximize Path Spectrum Consecutiveness (MPSC) e Fragmentation Aware (FA). O FF foi avaliado com e sem desfragmenta??o e os demais somente com desfragmenta??o. Empregou-se como gatilho o eventual bloqueio de conex?o. O segundo cen?rio alcan?ou mais de 80% de ganho relativo de probabilidade de bloqueio para carga de tr?fego de 50 erlang. Conclui-se que a nova estrat?gia de desfragmenta??o para EONs oferece ganhos consider?veis na utiliza??o espectral e, consequentemente, redu??o na probabilidade de bloqueio.