熊乾程，董 晨，洪祺瑜

1(福州大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，福州 350116)

2(福建省網(wǎng)絡(luò)計(jì)算與智能信息處理重點(diǎn)實(shí)驗(yàn)室，福州 350116)

3(網(wǎng)絡(luò)系統(tǒng)信息安全福建省高校重點(diǎn)實(shí)驗(yàn)室，福州 350116)

E-mail：dongchen@fzu.edu.cn

1 引 言

如今，全球性的產(chǎn)能過(guò)剩導(dǎo)致了企業(yè)間越發(fā)激烈的競(jìng)爭(zhēng)，而互聯(lián)網(wǎng)的飛速發(fā)展大幅降低了人與人之間交流成本，進(jìn)一步放大了客戶個(gè)性化的需求，在這樣一個(gè)技術(shù)、經(jīng)濟(jì)快速增長(zhǎng)的環(huán)境下，越來(lái)越多的企業(yè)從傳統(tǒng)的大規(guī)模生產(chǎn)向著能夠?qū)崟r(shí)收集生產(chǎn)信息，調(diào)整產(chǎn)品類型與生產(chǎn)能力的多品種、多批次智能化生產(chǎn)轉(zhuǎn)變[1].客戶的定制生產(chǎn)需求帶來(lái)了產(chǎn)品生命周期的多變性，工廠需要更加靈活的制造自動(dòng)化以適應(yīng)動(dòng)態(tài)的制造與供應(yīng)過(guò)程.然而，傳統(tǒng)的制造應(yīng)用中各生產(chǎn)環(huán)節(jié)大多是單獨(dú)且分離的，生產(chǎn)實(shí)體與虛擬系統(tǒng)的集成度較低，存在生產(chǎn)環(huán)節(jié)難以及時(shí)調(diào)整、供應(yīng)效率低下等問(wèn)題[2]，難以滿足如今技術(shù)發(fā)展與客戶需求的快速變化，急需制造商重新配置生產(chǎn)路徑與流程，重組制造單位.

面對(duì)生產(chǎn)制造需求快速變化帶來(lái)的挑戰(zhàn)，德國(guó)政府于2010年提出了智能工廠這一概念，作為工業(yè)4.0的核心，智能工廠旨在構(gòu)建面向制造業(yè)的信息物理系統(tǒng)，由物理實(shí)體負(fù)責(zé)生產(chǎn)中的智能協(xié)商，信息系統(tǒng)負(fù)責(zé)任務(wù)收發(fā)、數(shù)據(jù)采集以及實(shí)體生產(chǎn)過(guò)程的監(jiān)督，通過(guò)集成信息系統(tǒng)與物理實(shí)體，最終實(shí)現(xiàn)工廠中機(jī)器、原料、產(chǎn)品極其的自組織生產(chǎn)[3].

作為生產(chǎn)環(huán)節(jié)中的重要一環(huán)，靈活的原料供應(yīng)是多類型、多批次產(chǎn)品生產(chǎn)的基礎(chǔ)，自動(dòng)引導(dǎo)車(AGV)、自主移動(dòng)機(jī)器人(AMR)等技術(shù)的進(jìn)步給傳統(tǒng)的物料搬運(yùn)市場(chǎng)帶來(lái)了新的解決方案，倉(cāng)儲(chǔ)和制造設(shè)施內(nèi)的自動(dòng)負(fù)載運(yùn)輸被認(rèn)為是提高生產(chǎn)效率、降低運(yùn)營(yíng)成本的實(shí)用手段并廣泛運(yùn)用在自動(dòng)化生產(chǎn)制造環(huán)節(jié)[4]，盡管具備許多優(yōu)勢(shì)，在面對(duì)定制生產(chǎn)帶來(lái)動(dòng)態(tài)原料供應(yīng)需求變化時(shí)，多機(jī)器人系統(tǒng)需要更加高效且具備伸縮性，如何在供應(yīng)環(huán)節(jié)為自動(dòng)負(fù)載運(yùn)輸機(jī)器人系統(tǒng)的分配任務(wù)仍舊是個(gè)亟待處理的問(wèn)題[5].為了滿足動(dòng)態(tài)供應(yīng)需求、解決供應(yīng)問(wèn)題，我們提出一種運(yùn)用運(yùn)籌學(xué)理論的啟發(fā)式智能工廠多機(jī)器人供應(yīng)分配方法，能夠在面對(duì)不同的任務(wù)規(guī)模與機(jī)器人的數(shù)量時(shí)，在保證任務(wù)完成質(zhì)量的情況下，進(jìn)一步優(yōu)化分配結(jié)果.本文的主要貢獻(xiàn)如下：

