Robot Coordination for Energy-Balanced Matching and Sequence Dispatch of Robots to Events

作     者：Lukic, Milan Barnawi, Ahmed Stojmenovic, Ivan 

作者机构：Univ Novi Sad Fac Tech Sci Novi Sad 21000 Serbia King Abdulaziz Univ Jeddah 22254 Saudi Arabia Deakin Univ SIT Melbourne Vic Australia Univ Ottawa Sch Elect Engn & Comp Sci Ottawa ON K1N 6N5 Canada 

出 版 物：《IEEE TRANSACTIONS ON COMPUTERS》 (IEEE Trans Comput)

年 卷 期：2015年第64卷第5期

页      面：1416-1428页

核心收录：

学科分类：0808[工学-电气工程] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Serbian Ministry of Science and Education [TR32016] NSERC CRDPJ [386874 - 09] NSERC discovery grant 

主　　题：Robot coordination wireless sensor networks matching sequence dispatch centralized and distributed algorithm energy efficiency 

摘      要：Given a set of events and a set of robots, the dispatch problem is to allocate one robot for each event to visit it. In a single round, each robot may be allowed to visit only one event (matching dispatch), or several events in a sequence (sequence dispatch). In a distributed setting, each event is discovered by a sensor and reported to a robot. Here, we present novel algorithms aimed at overcoming the shortcomings of several existing solutions. We propose pairwise distance based matching algorithm (PDM) to eliminate long edges by pairwise exchanges between matching pairs. Our sequence dispatch algorithm (SQD) iteratively finds the closest event-robot pair, includes the event in dispatch schedule of the selected robot and updates its position accordingly. When event-robot distances are multiplied by robot resistance (inverse of the remaining energy), the corresponding energy-balanced variants are obtained. We also present generalizations which handle multiple visits and timing constraints. Our localized algorithm MAD is based on information mesh infrastructure and local auctions within the robot network for obtaining the optimal dispatch schedule for each robot. The simulations conducted confirm the advantages of our algorithms over other existing solutions in terms of average robot-event distance and lifetime.