Distributed Task Allocation Based On Market Mechanism

The rapid development of intelligent information technology and robotics technology is profoundly changing the world,and the replacement of humans by machines has also become an inevitable trend in the development of productivity.Many fields have higher and higher requirements for robots,and it is difficult for a single robot to meet the requirements for its operating ability,efficiency and intelligence.Scalability and robustness of multi-robots make it have stronger application potential in many scenarios,especially in the field of warehousing and logistics.It is a feasible way to use multi-robot systems to realize intelligent logistics.The research of multi-robot systems involves many problems,and task allocation is one of the difficulties,which is the basis of the entire multi-robot system application.Compared with a centralized architecture,distributed task allocation has better scalability,avoids single point of failure,and can also reduce deployment costs.This thesis focuses on the Multi-robot Task Allocation(MRTA)problems for the storage environment.According to the specific types of MRTA problems defined by MRTA taxonomy and the characteristics of the actual storage environment,two different types of minSum and minMax are established.Based on the MRTA mathematical model of target storage environment,a distributed task allocation method based on market mechanism is proposed.Aiming at the long-term allocation characteristics of the MRTA problem,a marketbased auction method is used to solve the static task allocation sub-problem.By introducing a complete consistency mechanism,the distribution algorithm can adapt to the general asynchronous communication occasions,and an improved fully distributed task distribution auction algorithm is proposed to achieve complete point-to-point communication without the need for a central node.Regarding possible abnormal convergence of the algorithm,a small random price is introduced to ensure the normal transmission of auction parameters.In terms of robot asynchronous communication,a structured information transmission model is designed to realize effective transmission of all auction algorithm parameters between robots.The MRTA problem facing the storage environment has two characteristics:internal dependence and cross dependence,so there is a lot of room for improvement in algorithm performance.Aiming at this problem,this thesis proposes a robot selfcoordination strategy and a multi-robot coordination strategy.The internal fusion of the hill climbing algorithm and the Pareto optimal principle method is used to further improve the overall task allocation efficiency of multi-robot systems.For the MRTA problem with respect to the warehousing environment,the minMax goal appears to be more humane in some occasions.This thesis optimizes its customized performance and proposes a task execution utility formula.Finally,for the common task assignment problems of heterogeneous robot systems in the storage environment,a matching mechanism for heterogeneous robot tasks is proposed,and simulation shows its effectiveness.