Distributed area partitioning for multi-robot coverage

Download

2035988_METU_CENG_MSc_Thesis.pdf

Date

2022-5-9

Author

Hocaoğlu, Burak

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

246
views

235
downloads

This thesis focuses on the distributed coverage area partitioning problem in a robotic swarm deployed over a known, two-dimensional environment. The goal is to split a region of interest into a number of subregions such that the amount of effort required to cover each subregion is approximately equal with respect to an objective function. Towards this end, the problem is defined as a distributed optimization problem, where the decision varibles are the locations of robots. Then, the proposed solution approach is described as a control mechanism driving each robot to better positions. At the end, robot positions will converge to a configuration where the total effort to process their subregion is minimal. Specifically, first, Lloyds Algorithm is deployed on the base approach to workload partitioning by converging to a Centroidal Voronoi Tesselation (CVT). Lloyds Algorithm provides a basic idea for convex problems where the deployment region has convex boundaries, but fails to provide reliability when used in a non-convex region. At this point, heuristics are added to reinforce the capabilities of Lloyds Algorithm to capture the dynamics missed when using CVT and to enable stable convergence in non-convex problems, converting the behaviour to converging to a Geodesic Voronoi Tesselation (GVT). Also, the model as the objective function and the control mechanism is revised for equitable workload partititoning. After that, various analyses are conducted with different centrality metrics whose results give the actual target locations that agents need to arrive, while heuristics refine how each agent arrives. These centrality metrics add new dynamics to how local workloads of each agent is defined, as well as optimizing them. This work provides qualitative and quantitative results of the proposed approaches. The experiments are done in non-convex two-dimensional environments where Lloyds Algorithm fails in its base form.

Subject Keywords

Swarm robotics, Distributed area partitioning, Centroidal voronoi tessellation, Distributed coverage control

URI

https://hdl.handle.net/11511/97754

Collections

Graduate School of Natural and Applied Sciences, Thesis

Suggestions

OpenMETU
Core

Distributed Target Tracking with Propagation Delayed Measurements Orguner, Umut (2009-07-09) This paper presents a framework for making distributed target tracking under significant signal propagation delays between the target and the sensors. Each sensor considered makes estimation using its own measurements compensating for the involved signal propagation delay using a deterministic sampling based algorithm proposed previously. Since the individual sensor readings might not be enough to localize the target, the sensors have to share their estimates with each other at specific time instants and co...
Distributed Models for Sparse Attack Construction and State Vector Estimation in the Smart Grid Ozay, Mete; Esnaola, Inaki; Yarman Vural, Fatoş Tunay; Kulkarni, Sanjeev R.; Poor, H. Vincent (2012-11-08) Two distributed attack models and two distributed state vector estimation methods are introduced to handle the sparsity of smart grid networks in order to employ unobservable false data injection attacks and estimate state vectors. First, Distributed Sparse Attacks in which attackers process local measurements in order to achieve consensus for an attack vector are introduced. In the second attack model, called Collective Sparse Attacks, it is assumed that the topological information of the network and the m...
Distributed Real-Time Protocols for Industrial Control Systems: Framework and Examples SCHMİDT, KLAUS WERNER; Schmidt, Şenan Ece (2012-10-01) The automation of today's large-scale industrial systems relies on the operation of distributed controller devices that perform local computations and exchange information via communication networks. The subject of this paper is the development of a family of shared-medium industrial communication protocols that support the transmission of real-time (RT) and nonreal-time (nRT) data among distributed controller devices. Different from existing protocols, we suggest to incorporate information that is availabl...
Hierarchical multitasking control of discrete event systems: Computation of projections and maximal permissiveness Schmidt, Klaus Verner; Cury, José E.r. (null; 2010-12-01) This paper extends previous results on the hierarchical and decentralized control of multitasking discrete event systems (MTDES). Colored observers, a generalization of the observer property, together with local control consistency, allow to derive sufficient conditions for synthesizing modular and hierarchical control that are both strongly nonblocking (SNB) and maximally permissive. A polynomial procedure to verify if a projection fulfills the above properties is proposed and in the case they fail for a g...
Collaborative Direction of Arrival estimation by using Alternating Direction Method of Multipliers in distributed sensor array networks employing Sparse Bayesian Learning framework Nurbas, Ekin; Onat, Emrah; Tuncer, Temel Engin (2022-10-01) In this paper, we present a new method for Direction of Arrival (DoA) estimation in distributed sensor array networks by using Alternating Direction Method of Multipliers (ADMM) in Sparse Bayesian Learning (SBL) framework. Our proposed method, CDoAE, has certain advantages compared to previous distributed DoA estimation methods. It does not require any special array geometry and there is no need for inter -array frequency and phase matching. CDoAE uses the distributed ADMM to update the parameter set extrac...

Citation Formats

B. Hocaoğlu, “Distributed area partitioning for multi-robot coverage,” M.S. - Master of Science, Middle East Technical University, 2022.