1)考慮原料供應(yīng)需求與運(yùn)行距離等因素，設(shè)計(jì)了用于反應(yīng)供應(yīng)任務(wù)的執(zhí)行效果以及機(jī)器人消耗的效用與成本函數(shù)，根據(jù)設(shè)計(jì)的效用與成本函數(shù)，建立了一個(gè)最大化供應(yīng)任務(wù)收益的智能工廠原料供應(yīng)優(yōu)化模型.

2)將基于多機(jī)器人系統(tǒng)的任務(wù)協(xié)作應(yīng)用在原料供應(yīng)環(huán)節(jié)，將原料供應(yīng)轉(zhuǎn)化為多機(jī)器人任務(wù)分配問(wèn)題的變體，提出一種基于博弈論的多機(jī)器人協(xié)作的供應(yīng)任務(wù)分配方案.

2 相關(guān)工作

由于在重復(fù)工作中的高速度、精度，以及解放人工成本帶來(lái)的生產(chǎn)效益，在過(guò)去的幾年里，多機(jī)器人系統(tǒng)在開(kāi)始廣泛集成在運(yùn)輸、倉(cāng)儲(chǔ)、工業(yè)制造等領(lǐng)域[6-8]，如何平衡效率、資源、成本等因素為多機(jī)器人系統(tǒng)合理的分配任務(wù)，已經(jīng)成為當(dāng)前研究的熱點(diǎn)[9]，很自然地讓人考慮如何將多機(jī)器人系統(tǒng)應(yīng)用于智能生產(chǎn)環(huán)節(jié).

Huang等人[10]提出了一種基于拍賣算法的智能工廠中的分布式機(jī)器人協(xié)作任務(wù)分配機(jī)制，考慮了異構(gòu)機(jī)器人與任務(wù)距離以及機(jī)器人能力與任務(wù)之間的匹配程度進(jìn)行任務(wù)劃分；Baroudi等人[11]提出了一種基于動(dòng)態(tài)多目標(biāo)拍賣的任務(wù)分配算法，綜合機(jī)器人的任務(wù)完成質(zhì)量、負(fù)載平衡以及運(yùn)行距離三個(gè)指標(biāo)設(shè)計(jì)了新的效用函數(shù)，并在現(xiàn)實(shí)場(chǎng)景中模擬了算法的有效性.基于市場(chǎng)機(jī)制的任務(wù)分配方法能夠考慮各機(jī)器人的結(jié)構(gòu)特性，并結(jié)合不同指標(biāo)快速產(chǎn)生機(jī)器人的任務(wù)分配，但是在工作時(shí)各系統(tǒng)獨(dú)立運(yùn)行，面對(duì)突發(fā)任務(wù)狀況無(wú)法及時(shí)響應(yīng)，且任務(wù)大多僅由單個(gè)機(jī)器人負(fù)責(zé)執(zhí)行，機(jī)器人資源無(wú)法得充分利用.

Afrin等考慮了工廠中的應(yīng)急管理問(wèn)題[12]，使用改進(jìn)多目標(biāo)遺傳算法NSGA-II對(duì)時(shí)間、能源和成本屬性進(jìn)行優(yōu)化，為應(yīng)急管理服務(wù)多機(jī)器人系統(tǒng)分配資源，比原始遺傳算法具有更強(qiáng)的尋優(yōu)能力，改進(jìn)可運(yùn)用于現(xiàn)有的多個(gè)多目標(biāo)優(yōu)化算法，取得了至少提升18%性能的表現(xiàn)，但在收斂速度上顯得比較緩慢.

Lee等人[13]提出一種智能工廠中無(wú)人機(jī)在線霧計(jì)算任務(wù)分配框架，考慮通信與計(jì)算等待時(shí)間設(shè)計(jì)了一種在線貪心算法，能夠在線優(yōu)化無(wú)人機(jī)任務(wù)分配，決定使用哪臺(tái)無(wú)機(jī)人進(jìn)行霧計(jì)算，所提出的在線算法能夠以不超過(guò)7.5%的差距實(shí)現(xiàn)接近最優(yōu)的任務(wù)分配.

