電子科技大學(xué) 劉露
4月23日，2023第九屆華為軟件精英挑戰(zhàn)賽-“普朗克計(jì)劃”全球總決賽及頒獎(jiǎng)典禮圓滿落幕。大賽吸引了來自全球645所高校、3887支隊(duì)伍、23078名大學(xué)生報(bào)名參賽，歷時(shí)一個(gè)多月的激烈角逐，經(jīng)過八大賽區(qū)區(qū)域初賽、區(qū)域復(fù)賽、全球總決賽等環(huán)節(jié)的層層考驗(yàn)。最終，成渝賽區(qū)來自電子科技大學(xué)的“_______”隊(duì)(“下劃線隊(duì)”)獲得全球總決賽冠軍。作為兩次獲得全球總冠軍的軟挑老兵，劉露撰文分享其賽隊(duì)參賽體驗(yàn)，包括解題思路及對抗策略、比賽收獲等。
華為軟件精英挑戰(zhàn)賽是華為公司面向全球在校大學(xué)生舉辦的大型軟件編程競賽，向來有趣且具有挑戰(zhàn)性，受到眾多參賽選手的青睞。2021年我獲得軟挑冠軍后，開始忙于考研及科研等事情，因此遺憾于未能參加2022年的比賽。到了今年，我終于又有空參加軟挑，早在比賽正式開始前，我就和兩位隊(duì)友組好了隊(duì)共同備戰(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)。
圖為總決賽地圖之一
初賽
初賽我們隊(duì)打得挺狼狽的，最終是以賽區(qū)第31名的成績茍進(jìn)了復(fù)賽。原因在于我們出現(xiàn)了策略上的失誤，期望能通過一個(gè)較通用的算法在四張公開的地圖上得到一個(gè)不錯(cuò)的分?jǐn)?shù)，但實(shí)際上，在數(shù)據(jù)集公開且數(shù)量較少的情況下，針對每個(gè)數(shù)據(jù)集分別設(shè)計(jì)擬合的算法是更容易拿到高分的。我們在初賽快結(jié)束時(shí)才意識到這個(gè)問題和著手設(shè)計(jì)擬合數(shù)據(jù)集的算法，但由于時(shí)間比較緊迫，分?jǐn)?shù)提升得比較有限，最終只是勉強(qiáng)搭上了進(jìn)入復(fù)賽的末班車。但塞翁失馬，焉知非福，我們在初賽設(shè)計(jì)的較通用的調(diào)度算法，雖然在初賽作用不大，卻成為了我們在復(fù)賽和決賽中均取得第一的重要因素。
復(fù)賽
復(fù)賽增加了障礙物，要求機(jī)器人具有尋路及讓路功能，難度一下子增加了不少。復(fù)賽前期我們主要在實(shí)現(xiàn)機(jī)器人尋路及讓路功能并優(yōu)化機(jī)器人的運(yùn)動，后期發(fā)現(xiàn)我們的尋路算法具有嚴(yán)重的bug，會將一些可達(dá)的工作臺判定為不可達(dá)(之前我們判定一個(gè)工作臺可達(dá)時(shí)會要求機(jī)器人能夠站在工作臺中心而不與障礙物碰撞，但實(shí)際上只要機(jī)器人離工作臺較近就能進(jìn)行買賣)，因此修復(fù)該bug就成為了一個(gè)極其緊急的任務(wù)。這個(gè)bug在復(fù)賽正式賽當(dāng)天凌晨4點(diǎn)才被一位隊(duì)友修復(fù)完，凌晨5點(diǎn)我就起床進(jìn)行代碼審查并進(jìn)行一些細(xì)微的調(diào)整，以確保剛大改完的代碼在復(fù)賽現(xiàn)場能按預(yù)期運(yùn)行。
由于復(fù)賽正式賽只有三個(gè)小時(shí)，并且地圖為兩張公開兩張隱藏，選手不易編寫擬合數(shù)據(jù)的策略，因此我們使用了初賽準(zhǔn)備的通用的調(diào)度策略，配合我們最終實(shí)現(xiàn)的尋路和讓路算法，我們較為順利地拿下了復(fù)賽全國第一名。
決賽
決賽引入紅藍(lán)雙方對抗，敵方機(jī)器人作為己方機(jī)器人的移動障礙，難度大幅增加。但我們沒有在決賽初期就設(shè)計(jì)針對決賽的策略，而是重構(gòu)了我們復(fù)賽階段最終的代碼，提升其簡潔性、可維護(hù)性和可拓展性，以便于在決賽階段我們能夠方便地修改代碼。重構(gòu)完畢后，我們便著手設(shè)計(jì)決賽策略，通過四張公開的練習(xí)地圖評估了讓機(jī)器人占領(lǐng)敵方工作臺和追蹤敵方機(jī)器人兩種攻擊策略的效果，也嘗試了一些避免被敵方機(jī)器人卡死的策略。事實(shí)證明，決賽初期的重構(gòu)確實(shí)是很有幫助的，我們嘗試的各種策略在重構(gòu)后的代碼上都能較為方便地實(shí)現(xiàn)。
需要指出的是，在決賽練習(xí)賽階段，我們排名大多數(shù)時(shí)間都是第十幾名，這是因?yàn)槲覀儧]有過多地?cái)M合練習(xí)賽數(shù)據(jù)，而是將精力放到準(zhǔn)備通用的策略上，我認(rèn)為這也是我們最終奪冠的關(guān)鍵。在決賽正式賽的天梯賽階段，我們隊(duì)排名始終靠前，我們分析了少數(shù)幾場我們失敗的對局，稍微修改了機(jī)器人的運(yùn)動控制，最終成功獲得天梯賽第一名，為我們在PK淘汰賽中爭取了一個(gè)占據(jù)優(yōu)勢的分組，進(jìn)而最終在PK淘汰賽中完勝，勇奪總冠軍。
決賽有一件比較有趣的事：由于我們的筆記本電腦本地跑測試太慢了，一位隊(duì)友直接將自己的臺式機(jī)背到了決賽現(xiàn)場，這臺機(jī)器大大加快了我們的測試速度，讓我們在修改代碼后能夠快速驗(yàn)證其有效性，這也是我們能夠奪冠的不可忽略的因素。
總決賽現(xiàn)場圖
整體方案
此處我們以一種自頂向下的方式介紹我們隊(duì)的整體方案。我們首先介紹最高層的對抗策略，然后介紹中層的調(diào)度算法、尋路算法、讓路算法，最后介紹最底層的運(yùn)動控制算法。
對抗策略
決賽地圖分為四種類型，賽題組在決賽前已經(jīng)公布了四種類型的特征，相當(dāng)于劃定了考試范圍，我們只需要分別考慮四種地圖對應(yīng)的策略即可，而不必考慮各種復(fù)雜又不一定會出現(xiàn)的情況。
我們先介紹四種地圖的共同點(diǎn)以及我們隊(duì)在每種地圖上都使用的共同策略。決賽地圖保證資源足夠豐富，避免了出現(xiàn)敵方卡住某些工作臺導(dǎo)致己方被完全卡住的情況，因此占領(lǐng)敵方工作臺在決賽中收益不高，我們隊(duì)無論作為紅方還是藍(lán)方，都不會采用該策略，我們采用的(但不是每張圖都采用)唯一攻擊策略就是追隨敵方機(jī)器人，以限制其移動或?qū)⑵渫耆ㄗ?。但我們還是需要考慮敵方占領(lǐng)我們的工作臺的情況，應(yīng)對措施為：如果發(fā)現(xiàn)某個(gè)己方機(jī)器人的目標(biāo)工作臺被敵方占領(lǐng)了，就切換目標(biāo)工作臺(由于決賽地圖保證資源足夠豐富，這是可行的)。
接下來介紹我們針對四種地圖各自的特征設(shè)計(jì)的策略。
·類型一：相對開闊的地形，各自的資源點(diǎn)都比較豐富，雙方運(yùn)輸路徑存在交錯(cuò)。策略：對于這種類型，我們采取了最佛系的做法，無論我們是藍(lán)方還是紅方，我們都不會去進(jìn)攻(占領(lǐng)敵方工作臺或追隨敵人)。這是因?yàn)榈貓D較開闊時(shí)，難以將敵方機(jī)器人卡住，而由于資源點(diǎn)又比較豐富，讓機(jī)器人去從事生產(chǎn)會更加劃算。
·類型二：相對開闊的地形，各自的資源點(diǎn)都比較豐富，地圖被分割為兩個(gè)不連通區(qū)域，其中一個(gè)區(qū)域?yàn)榧t色基地，只有紅色工作臺，機(jī)器人初始為3紅1藍(lán)，另一個(gè)區(qū)域?yàn)樗{(lán)色基地，只有藍(lán)色工作臺，機(jī)器人初始為3藍(lán)1紅。策略：賽題組設(shè)計(jì)這樣的地圖的目的很明確，就是讓選手必須控制在敵方基地的己方機(jī)器人去進(jìn)攻。在這種地圖上，無論在紅方還是藍(lán)方，我們都是讓在敵方基地的那個(gè)己方機(jī)器人去跟隨敵人機(jī)器人，以干擾其生產(chǎn)。
·類型三：相對狹窄的地形，雙方有各自獨(dú)立基地，基地之間存在多條路徑連通，并且基地外部存在一些分散的紅藍(lán)工作臺可使用。策略：由于地圖比較狹窄，如果己方機(jī)器人去跟隨的話，容易將敵方機(jī)器人卡在墻角，此時(shí)其他敵方機(jī)器人的路也可能被擋住，因此很有可能實(shí)現(xiàn)一換一甚至一換多的效果。所以，在這種圖上，無論我們是紅藍(lán)哪方，我們都選擇讓一個(gè)機(jī)器人去跟隨敵方機(jī)器人，其他三個(gè)機(jī)器人從事生產(chǎn)。此處的一個(gè)關(guān)鍵點(diǎn)是千萬別讓己方負(fù)責(zé)追隨的機(jī)器人在自己基地追隨敵人，因?yàn)閿撤綑C(jī)器人也可能來到己方基地?fù)v亂，如果在己方基地追隨它的話，容易卡住自己的基地。
·類型四：極為開闊的地形，整張地圖完全沒有藍(lán)色工作臺，只有紅色工作臺，且紅色工作臺點(diǎn)比較豐富。策略：在這種地圖上，作為藍(lán)方時(shí)，由于沒有藍(lán)色工作臺，只能去攻擊敵人，我們采取的策略是讓每個(gè)機(jī)器人都去追隨最近的敵方機(jī)器人，但我們會保證每個(gè)機(jī)器人追隨不同的敵人(否則極端情況下可能所有藍(lán)色機(jī)器人都去圍堵一個(gè)紅色機(jī)器人，四換一就太虧了)，這樣就容易出現(xiàn)每個(gè)藍(lán)色機(jī)器人各自卡死一個(gè)紅色機(jī)器人，完全阻礙敵方生產(chǎn)的情況;作為紅方時(shí)，我們讓每個(gè)機(jī)器人都從事生產(chǎn)，期望獲得較高的收益。
調(diào)度算法
調(diào)度算法的總體邏輯為，每次為每個(gè)空閑的機(jī)器人分配一個(gè)買賣任務(wù)，該任務(wù)指定了機(jī)器人先去哪個(gè)工作臺買然后去哪個(gè)工作臺賣。為了避免出現(xiàn)所有購買的產(chǎn)品被其他機(jī)器人買掉和所有售賣物品賣不掉的情況，需要對購買的工作臺和售賣的工作臺加鎖。加鎖就需要考慮鎖的粒度，我們不是對整個(gè)工作臺加鎖，而是對購買的工作臺的產(chǎn)品格和售賣的工作臺的原料格加鎖。但如果購買的物品為1、2或3的話，我們不會對工作臺的產(chǎn)品格加鎖，這樣做是考慮到1、2和3號物品生產(chǎn)較快且不需要原料，即使被其他機(jī)器人先買掉了也能快速生產(chǎn)出來。
一個(gè)空閑的機(jī)器人可選擇的買賣任務(wù)可能有多個(gè)，選擇哪一個(gè)呢?我們總是選擇性價(jià)比最高的任務(wù)。具體地，我們評估每個(gè)任務(wù)能帶來的收益，并估計(jì)完成該任務(wù)需要的時(shí)間，選擇其中收益除以時(shí)間最大的那個(gè)。估計(jì)完成一個(gè)任務(wù)所需的時(shí)間較為容易，只需要計(jì)算機(jī)器人從當(dāng)前位置移動到購買工作臺的路徑長度加上從購買工作臺移動到售賣工作臺的長度得到總移動距離，再除以運(yùn)動速度即可。關(guān)鍵是估計(jì)一個(gè)任務(wù)的價(jià)值，最簡單的估價(jià)方式就是用物品的售出價(jià)格減去購買價(jià)格，但這個(gè)估價(jià)方式忽略了很多需要考慮的因素。
我們來考慮完成一個(gè)買賣任務(wù)會帶來哪些直接或間接的收益：
·物品本身買賣會有一個(gè)直接的利潤;
·如果一個(gè)工作臺生產(chǎn)被阻塞(生產(chǎn)所需的原料都有了，但由于產(chǎn)品格非空，無法消耗掉這些原料)，則無法將任何物品賣給它，此處如果我們購買了它的產(chǎn)品，其材料格中的材料就能被消耗，我們就能賣物品給它了;
·將一個(gè)物品賣給一個(gè)工作臺，可以促進(jìn)該工作臺的生產(chǎn)，工作臺生產(chǎn)又帶來兩方面的好處：1、已有的材料被消耗，可以將更多的材料賣給它;2、生產(chǎn)出的產(chǎn)品可以被進(jìn)一步賣給其他工作臺促進(jìn)物品7的合成(如果工作臺的類型為4、5或6的話)。
為了體現(xiàn)以上這些考慮，我們實(shí)現(xiàn)了以下代碼所示的任務(wù)估值函數(shù)：
代碼中，direct_profit 表示買賣物品帶來的直接收益，unblocking_profit表示消除阻塞帶來的間接收益，sell_profit表示將一個(gè)物品賣給給定工作臺能夠帶來的間接收益，以下我們給出計(jì)算sell_profit的方法：
將物品賣給工作臺后，會導(dǎo)致工作臺消耗材料進(jìn)行生產(chǎn)，這樣材料格就會空出，可以收購新的物品，這就帶來一個(gè)間接的收益，我們此處用erase_profit表示。如果我們是將物品賣給類型為4、5或6的工作臺，還能促進(jìn)合成4、5、6，進(jìn)而促進(jìn)合成7。我們通過estimate_product_profit()函數(shù)計(jì)算在當(dāng)前狀態(tài)下合成4、5或6能帶來的收益，此處用progress_profit表示。接下來再看下estimate_product_profit()的實(shí)現(xiàn)：
estimate_product_profit()計(jì)算將一個(gè)類型為4、5或6的物品賣給工作臺7或9所帶來的收益，該收益類似于前面由direct_profit、erase_profit和progress_profit三部分組成，選擇三者和最大的返回。
尋路算法
我們將地圖分為0.25*0.25的格子，考慮水平線和垂直線的交點(diǎn)(而不是格子的中心點(diǎn))，我們將這樣的點(diǎn)稱為格點(diǎn)。注意到，根據(jù)賽題設(shè)置，一開始所有工作臺和機(jī)器人的中心都落在某個(gè)格點(diǎn)上，一個(gè)障礙物的四個(gè)角都各是一個(gè)格點(diǎn)。此外，前面提到過，有些工作臺中心機(jī)器人是無法到達(dá)的，但機(jī)器人不必到達(dá)工作臺中心就能進(jìn)行買賣，我們可以通過選擇一些距離工作臺中心距離小于0.4米的點(diǎn)作為一個(gè)工作臺的代表點(diǎn)來解決這個(gè)問題。實(shí)際實(shí)現(xiàn)時(shí)，我們選擇了4個(gè)距離工作臺中心距離為0.35米的點(diǎn)來作為代表點(diǎn)。尋路時(shí)，只要機(jī)器人能夠到達(dá)代表點(diǎn)中的任何一個(gè)，就可以認(rèn)為機(jī)器人能夠到達(dá)對應(yīng)工作臺。
在我們的實(shí)現(xiàn)中，機(jī)器人每幀都會進(jìn)行尋路，尋路時(shí)只考慮八個(gè)方向的移動，求出最短路徑，然后計(jì)算該路徑上機(jī)器人能直接到達(dá)的最遠(yuǎn)點(diǎn)，控制機(jī)器人向該點(diǎn)移去。
讓路算法
讓路算法分為碰撞檢測和尋找避讓點(diǎn)兩步。每一幀，由于我們都重新調(diào)用了尋路算法，我們可以根據(jù)計(jì)算得到的路徑預(yù)測機(jī)器人是否會碰撞，如果預(yù)測會碰撞，我們讓優(yōu)先級低的機(jī)器人尋找一個(gè)避讓點(diǎn)移動過去。避讓點(diǎn)的計(jì)算方法為：從機(jī)器人所在位置進(jìn)行BFS搜索一個(gè)可達(dá)的且不靠近要避讓的機(jī)器人的路徑的點(diǎn)。如果一個(gè)機(jī)器人無法找到避讓點(diǎn)，則會提升其優(yōu)先級以讓對方來避讓。
運(yùn)動控制
運(yùn)動控制這邊需要用到一點(diǎn)基礎(chǔ)的物理知識。設(shè)機(jī)器人當(dāng)前在點(diǎn)A，其最大加速度為a(可以通過賽題所給參數(shù)計(jì)算出a)，我們希望移動到并剛好停留在點(diǎn)B，假設(shè)機(jī)器人現(xiàn)在已經(jīng)朝向B，那么當(dāng)前幀機(jī)器人的速度應(yīng)該設(shè)置為多少呢?首先我們希望該速度盡可能大，這樣機(jī)器人能夠快速到達(dá)B，但速度又不能太大以至于我們無法在B處剎住車，因此我們所要的速度應(yīng)該滿足：當(dāng)以最大加速度a減速時(shí)，能夠在到達(dá)B前剎住車。設(shè)AB間的距離為s，則容易計(jì)算出該速度為sqrt(2as)。類似地，如果我們想讓機(jī)器人旋轉(zhuǎn)theta度，設(shè)角加速度為alpha，則將角速度設(shè)置為sqrt(2 * theta * alpha)。
最終我們的運(yùn)動控制如下：每一幀我們都計(jì)算機(jī)器人當(dāng)前朝向與到目標(biāo)點(diǎn)的方向的夾角theta，如果theta大于一定閾值，則將速度設(shè)置為0，按照上述方式設(shè)置角速度校正方向;如果theta小于一定閾值，則按照上述方式設(shè)置速度和角速度。
總結(jié)
此次軟挑，我們隊(duì)并非一帆風(fēng)順，初賽險(xiǎn)遭淘汰，復(fù)賽正式賽前還在修復(fù)嚴(yán)重的bug，決賽練習(xí)賽階段排名也不靠前，但好在有驚無險(xiǎn)，我們最終拿到了總冠軍。我認(rèn)為我們?nèi)俚年P(guān)鍵在于我們設(shè)計(jì)的算法比較有通用性，沒有過分?jǐn)M合數(shù)據(jù)集，因此能夠在復(fù)賽正式賽和決賽正式賽更換數(shù)據(jù)集后取得不錯(cuò)的成績。
（免責(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)資料所引致的錯(cuò)誤、不確或遺漏，概不負(fù)任何法律責(zé)任。
任何單位或個(gè)人認(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)鏈接。 ）
