Collective agent strategies in the GRADIS environment

Abstract

The common obstacle in using a graph representation of the problems, used successfully in many areas (e.g. pattern recognition) is time complexity of related computations. In some cases only using the parallel computations applied to the graph grammars with quadratic parsing time make the graph approach applicable in practical use. The paper focuses on the multiagent methods of obtaining the graph partitions in the GRADIS framework, that are optimal for further effective parallel computations (decomposing of a graph representation). Various criteria of optimum are discussed. Also the results of performed tests are presented. Częstą przeszkodą w stosowaniu grafowych reprezentacji problemów, tak skutecznych w wielu obszarach (np. rozpoznawanie obrazu), jest złożoność obliczeniowa operacji wykonywanych na tych reprezentacjach. W niektórych przypadkach jedynie połączenie techniki zrównoleglenia obliczeń oraz zastosowania gramatyk grafowych o kwadratowym czasie parsingu pozwala na praktyczne wykorzystanie grafowego modelu problemu. Artykuł niniejszy skupia się na metodach wieloagentowych pozwalających na optymalną dekompozycję reprezentacji grafowej problemu w środowisku GRADIS, przygotowującą do efektywnego zrównoleglenia obliczeń. W pracy omówiono różne kryteria optymalności, przedstawiono schemat i przebieg testów oraz ich wyniki.