[go: up one dir, main page]

CN114444828A - A method for dynamic task assignment of the same kind of agricultural machinery and multi-machine coordination - Google Patents

A method for dynamic task assignment of the same kind of agricultural machinery and multi-machine coordination Download PDF

Info

Publication number
CN114444828A
CN114444828A CN202011202172.9A CN202011202172A CN114444828A CN 114444828 A CN114444828 A CN 114444828A CN 202011202172 A CN202011202172 A CN 202011202172A CN 114444828 A CN114444828 A CN 114444828A
Authority
CN
China
Prior art keywords
task
machine
agricultural machinery
agricultural
cost
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Granted
Application number
CN202011202172.9A
Other languages
Chinese (zh)
Other versions
CN114444828B (en
Inventor
王猛
赵博
刘阳春
苑严伟
伟利国
汪凤珠
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Chinese Academy of Agricultural Mechanization Sciences
Original Assignee
Chinese Academy of Agricultural Mechanization Sciences
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Chinese Academy of Agricultural Mechanization Sciences filed Critical Chinese Academy of Agricultural Mechanization Sciences
Priority to CN202011202172.9A priority Critical patent/CN114444828B/en
Publication of CN114444828A publication Critical patent/CN114444828A/en
Application granted granted Critical
Publication of CN114444828B publication Critical patent/CN114444828B/en
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Classifications

    • GPHYSICS
    • G06COMPUTING OR CALCULATING; COUNTING
    • G06QINFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
    • G06Q10/00Administration; Management
    • G06Q10/06Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
    • G06Q10/063Operations research, analysis or management
    • G06Q10/0631Resource planning, allocation, distributing or scheduling for enterprises or organisations
    • GPHYSICS
    • G06COMPUTING OR CALCULATING; COUNTING
    • G06NCOMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
    • G06N20/00Machine learning
    • GPHYSICS
    • G06COMPUTING OR CALCULATING; COUNTING
    • G06QINFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
    • G06Q50/00Information and communication technology [ICT] specially adapted for implementation of business processes of specific business sectors, e.g. utilities or tourism
    • G06Q50/02Agriculture; Fishing; Forestry; Mining

Landscapes

  • Engineering & Computer Science (AREA)
  • Business, Economics & Management (AREA)
  • Human Resources & Organizations (AREA)
  • Theoretical Computer Science (AREA)
  • Strategic Management (AREA)
  • General Physics & Mathematics (AREA)
  • Economics (AREA)
  • Physics & Mathematics (AREA)
  • Tourism & Hospitality (AREA)
  • Software Systems (AREA)
  • Marketing (AREA)
  • General Business, Economics & Management (AREA)
  • Entrepreneurship & Innovation (AREA)
  • Marine Sciences & Fisheries (AREA)
  • Primary Health Care (AREA)
  • Animal Husbandry (AREA)
  • Life Sciences & Earth Sciences (AREA)
  • Mining & Mineral Resources (AREA)
  • Mathematical Physics (AREA)
  • Health & Medical Sciences (AREA)
  • General Engineering & Computer Science (AREA)
  • General Health & Medical Sciences (AREA)
  • Computing Systems (AREA)
  • Medical Informatics (AREA)
  • Agronomy & Crop Science (AREA)
  • Evolutionary Computation (AREA)
  • Data Mining & Analysis (AREA)
  • Computer Vision & Pattern Recognition (AREA)
  • Development Economics (AREA)
  • Educational Administration (AREA)
  • Artificial Intelligence (AREA)
  • Game Theory and Decision Science (AREA)
  • Operations Research (AREA)
  • Quality & Reliability (AREA)
  • Management, Administration, Business Operations System, And Electronic Commerce (AREA)

Abstract

A multi-machine cooperative dynamic task allocation method for the same kind of agricultural machine comprises the following steps: constructing a multi-machine cooperative cost function based on the performance of the agricultural machinery and the task parameters according to the multi-machine cooperative operation scene; constructing an agricultural machinery bidding cost function and a cluster cost function after bidding completion; constructing a multi-machine collaborative dynamic task allocation system based on a remote cloud service platform and a wireless ad hoc network; and when a new task needs to be distributed, the system distributes the new task by improving a contract network algorithm to finally obtain an optimal task distribution result. The invention solves the problem of how to reasonably and dynamically allocate tasks and task execution sequences under the condition that a new task is added or an agricultural machine is out of order in the operation process of a plurality of agricultural machines of the same kind in an agricultural machine cooperative society or farm.

Description

一种同种农机多机协同动态任务分配方法A dynamic task assignment method for the same kind of agricultural machinery and multi-machine cooperation

技术领域technical field

本发明涉及农机多机协同作业任务分配技术,特别是一种基于改进合同网算法的同种农机多机协同动态任务分配方法。The invention relates to a task assignment technology of agricultural machinery multi-machine cooperative operation, in particular to a multi-machine cooperative dynamic task allocation method of the same kind of agricultural machinery based on an improved contract network algorithm.

背景技术Background technique

随着我国农机合作社和农场作业模式的发展和推广,土地和农机都呈现集中的趋势,最常见的作业场景是作业前先将任务和顺序分配给指定农机,每台农机完成各自的作业任务后返回车库。在农机多机协同作业过程中常出现有新任务加入或有农机出现故障的问题,将待分配的任务进行实时有效的动态分配可以有效降低作业代价,缩短作业时间。With the development and promotion of agricultural machinery cooperatives and farm operation modes in China, both land and agricultural machinery have shown a trend of concentration. The most common operation scenario is to assign tasks and sequences to designated agricultural machinery before operation. After each agricultural machinery completes its own operation task Return to the garage. In the process of multi-machine cooperative operation of agricultural machinery, there are often problems that new tasks are added or agricultural machinery fails. Real-time and effective dynamic allocation of tasks to be allocated can effectively reduce the operation cost and shorten the operation time.

解决动态任务分配常用的方法有:一、使用启发式算法通过远程服务平台对未完成任务进行重新分配;二、使用合同网算法通过农机之间的招投标过程实现对未完成任务的重新分配。第一种方法属于集中式任务分配,将大量计算集中到服务器,对服务器压力较大,分配效果较好;第二种方法属于分布式任务分配,利用每台农机机载电脑的计算能力和农机间的相互通信完成任务分配,用时短、对服务器无压力,但是分配效果较差。为了减少服务器计算量,降低服务器故障概率,本领域亟需一种能充分利用机载电脑计算能力实现任务分配的办法。The commonly used methods to solve dynamic task assignment are: first, use heuristic algorithm to redistribute unfinished tasks through the remote service platform; second, use contract network algorithm to realize the reallocation of unfinished tasks through the bidding process between agricultural machines. The first method belongs to centralized task allocation, which concentrates a large amount of computing on the server, which puts more pressure on the server and has a better distribution effect; the second method belongs to distributed task allocation, which uses the computing power and agricultural machinery of each agricultural machine onboard computer. The mutual communication between them completes the task assignment, which takes a short time and has no pressure on the server, but the assignment effect is poor. In order to reduce the amount of server computing and reduce the probability of server failure, there is an urgent need in the art for a method that can fully utilize the computing power of an onboard computer to achieve task allocation.

发明内容SUMMARY OF THE INVENTION

本发明所要解决的技术问题是提供一种基于改进合同网算法的同种农机多机协同动态任务分配方法。The technical problem to be solved by the present invention is to provide a dynamic task assignment method based on the improved contract network algorithm for multi-machine cooperation of the same kind of agricultural machinery.

为了实现上述目的,本发明提供了一种同种农机多机协同动态任务分配方法,其中,该同种农机多机协同动态任务分配方法基于改进合同网算法进行动态任务分配,包括如下步骤:In order to achieve the above purpose, the present invention provides a method for dynamic task assignment of the same kind of agricultural machinery and multi-machine coordination.

S100、根据多机协同作业场景,基于农机性能和任务参数构建多机协同代价函数;S100. According to a multi-machine cooperative operation scenario, a multi-machine cooperative cost function is constructed based on agricultural machine performance and task parameters;

S200、构建农机投标代价函数和招标完成后机群代价函数;S200, constructing the agricultural machinery bidding cost function and the machine group cost function after the bidding is completed;

S300、构建基于远程云服务平台和无线自组网的多机协同动态任务分配系统;S300, constructing a multi-machine collaborative dynamic task assignment system based on a remote cloud service platform and a wireless ad hoc network;

S400、当有新任务需要分配时,系统通过改进合同网算法对新任务进行分配,最终得到最优的任务分配结果。S400. When there is a new task that needs to be allocated, the system allocates the new task by improving the contract network algorithm, and finally obtains the optimal task allocation result.

上述的同种农机多机协同动态任务分配方法,其中,步骤S100进一步包括:In the above-mentioned multi-machine collaborative dynamic task assignment method of the same kind of agricultural machinery, step S100 further includes:

S101、定义符号,假设m台农机作业,用集合{a1,…,am}表示;作业任务数量为n,用集合{T1,…,Tn}表示;第i台农机的性能参数表示为ai={vwi,di,wi,vi,tti}T,(i=1,2,…,m),其中vwi表示第i台农机的作业平均速度(km/h),di表示第i台农机的作业幅宽(m),wi表示第i台农机的平均作业能力(m2/h),vi表示第i台农机非作业状态行驶平均速度(km/h),tti表示第i台农机作业中每次掉头的平均时间(h);第j个任务的参数表示为:Tj={x1j,y1j,x2j,y2j,x3j,y3j,x4j,y4j,dTj,lTj,Si}T,(j=1,2,…,n,其中(x1j,y1j)、(x2j,y2j)、(x3j,y3j)和(x4j,y4j)分别表示任务Tj地块四个顶点的坐标,dTj表示任务Tj垂直作业路径的宽度,lTj表示任务Tj平行作业路径的长度,Sj表示任务Tj的面积;S101. Defining symbols, assuming that m sets of agricultural machinery work, represented by a set {a 1 , ..., a m }; the number of operation tasks is n, represented by a set {T 1 , ..., T n }; Expressed as a i = {v wi , d i , wi , v i , t ti } T , (i=1, 2,..., m), where v wi represents the average operating speed of the ith agricultural machine (km/ h), d i represents the working width of the ith agricultural machine (m), wi represents the average working capacity of the ith agricultural machine (m 2 /h), and vi represents the average running speed of the ith agricultural machine in the non-operating state ( km/h), t ti represents the average time (h) of each U-turn in the i-th agricultural machinery operation; the parameters of the j-th task are expressed as: T j ={x 1j , y 1j , x 2j , y 2j , x 3j , y 3j , x 4j , y 4j , d Tj , l Tj , S i } T , (j=1, 2,...,n, where (x1j, y1j), (x2j, y2j), (x3j, y3j ) and (x4j, y4j) represent the coordinates of the four vertices of the task Tj plot respectively, dTj represents the width of the vertical work path of the task Tj , l Tj represents the length of the parallel work path of the task Tj , Sj represents the task Tj area;

S102、采用如下公式计算每台农机的非作业路程:S102, the following formula is used to calculate the non-working distance of each agricultural machine:

Figure BDA0002755781420000021
Figure BDA0002755781420000021

其中,s(ai,Tj)表示农机ai到其第1个任务Tj的路程;s(ai,TjTk)表示农机ai从第j个任务Tj到第k个任务Tk的路程;s(ai,Tl)表示农机ai从最后一个任务Tl回到车库的路程;j,k,l∈{1,…,n};Among them, s( ai , T j ) represents the distance from the agricultural machinery a i to its first task T j ; s( ai , T j T k ) represents the agricultural machinery a i from the j th task T j to the k th task The distance of the task T k ; s( ai , T l ) represents the distance of the agricultural machine a i from the last task T l back to the garage; j, k, l∈{1,...,n};

Figure BDA0002755781420000022
Figure BDA0002755781420000022

Figure BDA0002755781420000031
Figure BDA0002755781420000031

Figure BDA0002755781420000032
Figure BDA0002755781420000032

S103、计算每台农机完成任务的总时间,所述总时间包括农机路上的时间、农机作业的时间和农机田间掉头的时间;S103, calculating the total time for each agricultural machine to complete the task, and the total time includes the time on the road of the agricultural machine, the time for the operation of the agricultural machine, and the time for the agricultural machine to turn around in the field;

Figure BDA0002755781420000033
Figure BDA0002755781420000033

其中,

Figure BDA0002755781420000034
kij为第i台农机在第j个任务地块作业行数,
Figure BDA0002755781420000035
式中
Figure BDA0002755781420000036
为向上取整符号,取值为不小于该符号内数值的最小整数;in,
Figure BDA0002755781420000034
k ij is the number of operation lines of the i-th agricultural machinery in the j-th task plot,
Figure BDA0002755781420000035
in the formula
Figure BDA0002755781420000036
It is a round-up symbol, and the value is the smallest integer not less than the value in the symbol;

S104、计算任务间距离,将车库作为起点,n个任务依次作为第2到n+1个点,建立任意两点间可行驶的最短距离矩阵D。S104 , calculating the distance between tasks, taking the garage as the starting point, and the n tasks as the 2nd to n+1st points in sequence, and establishing the shortest distance matrix D that can be traveled between any two points.

上述的同种农机多机协同动态任务分配方法,其中,所述最短距离矩阵D为:The above-mentioned method for dynamic task assignment of the same kind of agricultural machinery and multi-machine coordination, wherein, the shortest distance matrix D is:

Figure BDA0002755781420000037
其中dij表示第i-1个任务点到第j-1个任务点之间可行驶的最短距离,(i、j={2,…,n+1},i≠j)。
Figure BDA0002755781420000037
where d ij represents the shortest drivable distance between the i-1th mission point and the j-1th mission point, (i, j={2,...,n+1}, i≠j).

上述的同种农机多机协同动态任务分配方法,其中,如果两个任务地头相邻,认为该两个任务点之间可行驶的最短距离为0;如果两个任务地头不相邻,则该两个任务点之间可行驶的最短距离等于两个任务间路上的距离。The above-mentioned method for dynamic task assignment of the same kind of agricultural machinery and multi-machine cooperation, wherein, if two task heads are adjacent, it is considered that the shortest drivable distance between the two task points is 0; if the two task heads are not adjacent, the The shortest distance drivable between two mission points is equal to the distance on the road between the two missions.

上述的同种农机多机协同动态任务分配方法,其中,步骤102中,s(ai,Tj)=d1,j+1,s(ai,Tl)=d1,l+1In the above-mentioned method for dynamic task assignment of the same kind of agricultural machinery and multi-machine cooperation, wherein, in step 102, s( ai , T j )=d 1, j+1 , s( ai , T l )=d 1, l+1 ;

其中,农机进入任务地块的方式包括从路上进入和从地头连接处进入,农机从路上进入任务地块时x=0,农机从地头连接处进入任务地块时x=1;农机在该任务完成后回到路边时y=0,农机在该任务完成后回到地头连接处时y=1;Among them, the methods of agricultural machinery entering the task plot include entering from the road and entering from the headland connection. When the agricultural machinery enters the task plot from the road, x=0, and when the agricultural machine enters the task plot from the headland connection, x=1; y=0 when returning to the roadside after completion, and y=1 when the agricultural machinery returns to the headland connection after the task is completed;

农机进入第一个任务地块时从路上进入,第i台农机在第j个任务地块作业完成后的位置为:yij=(kij+xij)%2,其中,xij为第i台农机进入第j个任务地块的方式,%为求余;When the agricultural machinery enters the first task plot, it enters from the road. The position of the i-th agricultural machine after the j-th task plot is completed is: y ij =(k ij +x ij )%2, where x ij is the first The way that i agricultural machinery enters the jth task plot, % is the surplus;

当dj+1,k+1≠0时,任务i、j地头没有相连,此时农机ai从任务j到任务k的距离:s(ai,TjTk)=dj+1,k+1+yijlTj,xik=0;当dj+1,k+1=0时,任务i、j地头相连,此时农机ai从任务j到任务k的距离为:When d j+1, k+1 ≠ 0, tasks i and j are not connected, and the distance of agricultural machinery a i from task j to task k: s( ai , T j T k )=d j+1 , k+1 +y ij l Tj , x ik =0; when d j+1, k+1 =0, tasks i and j are connected to the ground, and the distance of agricultural machinery a i from task j to task k is:

s(ai,TjTk)=d′j+1,k+1+|yij-1|lTj,xik=1。s(a i , T j T k )=d′ j+1, k+1 +|y ij -1|l Tj , x ik =1.

上述的同种农机多机协同动态任务分配方法,其中,步骤105中,以多机协同中作业时间最长的农机作业时间作为多机协同代价:In the above-mentioned dynamic task assignment method for multi-machine collaboration of the same kind of agricultural machinery, wherein, in step 105, the operation time of the agricultural machinery with the longest operation time in the multi-machine collaboration is used as the cost of multi-machine collaboration:

f=max(ti)f=max(t i )

多机协同目标函数为使代价最低,即:The objective function of multi-machine cooperation is to minimize the cost, namely:

min(f)=min(max(ti))min(f)=min(max(t i ))

其中,f表示多机协同代价。Among them, f represents the multi-machine coordination cost.

上述的同种农机多机协同动态任务分配方法,其中,步骤S200进一步包括:The above-mentioned method for dynamic task assignment of the same kind of agricultural machinery and multi-machine coordination, wherein, step S200 further includes:

S201、构建农机ai对任务Tj投标的代价函数:S201 , constructing a cost function for agricultural machinery a i to bid on task T j :

Figure BDA0002755781420000041
Figure BDA0002755781420000041

Figure BDA0002755781420000042
为第i台农机添加任务Tj后所需作业的总时间;tmax为招标开始前整个机群的最大工作时间;
Figure BDA0002755781420000042
The total time required for the operation after adding the task T j for the i-th agricultural machine; t max is the maximum working time of the entire fleet before the bidding starts;

S202、构建第i台农机中标任务Tj后整个机群代价f′=f+Δfi j,其中,f′为招标完成后机群总代价;f为招标前的多机协同代价。S202, constructing the entire fleet cost f'=f+Δf i j after the i-th agricultural machine wins the bid task T j , where f' is the total cost of the fleet after the tender; f is the multi-machine coordination cost before the tender.

上述的同种农机多机协同动态任务分配方法,其中,步骤S400进一步包括:In the above-mentioned method for dynamic task assignment of the same kind of agricultural machinery and multi-machine coordination, wherein, step S400 further includes:

S401、确定招标者,平台选择正常作业农机作为招标者,为使招标过程通信距离最短,选择招标者

Figure BDA0002755781420000043
其中(xi,yi)为第i台农机当前位置;S401. Determine the tenderer, and the platform selects normal operating agricultural machinery as the tenderer. In order to minimize the communication distance during the tendering process, select the tenderer
Figure BDA0002755781420000043
Wherein ( xi , y i ) is the current position of the ith agricultural machine;

S402、招标者设定招标阈值,招标者在对任务Tj进行招标前,首先计算自身执行该任务的最小代价Δfj作为动态阈值,

Figure BDA0002755781420000051
其中
Figure BDA0002755781420000052
为招标者执行新增任务Tj的代价;投标者ai接收招标信息并计算自身执行该任务的最小代价Δfi J,如果Δfi J<Δfj发送投标信息,如果Δfi J≥Δfj,则不发送投标信息;S402. The tenderer sets a tendering threshold. Before tendering the task Tj , the tenderer first calculates the minimum cost Δfj for executing the task by itself as the dynamic threshold,
Figure BDA0002755781420000051
in
Figure BDA0002755781420000052
The cost of performing the new task T j for the tenderer; the tenderer a i receives the tender information and calculates the minimum cost Δf i J for executing the task itself, if Δf i J <Δf j sends the bidding information, if Δf i J ≥Δf j , the bidding information will not be sent;

S403、基于带阈值合同网算法的招投标过程;S403, a bidding process based on a threshold contract network algorithm;

S404、将中标者面积最小的任务进行招标;S404. Invite bids for the task with the smallest area of the winning bidder;

S405、执行农机间任务交换,设农机i执行任务Tj的路程代价

Figure BDA0002755781420000053
其中,si-j为农机i去掉任务Tj后的路程;S405. Execute task exchange between agricultural machines, and set the distance cost for agricultural machine i to perform task T j
Figure BDA0002755781420000053
Among them, s ij is the distance of agricultural machinery i after removing task T j ;

S406、得到最终动态任务分配结果。S406, obtain the final dynamic task assignment result.

上述的同种农机多机协同动态任务分配方法,其中,步骤S405中执行农机间任务交换进一步包括:The above-mentioned multi-machine collaborative dynamic task assignment method for the same kind of agricultural machinery, wherein, performing task exchange between agricultural machinery in step S405 further includes:

S4051、完成任务代价最大的农机i计算出最大路程代价

Figure BDA0002755781420000054
和对应的任务编号j;S4051. The agricultural machine i with the largest task completion cost calculates the largest distance cost
Figure BDA0002755781420000054
and the corresponding task number j;

S4052、农机i作为招标者对任务j进行交换招标;S4052, agricultural machinery i, as the tenderer, conducts exchange bidding for task j;

S4053、其他工作正常的农机作为投标者,投标者使用“删除-插入”的方式,依次将自身未执行任务删除,并利用插入方法计算替换后自身最小代价;S4053. Other agricultural machinery that works normally are used as bidders. The bidders use the "delete-insert" method to delete their unexecuted tasks in turn, and use the insertion method to calculate their own minimum cost after replacement;

S4054、如果替换后代价小于替换前,该任务作为投标信息;S4054. If the cost after replacement is less than that before replacement, the task is used as bidding information;

S4055、招标者使用“删除-插入”的方式,计算删除任务j后加入每个投标任后的代价,并取最小代价fi k和对应的任务k;S4055, the tenderer uses the "delete-insert" method to calculate the cost of adding each bidding task after deleting task j, and take the minimum cost f i k and the corresponding task k;

S4056、如果fi k<fi,则对任务j、k交换。S4056. If f i k < f i , swap tasks j and k.

上述的同种农机多机协同动态任务分配方法,其中,所述多机协同动态任务分配系统包括农机、服务器和客户端,所述农机安装有车载计算机、北斗定位模块和无线自组网模块,用于实现自身定位和与其他农机通信;所述服务器包括计算模块和存储模块,所述存储模块用于储存地块信息和农机信息;所述客户端用于选择和下发任务到指定作业机群。The above-mentioned multi-machine collaborative dynamic task allocation method for the same agricultural machinery, wherein the multi-machine collaborative dynamic task allocation system includes agricultural machinery, a server and a client, and the agricultural machinery is installed with a vehicle-mounted computer, a Beidou positioning module and a wireless ad hoc network module, It is used to realize its own positioning and communicate with other agricultural machinery; the server includes a computing module and a storage module, and the storage module is used to store plot information and agricultural machinery information; the client is used to select and issue tasks to the designated operating machine group .

本发明的技术效果在于:The technical effect of the present invention is:

本发明解决了农机合作社或农场多辆同种农机作业过程中出现的有新任务加入,或者有农机出现故障的情况下,如何合理的动态分配任务和任务执行顺序的问题。The invention solves the problem of how to reasonably dynamically allocate tasks and task execution sequence when new tasks are added or agricultural machines fail during the operation of agricultural machinery cooperatives or farms with multiple vehicles of the same type.

以下结合附图和具体实施例对本发明进行详细描述,但不作为对本发明的限定。The present invention is described in detail below with reference to the accompanying drawings and specific embodiments, but is not intended to limit the present invention.

附图说明Description of drawings

图1为本发明一实施例的动态任务分配流程图;1 is a flow chart of dynamic task allocation according to an embodiment of the present invention;

图2为本发明一实施例的任务交换流程图。FIG. 2 is a flowchart of task exchange according to an embodiment of the present invention.

具体实施方式Detailed ways

下面结合附图对本发明的结构原理和工作原理作具体的描述:Below in conjunction with accompanying drawing, structure principle and working principle of the present invention are described in detail:

参见图1,图1为本发明一实施例的动态任务分配流程图。本发明的同种农机多机协同动态任务分配方法,基于改进合同网算法进行动态任务分配,包括如下步骤:Referring to FIG. 1, FIG. 1 is a flowchart of dynamic task allocation according to an embodiment of the present invention. The multi-machine collaborative dynamic task assignment method of the same kind of agricultural machinery of the present invention performs dynamic task assignment based on an improved contract network algorithm, comprising the following steps:

步骤S100、根据多机协同作业场景,基于农机性能和任务参数构建多机协同代价函数;Step S100 , constructing a multi-machine collaborative cost function based on the agricultural machinery performance and task parameters according to the multi-machine collaborative operation scenario;

步骤S200、构建农机投标代价函数和招标完成后机群代价函数;Step S200, constructing the agricultural machinery bidding cost function and the fleet cost function after the bidding is completed;

步骤S300、构建基于远程云服务平台和无线自组网的多机协同动态任务分配系统;该多机协同动态任务分配系统,可包括农机、服务器和客户端,所述农机可安装有车载计算机、北斗定位模块和无线自组网模块,用于实现自身定位和与其他农机通信;所述服务器包括计算模块和存储模块,所述存储模块用于储存地块信息和农机信息,计算模块用于实现计算功能;所述客户端用于选择和下发任务到指定作业机群;Step S300, constructing a multi-machine collaborative dynamic task allocation system based on a remote cloud service platform and a wireless ad hoc network; the multi-machine collaborative dynamic task allocation system may include agricultural machinery, a server and a client, and the agricultural machinery may be installed with a vehicle-mounted computer, The Beidou positioning module and the wireless ad hoc network module are used to realize self-positioning and communicate with other agricultural machinery; the server includes a computing module and a storage module, the storage module is used to store plot information and agricultural machinery information, and the computing module is used to realize Computing function; the client is used to select and issue tasks to the designated operation group;

步骤S400、当有新任务需要分配时,所述多机协同动态任务分配系统通过改进合同网算法对新任务进行分配,并得到最优的任务分配结果。Step S400: When a new task needs to be allocated, the multi-machine collaborative dynamic task allocation system allocates the new task by improving the contract network algorithm, and obtains the optimal task allocation result.

其中,步骤S100进一步包括:Wherein, step S100 further includes:

步骤S101、定义符号,假设m台农机作业,用集合{a1,…,am}表示;作业任务数量为n,用集合{T1,…,Tn}表示;第i台农机的性能参数表示为ai={vwi,di,wi,vi,tti}T,(i=1,2,…,m),其中vwi表示第i台农机的作业平均速度(km/h),di表示第i台农机的作业幅宽(m),wi表示第i台农机的平均作业能力(m2/h),vi表示第i台农机非作业状态行驶平均速度(km/h),tti表示第i台农机作业中每次掉头的平均时间(h);第j个任务的参数表示为:Tj={x1j,y1j,x2j,y2j,x3j,y3j,x4j,y4j,dTj,lTj,Si}T,(j=1,2,…,n),其中(x1j,y1j)、(x2j,y2j)、(x3j,y3j)和(x4j,y4j)分别表示任务Tj地块四个顶点的坐标,dTj表示任务Tj垂直作业路径的宽度,lTj表示任务Tj平行作业路径的长度,Sj表示任务Tj的面积;Step S101, define symbols, assuming that m sets of agricultural machinery work, represented by a set {a 1 , ..., a m }; the number of operation tasks is n, represented by a set {T 1 , ..., T n }; the performance of the i-th agricultural machinery The parameters are expressed as a i = {v wi , d i , wi , v i , t ti } T , ( i =1, 2, . /h), d i represents the working width (m) of the ith agricultural machine, wi represents the average working capacity of the ith agricultural machine (m 2 /h), and vi represents the average speed of the ith agricultural machine in the non-operating state (km/h), t ti represents the average time (h) of each U-turn in the i-th agricultural machinery operation; the parameters of the j-th task are expressed as: T j ={x 1j , y 1j , x 2j , y 2j , x 3j , y 3j , x 4j , y 4j , d Tj , l Tj , S i } T , (j=1, 2, . . . , n), where (x 1j , y 1j ), (x 2j , y 2j ) ), (x 3j , y 3j ) and (x 4j , y 4j ) represent the coordinates of the four vertices of the task T j plot respectively, d Tj represents the width of the vertical work path of the task T j , and l Tj represents the parallel work of the task T j The length of the path, S j represents the area of the task T j ;

步骤S102、采用如下公式计算每台农机的非作业路程:Step S102, using the following formula to calculate the non-working distance of each agricultural machine:

Figure BDA0002755781420000071
Figure BDA0002755781420000071

其中,s(ai,Tj)表示农机ai到其第1个任务Tj的路程;s(ai,TjTk)表示农机ai从第j个任务Tj到第k个任务Tk的路程;s(ai,Tl)表示农机ai从最后一个任务Tl回到车库的路程;j,k,l∈{1,…,n};Among them, s( ai , T j ) represents the distance from the agricultural machinery a i to its first task T j ; s( ai , T j T k ) represents the agricultural machinery a i from the j th task T j to the k th task The distance of the task T k ; s( ai , T l ) represents the distance of the agricultural machine a i from the last task T l back to the garage; j, k, l∈{1,...,n};

Figure BDA0002755781420000072
Figure BDA0002755781420000072

Figure BDA0002755781420000073
Figure BDA0002755781420000073

Figure BDA0002755781420000074
Figure BDA0002755781420000074

步骤S103、计算每台农机完成任务的总时间,所述总时间包括农机路上的时间、农机作业的时间和农机田间掉头的时间;Step S103, calculating the total time for each agricultural machine to complete the task, and the total time includes the time on the road of the agricultural machine, the time of the operation of the agricultural machine and the time of the turn of the agricultural machine in the field;

Figure BDA0002755781420000075
Figure BDA0002755781420000075

其中,

Figure BDA0002755781420000076
kij为第i台农机在第j个任务地块作业行数,
Figure BDA0002755781420000077
式中
Figure BDA0002755781420000078
为向上取整符号,取值为不小于该符号内数值的最小整数;in,
Figure BDA0002755781420000076
k ij is the number of operation lines of the i-th agricultural machinery in the j-th task plot,
Figure BDA0002755781420000077
in the formula
Figure BDA0002755781420000078
It is a round-up symbol, and the value is the smallest integer not less than the value in the symbol;

步骤S104、计算任务间距离,将车库作为起点,即第一个点,n个任务依次作为第2到n+1个点,建立任意两点间可行驶的最短距离矩阵D。Step S104: Calculate the distance between tasks, take the garage as the starting point, that is, the first point, and n tasks as the 2nd to n+1st points in turn, and establish the shortest distance matrix D that can be traveled between any two points.

其中,所述最短距离矩阵D为:Wherein, the shortest distance matrix D is:

Figure BDA0002755781420000081
其中dij表示第i-1个任务点到第j-1个任务点之间可行驶的最短距离,(i、j={2,…,n+1},i≠j)。
Figure BDA0002755781420000081
where d ij represents the shortest drivable distance between the i-1th mission point and the j-1th mission point, (i, j={2,...,n+1}, i≠j).

如果两个任务地头相邻,认为该两个任务点之间可行驶的最短距离为0;如果两个任务地头不相邻,则该两个任务点之间可行驶的最短距离等于两个任务间路上的距离。If two mission heads are adjacent, the shortest distance drivable between the two mission points is considered to be 0; if the two mission heads are not adjacent, the shortest drivable distance between the two mission points is equal to the two missions distance on the road.

本实施例的步骤102中,s(ai,Tj)=d1,j+1,s(ai,Tl)=d1,l+1In step 102 of this embodiment, s( ai , Tj)=d1, j +1 , s( ai , T1)=d1, l +1 ;

其中,农机进入任务地块的方式包括从路上进入和从地头连接处进入,农机从路上进入任务地块时x=0,农机从地头连接处进入任务地块时x=1;农机在该任务完成后回到路边时y=0,农机在该任务完成后回到地头连接处时y=1;Among them, the methods of agricultural machinery entering the task plot include entering from the road and entering from the headland connection. When the agricultural machinery enters the task plot from the road, x=0, and when the agricultural machine enters the task plot from the headland connection, x=1; y=0 when returning to the roadside after completion, and y=1 when the agricultural machinery returns to the headland connection after the task is completed;

农机进入第一个任务地块时从路上进入,第i台农机在第j个任务地块作业完成后的位置为:yij=(kij+xij)%2,其中,xij为第i台农机进入第j个任务地块的方式,%为求余;When the agricultural machinery enters the first task plot, it enters from the road. The position of the i-th agricultural machine after the j-th task plot is completed is: y ij =(k ij +x ij )%2, where x ij is the first The way that i agricultural machinery enters the jth task plot, % is the surplus;

当dj+1,k+1≠0时,任务i、j地头没有相连,此时农机ai从任务j到任务k的距离:s(ai,TjTk)=dj+1,k+1+yijlTj,xik=0;当dj+1,k+1=0时,任务i、j地头相连,此时农机ai从任务j到任务k的距离为:When d j+1, k+1 ≠ 0, tasks i and j are not connected, and the distance of agricultural machinery a i from task j to task k: s( ai , T j T k )=d j+1 , k+1 +y ij l Tj , x ik =0; when d j+1, k+1 =0, tasks i and j are connected to the ground, and the distance of agricultural machinery a i from task j to task k is:

s(ai,TjTk)=d′j+1,k+1+|yij-1|lTj,xik=1。s(a i , T j T k )=d′ j+1, k+1 +|y ij -1|l Tj , x ik =1.

在步骤105中,以多机协同作业时间最长的农机作业时间为代价构建多机协同代价函数:f=max(ti)。In step 105, a multi-machine cooperative cost function is constructed at the cost of the agricultural machine operation time with the longest multi-machine cooperative operation time: f=max(t i ).

多机协同目标函数为使代价最低,即:The objective function of multi-machine cooperation is to minimize the cost, namely:

min(f)=min(max(ti))min(f)=min(max(t i ))

其中,f表示多机协同代价。Among them, f represents the multi-machine coordination cost.

本实施例中,步骤S200进一步包括:In this embodiment, step S200 further includes:

步骤S201、构建农机ai对任务Tj投标的代价函数:Step S201, constructing a cost function for agricultural machinery a i to bid on task T j :

Figure BDA0002755781420000091
Figure BDA0002755781420000091

Figure BDA0002755781420000092
为第i台农机添加任务Tj后所需作业的总时间;tmax为招标开始前整个机群的最大工作时间;
Figure BDA0002755781420000092
The total time required for the operation after adding the task T j for the i-th agricultural machine; t max is the maximum working time of the entire fleet before the bidding starts;

步骤S202、构建第i台农机中标任务Tj后整个机群代价f′=f+Δfi j,其中,f′为招标完成后机群总代价;f为招标前的多机协同代价。Step S202 , constructing the entire fleet cost f′=f+Δf i j after the i-th agricultural machine wins the bid task T j , where f′ is the total cost of the fleet after the tender; f is the multi-machine coordination cost before the tender.

步骤S400进一步包括:Step S400 further includes:

步骤S401、确定招标者,平台选择正常作业农机作为招标者,为使招标过程通信距离最短,选择招标者

Figure BDA0002755781420000093
其中(xi,yi)为第i台农机当前位置;Step S401, determine the tenderer, the platform selects normal operation agricultural machinery as the tenderer, and selects the tenderer in order to make the communication distance in the tendering process the shortest
Figure BDA0002755781420000093
Wherein ( xi , y i ) is the current position of the ith agricultural machine;

步骤S402、招标者设定招标阈值,招标者在对任务Tj进行招标前,首先计算自身执行该任务的最小代价Δfj作为动态阈值,

Figure BDA0002755781420000094
其中
Figure BDA0002755781420000095
为招标者执行新增任务Tj的代价;投标者ai接收招标信息并计算自身执行该任务的最小代价Δfi J,如果Δfi J<Δfj发送投标信息,如果Δfi J≥Δfj,则不发送投标信息;Step S402, the tenderer sets a tendering threshold, and before tendering the task Tj , the tenderer first calculates the minimum cost Δfj for performing the task by itself as the dynamic threshold,
Figure BDA0002755781420000094
in
Figure BDA0002755781420000095
The cost of performing the new task T j for the tenderer; the tenderer a i receives the tender information and calculates the minimum cost Δf i J for executing the task itself, if Δf i J <Δf j sends the bidding information, if Δf i J ≥Δf j , the bidding information will not be sent;

步骤S403、基于带阈值合同网算法进行招投标;Step S403, bidding based on the contract network algorithm with threshold;

步骤S404、将中标者面积最小的任务进行招标;Step S404, bidding for the task with the smallest area of the winning bidder;

步骤S405、执行农机间任务交换,设农机i执行任务Tj的路程代价

Figure BDA0002755781420000096
其中,si-j为农机i去掉任务Tj后的路程;Step S405, perform task exchange between agricultural machines, and set the distance cost of agricultural machine i to perform task T j
Figure BDA0002755781420000096
Among them, s ij is the distance of agricultural machinery i after removing task T j ;

步骤S406、得到最终动态任务分配结果。Step S406, obtaining the final dynamic task assignment result.

参见图2,图2为本发明一实施例的任务交换流程图。本实施例的步骤S405中执行农机间任务交换进一步包括:Referring to FIG. 2, FIG. 2 is a flowchart of task exchange according to an embodiment of the present invention. In step S405 of this embodiment, performing task exchange between agricultural machines further includes:

步骤S4051、完成任务代价最大的农机i计算出最大路程代价

Figure BDA0002755781420000097
和对应的任务编号j;Step S4051, the agricultural machine i with the largest task cost calculates the largest distance cost
Figure BDA0002755781420000097
and the corresponding task number j;

步骤S4052、农机i作为招标者对任务j进行交换招标;Step S4052, agricultural machinery i, as the tenderer, conducts exchange bidding for task j;

步骤S4053、其他工作正常的农机作为投标者,投标者使用“删除-插入”的方式,依次将自身未执行任务删除,并利用插入方法计算替换后自身最小代价;In step S4053, other agricultural machinery that works normally are used as bidders, and the bidders use the "delete-insert" method to delete their unexecuted tasks in turn, and use the insertion method to calculate their own minimum cost after replacement;

步骤S4054、如果替换后代价小于替换前,该任务作为投标信息;Step S4054, if the cost after replacement is less than that before replacement, the task is used as bidding information;

步骤S4055、招标者使用“删除-插入”的方式,计算删除任务j后加入每个投标任后的代价,并取最小代价fi k和对应的任务k;Step S4055, the tenderer uses the "delete-insert" method to calculate the cost of adding each bidding task after deleting task j, and take the minimum cost f i k and the corresponding task k;

步骤S4056、如果fi k<fi,则对任务j、k交换。Step S4056, if f i k < f i , swap tasks j and k.

本发明解决了农机合作社或农场多辆同种农机作业过程中出现的有新任务加入,或者有农机出现故障的情况下,如何合理的动态分配任务和任务执行顺序的问题。The invention solves the problem of how to reasonably dynamically allocate tasks and task execution sequence when new tasks are added or agricultural machines fail during the operation of agricultural machinery cooperatives or farms with multiple vehicles of the same type.

当然,本发明还可有其它多种实施例,在不背离本发明精神及其实质的情况下,熟悉本领域的技术人员当可根据本发明作出各种相应的改变和变形,但这些相应的改变和变形都应属于本发明所附的权利要求的保护范围。Of course, the present invention can also have other various embodiments, without departing from the spirit and essence of the present invention, those skilled in the art can make various corresponding changes and modifications according to the present invention, but these corresponding Changes and deformations should belong to the protection scope of the appended claims of the present invention.

Claims (10)

1.一种同种农机多机协同动态任务分配方法,其特征在于,该同种农机多机协同动态任务分配方法基于改进合同网算法进行动态任务分配,包括如下步骤:1. a kind of agricultural machinery multi-machine collaborative dynamic task allocation method of the same kind, is characterized in that, this same kind of agricultural machinery multi-machine collaborative dynamic task allocation method carries out dynamic task allocation based on improved contract network algorithm, comprises the steps: S100、根据多机协同作业场景,基于农机性能和任务参数构建多机协同代价函数;S100. According to a multi-machine cooperative operation scenario, a multi-machine cooperative cost function is constructed based on agricultural machine performance and task parameters; S200、构建农机投标代价函数和招标完成后机群代价函数;S200, constructing the agricultural machinery bidding cost function and the machine group cost function after the bidding is completed; S300、构建基于远程云服务平台和无线自组网的多机协同动态任务分配系统;以及S300. Construct a multi-machine collaborative dynamic task assignment system based on a remote cloud service platform and a wireless ad hoc network; and S400、当有新任务需要分配时,系统通过改进合同网算法对新任务进行分配,并得到最优的任务分配结果。S400 , when a new task needs to be allocated, the system allocates the new task by improving the contract network algorithm, and obtains an optimal task allocation result. 2.如权利要求1所述的同种农机多机协同动态任务分配方法,其特征在于,步骤S100进一步包括:2. The multi-machine collaborative dynamic task assignment method of the same kind of agricultural machinery as claimed in claim 1, wherein step S100 further comprises: S101、定义符号,假设m台农机作业,用集合{a1,…,am}表示;作业任务数量为n,用集合{T1,…,Tn}表示;第i台农机的性能参数表示为ai={vwi,di,wi,vi,tti}T,(i=1,2,…,m),其中vwi表示第i台农机的作业平均速度(km/h),di表示第i台农机的作业幅宽(m),wi表示第i台农机的平均作业能力(m2/h),vi表示第i台农机非作业状态行驶平均速度(km/h),tti表示第i台农机作业中每次掉头的平均时间(h);第j个任务的参数表示为:Tj={x1j,y1j,x2j,y2j,x3j,y3j,x4j,y4j,dTj,lTj,Si}T,(j=1,2,…,n,其中(x1j,y1j)、(x2j,y2j)、(x3j,y3j)和(x4j,y4j)分别表示任务Tj地块四个顶点的坐标,dTj表示任务Tj垂直作业路径的宽度,lTj表示任务Tj平行作业路径的长度,Sj表示任务Tj的面积;S101. Define symbols, assuming that m sets of agricultural machinery work, represented by a set {a 1 , ..., a m }; the number of operation tasks is n, represented by a set {T 1 , ..., T n }; Expressed as a i = {v wi , d i , wi , v i , t ti } T , (i=1, 2,..., m), where v wi represents the average operating speed of the ith agricultural machine (km/ h), d i represents the working width (m) of the ith agricultural machine, wi represents the average working capacity of the ith agricultural machine (m 2 /h), and vi represents the average running speed of the ith agricultural machine in the non-operating state ( km/h), t ti represents the average time (h) of each U-turn in the i-th agricultural machinery operation; the parameters of the j-th task are expressed as: T j ={x 1j , y 1j , x 2j , y 2j , x 3j , y 3j , x 4j , y 4j , d Tj , l Tj , S i } T , (j=1, 2, ..., n, where (x1j, y1j), (x2j, y2j), (x3j, y3j ) and (x4j, y4j) represent the coordinates of the four vertices of the task Tj plot respectively, dTj represents the width of the vertical work path of the task Tj , l Tj represents the length of the parallel work path of the task Tj , Sj represents the task Tj area; S102、采用如下公式计算每台农机的非作业路程:S102, the following formula is used to calculate the non-working distance of each agricultural machine:
Figure FDA0002755781410000011
Figure FDA0002755781410000011
其中,s(ai,Tj)表示农机ai到其第1个任务Tj的路程;s(ai,TjTk)表示农机ai从第j个任务Tj到第k个任务Tk的路程;s(ai,Tl)表示农机ai从最后一个任务Tl回到车库的路程;j,k,l∈{1,…,n};Among them, s( ai , T j ) represents the distance from the agricultural machinery a i to its first task T j ; s( ai , T j T k ) represents the agricultural machinery a i from the j th task T j to the k th task The distance of the task T k ; s( ai , T l ) represents the distance of the agricultural machine a i from the last task T l back to the garage; j, k, l∈{1,...,n};
Figure FDA0002755781410000021
Figure FDA0002755781410000021
Figure FDA0002755781410000022
Figure FDA0002755781410000022
Figure FDA0002755781410000023
Figure FDA0002755781410000023
S103、计算每台农机完成任务的总时间,所述总时间包括农机路上的时间、农机作业的时间和农机田间掉头的时间;S103, calculating the total time for each agricultural machine to complete the task, and the total time includes the time on the road of the agricultural machine, the time for the operation of the agricultural machine, and the time for the agricultural machine to turn around in the field;
Figure FDA0002755781410000024
Figure FDA0002755781410000024
其中,
Figure FDA0002755781410000025
kij为第i台农机在第j个任务地块作业行数,
Figure FDA0002755781410000026
式中
Figure FDA0002755781410000027
为向上取整符号,取值为不小于该符号内数值的最小整数;
in,
Figure FDA0002755781410000025
k ij is the number of operation lines of the i-th agricultural machinery in the j-th task plot,
Figure FDA0002755781410000026
in the formula
Figure FDA0002755781410000027
It is a round-up symbol, and the value is the smallest integer not less than the value in the symbol;
S104、计算任务间距离,将车库作为起点,n个任务依次作为第2到n+1个点,建立任意两点间可行驶的最短距离矩阵D。S104 , calculating the distance between tasks, taking the garage as the starting point, and the n tasks as the 2nd to n+1st points in sequence, and establishing the shortest distance matrix D that can be traveled between any two points.
3.如权利要求2所述的同种农机多机协同动态任务分配方法,其特征在于,所述最短距离矩阵D为:3. the same kind of agricultural machinery multi-machine collaborative dynamic task allocation method as claimed in claim 2, is characterized in that, described shortest distance matrix D is:
Figure FDA0002755781410000028
其中dij表示第i-1个任务点到第j-1个任务点之间可行驶的最短距离,(i、j={2,…,n+1},i≠j)。
Figure FDA0002755781410000028
where d ij represents the shortest drivable distance between the i-1th mission point and the j-1th mission point, (i, j={2,...,n+1}, i≠j).
4.如权利要求2或3所述的同种农机多机协同动态任务分配方法,其特征在于,如果两个任务地头相邻,认为该两个任务点之间可行驶的最短距离为0;如果两个任务地头不相邻,则该两个任务点之间可行驶的最短距离等于两个任务间路上的距离。4. The same kind of agricultural machinery multi-machine collaborative dynamic task assignment method as claimed in claim 2 or 3, characterized in that, if two task fields are adjacent, it is considered that the shortest drivable distance between the two task points is 0; If the two missions are not adjacent, the shortest distance drivable between the two mission points is equal to the distance on the road between the two missions. 5.如权利要求4所述的同种农机多机协同动态任务分配方法,其特征在于,步骤102中,s(ai,Tj)=d1,j+1,s(ai,Tl)=d1,l+15. The multi-machine collaborative dynamic task assignment method for the same kind of agricultural machinery according to claim 4, wherein in step 102, s( ai , Tj)=d1, j +1 , s( ai ,T l )=d 1,l+1 ; 其中,农机进入任务地块的方式包括从路上进入和从地头连接处进入,农机从路上进入任务地块时x=0,农机从地头连接处进入任务地块时x=1;农机在该任务完成后回到路边时y=0,农机在该任务完成后回到地头连接处时y=1;Among them, the methods of agricultural machinery entering the task plot include entering from the road and entering from the headland connection. When the agricultural machinery enters the task plot from the road, x=0, and when the agricultural machine enters the task plot from the headland connection, x=1; y=0 when returning to the roadside after completion, and y=1 when the agricultural machinery returns to the headland connection after the task is completed; 农机进入第一个任务地块时从路上进入,第i台农机在第j个任务地块作业完成后的位置为:yij=(kij+xij)%2,其中,xij为第i台农机进入第j个任务地块的方式,%为求余;When the agricultural machinery enters the first task plot, it enters from the road. The position of the i-th agricultural machine after the j-th task plot is completed is: y ij =(k ij +x ij )%2, where x ij is the first The way that i agricultural machinery enters the jth task plot, % is the surplus; 当dj+1,k+1≠0时,任务i、j地头没有相连,此时农机ai从任务j到任务k的距离:s(ai,TjTk)=dj+1,k+1+yijlTj,xik=0;当dj+1,k+1=0时,任务i、j地头相连,此时农机ai从任务j到任务k的距离为:When d j+1, k+1 ≠ 0, tasks i and j are not connected, and the distance of agricultural machinery a i from task j to task k: s( ai , T j T k )=d j+1 , k+1 +y ij l Tj , x ik =0; when d j+1, k+1 =0, tasks i and j are connected to the ground, and the distance of agricultural machinery a i from task j to task k is: s(ai,TjTk)=d′j+1,k+1+|yij-1|lTj,xik=1。s(a i , T j T k )=d′ j+1, k+1 +|y ij -1|l Tj , x ik =1. 6.如权利要求5所述的同种农机多机协同动态任务分配方法,其特征在于,步骤105中,以多机协同作业时间最长的农机作业时间为代价构建多机协同代价函数:f=max(ti)。6. The same kind of agricultural machinery multi-machine collaborative dynamic task assignment method as claimed in claim 5, wherein in step 105, a multi-machine collaborative cost function is constructed at the cost of the agricultural machinery operation time with the longest multi-machine cooperative operation time: f =max(t i ). 多机协同目标函数为使代价最低,即:The objective function of multi-machine cooperation is to minimize the cost, namely: min(f)=min(max(ti))min(f)=min(max(t i )) 其中,f表示多机协同代价。Among them, f represents the multi-machine coordination cost. 7.如权利要求6所述的同种农机多机协同动态任务分配方法,其特征在于,步骤S200进一步包括:7. The multi-machine collaborative dynamic task assignment method of the same kind of agricultural machinery as claimed in claim 6, wherein step S200 further comprises: S201、构建农机ai对任务Tj投标的代价函数:S201 , constructing a cost function for agricultural machinery a i to bid on task T j :
Figure FDA0002755781410000031
其中
Figure FDA0002755781410000032
Figure FDA0002755781410000031
in
Figure FDA0002755781410000032
Figure FDA0002755781410000033
为第i台农机添加任务Tj后所需作业的总时间;tmax为招标开始前整个机群的最大工作时间;
Figure FDA0002755781410000033
The total time required for the operation after adding the task T j for the i-th agricultural machine; t max is the maximum working time of the entire fleet before the bidding starts;
S202、构建第i台农机中标任务Tj后整个机群代价f′=f+Δfi j,其中,f′为招标完成后机群总代价;f为招标前的多机协同代价。S202, constructing the entire fleet cost f'=f+Δf i j after the i-th agricultural machine wins the bid task T j , where f' is the total cost of the fleet after the tender; f is the multi-machine coordination cost before the tender.
8.如权利要求7所述的同种农机多机协同动态任务分配方法,其特征在于,步骤S400进一步包括:8. The multi-machine collaborative dynamic task assignment method of the same kind of agricultural machinery as claimed in claim 7, wherein step S400 further comprises: S401、确定招标者,平台选择正常作业农机作为招标者,为使招标过程通信距离最短,选择招标者
Figure FDA0002755781410000041
其中(xi,yi)为第i台农机当前位置;
S401. Determine the tenderer, and the platform selects normal operating agricultural machinery as the tenderer. In order to minimize the communication distance during the tendering process, select the tenderer
Figure FDA0002755781410000041
Wherein ( xi , y i ) is the current position of the ith agricultural machine;
S402、招标者设定招标阈值,招标者在对任务Tj进行招标前,首先计算自身执行该任务的最小代价Δfj作为动态阈值,
Figure FDA0002755781410000042
其中
Figure FDA0002755781410000043
为招标者执行新增任务Tj的代价;投标者ai接收招标信息并计算自身执行该任务的最小代价Δfi j,如果Δfi j<Δfj发送投标信息,如果Δfi j≥Δfj,则不发送投标信息;
S402. The tenderer sets a tendering threshold. Before tendering the task Tj , the tenderer first calculates the minimum cost Δfj for executing the task by itself as the dynamic threshold,
Figure FDA0002755781410000042
in
Figure FDA0002755781410000043
The cost of performing the new task T j for the tenderer; the tenderer a i receives the tender information and calculates the minimum cost Δf i j for executing the task itself, if Δf i j <Δf j sends the bidding information, if Δf i j ≥Δf j , the bidding information will not be sent;
S403、基于带阈值合同网算法的招投标过程;S403, a bidding process based on a threshold contract network algorithm; S404、将中标者面积最小的任务进行招标;S404. Invite bids for the task with the smallest area of the winning bidder; S405、执行农机间任务交换,设农机i执行任务Tj的路程代价
Figure FDA0002755781410000044
其中,si-j为农机i去掉任务Tj后的路程;
S405. Execute task exchange between agricultural machines, and set the distance cost for agricultural machine i to perform task T j
Figure FDA0002755781410000044
Among them, s ij is the distance of agricultural machinery i after removing task T j ;
S406、得到最终动态任务分配结果。S406, obtain the final dynamic task assignment result.
9.如权利要求8所述的同种农机多机协同动态任务分配方法,其特征在于,步骤S405中执行农机间任务交换进一步包括:9. The multi-machine collaborative dynamic task assignment method for the same kind of agricultural machinery as claimed in claim 8, wherein in step S405, performing task exchange between agricultural machinery further comprises: S4051、完成任务代价最大的农机i计算出最大路程代价
Figure FDA0002755781410000045
和对应的任务编号j;
S4051. The agricultural machine i with the largest task completion cost calculates the largest distance cost
Figure FDA0002755781410000045
and the corresponding task number j;
S4052、农机i作为招标者对任务j进行交换招标;S4052, agricultural machinery i, as the tenderer, conducts exchange bidding for task j; S4053、其他工作正常的农机作为投标者,投标者使用“删除-插入”的方式,依次将自身未执行任务删除,并利用插入方法计算替换后自身最小代价;S4053. Other agricultural machinery that works normally are used as bidders. The bidders use the "delete-insert" method to delete their unexecuted tasks in turn, and use the insertion method to calculate their own minimum cost after replacement; S4054、如果替换后代价小于替换前,该任务作为投标信息;S4054. If the cost after replacement is less than that before replacement, the task is used as bidding information; S4055、招标者使用“删除-插入”的方式,计算删除任务j后加入每个投标任后的代价,并取最小代价fi k和对应的任务k;S4055, the tenderer uses the "delete-insert" method to calculate the cost of adding each bidding task after deleting task j, and take the minimum cost f i k and the corresponding task k; S4056、如果fi k<fi,则对任务j、k交换。S4056. If f i k < f i , swap tasks j and k.
10.如权利要求9所述的同种农机多机协同动态任务分配方法,其特征在于,步骤S300中所述的多机协同动态任务分配系统包括农机、服务器和客户端,所述农机安装有车载计算机、北斗定位模块和无线自组网模块,用于实现自身定位和与其他农机通信;所述服务器包括计算模块和存储模块,所述存储模块用于储存地块信息和农机信息;所述客户端用于选择和下发任务到指定作业机群。10. The method for dynamic task assignment of the same kind of agricultural machinery and multi-machine coordination according to claim 9, wherein the multi-machine cooperative dynamic task assignment system described in step S300 comprises an agricultural machine, a server and a client, and the agricultural machine is installed with a The vehicle-mounted computer, the Beidou positioning module and the wireless ad hoc network module are used to realize self-positioning and communicate with other agricultural machinery; the server includes a computing module and a storage module, and the storage module is used to store plot information and agricultural machinery information; the The client is used to select and send tasks to the specified job cluster.
CN202011202172.9A 2020-11-02 2020-11-02 A method for dynamic task allocation of multiple agricultural machines of the same type Active CN114444828B (en)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN202011202172.9A CN114444828B (en) 2020-11-02 2020-11-02 A method for dynamic task allocation of multiple agricultural machines of the same type

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN202011202172.9A CN114444828B (en) 2020-11-02 2020-11-02 A method for dynamic task allocation of multiple agricultural machines of the same type

Publications (2)

Publication Number Publication Date
CN114444828A true CN114444828A (en) 2022-05-06
CN114444828B CN114444828B (en) 2025-05-27

Family

ID=81357121

Family Applications (1)

Application Number Title Priority Date Filing Date
CN202011202172.9A Active CN114444828B (en) 2020-11-02 2020-11-02 A method for dynamic task allocation of multiple agricultural machines of the same type

Country Status (1)

Country Link
CN (1) CN114444828B (en)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN117621091A (en) * 2024-01-26 2024-03-01 深圳威洛博机器人有限公司 Gait cooperative control method and system for robot

Citations (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7813993B1 (en) * 2002-08-30 2010-10-12 Advanced Micro Devices, Inc. Method and apparatus for scheduling a resource
CN105139069A (en) * 2015-07-30 2015-12-09 江苏科技大学 Method for improving contract net based on particle swarm algorithm
CN109343945A (en) * 2018-09-11 2019-02-15 中国空间技术研究院 A Multi-task Dynamic Allocation Method Based on Contract Net Algorithm
CN109886574A (en) * 2019-02-20 2019-06-14 哈尔滨工程大学 A multi-robot task assignment method based on improved threshold method
CN110456633A (en) * 2019-06-29 2019-11-15 西南电子技术研究所(中国电子科技集团公司第十研究所) Airborne Multi-platform Distributed Task Allocation Method
CN111417084A (en) * 2020-03-26 2020-07-14 仲恺农业工程学院 Distribution method, system, medium and equipment for agricultural situation acquisition task
CN111716356A (en) * 2020-06-18 2020-09-29 南京邮电大学 A Humanoid Multi-Robot Collaboration Method

Patent Citations (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7813993B1 (en) * 2002-08-30 2010-10-12 Advanced Micro Devices, Inc. Method and apparatus for scheduling a resource
CN105139069A (en) * 2015-07-30 2015-12-09 江苏科技大学 Method for improving contract net based on particle swarm algorithm
CN109343945A (en) * 2018-09-11 2019-02-15 中国空间技术研究院 A Multi-task Dynamic Allocation Method Based on Contract Net Algorithm
CN109886574A (en) * 2019-02-20 2019-06-14 哈尔滨工程大学 A multi-robot task assignment method based on improved threshold method
CN110456633A (en) * 2019-06-29 2019-11-15 西南电子技术研究所(中国电子科技集团公司第十研究所) Airborne Multi-platform Distributed Task Allocation Method
CN111417084A (en) * 2020-03-26 2020-07-14 仲恺农业工程学院 Distribution method, system, medium and equipment for agricultural situation acquisition task
CN111716356A (en) * 2020-06-18 2020-09-29 南京邮电大学 A Humanoid Multi-Robot Collaboration Method

Non-Patent Citations (2)

* Cited by examiner, † Cited by third party
Title
B. WU: "Price-Based Negotiation for Task Assignment in a Distributed Network Manufacturing Mode Environment", ADVANCED MANUFACTURING TECHNOLOGY, 31 January 2003 (2003-01-31), pages 145 *
赵博等: "核电厂数字化仪控系统动态流程图 方法分析研究", 核科学与工程, 28 February 2018 (2018-02-28), pages 99 - 106 *

Cited By (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN117621091A (en) * 2024-01-26 2024-03-01 深圳威洛博机器人有限公司 Gait cooperative control method and system for robot
CN117621091B (en) * 2024-01-26 2024-04-09 深圳威洛博机器人有限公司 Gait cooperative control method and system for robot

Also Published As

Publication number Publication date
CN114444828B (en) 2025-05-27

Similar Documents

Publication Publication Date Title
Guazzone et al. A game-theoretic approach to coalition formation in green cloud federations
CN106453146B (en) Method, system, device and readable storage medium for allocating private cloud computing resources
CN107659433B (en) Cloud resource scheduling method and equipment
CN112600887B (en) Computing power management method and device
CN110826968A (en) Urban crowdsourcing distribution task optimal scheduling method based on path planning
CN110231990A (en) Block chain resource optimal allocation method and device based on secondary auction
CN113269424B (en) Robot cluster task assignment method, system, device and storage medium
CN108776863B (en) A crowdsensing incentive method based on user base maximization
CN114444828A (en) A method for dynamic task assignment of the same kind of agricultural machinery and multi-machine coordination
CN112948116B (en) A Cooperative Computing Resource Allocation Method for Edge Computing Based on Online Incentives
CN109040193B (en) Mobile device cloud resource allocation method based on independent subtasks
CN102331948A (en) Resource state-based virtual machine structure adjustment method and adjustment system
CN115392776A (en) Spatial crowdsourcing task allocation method based on multi-skill cooperation
CN114548913A (en) A Multi-stage Task Assignment Method to Maximize the Number of Task Assignments
CN118484296A (en) A heuristic graph partitioning method based on GPU computing power awareness
CN102158533A (en) Distributed web service selection method based on QoS (Quality of Service)
CN111078380B (en) A multi-objective task scheduling method and system
CN103002067A (en) Acquiring method of internet protocol (IP) addresses of virtual machine
CN107832864B (en) Network contract special car distribution and pricing method under bidding environment
CN117350778A (en) A hub location selection method under different transportation demand types based on fusion algorithm
CN115525424A (en) Distributed computing system and method for group robots
CN109213588A (en) A kind of cloud data center Batch Arrival task allocation apparatus, system and method
CN114612024B (en) Regional delivery quantity optimization method, device, computer equipment and storage medium
Guazzone et al. Distributed coalition formation in energy-aware cloud federations: A game-theoretic approach (extended version)
CN106850849A (en) A kind of data processing method, device and server

Legal Events

Date Code Title Description
PB01 Publication
PB01 Publication
SE01 Entry into force of request for substantive examination
SE01 Entry into force of request for substantive examination
GR01 Patent grant
GR01 Patent grant