Gerçek zamanlı çoklu-robot çoklu-hedef problemi için artımlı atama yöntemi

In this study, the real-world Multiple Travelling Robot Problem (MTRP) is analyzed and an integrated approach is proposed to solve this problem in real time. MTRP is a generalization of the well-known Multiple Traveling Salesman Problems and is solved by a multi-robot team. In MTRP, a different version of the well known NP-hard MTSP (Multiple Traveling Salesman Problem), each target must be visited by at least one robot in its open tour. Depending on the selected application domain, various objectives may be defined for this problem (e.g. minimization of total path length, time, makespan etc.). Although this problem has emerged from Operations Research, it has become one of the main problems in multi-robot research for different missions (e.g., search and rescue, space, or surveillance operations, etc.). In this article, besides the target allocation issue, the real challenges of this problem are presented. Unpredictability of the exact processing times of tasks, unstable cost values during runtime and inconsistencies due to uncertain information form the main difficulties of the task allocation problem for robot systems. Since the real world is beyond the control of robots, in most cases, the Operations Research solutions are not directly applicable due to either robot hardware/software limitations or environmental dynamics. These approaches may become impractical when the size of the mission is even moderate or the cost values change frequently because of the uncertain knowledge, changes in the environment (including failures) or the changing structure of the mission (e.g. online tasks). Furthermore, robots have continuous path planning burdens for target sets in dynamic environments. Expensive computational efforts for initial allocations may become redundant. We propose a solution as a generalized framework – DEMiR-CF (Distributed and Efficient Multi-Robot Cooperation Framework) –which includes dynamic task selection, distributed task allocation and contingency handling mechanisms. These mechanisms and lower level robot controllers, the motor and sensory modules are integrated together to solve the real-world MTRP. DEMiR-CF, while capable of handling diverse contingencies, performs an incremental task allocation method based on the current information about the environment. Globally efficient solutions are obtained by the proposed mechanisms that form priority based rough schedules and select the most suitable tasks from these schedules. Rough schedules are formed by using information regarding the beliefs about the other robots. Since DEMiR-CF is for real-world task execution, communication requirements are kept at minimum as much as possible. The approach is distributed and computationally efficient. Target allocation and route construction is integrated into each other by an incremental assignment approach. Real time conditions and contingencies that change the problem instance are handled at the same time by the designed contingency handling mechanisms. Robots keep system models to correct models of their own or warn other robots to maintain system consistency. Empirical evaluations of the system performed on the Webots simulator and on Khepera II robots reveal the efficiency of the integrated components of the approach. Experiments are designed in three sets. In the first set of the experiments, evaluations of the proposed cost functions to be used with DEMiRCF are performed. Comparisons are made both with the optimal results taken from the IP solver CPLEX and that of the Prim Allocation approach, one of the efficient methods to solve this problem. As the results illustrate, allocating all targets from scratch and generating routes of robots may result in suboptimal solutions. Therefore the target allocation and the route construction should be integrated for efficient heuristic approaches. This integration and incremental allocation is also useful for eliminating redundant calculations especially in highly dynamic or unknown environments. In the second set of experiments, scalability of the framework and the response efficiency of the contingency handling mechanism integrated into the framework are evaluated. The scalability of the approach is validated and the efficiency of using the contingency handling mechanisms is observed in the results. The third set of experiments is performed on real robots. As results illustrate, both incremental task selection and allocation approaches produce efficient results and the contingency handling mechanisms make the system robust and allow the handling of real-time online situations.