Greedy extension of localized auction based protocols for wireless robot-robot coordination

Abstract

We assume that an event was reported to one of robots, and a response by one robot is required. The goal of robot-robot coordination for task assignment is to select the best robot for responding to a reported event so that communication cost for selecting, and response time for performing the task are minimized. Existing solutions, except those recently proposed in [3], are either centralized, neglecting communication cost, assuming complete graph, or based on flooding with individual responses to robot decision maker (simple auction protocol - SAP), ignoring communication cost and response time bound. This article proposes greedy improvement to previously proposed (in [3]) k-hop simple auction protocol (k-SAP) and k-hop simple auction aggregation protocol (k-SAAP) for task assignment in multi-hop wireless robot networks. After decision about the best robot is made by k-SAP or k-SAAP, new 1-SAP greedy auction is initiated by that robot in order to search for possibly better robot in 1-hop neighborhood. Such greedy approach proceeds until no better robot is found. Improvement of new k-SAPG and k-SAAPG over k-SAP and k-SAAP by applying greedy approach is shown by simulation results. © 2009 IEEE.