Evolving and co-evolving meta-level reasoning strategies for multi-agent collaboration : a thesis presented in partial fulfilment of the requirements for the degree of Doctor of Philosophy in Computer Science at Massey University, Albany, New Zealand

Abstract

This research presents a novel hybrid evolutionary algorithm for generating meta-level reasoning strategies through computational graphs to solve multi-agent planning and collaboration problems in dynamic environments using only a sparse training set. We enhanced Genetic Network Programming (GNP) by reducing its reliance on randomness, using conflict extractions and optimal search in computational mechanisms to explore nodes more systematically. We incorporated three algorithms into the GNP core. Firstly, we used private conflict kernels to extract conflict-generating structures from graph solutions, which enhances selection, crossover, and mutation operations. Secondly, we enhanced the GNP algorithm by incorporating optimal search and merged Conflict Directed A* with GNP to reduce the search branching factor. We call our novel algorithm Conflict-Directed A* with Genetic Network Programming (CDA*-GNP), which identifies the most effective combination of processing nodes within the graph solution. Additionally, we investigated the use of a chromosome structure with multiple subprograms of varying sizes that the algorithm automatically adjusts. Thirdly, we applied Conflict-Directed A* to a genetically co-evolving heterogeneous cooperative system. A set of agents with diversified computational node composition is evolved to identify the best collection of team members and to efficiently prevent conflicting members from being in the same team. Also, we incorporated methods to enhance the population diversity in each proposed algorithm. We tested the proposed algorithms using four cooperative multi-agent testbeds, including the prey and predator problem and the original tile world problem. More complex multi-agent and multi-task benchmarking testbeds were also introduced for further evaluation. As compared to existing variants of GNP, experimental results show that our algorithm has smoother and more stable fitness improvements across generations. Using the popular tile world problem as a benchmarking testbed, CDA*-GNP achieved better performance results than the best existing variant of GNP for solving the problem. Our algorithm returned 100% accuracy on the test set compared to only 83% reported in the literature. Moreover, CDA*-GNP is 78% faster in terms of the average number of generations and 74% faster in terms of the average number of fitness evaluations. In general, our findings suggest that a hybrid algorithm that balances the utilization of Genetic Network Programming and Optimal strategies leads to the evolution of high-quality solutions faster.