[發(fā)明專(zhuān)利]用于多機(jī)器人的訂單派送方法及系統(tǒng)

有效

• 申請(qǐng)?zhí)枺?/td>: 202010350781.2
• 申請(qǐng)日: 2020-04-28
• 公開(kāi)（公告）號(hào): CN111539574B
• 公開(kāi)（公告）日: 2021-04-09
• 發(fā)明（設(shè)計(jì)）人: 霍向;吳新開(kāi);宋濤
• 申請(qǐng)（專(zhuān)利權(quán)）人: 北京洛必德科技有限公司
• 主分類(lèi)號(hào): G06Q10/04
• 分類(lèi)號(hào): G06Q10/04
• 代理公司: 北京知匯林知識(shí)產(chǎn)權(quán)代理事務(wù)所(普通合伙) 11794
• 代理人: 董濤

1.一種用于多機(jī)器人的訂單派送方法，其特征在于，包括：

S1、訂單派送服務(wù)器接收用戶(hù)通過(guò)終端設(shè)備發(fā)送的訂單請(qǐng)求消息，所述訂單請(qǐng)求消息包括用戶(hù)終端標(biāo)識(shí)、下單時(shí)間、用戶(hù)位置和訂單物品信息；

S2、訂單派送服務(wù)器根據(jù)用戶(hù)發(fā)送的訂單請(qǐng)求消息以及機(jī)器人的位置信息，利用訂單排序算法對(duì)用戶(hù)訂單的重要性進(jìn)行排序；

S3、訂單派送服務(wù)器根據(jù)用戶(hù)訂單的重要性排序?yàn)橛脩?hù)訂單匹配訂單派送機(jī)器人；

S4、訂單派送服務(wù)器采用改進(jìn)型全局路徑規(guī)劃算法為訂單派送機(jī)器人規(guī)劃出與其所匹配的訂單相對(duì)應(yīng)的訂單派送全局路徑；

S5、訂單派送服務(wù)器對(duì)規(guī)劃出的訂單派送全局路徑進(jìn)行局部防撞優(yōu)化，得到訂單派送優(yōu)化路徑；

S6、訂單派送服務(wù)器將訂單派送優(yōu)化路徑發(fā)送給相應(yīng)的機(jī)器人；

S7、機(jī)器人根據(jù)接收的訂單派送優(yōu)化路徑對(duì)相應(yīng)訂單執(zhí)行派送任務(wù)；

S2中所述的利用訂單排序算法對(duì)用戶(hù)訂單的重要性進(jìn)行排序，具體為：

計(jì)算用戶(hù)訂單的重要性評(píng)價(jià)值Y_i，計(jì)算公式為：

式中，i為用戶(hù)訂單請(qǐng)求標(biāo)識(shí)，ω_i為訂單請(qǐng)求i的訂單物品重要性評(píng)價(jià)值，和為預(yù)先設(shè)置的訂單時(shí)間評(píng)價(jià)參數(shù)，t為當(dāng)前時(shí)刻，t_i為訂單請(qǐng)求i的下單時(shí)間，和為訂單距離評(píng)價(jià)參數(shù)，d_i為訂單請(qǐng)求i的用戶(hù)位置與機(jī)器人初始時(shí)刻停留位置的距離，v為設(shè)置的機(jī)器人的移動(dòng)速度；

按照計(jì)算出的用戶(hù)訂單的重要性評(píng)價(jià)值的大小對(duì)用戶(hù)訂單的重要性進(jìn)行排序；

S4中所述的改進(jìn)型全局路徑規(guī)劃算法，具體為：

S401、建立機(jī)器人運(yùn)行環(huán)境的柵格地圖，柵格的邊長(zhǎng)為機(jī)器人最大外廓長(zhǎng)度加上設(shè)置的避障安全距離，柵格的狀態(tài)為有障礙物狀態(tài)或者可通行狀態(tài)；

S402、將機(jī)器人初始時(shí)刻停留的位置所屬的柵格設(shè)置為第一個(gè)父節(jié)點(diǎn)，將用戶(hù)訂單請(qǐng)求信息中的用戶(hù)位置所屬的柵格設(shè)置為路徑目標(biāo)位置；

