Distributed Discrete Consensus Algorithms: Theory and Applications for the Task Assignment Problem
Distributed computation paradigms belong to a research field of increasing interest. Using these algorithms will allow to exploit the capabilities of large scale networks and systems in the near future. Relevant information for the resolution of a problem are distributed among a network of agents with limited memory and computation capability; the problem is solved only by means of local computation and message exchange between neighbour agents. In this thesis we consider the multi-agent assignment problem dealt with distributed computation: a network of agents has to cooperatively negotiate the assignment of a number of tasks by applying a distributed discrete consensus algorithm which defines how the agents exchange information. Consensus algorithms are dealt with always more frequently in the related scientific literature. Therefore, in the first chapter of this thesis we present a related literature review containing some of the most interesting works concerning distributed computation and, in particular, distributed consensus algorithms: some of these works deal with the theory of consensus algorithms, in particular convergence properties, others deal with applications of these algorithms. In the second chapter the main contribution of this thesis is presented: aniterative distributed discrete consensus algorithm based on the resolution of local linear integer optimization problems (L-ILPs) to be used for the multi-agent assignment problem. The algorithm is characterized by theorems proving convergence to a final solution and the value of the convergence time expressed in terms of number of iterations. The chapter is concluded by a performance analysis by means of the results of simulations performed with Matlab software. All the results are presented considering two different network topologies in order to model two different real life scenarios for the connection among agents. The third chapter presents an interesting application of the proposed algorithm: a network of charging stations (considered as agents) has to reach a consensus on the assignment of a number of Electric Vehicles (EVs) requiring to be recharged. In this application the algorithm proposed in the previous chapter undergoes several modifications in order to model effectively this case: considering the inter-arrival times of vehicles to a charging station, a non-linear element appears in the objective function and therefore a novel algorithm to be performed before the assignment algorithm is presented; this algorithm defines the order in which the assigned vehicles have to reach a charging station. Moreover, a communication protocol is proposed by which charging stations and vehicles can communicate and exchange information also allowing charging stations to send to each assigned vehicle the maximum waiting time which can pass before a vehicle loses its right to be recharged. The chapter ends with an example of application of the rivisited assignment algorithm. In the fourth and last chapter, we present an application in an industrial environment: a network of Autonomous Guided Vehicles (AGVs) in a warehouse modeled as a graph has to perform the distributed discrete consensus algorithm in order to assign themselves a set of destinations in which some tasks are located. This application deals not only with the task assignment problem but also with the following destination reaching problem: therefore a distributed coordination algorithm is proposed which allows the AGVs to move into the warehouse avoiding collisions and deadlock. An example of the control strategy application involving both the assignment and coordination algorithms concludes this chapter.