日前，2023第九屆華為軟件精英挑戰(zhàn)賽-“普朗克計(jì)劃”全球總決賽及頒獎(jiǎng)典禮圓滿落幕。大賽吸引了來(lái)自全球645所高校、3887支隊(duì)伍、23078名大學(xué)生報(bào)名參賽，歷時(shí)一個(gè)多月的激烈角逐，經(jīng)過(guò)八大賽區(qū)區(qū)域初賽、區(qū)域復(fù)賽、全球總決賽等環(huán)節(jié)的層層考驗(yàn)。最終，9支優(yōu)秀隊(duì)伍憑借優(yōu)異表現(xiàn)分享了66萬(wàn)元總獎(jiǎng)金池。其中，武長(zhǎng)賽區(qū)來(lái)自中南大學(xué)的“比賽周期怎么這么長(zhǎng)”隊(duì)獲得全球總決賽亞軍。作為軟挑老兵，來(lái)自中南大學(xué)的優(yōu)秀選手唐京撰文分享其賽隊(duì)參賽體驗(yàn)，包括參賽初衷、解題思路及方案、比賽收獲等。

圖左二為唐京

比賽初衷

作為軟挑老兵，去年參賽隊(duì)伍“AAAAAA”的一員我和另外一位隊(duì)友一起獲得了2022年軟件精英挑戰(zhàn)賽決賽旅游獎(jiǎng)。在旅游的同時(shí)也留下了不小的遺憾，于是今年決定再戰(zhàn)一回。

賽題介紹

今年賽題抽象自華為云智能機(jī)器人的真實(shí)業(yè)務(wù)，模擬了多機(jī)器人的運(yùn)行環(huán)境以及真實(shí)機(jī)器人的狀態(tài)信息，由參賽者通過(guò)代碼操控機(jī)器人完成特定任務(wù)以實(shí)現(xiàn)收益最大化。大賽賽題還原物理引擎、激光雷達(dá)、真實(shí)操控接口等機(jī)器人業(yè)務(wù)真實(shí)場(chǎng)景，引入業(yè)界熱門算法難題，包括最優(yōu)調(diào)度問(wèn)題、多機(jī)器人路徑協(xié)調(diào)規(guī)劃問(wèn)題、動(dòng)態(tài)避障算法等，在初賽、復(fù)賽、決賽進(jìn)行有層次的難度遞進(jìn)。

今年的軟挑題目比以往的更加復(fù)雜，除了對(duì)算法具有較高的要求以外，還需要極為復(fù)雜的細(xì)節(jié)實(shí)現(xiàn)。

方案

我們的方案由調(diào)度、移動(dòng)、防守、攻擊等策略組成。

·調(diào)度

版本八

首先定義7號(hào)生產(chǎn)線由一系列的工作臺(tái)組成，這些工作臺(tái)能夠完整的生產(chǎn)出7號(hào)物品并賣出。

決賽正式賽前夜，通過(guò)總結(jié)之前若干個(gè)版本的調(diào)度的不足，我們認(rèn)為當(dāng)?shù)貓D中存在7號(hào)生產(chǎn)線時(shí)，調(diào)度策略應(yīng)盡可能達(dá)到以下要求：

1.7號(hào)生產(chǎn)線上，物品4,5,6的生產(chǎn)應(yīng)該盡可能均衡。

2.順路原則，要賣出一個(gè)工作臺(tái)上的物品，最好帶一個(gè)物品過(guò)來(lái)放入它的材料格再賣出這個(gè)物品。

3.避免擁擠，不要讓太多的機(jī)器人前往相同的工作臺(tái)。

4.處于7號(hào)生產(chǎn)線上的1,2,3,4,5,6物品盡量不要賣給9號(hào)工作臺(tái)。

5.當(dāng)一些工作臺(tái)上已經(jīng)集齊了一些原材料，優(yōu)先考慮塞滿這些工作臺(tái)的原材料格。

6.機(jī)器人的每單位移動(dòng)獲得的利潤(rùn)越大越好。

