| We propose market-based coordinated task allocation mechanisms, which allocate complex tasks that require synchronized and collaborated services of multiple robot agents to robot agents, and an auditing mechanism, which ensures proper behaviors of robot agents by verifying inter-agent activities, for self-interested, fully-distributed, and large-scale multi-robot systems that have multi-agent tasks with real-time constraints in dynamic environments. The studied coordinated task allocation mechanisms include auction mechanisms such as forward auction, reverse auction, forward/reverse auction, and sealed-bid auction with different bidding strategies, which are represented by different utility functions. The coordinated task allocation mechanisms also include 1-to-1 task exchange, which reallocates tasks assigned by auctions in order to adapt to changing environments in real-time. Because the robot agents are self-interested, the agents may try free-riding and cheating, which is to consume resources without providing enough services. Free-riding and cheating attempts may deteriorate the overall performance by discouraging contribution of each robot agent---contribution of honest agents may be not rewarded with enough amount of service consumption. In order to encourage contribution and to ensure the amount contribution is properly accounted, we propose an auditing mechanism with a credit system, which can be combined with the proposed coordinated task allocation mechanisms.;We conduct both physical robot experiments and software agent simulations for the coordinated task allocation mechanisms. The experimental results suggest that the proposed mechanisms are scalable and fault-tolerant and work in physical robot systems. We compare the proposed methods to control methods with various performance metrics and the results suggest that the performance can be enhanced by the proposed approaches. We observe and analyze issues such as deadlock, pingpong-bidding, pingpong-swapping, and others. We analyze the auditing mechanism with mathematical analysis and software simulations on the behavior of the mechanism. The results from both analysis and simulations suggest that the auditing mechanism can detect cheating attempts with high probability without excessive communication overheads in various conditions. We also suggest an adaptive mechanism to be included in the auditing mechanism so that each robot or peer can tune the communication overheads and detection probability according to the dynamic environments. The analysis and simulations of the evolutionary game theory on the behaviors of peers or robots suggest that the auditing mechanism can discourage free-riding and cheating attempts effectively without harming the popularity of systems with auditing mechanisms. The analysis shows that a strategy where nodes behave honestly and contribute properly is evolutionarily stable and the simulations show that such a strategy takes the dominance even if the strategy had minor initial population. |