近年來(lái)，一些學(xué)者借鑒經(jīng)濟(jì)學(xué)中的博弈理論，通過(guò)啟發(fā)式改進(jìn)應(yīng)用于任務(wù)分配中，綜合速度與分配質(zhì)量取得了不錯(cuò)的成果[14-15]，針對(duì)上述智能工廠種任務(wù)資源分配存在的問(wèn)題，提出一種能夠適應(yīng)智能工廠中不同規(guī)模任務(wù)要求，保證分配質(zhì)量同時(shí)實(shí)現(xiàn)快速分配響應(yīng)的多機(jī)器人任務(wù)分配方法是十分必要的.

3 智能工廠中的供應(yīng)問(wèn)題

3.1 場(chǎng)景描述

如圖1所示，在智能工廠的供應(yīng)問(wèn)題場(chǎng)景中，工廠中存在多條生產(chǎn)線以應(yīng)對(duì)不同需求的生產(chǎn)任務(wù)，工廠從客戶處接受需求訂單，原料供應(yīng)由供應(yīng)機(jī)器人承擔(dān)，任務(wù)經(jīng)過(guò)云計(jì)算分解得到數(shù)字化供應(yīng)需求，由工廠內(nèi)生產(chǎn)設(shè)施對(duì)空閑的供應(yīng)機(jī)器人進(jìn)行廣播后得到供應(yīng)任務(wù)初步分配，供應(yīng)機(jī)器人之間通過(guò)通信后進(jìn)一步調(diào)整確定最終的資源運(yùn)送方案，執(zhí)行對(duì)應(yīng)訂單任務(wù)的機(jī)器人從倉(cāng)庫(kù)中將材料取出并補(bǔ)充至對(duì)應(yīng)生產(chǎn)線，供應(yīng)機(jī)器人同一時(shí)間只能執(zhí)行一項(xiàng)供應(yīng)任務(wù)，每個(gè)供應(yīng)任務(wù)需要一個(gè)或多個(gè)供應(yīng)機(jī)器人完成.

圖1 智能工廠動(dòng)態(tài)生產(chǎn)示意圖Fig.1 Illustration of a dynamic production in smart factory

3.2 表示與前提

使用T(t1，…，tn)代表一系列材料供應(yīng)任務(wù)，每個(gè)任務(wù)需要機(jī)器人將要求的生產(chǎn)材料補(bǔ)充至對(duì)應(yīng)的生產(chǎn)線，其中，運(yùn)送任務(wù)由移動(dòng)供應(yīng)機(jī)器人R(r1，…，rm)承擔(dān)，供應(yīng)機(jī)器人之間都是同質(zhì)的，對(duì)于每個(gè)可執(zhí)行任務(wù)，機(jī)器人之間都可以相互交換；生產(chǎn)由位置固定的制造生產(chǎn)線MR(mr1，…，mrl)執(zhí)行，供應(yīng)材料M(m1，…，mk)貯存在倉(cāng)庫(kù)W(s1，…，sk)中.

下標(biāo)m，n分別代表定制化生產(chǎn)任務(wù)與供應(yīng)機(jī)器人的數(shù)量，其中m滿足m?n，機(jī)器人的rm的位置由Prm表示，制造生產(chǎn)線mrl的位置由Pmrl表示，供應(yīng)材料次序與倉(cāng)庫(kù)一一對(duì)應(yīng)，mk的位置由Pmk表示.在確定將供應(yīng)機(jī)器人ri分配給對(duì)應(yīng)任務(wù)tj后，將獲得一個(gè)效用U(ri，tj)用于表示機(jī)器人ri對(duì)與任務(wù)tj的執(zhí)行效果，供應(yīng)任務(wù)T的整體執(zhí)行效用U(如式(1)所示)通過(guò)各任務(wù)的效用加和表示：

U=∑mi=1∑nj=1xijU(ri，tj)

(1)

其中xij∈{0，1}表示供應(yīng)機(jī)器人ri對(duì)于訂單任務(wù)tj的執(zhí)行狀態(tài)；同時(shí)，存在一個(gè)成本函數(shù)cost(ri，tj)用于反應(yīng)供應(yīng)機(jī)器人輸運(yùn)的消耗，這個(gè)成本函數(shù)與運(yùn)行距離成正比，用Cost反應(yīng)執(zhí)行對(duì)應(yīng)任務(wù)的機(jī)器人的消耗總和，如式(2)所示：