于是有了我們的核心調(diào)度代碼，以利潤(rùn)除以距離為基礎(chǔ)分?jǐn)?shù)(為了防止距離過(guò)近時(shí)該式子的值過(guò)大，給距離加上了一個(gè)常數(shù)10)，根據(jù)上面總結(jié)的規(guī)則來(lái)調(diào)整分?jǐn)?shù)的權(quán)重，機(jī)器人會(huì)選擇分?jǐn)?shù)最大的任務(wù)去執(zhí)行：

工作臺(tái)拆點(diǎn)

為了使機(jī)器人在工作臺(tái)處的移動(dòng)更加精細(xì)，我們對(duì)工作臺(tái)做了特殊處理。首先，在以工作臺(tái)為中心，0.4為半徑的圓內(nèi)，在八個(gè)方向上每隔0.05米增加一個(gè)采樣點(diǎn)。然后將工作臺(tái) P 附近的采樣點(diǎn)按如下規(guī)則劃分成五個(gè)集合：設(shè)采樣點(diǎn)為 Q，向量PQ的坐標(biāo)為 (x, y)。

在購(gòu)買物品時(shí)，我們會(huì)將機(jī)器人導(dǎo)航到我們需要的區(qū)域再進(jìn)行購(gòu)買，這個(gè)方法能夠解決復(fù)賽練習(xí)賽圖3在瓶頸處工作臺(tái)上方購(gòu)買后繞路的問(wèn)題，當(dāng)然，對(duì)于那張圖，需要經(jīng)過(guò)計(jì)算后額外采樣一些更遠(yuǎn)的點(diǎn)來(lái)達(dá)到這個(gè)目的。

地圖點(diǎn)采樣

根據(jù)機(jī)器人半徑的設(shè)定，可以發(fā)現(xiàn)#..#這種格子能夠讓一個(gè)半徑0.45的機(jī)器人恰好從中間兩個(gè)格子的分界線通過(guò)，而#...#這種格子能夠讓一個(gè)半徑0.53的機(jī)器人恰好從中間格子的中間通過(guò)，因此我們將棋盤劃為成201*201的形式，所有線段的交點(diǎn)為棋盤采樣點(diǎn)：

由于我們機(jī)器人導(dǎo)航用到了A*算法，而201*201的劃分會(huì)導(dǎo)致采樣點(diǎn)高達(dá)原棋盤的四倍，而實(shí)際上并不需要用到這么多采樣點(diǎn)，我們?cè)?01*201的棋盤上進(jìn)行了隔點(diǎn)采樣，并針對(duì)一些特殊情況做出了處理，使得采樣點(diǎn)數(shù)達(dá)到至多一萬(wàn)，平均只有幾千的級(jí)別：

特殊情況特征：

7*7或5*5的矩形(也可以是下述情況的旋轉(zhuǎn))，CD至少有一個(gè)為.，Z可以替換為任意字符，格子中心替換為X。

·移動(dòng)

我們初賽采用簡(jiǎn)單旋轉(zhuǎn)加移動(dòng)。初賽正式賽結(jié)束后發(fā)現(xiàn)這樣碰撞損失過(guò)高，又在復(fù)賽開(kāi)始前實(shí)現(xiàn)了DWA算法，達(dá)到了初賽地圖上幾乎無(wú)碰撞的效果。復(fù)賽開(kāi)始后發(fā)現(xiàn)DWA算法失效了，在QQ群窺探到有大佬使用ORCA算法達(dá)到非常好的效果，于是我們?cè)趶?fù)賽練習(xí)賽花了很多天實(shí)現(xiàn)了ORCA算法，并調(diào)整了一些參數(shù)達(dá)到了不錯(cuò)的效果。

我們的路徑規(guī)劃算法采用最短路預(yù)處理+局部導(dǎo)航機(jī)制+Astar 算法相結(jié)合的方式，每一幀都用 Astar 算法計(jì)算出每個(gè)機(jī)器人到目標(biāo)點(diǎn)的路徑，并找到最后一個(gè)可以不經(jīng)障礙直線到達(dá)的路徑點(diǎn)移動(dòng)過(guò)去。