S403、判定父節(jié)點(diǎn)是否為路徑目標(biāo)位置，即父節(jié)點(diǎn)所在的柵格位置是否是用戶(hù)訂單請(qǐng)求信息中的用戶(hù)位置；

S404、若父節(jié)點(diǎn)是路徑目標(biāo)位置，則訂單派送服務(wù)器保留父節(jié)點(diǎn)位置，從而獲得了從機(jī)器人初始時(shí)刻停留的位置到用戶(hù)訂單請(qǐng)求信息中的用戶(hù)位置的全局路徑；

S405、若父節(jié)點(diǎn)不是路徑目標(biāo)位置，則以父節(jié)點(diǎn)為中心，將周?chē)鸂顟B(tài)為可通行狀態(tài)的柵格設(shè)置為待選子節(jié)點(diǎn)；

S406、作父節(jié)點(diǎn)所在柵格中心與路徑目標(biāo)位置中心的連線(xiàn)，以該連線(xiàn)為正向方向線(xiàn)，再過(guò)父節(jié)點(diǎn)所在柵格中心作正方向線(xiàn)的垂直線(xiàn)，以該連線(xiàn)為縱向方向線(xiàn)；

S407、將正向方向線(xiàn)與縱向方向線(xiàn)穿過(guò)的待選子節(jié)點(diǎn)設(shè)置為子節(jié)點(diǎn)，且不將其他待選子節(jié)點(diǎn)設(shè)置為子節(jié)點(diǎn)；如果正向方向線(xiàn)與縱向方向線(xiàn)不穿過(guò)待選子節(jié)點(diǎn)，則將所有待選子節(jié)點(diǎn)設(shè)置為子節(jié)點(diǎn)；

S408、計(jì)算各個(gè)子節(jié)點(diǎn)的評(píng)價(jià)函數(shù)值，選取評(píng)價(jià)函數(shù)值最小的子節(jié)點(diǎn)作為下一個(gè)父節(jié)點(diǎn)，如果有多個(gè)子節(jié)點(diǎn)的評(píng)價(jià)函數(shù)值最小，則隨機(jī)選擇其中一個(gè)子節(jié)點(diǎn)作為下一個(gè)父節(jié)點(diǎn)；

S409、跳轉(zhuǎn)執(zhí)行S403；

S408中所述的計(jì)算各個(gè)子節(jié)點(diǎn)的評(píng)價(jià)函數(shù)值，具體為：

為所有子節(jié)點(diǎn)設(shè)定標(biāo)號(hào)(1，...m，...，M)，M為子節(jié)點(diǎn)的總個(gè)數(shù)，按如下公式依次計(jì)算各個(gè)子節(jié)點(diǎn)的評(píng)價(jià)函數(shù)值：

式中，Z_m為子節(jié)點(diǎn)m的評(píng)價(jià)函數(shù)值，為父節(jié)點(diǎn)到子節(jié)點(diǎn)m的路徑距離，為子節(jié)點(diǎn)m所在柵格中心到路徑目標(biāo)位置的直線(xiàn)距離，為子節(jié)點(diǎn)m的安全評(píng)價(jià)值，每個(gè)可通行狀態(tài)的柵格的安全評(píng)價(jià)值預(yù)先設(shè)置；

S5中所述的訂單派送服務(wù)器對(duì)規(guī)劃出的訂單派送全局路徑進(jìn)行局部防撞優(yōu)化，得到訂單派送優(yōu)化路徑，具體為：

S501、根據(jù)訂單派送全局路徑內(nèi)所有的柵格位置、當(dāng)前時(shí)間、機(jī)器人在初始時(shí)刻停留的位置信息、裝載訂單物品的時(shí)間和機(jī)器人的移動(dòng)速度信息，計(jì)算出到達(dá)訂單派送全局路徑內(nèi)的柵格位置的到達(dá)時(shí)間；

S502、判定是否存不同的機(jī)器人將在同一時(shí)間到達(dá)同一個(gè)柵格位置的情況；如果不存在，則執(zhí)行S503；如果存在，則執(zhí)行S504；

S503、將規(guī)劃出的訂單派送全局路徑作為訂單派送優(yōu)化路徑；