Cost=∑mi=1∑nj=1xijcost(ri，tj)

(2)

為完備供應(yīng)機(jī)器人工作環(huán)境，本文在此對(duì)供應(yīng)任務(wù)與執(zhí)行場(chǎng)景做出以下假設(shè)：

1)供應(yīng)場(chǎng)景在一個(gè)大小為length×width的矩形工廠進(jìn)行.

2)當(dāng)前工作場(chǎng)景環(huán)境已知，執(zhí)行供應(yīng)任務(wù)時(shí)機(jī)器人無(wú)須考慮創(chuàng)建環(huán)境地圖.

3)供應(yīng)機(jī)器人初始位于工廠內(nèi)隨機(jī)位置，能夠?qū)崟r(shí)獲取當(dāng)前任務(wù)與自身位置信息.

4)訂單任務(wù)之間不存在順序依存關(guān)系，供應(yīng)機(jī)器人可按各自偏好自由執(zhí)行任務(wù).

3.3 供應(yīng)問(wèn)題模型

由于供應(yīng)機(jī)器人的同質(zhì)性，對(duì)于相同材料的機(jī)器人具有相同的運(yùn)送能力，通過(guò)云端的計(jì)算分解可以得到當(dāng)前各供應(yīng)任務(wù)所需的機(jī)器人數(shù)，結(jié)合各任務(wù)所需的機(jī)器人數(shù)設(shè)計(jì)得到任務(wù)tj的效用表示如式(3)：

U(tj)=Cj-Cj-∑mi=1xij

(3)

其中Cj代表任務(wù)tj需要的供應(yīng)機(jī)器人數(shù)量，xij∈{0，1}表示機(jī)器人ri對(duì)于任務(wù)tj的執(zhí)行狀態(tài).對(duì)于供應(yīng)任務(wù)t，過(guò)多的機(jī)器人分配會(huì)導(dǎo)致資源的浪費(fèi)，過(guò)少的機(jī)器人數(shù)量則會(huì)影響任務(wù)的完成，最大效用加和MAX_UTILITY在滿足每個(gè)任務(wù)t的分配數(shù)量要求后達(dá)到[16]：

MAX_UTILTY=∑nj=1Cj

(4)

供應(yīng)機(jī)器人ri為完成供應(yīng)任務(wù)tj，將生產(chǎn)材料mk運(yùn)輸至生產(chǎn)線mrl處的消耗表示如式(5)所示：

cost(ri，tj)=ωd(Pri，Pmk)+d(Pmk，Pmrl)2(length+width)2+ε

(5)

其中d表示兩個(gè)位置的距離函數(shù)，ε是一個(gè)大于零的常數(shù)，ω代表權(quán)重系數(shù)，供應(yīng)問(wèn)題的總收益是供應(yīng)任務(wù)整體執(zhí)行效用與執(zhí)行對(duì)應(yīng)任務(wù)的機(jī)器人消耗總和的差值，結(jié)合效用與成本比函數(shù)建立供應(yīng)問(wèn)題優(yōu)化模型如式(6)-式(9)所示，以期在最大化效用加和的同時(shí)最小化執(zhí)行對(duì)應(yīng)任務(wù)的機(jī)器人成本：

max∑nj=1U(tj)-∑mi=1∑nj=1xijcost(ri，tj)

(6)

s.t.Cj-∑mi=1xij=0 ?tj∈T

(7)

∑nj=1xij≤1i=1，…，m

(8)

xij∈{0，1}i=1，…，mj=1，…，n

(9)

式(7)要求每個(gè)任務(wù)分配得到其需求的供應(yīng)機(jī)器人數(shù)量，式(8)限定了供應(yīng)機(jī)器人在同一時(shí)間只能執(zhí)行一項(xiàng)任務(wù).在此，定義解決方案π，對(duì)于給定的m個(gè)供應(yīng)機(jī)器人與n個(gè)供應(yīng)任務(wù)，每個(gè)任務(wù)tj需要Cj個(gè)供應(yīng)機(jī)器人完成，方案π代表全體滿足供應(yīng)任務(wù)要求的可能任務(wù)分配解決方案，目的是找到最大化供應(yīng)總收益的方案π*如公式(10-14)所示：

π*=argmaxprofit(π)

(10)

其中：

profit(π)=U(π)-Cost(π)

(11)

