Graph algorithms to determine sufficient connectivity of collaborative autonomous systems

Abstract

Systems of interacting agents such as robots are becoming increasingly common. The problem is that the available resources are often limited and there is a need for agents to interact so that they accomplish their mission. This thesis is a part of the SynTM project which aims at tackling this problem by producing cooperative agents with minimal interactions. The idea is to go from a high-level specification of some agents’ joint mission to an implementation of a loosely coupled set of cooperative agents with minimal interaction. Our contribution consists of designing algorithms for the reduction of the required interactions among the agents while still fulfilling the original specification. An algorithm using a technique named Ecooperative bisimulation, was proposed in the SynTM project as a proof of concept. An implementation of this algorithm features poor performance due the high computational complexity of the algorithm both in space and time. We set out to create algorithms with better performance so we propose and implement new algorithms followed by doing computational complexity analysis. The algorithms are compared using both their practical performance and complexity. Our results show that the first proposed algorithm features a time complexity one degree less than the existing algorithm together with a large speed increase, especially for large problems. The second proposed algorithm features the same complexity as the first, with equal or slightly better performance except for very large problems. Keywords: