Distributed area partitioning for multi-robot coverage

2022-5-9
Hocaoğlu, Burak
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.

Suggestions

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...
Network-wide energy efficiency in wireless networks with multiple access points
Ozel, Omur; Uysal, Elif (2013-10-01)
This paper presents a distributed mechanism for improving the overall energy efficiency of a wireless network where users can control their uplink transmit power targeted to the multiple access points in the network. This mechanism lets the network achieve a trade-off between energy efficiency and spectral efficiency through the use of suitably designed utility functions. A user's utility is a function of throughput and average transmission power. Throughput is assumed to be a sigmoidal function of signal-t...
Citation Formats
B. Hocaoğlu, “Distributed area partitioning for multi-robot coverage,” M.S. - Master of Science, Middle East Technical University, 2022.