U(π)=∑nj=1U(tj)

(12)

Cost(π)=∑mi=1∑nj=1xijcost(ri，tj)

(13)

且滿足：

U(π*)=MAX_UTILITY

(14)

4 基于博弈論的供應(yīng)任務(wù)分配算法

在博弈論中使用的最廣的解是John F. Nash提出的均衡概念[17]，對(duì)于一組行動(dòng)剖面a，每個(gè)參與者i采取行動(dòng)記為ai，存在行動(dòng)剖面a*，對(duì)于每個(gè)參與者i，有：

(a*-i，a*i)i(a*-i，ai)，?ai∈a

(15)

其中a*-i表示除了參與者i外其他所有參與者采取的最優(yōu)行動(dòng)序列，對(duì)于參與者i，當(dāng)沒(méi)有其他行動(dòng)產(chǎn)生優(yōu)于選擇a*i的結(jié)果時(shí)，稱這個(gè)行動(dòng)剖面為滿足納什平衡[18].納什平衡體現(xiàn)了當(dāng)前行動(dòng)組合的穩(wěn)定狀態(tài)，對(duì)于該狀態(tài)每個(gè)參與者擁有對(duì)于對(duì)其他參與者行動(dòng)的正確預(yù)期，并堅(jiān)持自己的行動(dòng)不產(chǎn)生偏移.

基于博弈論的任務(wù)分配算法主要可分為兩步驟，首先根據(jù)機(jī)器人對(duì)可執(zhí)行任務(wù)的偏好，通過(guò)貪婪選擇快速分配滿足任務(wù)需求數(shù)量的機(jī)器人劃分；各機(jī)器人再通過(guò)與工廠內(nèi)其他機(jī)器人交換當(dāng)前執(zhí)行的任務(wù)信息，進(jìn)一步優(yōu)化劃分的結(jié)果，尋找任務(wù)的穩(wěn)定分配，算法整體流程如圖2所示.

圖2 分配算法整體流程Fig.2 Overall flow chart of allocation algorithm

4.1 基于貪心的任務(wù)初始劃分

由上述模型可知，所提出的智能工廠內(nèi)供應(yīng)任務(wù)方案要求在給出滿足任務(wù)需求的機(jī)器人數(shù)量分配同時(shí)，最小化供應(yīng)機(jī)器人的總體損失.在此首先定義執(zhí)行任務(wù)T的供應(yīng)機(jī)器人偏好矩陣Bm×n=(bij)，bij計(jì)算如式(16)所示：

bij=ln(1-cost(ri，tj)cost(ri，tj))

(16)

bij反應(yīng)了供應(yīng)機(jī)器人ri與任務(wù)tj間聯(lián)系的緊密程度[19]，bij越高代表供應(yīng)機(jī)器人ri越傾向于執(zhí)行任務(wù)tj.供應(yīng)機(jī)器人對(duì)當(dāng)前所有可執(zhí)行任務(wù)計(jì)算各自偏好，作為報(bào)價(jià)向任務(wù)點(diǎn)發(fā)送訊息，工作臺(tái)根據(jù)任務(wù)要求的機(jī)器人數(shù)按報(bào)價(jià)從高到低選取執(zhí)行任務(wù)的機(jī)器人，算法偽代碼如下所示：

算法1.基于貪婪策略選擇的任務(wù)劃分

輸入：機(jī)器人R、任務(wù)T坐標(biāo)

輸出：任務(wù)分配集合S

Foreachri∈R、tj∈Tdo

Calculatebij

Endfor

ForeachSj∈Sdo

Sort thebijreceived from each supply robot in descending order for each task

Select the robots in order until |Sj|=Cj

record the highest bias of each robot for executable tasks asmax(bi)

Endfor

IfS1∩S2…∩Sn+1=?

Go to the next stage to find the equilibrium solution

Else

Foreachri∈R、Sj∈Sdo

ifri∈Sjandbij≠max(bi)

removerifromSj

Endfor

Foreachri∈Sn+1、Sj∈Sdo

Selectriwith the highestbijuntil |Sj|=Cj

Endfor

Go to the next stage to find the equilibrium solution

