Adaptive Task Allocation, Localization and Motion Planning for the Multi-Robot System

With shortening product life cycles and increasing demands for product diversifications, a fully autonomous transport system with high performance and flexibility is strongly expected. The relevant study becomes more and more attractive and important. In this thesis, we focus on three important problems involved with it.

The first problem is the Multi-Robot Task Allocation (MRTA) problem. In this thesis, a novel approach named Distributed Heterogeneous Hash Tables (DHHT) is proposed to solve the task allocation problem. Our approach assigns robots to a set of transportation tasks offered by loading stations in two steps: firstly, a robot is assigned to the station; then the robot gets a specific transportation task from the station with the help of a contract net protocol. The experimental results have shown that our approach reached a fair distribution of robots among stations, and thus achieved a high total delivery efficiency of the system.

The second problem is the localization of the autonomous mobile robot. We introduce an effective and robust dynamic localization method, which separates localization from the mapping process. ... mehrIn localization process, a particle filter coupled with a distance filter and a scan matching method achieves a more robust localization against dynamic obstacles. In mapping process, we introduce an extend sensor model which takes dynamic influences as well as the state transition probability of the map directly into the map update step. The empirical evaluation shows that our approach achieves a robust localization in several highly dynamic real-world environments. At the same time the mapping stays consistent with the ground truth.

The third relevant problem is the Multi-Robot Motion Planning (MRMP) problem. At first, we propose a road map based approach called Adaptive Road Map Optimization (ARMO) to deal with the Multi-Robot Path Planning (MRPP) problem. Our approach generates an optimal road map by considering environment constraints and the current demands of stations in a pre-processing phase. Then, the robots extract individual paths from the optimal road map by a local path planner and navigate themselves cooperatively by a local navigation module. The experimental results showed that the ARMO approach lead to a more efficient navigation than conventional prioritized based decoupled path planning (PRIOR) methods. Furthermore, we propose a Behavior-Based Multi-Robot Collision Avoidance (BBMRCA) method inspired by swarm intelligence to solve the multi-robot motion planning problem. We evaluated BBMRCA methods with up to 100 robots in a simulation environment and the experimental results have shown that the quality of solutions and the scalability are at the same level as ARMO and significantly better than those of conventional decoupled prioritized planning methods.

The work presented in this thesis has been conducted within the context of the project “KARIS (Kleinskalige Autonomes Redundantes Intralogistiksystem)” and its follow-up project “KARIS Pro”. The projects act as a focal point for the research and as a result that provide a distributed multi-robot system KARIS to accomplish transportation tasks in the field of intra-logistics and production. So in the end, we describe a demonstration and two pilot applications within the two projects roughly.

In summary, we propose a fully decentralized task allocation method which can facilitate a fair distribution of robots among the loading stations. We introduce an effective and robust localization method to achieve an accurate localization in highly dynamic real world environments. We also propose two decoupled multi-robot motion planning methods which can efficiently navigate a huge number of robots in a structured and crowded environment. Through the experiments in the simulation and on the real system, we have shown that our system is able to self-organize the transport task in a human workspace in a more flexible and efficient way.