在復(fù)賽時(shí)，由于沒(méi)有可移動(dòng)障礙(即敵方機(jī)器人)的存在，我們僅使用最短路算法事先預(yù)處理好路徑。而決賽加入了移動(dòng)障礙后，我們加入了 Astar 算法。

在 Astar 算法中，我們考慮了敵方機(jī)器人和障礙的距離懲罰，距離越大，懲罰越大，這會(huì)使我們的機(jī)器人稍微繞一下路，但是盡可能地減少了與敵方機(jī)器人和障礙的碰撞，也使得我們的機(jī)器人在被敵方機(jī)器人追逐時(shí)顯得十分靈活。

在 Astar 搜索過(guò)程中，我們減少了敵人的半徑，這使得我們?cè)谝恍O端情況也能避開(kāi)敵人，機(jī)器人看起來(lái)會(huì)非常靈活。

局部導(dǎo)航用來(lái)為機(jī)器人規(guī)劃一個(gè)局部目標(biāo)，機(jī)器人會(huì)認(rèn)為從當(dāng)前位置到局部目標(biāo)一定是可達(dá)的(不會(huì)與任何物體碰撞)，ORCA算法會(huì)驅(qū)動(dòng)機(jī)器人向局部目標(biāo)進(jìn)行移動(dòng)。局部導(dǎo)航帶有一定的避讓策略，當(dāng)A*搜索不到路徑時(shí)，會(huì)啟用局部導(dǎo)航作為保底機(jī)制。

·進(jìn)攻

我們分為兩種進(jìn)攻型機(jī)器人，一種進(jìn)攻型機(jī)器人直接追著敵人跑，在運(yùn)氣好的情況下能達(dá)到卡死敵方運(yùn)輸型機(jī)器人的效果。

另一種是防守型，防守型機(jī)器人會(huì)占用敵人7號(hào)生產(chǎn)線上的同類工作臺(tái)，從而達(dá)到阻斷敵人的7號(hào)生產(chǎn)線的效果，防守型機(jī)器人在一些狹窄的工作臺(tái)附近效果非常好(這部分實(shí)現(xiàn)得不夠好，導(dǎo)致在對(duì)戰(zhàn)時(shí)浪費(fèi)了兩個(gè)藍(lán)色機(jī)器人但沒(méi)有達(dá)到阻斷敵方7號(hào)生產(chǎn)線的效果)。

·防守

在路徑上避開(kāi)敵人的工作由A*算法完成，但會(huì)存在一些敵人站在我方的工作臺(tái)不動(dòng)，且難以撞開(kāi)。因此在嘗試到一些工作臺(tái)無(wú)法到達(dá)時(shí)，我們會(huì)將這個(gè)工作臺(tái)禁用一段時(shí)間，當(dāng)禁用結(jié)束后再嘗試仍然無(wú)法到達(dá)工作臺(tái)，我們會(huì)將工作臺(tái)的禁用時(shí)間翻倍... ...

我們將工作臺(tái)分為了三類，用一個(gè)變量rushAble表示。rushAble=0表示工作臺(tái)位于墻角，當(dāng)敵人處于這樣，我方機(jī)器人難以將器撞開(kāi)。rushAble=1表示能夠?qū)橙俗查_(kāi)，但進(jìn)入這樣的工作臺(tái)有被敵人卡死的風(fēng)險(xiǎn)。rushAble=2表示這樣的工作臺(tái)附近是空曠的，可以被狀態(tài)，并且不存在被卡死的風(fēng)險(xiǎn)。在進(jìn)入rushAble<= 1的工作臺(tái)，如果周圍有敵人能使得我方機(jī)器人卡死，則機(jī)器人會(huì)被禁用購(gòu)買任務(wù)，防止機(jī)器人購(gòu)買了物品但賣不出去(如果買了一個(gè)物品7沒(méi)有賣出去，很可能成為PK賽中決勝的關(guān)鍵)。

有時(shí)候機(jī)器人難免會(huì)被敵人卡住，我們?cè)O(shè)置了卡死判定機(jī)制，并且采用低速旋轉(zhuǎn)+全速移動(dòng)讓機(jī)器人脫離被卡死的狀態(tài)。

總結(jié)