用S={S1，…，Sn+1}表示當(dāng)前任務(wù)分配集合，其中Sj代表任務(wù)tj的供應(yīng)機(jī)器人分配集合，j∈[1，n]；Sn+1代表當(dāng)前為未被分配的機(jī)器人的集合.由于初始劃分沒(méi)有考慮到供應(yīng)機(jī)器人的限制條件，可能會(huì)出現(xiàn)單個(gè)供應(yīng)機(jī)器人被分配到多個(gè)任務(wù)的情況，供應(yīng)機(jī)器人對(duì)此選擇自己偏好最高的任務(wù)執(zhí)行，造成的其他任務(wù)的機(jī)器人缺省通過(guò)貪心算法選擇當(dāng)前未分配任務(wù)的供應(yīng)機(jī)器人的最高報(bào)價(jià)，在滿足所有供應(yīng)任務(wù)機(jī)器人數(shù)量要求后，進(jìn)入下一階段求取任務(wù)劃分的平衡解.

4.2 求取區(qū)域平衡解

經(jīng)過(guò)節(jié)4.1的任務(wù)初步分配后，我們得到一個(gè)不相交的供應(yīng)任務(wù)機(jī)器人劃分集合S={S1，…，Sk+1}，對(duì)于每個(gè)集合Sj，滿足：|Sj|=Cj，j∈[1，n].用集合P={Ps1，…Psk+1}表示供應(yīng)機(jī)器人任務(wù)分配集合的執(zhí)行效用，其中PSj表示集合Sj對(duì)于任務(wù)tj的執(zhí)行的效果，PSUM表示當(dāng)前任務(wù)劃分的總體效果：

Psj=∑ri∈Sjbij

(17)

PSUM=∑nj=1Psj

(18)

求取供應(yīng)任務(wù)分配的平衡解就是一個(gè)尋求穩(wěn)定的任務(wù)劃分區(qū)域的過(guò)程，在該穩(wěn)定狀態(tài)下，沒(méi)有任何一對(duì)完成通信的供應(yīng)機(jī)器人能在其它機(jī)器人保持原有動(dòng)作的狀態(tài)下通過(guò)交換自己的行動(dòng)使得當(dāng)前任務(wù)劃分的總體效果更優(yōu).供應(yīng)機(jī)器人通過(guò)自身廣播與工廠內(nèi)其他機(jī)器人交換執(zhí)行任務(wù)的訊息以及對(duì)于當(dāng)前分配任務(wù)的偏好.在通信過(guò)程中，對(duì)于執(zhí)行供應(yīng)任務(wù)ti的機(jī)器人rp與執(zhí)行供應(yīng)任務(wù)tj的機(jī)器人rq，若存在bpi+bqj

4.3 算法分析

在基于貪心的初始任務(wù)劃分部分，工作臺(tái)按照機(jī)器人對(duì)各任務(wù)的偏好大小對(duì)收到的報(bào)價(jià)進(jìn)行降序排列，最壞的時(shí)間復(fù)雜度為O(n*mlogm)；在尋求區(qū)域平衡解時(shí)，供應(yīng)機(jī)器人群體兩兩完成通信最多需要m(m-1)/2次交換，因此算法的整體時(shí)間復(fù)雜度為O(max{n*mlogm，m2})，能在多項(xiàng)式時(shí)間內(nèi)得到一個(gè)滿足任務(wù)要求的原料供應(yīng)分配解決方案.

5 實(shí)驗(yàn)分析

5.1 實(shí)驗(yàn)設(shè)置

在實(shí)驗(yàn)環(huán)境方面，實(shí)驗(yàn)使用python3.6在win10操作系統(tǒng)上對(duì)所提出算法進(jìn)行編程，處理器使用i5-4210H 2.90Hz，內(nèi)存16GB；在實(shí)驗(yàn)參數(shù)設(shè)置上將模擬實(shí)驗(yàn)的矩形工廠大小設(shè)置為600X400，機(jī)器人與任務(wù)初始位置在工廠范圍內(nèi)隨機(jī)生成，設(shè)置消耗權(quán)重系數(shù)ω為1，供應(yīng)機(jī)器人數(shù)量從集合從區(qū)間[4，100]之間選取，任務(wù)數(shù)量從區(qū)間[2，30]之間選取，并保證任務(wù)數(shù)量小于供應(yīng)機(jī)器人數(shù)1/2且任務(wù)要求的機(jī)器人數(shù)量加和不超過(guò)當(dāng)前可用的供應(yīng)機(jī)器人總數(shù).

5.2 實(shí)驗(yàn)實(shí)例

