Multi-robot Task Scheduling Method Based On Parallel Computing

The multi-robot collaboration system is a complex discrete event dynamic system with multiple robots and multiple shared resources.Multi-robot task scheduling aims to schedule robots to use the available resources in the system to complete a number of given tasks.The goal of scheduling is to make all tasks be completed in the shortest time,maximize the utilization of system resources,and minimize the idle waiting time of available system resources.Multi-robot optimal task scheduling is of great significance in many fields in reality.For example,in a flexible manufacturing system,optimal task scheduling not only means that more products can be produced per unit time to meet the ever-changing market demand,but also greatly increase the utilization rate of system resources,reduce product production costs,and so on;For another example,in the field of automated military affairs,optimal task scheduling means faster response to the enemy's situation,rapid completion of target tasks,and so on.However,the multi-robot task scheduling problem belongs to the most difficult type of NP-hard combinatorial optimization problem,and even for some small-scale problems,it is impossible to solve an optimal solution in acceptable polynomial time.Although its application prospects are very attractive,its inherent computational complexity has brought huge challenges to its applications.In response to the above difficulties,this thesis proposes a method of fast task scheduling based on parallel computing for multi-robots,which utilizes more physical computing resources to speed up the problem solving process,the specific content includes:(1)A parallel A~* algorithm based on multi-core computing is proposed for multi-robot task scheduling.The parallel A~* algorithm is obtained by converting the method of serial A~*algorithm expansion node to parallel multi-node expansion;the parallel algorithm based on multi-core computing uses the shared memory model,which has the problem of data competition access.For this purpose,two efficient Treap data structure that supports concurrent access is used to represent the OPEN list,and two efficient binary balanced trees that support concurrent access are designed to represent the CLOSED list;the OPENMP framework is used to implement parallel algorithms,in the experimental test on a 4-core computing device,we observed a speedup of nearly 3 times;we observed the versatility of the hash partition mechanism for the design of concurrent data structures,and we abstracted it to a concurrent data structure design method independent of specific problems.Applied to the parallel generation algorithm of Petri net reachability graph based on shared memory model,it not only verifies the validity and versatility of this design idea,but also proposes a parallel algorithm that can quickly generate Petri net reachability graph.(2)The performance of the parallel A~* algorithm based on multi-core computing is usually limited by the actual number of physical cores owned by the machine,so a parallel A~* algorithm based on multi-computer computing is proposed for multi-robot task scheduling.The parallel A~* algorithm is obtained by converting the method of serial A~*algorithm expansion node to parallel multi-node expansion;the parallel algorithm based on multi-computer computing uses a distributed memory model,and uses a hash partition mechanism to split the OPEN list and the CLOSED list into several sub-lists and stored on each computing node in a distributed manner;the MPI message passing interface is used to implement the parallel algorithm,and from the experimental result tested on two computing nodes indirectly connected by a high-speed router,a speedup of about 4 times was observed at the highest.(3)To make full use of the physical computing resources of the system to accelerate the calculation of the multi-robot task scheduling,a multi-core + multi-machine parallel computing A~* search algorithm combining the above two methods is proposed.On the basis of the multi-machine parallel A~* algorithm,let each computing node process its assigned successor nodes in parallel to obtain the parallel algorithm;use the method in multi-core parallel A~* for the design of the concurrent OPEN list and the concurrent CLOSED list owned by each computing node to deal with data competition access problems;mixed-use of OPENMP framework + MPI message passing interface to implement this parallel algorithm,and test it on two 4-core computing nodes indirectly connected by high-speed routers,in the experimental result,a speedup of about 4 times was observed at the highest.(4)In response to the large memory requirements of the A~* algorithm,a parallel IDA~*algorithm based on the Spark cloud computing platform is proposed for multi-robot task scheduling.The parallel window search is adopted to parallelize the IDA~* algorithm,in this way,several limited depth-first search with different cost bounds are performed in parallel.The feasibility and effectiveness of this method are verified through experiments.