An intelligent and unified framework for multiple robot and human coalition formation

Abstract

Robotic systems have proven effective with recent deployments of unmanned robots in numerous missions. Teaming multiple agents requires efficient coalition formation, which is an NP-complete problem that is also hard to approximate within a reasonable factor. The computational complexity of the problem has led to the development of a number of greedy, approximation, and market-based solving techniques; however, no single algorithm can cater to a wide spectrum of mission situations. The primary contribution of this dissertation is the development of a unified framework, called i-CiFHaR, the first of its kind to incorporate a library of diverse coalition formation algorithms, each employing a different problem solving mechanism. i-CiFHaR employs unsupervised learning to mine crucial patterns among the algorithms and makes intelligent and optimized decisions over the library to select the most appropriate algorithm(s) to apply in accordance with multiple mission criteria by leveraging Bayesian reasoning.

The second major contribution of this dissertation adds to the state-of-the-art in swarm intelligence by presenting two novel hybrid ant colony optimization algorithms that are applicable to a wide spectrum of combinatorial optimization problems. The algorithms effectively address search stagnation, a common drawback of existing ant algorithms by leveraging novel pheromone update policies that integrate the simulated annealing methodology. The presented algorithms outperformed existing state-of-the-art ant algorithms when applied to three NP-complete problems in terms of solution quality by exhibiting a higher searching capability.