我們采用一個(gè)實(shí)驗(yàn)實(shí)例來(lái)展示供應(yīng)任務(wù)的分配過(guò)程，選取機(jī)器人數(shù)m=15，供應(yīng)任務(wù)數(shù)n=5，各任務(wù)所需供應(yīng)機(jī)器人數(shù)用元組O1-5=(O1，O2，O3，O4，O5)表示且滿足節(jié)5.1中的實(shí)驗(yàn)設(shè)置，任務(wù)分配總收益由全體執(zhí)行供應(yīng)任務(wù)的機(jī)器人效用之和與機(jī)器人執(zhí)行任務(wù)所產(chǎn)生的消耗的差值得到，計(jì)算如式(3)-式(6)，反映了任務(wù)分配的總體質(zhì)量，作為實(shí)驗(yàn)的評(píng)判標(biāo)準(zhǔn)之一，表1展示了當(dāng)前各可用供應(yīng)機(jī)器人對(duì)任務(wù)的執(zhí)行偏好，與計(jì)算如式(16).機(jī)器人根據(jù)自己的偏好對(duì)項(xiàng)任務(wù)發(fā)布點(diǎn)發(fā)送訊息，并按節(jié)4.1所示算法流程進(jìn)行任務(wù)的初步分配，得到一個(gè)不相交的供應(yīng)任務(wù)機(jī)器人劃分集合；在求取區(qū)域平衡解階段，供應(yīng)機(jī)器人通過(guò)個(gè)體間的通信，尋找能夠提升供應(yīng)任務(wù)總收益的機(jī)器人任務(wù)分配新方案并調(diào)整當(dāng)前分配，如圖3所示，實(shí)驗(yàn)實(shí)例在經(jīng)過(guò)9次迭代后收益達(dá)到最大并得到一個(gè)穩(wěn)定的供應(yīng)機(jī)器人-任務(wù)對(duì)分配.

表1 供應(yīng)機(jī)器人-任務(wù)執(zhí)行偏好Table 1 Task execution preference of supply robot

5.3 收益與任務(wù)數(shù)

在這一部分，實(shí)驗(yàn)探索了供應(yīng)任務(wù)分配面對(duì)新任務(wù)出現(xiàn)時(shí)收益的變化，固定供應(yīng)機(jī)器人數(shù)從10至100，供應(yīng)任務(wù)數(shù)量從5開(kāi)始逐步上升，并在任務(wù)數(shù)量達(dá)到30時(shí)所需機(jī)器人達(dá)到當(dāng)前機(jī)器人總數(shù)，取20次測(cè)試任務(wù)分配收益的平均值，結(jié)果如表2所示，定義的效用函數(shù)與完成參與完成任務(wù)的機(jī)器人數(shù)量掛鉤，收益伴隨任務(wù)的增加而增加；同時(shí)，由于在同一時(shí)間機(jī)器人只能執(zhí)行一個(gè)分配任務(wù)的限制，參與到分配的機(jī)器人因?yàn)槿蝿?wù)的增加而趨近最大值，會(huì)出現(xiàn)能夠最大化某一任務(wù)的機(jī)器人已經(jīng)被占用這一情況，因此效用的增長(zhǎng)趨勢(shì)會(huì)隨著任務(wù)的增加而減緩.

圖3 任務(wù)迭代與最終分配結(jié)果Fig.3 Iteration and final assignment of tasks

表2 不同機(jī)器人數(shù)量下任務(wù)數(shù)與收益Table 2 Number of tasks and profit under different number of robots

由于所提出的智能工廠內(nèi)供應(yīng)任務(wù)分配方案是在滿足各任務(wù)需求的機(jī)器人數(shù)量前提下執(zhí)行，根據(jù)效用計(jì)算式(3)、式(4)以及所建立的供應(yīng)優(yōu)化模型目標(biāo)(6)-式(9)，我們可以將算法性能比較轉(zhuǎn)化為任務(wù)分配方案所產(chǎn)生成本消耗的比較，固定供應(yīng)機(jī)器人數(shù)100，隨著參與到供應(yīng)任務(wù)的機(jī)器人數(shù)量增加，供應(yīng)機(jī)器人個(gè)體間通信得到更優(yōu)解的可能相應(yīng)增長(zhǎng)，如圖4所示，在對(duì)比最小化成本的貪心算法時(shí)，我們提出的算法在任務(wù)數(shù)的增加時(shí)性能上進(jìn)一步占優(yōu)，并在任務(wù)數(shù)等于30時(shí)達(dá)到最高的19.5%.