此次軟挑，我們隊(duì)并非一帆風(fēng)順，復(fù)賽險(xiǎn)遭淘汰。在復(fù)賽的前一天的時(shí)候，我們?nèi)齻€(gè)才第一次真正的開(kāi)始討論，在此之前各自都有各自的想法以及解法(此處必須要感謝我們武長(zhǎng)賽區(qū)工作人員，中午一點(diǎn)給我們聯(lián)系自習(xí)室，晚上12點(diǎn)還在熬夜關(guān)注我們)。終于，在距離復(fù)賽只有9個(gè)小時(shí)的時(shí)候，我們找到了一個(gè)新的解法并且?guī)椭覀儠x級(jí)了決賽。決賽前一晚，我們?cè)跍y(cè)試2p和4p地圖以及一些自制地圖時(shí)，突然發(fā)現(xiàn)了代碼里存在一萬(wàn)個(gè)bug(當(dāng)時(shí)待解決問(wèn)題的列表列了十項(xiàng)有余，還有幾個(gè)要新加的策略)，于是我又拉著我的兩個(gè)隊(duì)友開(kāi)肝，其實(shí)當(dāng)時(shí)已經(jīng)心態(tài)有點(diǎn)不穩(wěn)了，好在隊(duì)友們互相都沒(méi)給壓力，互相沒(méi)有怪罪(雖然嘴上說(shuō)著沒(méi)拿獎(jiǎng)有這個(gè)過(guò)程也很值得，但是其實(shí)心里想的都是必須拿獎(jiǎng))。于是我們開(kāi)啟了第n個(gè)通宵。盡管第二天的正式賽我們策略還是出現(xiàn)了失誤，但好在付出有了回報(bào)。 這次軟挑，可以說(shuō)有笑有淚，有成長(zhǎng)有沉淀，有認(rèn)識(shí)志同道合的新朋友，更有舊友重逢。這次與以往不一樣，我們?nèi)齻€(gè)真正感受到了團(tuán)隊(duì)三個(gè)人的力量，少了任何人都無(wú)法拿到亞軍。非常感謝武長(zhǎng)賽區(qū)工作組對(duì)我們的關(guān)心和鼓勵(lì)，更要感謝張?jiān)埨蠋煹荣愵}組專家對(duì)我們時(shí)時(shí)刻刻每件事情都有回應(yīng)，當(dāng)然最感謝的還是我們?nèi)齻€(gè)一起熬過(guò)的每一個(gè)夜，和多少次凌晨因?yàn)橄氲搅诵孪敕ㄅ榔饋?lái)的自己。希望未來(lái)的旅途能再與軟挑相遇!

（免責(zé)聲明：本網(wǎng)站內(nèi)容主要來(lái)自原創(chuàng)、合作伙伴供稿和第三方自媒體作者投稿，凡在本網(wǎng)站出現(xiàn)的信息，均僅供參考。本網(wǎng)站將盡力確保所提供信息的準(zhǔn)確性及可靠性，但不保證有關(guān)資料的準(zhǔn)確性及可靠性，讀者在使用前請(qǐng)進(jìn)一步核實(shí)，并對(duì)任何自主決定的行為負(fù)責(zé)。本網(wǎng)站對(duì)有關(guān)資料所引致的錯(cuò)誤、不確或遺漏，概不負(fù)任何法律責(zé)任。
任何單位或個(gè)人認(rèn)為本網(wǎng)站中的網(wǎng)頁(yè)或鏈接內(nèi)容可能涉嫌侵犯其知識(shí)產(chǎn)權(quán)或存在不實(shí)內(nèi)容時(shí)，應(yīng)及時(shí)向本網(wǎng)站提出書(shū)面權(quán)利通知或不實(shí)情況說(shuō)明，并提供身份證明、權(quán)屬證明及詳細(xì)侵權(quán)或不實(shí)情況證明。本網(wǎng)站在收到上述法律文件后，將會(huì)依法盡快聯(lián)系相關(guān)文章源頭核實(shí)，溝通刪除相關(guān)內(nèi)容或斷開(kāi)相關(guān)鏈接。 ）