Optimal ant colony algorithm based multi-robot task allocation and processing sequence scheduling

摘要

Multi-robot task allocation and processing sequence scheduling problem is to allocate relative more tasks to relative less robots and schedule task processing sequences for these robots so that the robots can finish these tasks within the least time. To solve this problem, an optimal ant colony algorithm based approach was proposed. In this approach, two kinds of pheromone were used to record the proneness of task allocation and task processing sequence. To find optimal solution, each ant would search the task allocation and processing sequence solution respectively according to the policy designed in this paper. At first, the ant selected a task to allocate and schedule. To do this, it would choose a robot to process this task according to the pheromone density between robot and task. Then, the ant scheduled the task processing sequence for this selected robot according to the pheromone density between tasks. It would choose a task from this robot’s scheduled task list for this task to be followed. The ant would repeat the above two processes until all the tasks were scheduled. All ants repeated these scheduled process until the finish condition was met, and the optimal scheme could be got. A simulation environment was designed and simulation studies compared with the approach proposed before in our recent work were done to validate the proposed approach. The results shown that the proposed approach was effective and it can improve the robots’ working efficiency greatly compared with the approach proposed in our recent work.