日前，2023第九屆華為軟件精英挑戰(zhàn)賽-“普朗克計劃”全球總決賽及頒獎典禮圓滿落幕。大賽吸引了來自全球645所高校、3887支隊伍、23078名大學(xué)生報名參賽，歷時一個多月的激烈角逐，經(jīng)過八大賽區(qū)區(qū)域初賽、區(qū)域復(fù)賽、全球總決賽等環(huán)節(jié)的層層考驗。最終，9支優(yōu)秀隊伍憑借優(yōu)異表現(xiàn)分享了66萬元總獎金池。其中，武長賽區(qū)來自中南大學(xué)的“比賽周期怎么這么長”隊獲得全球總決賽亞軍。作為軟挑老兵，來自中南大學(xué)的優(yōu)秀選手唐京撰文分享其賽隊參賽體驗，包括參賽初衷、解題思路及方案、比賽收獲等。
圖左二為唐京
比賽初衷
作為軟挑老兵，去年參賽隊伍“AAAAAA”的一員我和另外一位隊友一起獲得了2022年軟件精英挑戰(zhàn)賽決賽旅游獎。在旅游的同時也留下了不小的遺憾，于是今年決定再戰(zhàn)一回。
賽題介紹
今年賽題抽象自華為云智能機器人的真實業(yè)務(wù)，模擬了多機器人的運行環(huán)境以及真實機器人的狀態(tài)信息，由參賽者通過代碼操控機器人完成特定任務(wù)以實現(xiàn)收益最大化。大賽賽題還原物理引擎、激光雷達、真實操控接口等機器人業(yè)務(wù)真實場景，引入業(yè)界熱門算法難題，包括最優(yōu)調(diào)度問題、多機器人路徑協(xié)調(diào)規(guī)劃問題、動態(tài)避障算法等，在初賽、復(fù)賽、決賽進行有層次的難度遞進。
今年的軟挑題目比以往的更加復(fù)雜，除了對算法具有較高的要求以外，還需要極為復(fù)雜的細節(jié)實現(xiàn)。
方案
我們的方案由調(diào)度、移動、防守、攻擊等策略組成。
·調(diào)度
版本八
首先定義7號生產(chǎn)線由一系列的工作臺組成，這些工作臺能夠完整的生產(chǎn)出7號物品并賣出。
決賽正式賽前夜，通過總結(jié)之前若干個版本的調(diào)度的不足，我們認為當(dāng)?shù)貓D中存在7號生產(chǎn)線時，調(diào)度策略應(yīng)盡可能達到以下要求：
1.7號生產(chǎn)線上，物品4,5,6的生產(chǎn)應(yīng)該盡可能均衡。
2.順路原則，要賣出一個工作臺上的物品，最好帶一個物品過來放入它的材料格再賣出這個物品。
3.避免擁擠，不要讓太多的機器人前往相同的工作臺。
4.處于7號生產(chǎn)線上的1,2,3,4,5,6物品盡量不要賣給9號工作臺。
5.當(dāng)一些工作臺上已經(jīng)集齊了一些原材料，優(yōu)先考慮塞滿這些工作臺的原材料格。
6.機器人的每單位移動獲得的利潤越大越好。
于是有了我們的核心調(diào)度代碼，以利潤除以距離為基礎(chǔ)分數(shù)(為了防止距離過近時該式子的值過大，給距離加上了一個常數(shù)10)，根據(jù)上面總結(jié)的規(guī)則來調(diào)整分數(shù)的權(quán)重，機器人會選擇分數(shù)最大的任務(wù)去執(zhí)行：
工作臺拆點
為了使機器人在工作臺處的移動更加精細，我們對工作臺做了特殊處理。首先，在以工作臺為中心，0.4為半徑的圓內(nèi)，在八個方向上每隔0.05米增加一個采樣點。然后將工作臺 P 附近的采樣點按如下規(guī)則劃分成五個集合：設(shè)采樣點為 Q，向量PQ的坐標為 (x, y)。
在購買物品時，我們會將機器人導(dǎo)航到我們需要的區(qū)域再進行購買，這個方法能夠解決復(fù)賽練習(xí)賽圖3在瓶頸處工作臺上方購買后繞路的問題，當(dāng)然，對于那張圖，需要經(jīng)過計算后額外采樣一些更遠的點來達到這個目的。
地圖點采樣
根據(jù)機器人半徑的設(shè)定，可以發(fā)現(xiàn)#..#這種格子能夠讓一個半徑0.45的機器人恰好從中間兩個格子的分界線通過，而#...#這種格子能夠讓一個半徑0.53的機器人恰好從中間格子的中間通過，因此我們將棋盤劃為成201*201的形式，所有線段的交點為棋盤采樣點：
由于我們機器人導(dǎo)航用到了A*算法，而201*201的劃分會導(dǎo)致采樣點高達原棋盤的四倍，而實際上并不需要用到這么多采樣點，我們在201*201的棋盤上進行了隔點采樣，并針對一些特殊情況做出了處理，使得采樣點數(shù)達到至多一萬，平均只有幾千的級別：
特殊情況特征：
7*7或5*5的矩形(也可以是下述情況的旋轉(zhuǎn))，CD至少有一個為.，Z可以替換為任意字符，格子中心替換為X。
·移動
我們初賽采用簡單旋轉(zhuǎn)加移動。初賽正式賽結(jié)束后發(fā)現(xiàn)這樣碰撞損失過高，又在復(fù)賽開始前實現(xiàn)了DWA算法，達到了初賽地圖上幾乎無碰撞的效果。復(fù)賽開始后發(fā)現(xiàn)DWA算法失效了，在QQ群窺探到有大佬使用ORCA算法達到非常好的效果，于是我們在復(fù)賽練習(xí)賽花了很多天實現(xiàn)了ORCA算法，并調(diào)整了一些參數(shù)達到了不錯的效果。
我們的路徑規(guī)劃算法采用最短路預(yù)處理+局部導(dǎo)航機制+Astar 算法相結(jié)合的方式，每一幀都用 Astar 算法計算出每個機器人到目標點的路徑，并找到最后一個可以不經(jīng)障礙直線到達的路徑點移動過去。
在復(fù)賽時，由于沒有可移動障礙(即敵方機器人)的存在，我們僅使用最短路算法事先預(yù)處理好路徑。而決賽加入了移動障礙后，我們加入了 Astar 算法。
在 Astar 算法中，我們考慮了敵方機器人和障礙的距離懲罰，距離越大，懲罰越大，這會使我們的機器人稍微繞一下路，但是盡可能地減少了與敵方機器人和障礙的碰撞，也使得我們的機器人在被敵方機器人追逐時顯得十分靈活。
在 Astar 搜索過程中，我們減少了敵人的半徑，這使得我們在一些極端情況也能避開敵人，機器人看起來會非常靈活。
局部導(dǎo)航用來為機器人規(guī)劃一個局部目標，機器人會認為從當(dāng)前位置到局部目標一定是可達的(不會與任何物體碰撞)，ORCA算法會驅(qū)動機器人向局部目標進行移動。局部導(dǎo)航帶有一定的避讓策略，當(dāng)A*搜索不到路徑時，會啟用局部導(dǎo)航作為保底機制。
·進攻
我們分為兩種進攻型機器人，一種進攻型機器人直接追著敵人跑，在運氣好的情況下能達到卡死敵方運輸型機器人的效果。
另一種是防守型，防守型機器人會占用敵人7號生產(chǎn)線上的同類工作臺，從而達到阻斷敵人的7號生產(chǎn)線的效果，防守型機器人在一些狹窄的工作臺附近效果非常好(這部分實現(xiàn)得不夠好，導(dǎo)致在對戰(zhàn)時浪費了兩個藍色機器人但沒有達到阻斷敵方7號生產(chǎn)線的效果)。
·防守
在路徑上避開敵人的工作由A*算法完成，但會存在一些敵人站在我方的工作臺不動，且難以撞開。因此在嘗試到一些工作臺無法到達時，我們會將這個工作臺禁用一段時間，當(dāng)禁用結(jié)束后再嘗試仍然無法到達工作臺，我們會將工作臺的禁用時間翻倍... ...
我們將工作臺分為了三類，用一個變量rushAble表示。rushAble=0表示工作臺位于墻角，當(dāng)敵人處于這樣，我方機器人難以將器撞開。rushAble=1表示能夠?qū)橙俗查_，但進入這樣的工作臺有被敵人卡死的風(fēng)險。rushAble=2表示這樣的工作臺附近是空曠的，可以被狀態(tài)，并且不存在被卡死的風(fēng)險。在進入rushAble<= 1的工作臺，如果周圍有敵人能使得我方機器人卡死，則機器人會被禁用購買任務(wù)，防止機器人購買了物品但賣不出去(如果買了一個物品7沒有賣出去，很可能成為PK賽中決勝的關(guān)鍵)。
有時候機器人難免會被敵人卡住，我們設(shè)置了卡死判定機制，并且采用低速旋轉(zhuǎn)+全速移動讓機器人脫離被卡死的狀態(tài)。
總結(jié)
此次軟挑，我們隊并非一帆風(fēng)順，復(fù)賽險遭淘汰。在復(fù)賽的前一天的時候，我們?nèi)齻€才第一次真正的開始討論，在此之前各自都有各自的想法以及解法(此處必須要感謝我們武長賽區(qū)工作人員，中午一點給我們聯(lián)系自習(xí)室，晚上12點還在熬夜關(guān)注我們)。終于，在距離復(fù)賽只有9個小時的時候，我們找到了一個新的解法并且?guī)椭覀儠x級了決賽。決賽前一晚，我們在測試2p和4p地圖以及一些自制地圖時，突然發(fā)現(xiàn)了代碼里存在一萬個bug(當(dāng)時待解決問題的列表列了十項有余，還有幾個要新加的策略)，于是我又拉著我的兩個隊友開肝，其實當(dāng)時已經(jīng)心態(tài)有點不穩(wěn)了，好在隊友們互相都沒給壓力，互相沒有怪罪(雖然嘴上說著沒拿獎有這個過程也很值得，但是其實心里想的都是必須拿獎)。于是我們開啟了第n個通宵。盡管第二天的正式賽我們策略還是出現(xiàn)了失誤，但好在付出有了回報。 這次軟挑，可以說有笑有淚，有成長有沉淀，有認識志同道合的新朋友，更有舊友重逢。這次與以往不一樣，我們?nèi)齻€真正感受到了團隊三個人的力量，少了任何人都無法拿到亞軍。非常感謝武長賽區(qū)工作組對我們的關(guān)心和鼓勵，更要感謝張元龍老師等賽題組專家對我們時時刻刻每件事情都有回應(yīng)，當(dāng)然最感謝的還是我們?nèi)齻€一起熬過的每一個夜，和多少次凌晨因為想到了新想法爬起來的自己。希望未來的旅途能再與軟挑相遇!
（免責(zé)聲明：本網(wǎng)站內(nèi)容主要來自原創(chuàng)、合作伙伴供稿和第三方自媒體作者投稿，凡在本網(wǎng)站出現(xiàn)的信息，均僅供參考。本網(wǎng)站將盡力確保所提供信息的準確性及可靠性，但不保證有關(guān)資料的準確性及可靠性，讀者在使用前請進一步核實，并對任何自主決定的行為負責(zé)。本網(wǎng)站對有關(guān)資料所引致的錯誤、不確或遺漏，概不負任何法律責(zé)任。
任何單位或個人認為本網(wǎng)站中的網(wǎng)頁或鏈接內(nèi)容可能涉嫌侵犯其知識產(chǎn)權(quán)或存在不實內(nèi)容時，應(yīng)及時向本網(wǎng)站提出書面權(quán)利通知或不實情況說明，并提供身份證明、權(quán)屬證明及詳細侵權(quán)或不實情況證明。本網(wǎng)站在收到上述法律文件后，將會依法盡快聯(lián)系相關(guān)文章源頭核實，溝通刪除相關(guān)內(nèi)容或斷開相關(guān)鏈接。 ）
