Move and Improve: a Market-Based Mechanism for the Multiple Depot Multiple Travelling Salesmen Problem

详细信息    查看全文

• 作者：Anis Koubâa ; Omar Cheikhrouhou…
• 关键词：Cooperative mobile robots ; Robot operating system ROS ; Multiple depot multiple traveling salesman problem ; Webots
• 刊名：Journal of Intelligent & Robotic Systems
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：85
• 期：2
• 页码：307-330
• 全文大小：
• 刊物类别：Engineering
• 刊物主题：Control, Robotics, Mechatronics; Electrical Engineering; Artificial Intelligence (incl. Robotics); Mechanical Engineering;
• 出版者：Springer Netherlands
• ISSN：1573-0409
• 卷排序：85

文摘

Consider the problem of having a team of cooperative and autonomous robots to repeatedly visit a set of target locations and return back to their initial locations. This problem is known as multi-robot patrolling and can be cast to the multiple depot multiple traveling salesman problem (MD-MTSP), which applies to several mobile robots applications. As an NP-Hard problem, centralized approaches using meta-heuristic search are typically used to solve it, but such approaches are computation-intensive and cannot effectively deal with the dynamic nature of the system. This paper provides a distributed solution based on a market-based approach, called Move-and-Improve. It involves the cooperation of the robots to incrementally allocate targets and remove possible overlap. The concept is simple: in each step, a robot moves and attempts to improve its solution while communicating with its neighbors. Our approach consists of four main phases: (1) initial target allocation, (2) tour construction, (3) negotiation of conflicting targets, (4) solution improvement. To validate the efficiency of the Move-and-Improve distributed algorithm, we first conducted extensive simulations using Webots and evaluated its performance in terms of total traveled distance, maximum tour length, and ratio of overlapped targets, under different settings. We also demonstrated through MATLAB simulations the benefits of using our decentralized approach as compared to a centralized Genetic Algorithm approach to solve the MD-MTSP problem. Finally, we implemented Move-and-Improve using ROS and deployed it on real robots.