An Intelligent Task Assignment Method For Multi-robot Systems

Robots are of great help to the innovation of human life and work.Multi-robot system is the development direction of robots in the future,which is of great significance to manufacturing,processing industry,dangerous environment and unknown environment.Task allocation of multi-robot system is to find a good corresponding relationship between robots and tasks.It is very important for the efficiency of multi robot system,which determines the efficiency,completion and resource consumption of multi-robot system.In general,multi-robot system has the characteristics of large scale,many conflicts and many alternatives.It is an NP-hard problem that how to reasonably allocate robots to perform a certain task,which robots perform a certain task together,and when robots perform a certain task.This paper uses E-cargo model and timed Petri net to model the multi-robot system according to the characteristics of the task allocation problem of the multi-robot system.On the basis of the modeling,the characteristics of Hungarian algorithm and Heuristic A* search algorithm are analyzed,improving the existing problems of the two algorithms.The main work is as follows:(1)According to the characteristics of the task allocation problem that complex tasks need to be performed by multiple robots,this paper proposes a pre-allocation method based on E-cargo model combined with Hungarian algorithm for task allocation.Firstly,E-cargo model is introduced to model the task allocation problem of multi-robot system;secondly,the limitation of Hungarian algorithm that can only be applied to special cases is solved by transforming the benefit matrix;thirdly,a pre-allocation method based on the greedy algorithm is introduced to complete the assignment of some tasks in the system through pre-allocation,reducing the dimension of the benefit value matrix entering the Hungarian algorithm to avoid the infinite loop problem when Hungarian algorithm being applied to the too large benefit value matrix and the matrix whose value repeatability relatively high.Finally,the Hungarian algorithm is used to solve the task allocation problem of dynamic large-scale multi-robot system.(2)Heuristic A* algorithm is a heuristic intelligent search algorithm based on Artificial Intelligence,which has the advantage of not having to expand all state nodes to obtain the system path.And if the heuristic function is adopted,it can ensure that the obtained scheduling path is optimal.This paper transforms the task allocation problem into a search problem in the reachability graph of Petri nets.Aiming at the characteristics of frequent conflicts in calling shared resources during the collaborative completion of multi-robot systems,a timed Petri net is used to model the task allocation problem of multi-robot systems,describing the time required for a multi-robot system to perform a task,invoking services provided by other robots and the contention,conflicts,etc.of shared resources by multi-robot.Then the Heuristic A * search algorithm is introduced to search the reachable graph of the time Petri net model.And the binary decision graph BDD is used to compress the state set,so as to improve the search speed and get the optimal task execution sequence.