圖4 算法性能比較Fig.4 Algorithm performance comparison

5.4 與最優(yōu)結(jié)果對(duì)比

在本節(jié)，實(shí)驗(yàn)固定任務(wù)數(shù)，保持供應(yīng)機(jī)器人數(shù)增長(zhǎng)，從成本角度與能得到最優(yōu)結(jié)果的暴力匹配算法進(jìn)行比較，取20次實(shí)驗(yàn)平均值，由于機(jī)器的限制，實(shí)驗(yàn)最多只能得到15個(gè)供應(yīng)機(jī)器人與4個(gè)分配任務(wù)的最優(yōu)結(jié)果.圖5(a)展示了最小化成本算法與最優(yōu)結(jié)果的成本比值，在任務(wù)數(shù)等于2時(shí)最優(yōu)成本比值，從參與任務(wù)的機(jī)器人數(shù)量4時(shí)的82.2%開(kāi)始隨著機(jī)器人數(shù)量的增加逐漸提升，在機(jī)器人數(shù)量達(dá)到15時(shí)取得最高比值94.5%；在任務(wù)數(shù)等于4時(shí)性能下降到85%上下.在圖5(b)中，任務(wù)數(shù)等于2時(shí)，所提出的算法面對(duì)不同機(jī)器人數(shù)量，與最優(yōu)結(jié)果的比值均能夠超過(guò)96%，最高達(dá)到99.3%；在任務(wù)數(shù)4時(shí)也能夠至少達(dá)到最優(yōu)成本結(jié)果的93%.從與最優(yōu)結(jié)果的比值中可以看出，在損耗上所提出的算法能夠找到非常接近最優(yōu)結(jié)果任務(wù)分配解決方案.

圖5 與最優(yōu)算法的成本比較Fig.5 Cost comparison with optimal algorithm

5.5 執(zhí)行時(shí)間

算法面對(duì)不同任務(wù)與供應(yīng)機(jī)器人數(shù)量時(shí)執(zhí)行任務(wù)分配100次的平均時(shí)間如圖6所示，在固定任務(wù)數(shù)時(shí)，任務(wù)分配時(shí)間隨著供應(yīng)機(jī)器人數(shù)量的增加呈現(xiàn)上升趨勢(shì)；固定機(jī)器人數(shù)時(shí)，任務(wù)分配的時(shí)間也會(huì)隨著任務(wù)數(shù)的增加而增加，總體而言，機(jī)器人與任務(wù)數(shù)量的增長(zhǎng)對(duì)分配時(shí)間的影響并不顯著，在面對(duì)給定100個(gè)機(jī)器人與30個(gè)分配任務(wù)時(shí)算法也能在很短的時(shí)間內(nèi)(0.645秒)內(nèi)給出分配結(jié)果.

圖6 不同任務(wù)數(shù)量下算法執(zhí)行時(shí)間Fig.6 Algorithm execution time under different number of tasks

6 結(jié) 論

在本文中，針對(duì)智能工廠下的原料供應(yīng)問(wèn)題，我們考慮任務(wù)需求與運(yùn)行距離等因素，設(shè)計(jì)了效用函數(shù)U與成本函數(shù)cost用于反應(yīng)供應(yīng)任務(wù)的執(zhí)行效果與產(chǎn)生的消耗，根據(jù)設(shè)計(jì)的效用與成本函數(shù)，構(gòu)建了一個(gè)最大化任務(wù)收益的供應(yīng)優(yōu)化模型，提出一種基于多機(jī)器人協(xié)作的供應(yīng)任務(wù)解決方案，通過(guò)算法分析與實(shí)驗(yàn)結(jié)果表明，所提出算法能夠處理不同供應(yīng)任務(wù)機(jī)器人規(guī)模，并在保證任務(wù)完成質(zhì)量的同時(shí)在短時(shí)間內(nèi)迅速實(shí)現(xiàn)任務(wù)分配，對(duì)比最小化成本的貪心算法具有較大優(yōu)勢(shì).今后我們將考慮異構(gòu)供應(yīng)機(jī)器人的任務(wù)分配用以處理更加復(fù)雜的供應(yīng)分配問(wèn)題；未來(lái)還將考慮故障恢復(fù)進(jìn)一步增強(qiáng)分配的魯棒性.