A Comparative Study of Dynamical Sequential and Global Optimal Task Reallocation Methodology for Distributed Multi-Robot System

概要

We firstly consider a kind of dynamical mobile task assignment problem, which allows the condition of tasks and robots to be time dependent before assigned robots accomplish the relational tasks. For such new domain, we propose two methods, one is called dynamical sequential task allocation and reallocation, and another is global optimal task allocation and reallocation, for the distributed multi-robot coordination system. The former approach implements multi-round negotiation and body expansion behavior for mobile tasks selection. To utilize body expansion behavior, we set two distance thresholds for robot decision making. The latter method is extended from combinatorial optimization and market-based task allocation. Robots bid tasks and transmit the costs to other robots. Then robots select tasks from the combinatorial cost table based on the objective function. This paper is a comparative study of the mentioned methods above. The simulation results show that minimal executed costs and maximal accomplished efficiency are obtained by global optimal task allocation and reallocation method, while this method consumes numerous communication costs and computation times. Reversely, dynamical sequential task allocation and reallocation is an approximative global optimal assignment approach. Otherwise it expends acceptable communication costs and computation times.