S504、確定同一個(gè)到達(dá)時(shí)間，機(jī)器人訂單派送全局路徑的柵格有相同的情況下的相同柵格，為這些柵格建立沖突柵格集合{c₁，...，c_a，...c_A}，A是相同柵格的個(gè)數(shù)；以此選擇出沖突柵格集合中的柵格；選擇出一個(gè)柵格后，設(shè)定該柵格為待優(yōu)化柵格，然后再確定在同一個(gè)到達(dá)時(shí)間，都在該柵格的機(jī)器人的編號(hào)，為這些機(jī)器人編號(hào)建立沖突機(jī)器人集合{e₁，...，e_b，...，e_B}，B是沖突機(jī)器人的個(gè)數(shù)；

S505、統(tǒng)計(jì)出沖突機(jī)器人集合{e₁，...，e_b，...，e_B}中機(jī)器人的訂單派送全局路徑長(zhǎng)度，選擇其中與最短和次短的訂單派送全局路徑長(zhǎng)度相對(duì)應(yīng)的兩個(gè)機(jī)器人；當(dāng)有兩個(gè)以上的最短和次短的全局路徑長(zhǎng)度的機(jī)器人后，隨機(jī)選擇其中兩個(gè)機(jī)器人；將這兩個(gè)機(jī)器人設(shè)定為待優(yōu)化機(jī)器人，待優(yōu)化機(jī)器人中全局路徑長(zhǎng)度長(zhǎng)的機(jī)器人為高優(yōu)先級(jí)待優(yōu)化機(jī)器人，待優(yōu)化機(jī)器人中全局路徑長(zhǎng)度短的機(jī)器人為低優(yōu)先級(jí)待優(yōu)化機(jī)器人，當(dāng)待優(yōu)化機(jī)器人的全局路徑長(zhǎng)度相同時(shí)，隨機(jī)選擇一個(gè)機(jī)器人為高優(yōu)先級(jí)待優(yōu)化機(jī)器人，另一個(gè)機(jī)器人為低優(yōu)先級(jí)待優(yōu)化機(jī)器人；

S506、重新為低優(yōu)先級(jí)待優(yōu)化機(jī)器人規(guī)劃派送訂單以及訂單派送全局路徑，此時(shí)將會(huì)將機(jī)器人運(yùn)行環(huán)境地圖中的待優(yōu)化柵格設(shè)置為有障礙物狀態(tài)的柵格，利用改進(jìn)型全局路徑規(guī)劃算法為低優(yōu)先級(jí)待優(yōu)化機(jī)器人規(guī)劃派送訂單以及訂單派送全局路徑；如果將機(jī)器人運(yùn)行環(huán)境地圖中的待優(yōu)化柵格設(shè)置為有障礙物狀態(tài)的柵格后，機(jī)器人初始時(shí)刻停留的位置到路徑目標(biāo)位置不再能夠規(guī)劃出訂單派送全局路徑，則仍然保留之前規(guī)劃的訂單派送全局路徑，并在該機(jī)器人在初始時(shí)刻停留的位置或者裝載訂單物品的位置增加一個(gè)停留時(shí)間，該停留時(shí)間將根據(jù)之前規(guī)劃的全局路徑長(zhǎng)度以及訂單請(qǐng)求信息確定；

S507、重新為低優(yōu)先級(jí)待優(yōu)化機(jī)器人規(guī)劃派送訂單以及訂單派送全局路徑或者重新為低優(yōu)先級(jí)待優(yōu)化機(jī)器人在初始時(shí)刻停留的位置或者裝載訂單物品的位置增加一個(gè)停留時(shí)間后，執(zhí)行S501。

2.一種用于多機(jī)器人的訂單派送系統(tǒng)，其特征在于，包括：終端設(shè)備、訂單派送服務(wù)器和機(jī)器人，所述終端設(shè)備、所述機(jī)器人的數(shù)量為多個(gè)，終端設(shè)備與訂單派送服務(wù)器之間、訂單派送服務(wù)器與機(jī)器人之間、機(jī)器人與終端設(shè)備之間建立網(wǎng)絡(luò)連接，所述系統(tǒng)用于執(zhí)行權(quán)利要求1所述的訂單派送方法。