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

• Published in: IEEE transactions on computers 2015-05, Vol.64 (5), p.1416-1428
• Main Authors: Lukic, Milan, Barnawi, Ahmed, Stojmenovic, Ivan
• Format: Article
• Language: English
• Subjects: Algorithm design and analysis; Algorithms; Educational institutions; Robot kinematics; Robot sensing systems; Robots; Schedules; Wireless sensor networks
• ISSN: 0018-9340; 1557-9956
• DOI: 10.1109/TC.2014.2329689

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.