Formal Methods Based Hybrid Control Synthesis for Multi-Agent Systems

Abstract

[CA] Aquesta tesi investiga el conflicte entre el manteniment de la connectivitat i les especificacions de tasques en sistemes multiagent. A causa de les seues limitacions físiques, la comunicació entre agents es veu limitada a una certa distància que implica una restricció addicional en el pla de moviment. Degut a esta restricció, pot ocòrrer que l'especificació de la tasca per a un agent determinat siga impossible d'acomplir. En aquest cas, s'ha de trobar un pla de moviment alternatiu amb la finalitat d'acomplir el màxim possible aquesta especificació inviable. Al mateix temps, s'han de tenir en compte factors com el cost d'implementació del nou pla de moviment i la seua desviació del pla original. La sol·lució proposada inclou una rel·laxació de les restriccions de manteniment de connectivitat originals així com de les especificacions de les tasques. A través d'aquesta rel·laxació, es pot obtindre un pla de moviment viable. Una funció de cost mesura la desviació amb el pla original; minimitzant aquesta funció, es pot aconseguir una rel·laxació óptima de les especificacions originals que acomplisca al màxim els requeriments. Finalment, les simulacions que es presenten, basades en aquest framework, verifiquen els resultats previstos en aquesta tesi.

[ES] This thesis investigates the conflict between connectivity maintenance and task specifications in multi-agent systems. Due to physical limitations, communication between agents is limited to a certain distance that provides an extra constraint to the motion plan. Because of this extra constraint, it may happen that the task specification for an agent is rendered infeasible. Thus, an alternative motion plan needs to be devised so that the infeasible task specification is fulfilled the most, while taking into account factors such as the implementation cost of the new motion plan and its deviation from the original. The proposed solution involves a relaxation of the original connectivity maintenance constraints and task specifications. Through this relaxation, a feasible motion plan may be achieved. A cost function measures the deviation from the original plan; by minimizing this cost function, we can obtain an optimal relaxation of the original specifications that meets the user requirements the most. Finally, simulations based on this framework are presented to verify the results predicted by the analysis in the paper.