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