Improving Scalability in Multi-Robot Systems with Abstraction and Specialization

Abstract

Planning and controlling multi-robot systems is challenging due to high dimensionality. When the number of robots increases in the system, the complexity of computation grows exponentially. In this thesis, we examine the scalability problem in planning and control of the multi-robot system. We propose two ideas to improve the scalability of multi-robot systems: abstraction and specialization.
For planning with abstraction, we propose a Hybrid Hierarchical Partially Observable Markov Decision Processes (POMDPs) structure for improved scalability and efficiency in an indoor environment that creates abstract states of convex hulls over the grid environment. We focus our application on the problem of pursuit-evasion with multiple pursuers and one evader whose location is unknown if not visible to the pursuers. This approach is scalable that it significantly reduces the number of states expanded in the policy tree to solve the problem by abstracting environment structures.
Specialization is important for systems with a large number of robots. Connectivity maintenance is essential for collaborative behaviors since robots need to communicate with neighbor robots to share states and information. It is inefficient for a robot to both attend to task behaviors and also maintain connectivity. Therefore, we introduce the idea of connection robots, whose goal is to maintain connectivity of the robot team by correcting the topology of the connectivity graph so as to provide flexibility for the task robots to perform task behaviors. We propose a scalable distributed approach of topology correction that is able to guarantee a faster convergence rate with response to dynamic environment and tasks.