電子科技大學(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)，包括解題思路及對(duì)抗策略、比賽收獲等。
華為軟件精英挑戰(zhàn)賽是華為公司面向全球在校大學(xué)生舉辦的大型軟件編程競(jìng)賽，向來有趣且具有挑戰(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í)場(chǎng)景，引入業(yè)界熱門算法難題，包括最優(yōu)調(diào)度問題、多機(jī)器人路徑協(xié)調(diào)規(guī)劃問題、動(dòng)態(tài)避障算法等，在初賽、復(fù)賽、決賽進(jìn)行有層次的難度遞進(jìn)。
圖為總決賽地圖之一
初賽
初賽我們隊(duì)打得挺狼狽的，最終是以賽區(qū)第31名的成績(jī)茍進(jìn)了復(fù)賽。原因在于我們出現(xiàn)了策略上的失誤，期望能通過一個(gè)較通用的算法在四張公開的地圖上得到一個(gè)不錯(cuò)的分?jǐn)?shù)，但實(shí)際上，在數(shù)據(jù)集公開且數(shù)量較少的情況下，針對(duì)每個(gè)數(shù)據(jù)集分別設(shè)計(jì)擬合的算法是更容易拿到高分的。我們?cè)诔踬惪旖Y(jié)束時(shí)才意識(shí)到這個(gè)問題和著手設(shè)計(jì)擬合數(shù)據(jù)集的算法，但由于時(shí)間比較緊迫，分?jǐn)?shù)提升得比較有限，最終只是勉強(qiáng)搭上了進(jìn)入復(fù)賽的末班車。但塞翁失馬，焉知非福，我們?cè)诔踬愒O(shè)計(jì)的較通用的調(diào)度算法，雖然在初賽作用不大，卻成為了我們?cè)趶?fù)賽和決賽中均取得第一的重要因素。
復(fù)賽
復(fù)賽增加了障礙物，要求機(jī)器人具有尋路及讓路功能，難度一下子增加了不少。復(fù)賽前期我們主要在實(shí)現(xiàn)機(jī)器人尋路及讓路功能并優(yōu)化機(jī)器人的運(yùn)動(dòng)，后期發(fā)現(xiàn)我們的尋路算法具有嚴(yán)重的bug，會(huì)將一些可達(dá)的工作臺(tái)判定為不可達(dá)(之前我們判定一個(gè)工作臺(tái)可達(dá)時(shí)會(huì)要求機(jī)器人能夠站在工作臺(tái)中心而不與障礙物碰撞，但實(shí)際上只要機(jī)器人離工作臺(tái)較近就能進(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)場(chǎng)能按預(yù)期運(yùn)行。
由于復(fù)賽正式賽只有三個(gè)小時(shí)，并且地圖為兩張公開兩張隱藏，選手不易編寫擬合數(shù)據(jù)的策略，因此我們使用了初賽準(zhǔn)備的通用的調(diào)度策略，配合我們最終實(shí)現(xiàn)的尋路和讓路算法，我們較為順利地拿下了復(fù)賽全國第一名。
決賽
決賽引入紅藍(lán)雙方對(duì)抗，敵方機(jī)器人作為己方機(jī)器人的移動(dòng)障礙，難度大幅增加。但我們沒有在決賽初期就設(shè)計(jì)針對(duì)決賽的策略，而是重構(gòu)了我們復(fù)賽階段最終的代碼，提升其簡(jiǎn)潔性、可維護(hù)性和可拓展性，以便于在決賽階段我們能夠方便地修改代碼。重構(gòu)完畢后，我們便著手設(shè)計(jì)決賽策略，通過四張公開的練習(xí)地圖評(píng)估了讓機(jī)器人占領(lǐng)敵方工作臺(tái)和追蹤敵方機(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ù)幾場(chǎng)我們失敗的對(duì)局，稍微修改了機(jī)器人的運(yùn)動(dòng)控制，最終成功獲得天梯賽第一名，為我們?cè)赑K淘汰賽中爭(zhēng)取了一個(gè)占據(jù)優(yōu)勢(shì)的分組，進(jìn)而最終在PK淘汰賽中完勝，勇奪總冠軍。
決賽有一件比較有趣的事：由于我們的筆記本電腦本地跑測(cè)試太慢了，一位隊(duì)友直接將自己的臺(tái)式機(jī)背到了決賽現(xiàn)場(chǎng)，這臺(tái)機(jī)器大大加快了我們的測(cè)試速度，讓我們?cè)谛薷拇a后能夠快速驗(yàn)證其有效性，這也是我們能夠奪冠的不可忽略的因素。
總決賽現(xiàn)場(chǎng)圖
整體方案
此處我們以一種自頂向下的方式介紹我們隊(duì)的整體方案。我們首先介紹最高層的對(duì)抗策略，然后介紹中層的調(diào)度算法、尋路算法、讓路算法，最后介紹最底層的運(yùn)動(dòng)控制算法。
對(duì)抗策略
決賽地圖分為四種類型，賽題組在決賽前已經(jīng)公布了四種類型的特征，相當(dāng)于劃定了考試范圍，我們只需要分別考慮四種地圖對(duì)應(yīng)的策略即可，而不必考慮各種復(fù)雜又不一定會(huì)出現(xiàn)的情況。
我們先介紹四種地圖的共同點(diǎn)以及我們隊(duì)在每種地圖上都使用的共同策略。決賽地圖保證資源足夠豐富，避免了出現(xiàn)敵方卡住某些工作臺(tái)導(dǎo)致己方被完全卡住的情況，因此占領(lǐng)敵方工作臺(tái)在決賽中收益不高，我們隊(duì)無論作為紅方還是藍(lán)方，都不會(huì)采用該策略，我們采用的(但不是每張圖都采用)唯一攻擊策略就是追隨敵方機(jī)器人，以限制其移動(dòng)或?qū)⑵渫耆ㄗ?。但我們還是需要考慮敵方占領(lǐng)我們的工作臺(tái)的情況，應(yīng)對(duì)措施為：如果發(fā)現(xiàn)某個(gè)己方機(jī)器人的目標(biāo)工作臺(tái)被敵方占領(lǐng)了，就切換目標(biāo)工作臺(tái)(由于決賽地圖保證資源足夠豐富，這是可行的)。
接下來介紹我們針對(duì)四種地圖各自的特征設(shè)計(jì)的策略。
·類型一：相對(duì)開闊的地形，各自的資源點(diǎn)都比較豐富，雙方運(yùn)輸路徑存在交錯(cuò)。策略：對(duì)于這種類型，我們采取了最佛系的做法，無論我們是藍(lán)方還是紅方，我們都不會(huì)去進(jìn)攻(占領(lǐng)敵方工作臺(tái)或追隨敵人)。這是因?yàn)榈貓D較開闊時(shí)，難以將敵方機(jī)器人卡住，而由于資源點(diǎn)又比較豐富，讓機(jī)器人去從事生產(chǎn)會(huì)更加劃算。
·類型二：相對(duì)開闊的地形，各自的資源點(diǎn)都比較豐富，地圖被分割為兩個(gè)不連通區(qū)域，其中一個(gè)區(qū)域?yàn)榧t色基地，只有紅色工作臺(tái)，機(jī)器人初始為3紅1藍(lán)，另一個(gè)區(qū)域?yàn)樗{(lán)色基地，只有藍(lán)色工作臺(tái)，機(jī)器人初始為3藍(lán)1紅。策略：賽題組設(shè)計(jì)這樣的地圖的目的很明確，就是讓選手必須控制在敵方基地的己方機(jī)器人去進(jìn)攻。在這種地圖上，無論在紅方還是藍(lán)方，我們都是讓在敵方基地的那個(gè)己方機(jī)器人去跟隨敵人機(jī)器人，以干擾其生產(chǎn)。
·類型三：相對(duì)狹窄的地形，雙方有各自獨(dú)立基地，基地之間存在多條路徑連通，并且基地外部存在一些分散的紅藍(lán)工作臺(tái)可使用。策略：由于地圖比較狹窄，如果己方機(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)色工作臺(tái)，只有紅色工作臺(tái)，且紅色工作臺(tái)點(diǎn)比較豐富。策略：在這種地圖上，作為藍(lán)方時(shí)，由于沒有藍(lán)色工作臺(tái)，只能去攻擊敵人，我們采取的策略是讓每個(gè)機(jī)器人都去追隨最近的敵方機(jī)器人，但我們會(huì)保證每個(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è)工作臺(tái)買然后去哪個(gè)工作臺(tái)賣。為了避免出現(xiàn)所有購買的產(chǎn)品被其他機(jī)器人買掉和所有售賣物品賣不掉的情況，需要對(duì)購買的工作臺(tái)和售賣的工作臺(tái)加鎖。加鎖就需要考慮鎖的粒度，我們不是對(duì)整個(gè)工作臺(tái)加鎖，而是對(duì)購買的工作臺(tái)的產(chǎn)品格和售賣的工作臺(tái)的原料格加鎖。但如果購買的物品為1、2或3的話，我們不會(huì)對(duì)工作臺(tái)的產(chǎn)品格加鎖，這樣做是考慮到1、2和3號(hào)物品生產(chǎn)較快且不需要原料，即使被其他機(jī)器人先買掉了也能快速生產(chǎn)出來。
一個(gè)空閑的機(jī)器人可選擇的買賣任務(wù)可能有多個(gè)，選擇哪一個(gè)呢?我們總是選擇性價(jià)比最高的任務(wù)。具體地，我們?cè)u(píng)估每個(gè)任務(wù)能帶來的收益，并估計(jì)完成該任務(wù)需要的時(shí)間，選擇其中收益除以時(shí)間最大的那個(gè)。估計(jì)完成一個(gè)任務(wù)所需的時(shí)間較為容易，只需要計(jì)算機(jī)器人從當(dāng)前位置移動(dòng)到購買工作臺(tái)的路徑長(zhǎng)度加上從購買工作臺(tái)移動(dòng)到售賣工作臺(tái)的長(zhǎng)度得到總移動(dòng)距離，再除以運(yùn)動(dòng)速度即可。關(guān)鍵是估計(jì)一個(gè)任務(wù)的價(jià)值，最簡(jiǎn)單的估價(jià)方式就是用物品的售出價(jià)格減去購買價(jià)格，但這個(gè)估價(jià)方式忽略了很多需要考慮的因素。
我們來考慮完成一個(gè)買賣任務(wù)會(huì)帶來哪些直接或間接的收益：
·物品本身買賣會(huì)有一個(gè)直接的利潤(rùn);
·如果一個(gè)工作臺(tái)生產(chǎn)被阻塞(生產(chǎn)所需的原料都有了，但由于產(chǎn)品格非空，無法消耗掉這些原料)，則無法將任何物品賣給它，此處如果我們購買了它的產(chǎn)品，其材料格中的材料就能被消耗，我們就能賣物品給它了;
·將一個(gè)物品賣給一個(gè)工作臺(tái)，可以促進(jìn)該工作臺(tái)的生產(chǎn)，工作臺(tái)生產(chǎn)又帶來兩方面的好處：1、已有的材料被消耗，可以將更多的材料賣給它;2、生產(chǎn)出的產(chǎn)品可以被進(jìn)一步賣給其他工作臺(tái)促進(jìn)物品7的合成(如果工作臺(tái)的類型為4、5或6的話)。
為了體現(xiàn)以上這些考慮，我們實(shí)現(xiàn)了以下代碼所示的任務(wù)估值函數(shù)：
代碼中，direct_profit 表示買賣物品帶來的直接收益，unblocking_profit表示消除阻塞帶來的間接收益，sell_profit表示將一個(gè)物品賣給給定工作臺(tái)能夠帶來的間接收益，以下我們給出計(jì)算sell_profit的方法：
將物品賣給工作臺(tái)后，會(huì)導(dǎo)致工作臺(tái)消耗材料進(jìn)行生產(chǎn)，這樣材料格就會(huì)空出，可以收購新的物品，這就帶來一個(gè)間接的收益，我們此處用erase_profit表示。如果我們是將物品賣給類型為4、5或6的工作臺(tái)，還能促進(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的物品賣給工作臺(tái)7或9所帶來的收益，該收益類似于前面由direct_profit、erase_profit和progress_profit三部分組成，選擇三者和最大的返回。
尋路算法
我們將地圖分為0.25*0.25的格子，考慮水平線和垂直線的交點(diǎn)(而不是格子的中心點(diǎn))，我們將這樣的點(diǎn)稱為格點(diǎn)。注意到，根據(jù)賽題設(shè)置，一開始所有工作臺(tái)和機(jī)器人的中心都落在某個(gè)格點(diǎn)上，一個(gè)障礙物的四個(gè)角都各是一個(gè)格點(diǎn)。此外，前面提到過，有些工作臺(tái)中心機(jī)器人是無法到達(dá)的，但機(jī)器人不必到達(dá)工作臺(tái)中心就能進(jìn)行買賣，我們可以通過選擇一些距離工作臺(tái)中心距離小于0.4米的點(diǎn)作為一個(gè)工作臺(tái)的代表點(diǎn)來解決這個(gè)問題。實(shí)際實(shí)現(xiàn)時(shí)，我們選擇了4個(gè)距離工作臺(tái)中心距離為0.35米的點(diǎn)來作為代表點(diǎn)。尋路時(shí)，只要機(jī)器人能夠到達(dá)代表點(diǎn)中的任何一個(gè)，就可以認(rèn)為機(jī)器人能夠到達(dá)對(duì)應(yīng)工作臺(tái)。
在我們的實(shí)現(xiàn)中，機(jī)器人每幀都會(huì)進(jìn)行尋路，尋路時(shí)只考慮八個(gè)方向的移動(dòng)，求出最短路徑，然后計(jì)算該路徑上機(jī)器人能直接到達(dá)的最遠(yuǎn)點(diǎn)，控制機(jī)器人向該點(diǎn)移去。
讓路算法
讓路算法分為碰撞檢測(cè)和尋找避讓點(diǎn)兩步。每一幀，由于我們都重新調(diào)用了尋路算法，我們可以根據(jù)計(jì)算得到的路徑預(yù)測(cè)機(jī)器人是否會(huì)碰撞，如果預(yù)測(cè)會(huì)碰撞，我們讓優(yōu)先級(jí)低的機(jī)器人尋找一個(gè)避讓點(diǎn)移動(dòng)過去。避讓點(diǎn)的計(jì)算方法為：從機(jī)器人所在位置進(jìn)行BFS搜索一個(gè)可達(dá)的且不靠近要避讓的機(jī)器人的路徑的點(diǎn)。如果一個(gè)機(jī)器人無法找到避讓點(diǎn)，則會(huì)提升其優(yōu)先級(jí)以讓對(duì)方來避讓。
運(yùn)動(dòng)控制
運(yùn)動(dòng)控制這邊需要用到一點(diǎn)基礎(chǔ)的物理知識(shí)。設(shè)機(jī)器人當(dāng)前在點(diǎn)A，其最大加速度為a(可以通過賽題所給參數(shù)計(jì)算出a)，我們希望移動(dòng)到并剛好停留在點(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)動(dòng)控制如下：每一幀我們都計(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)鍵在于我們?cè)O(shè)計(jì)的算法比較有通用性，沒有過分?jǐn)M合數(shù)據(jù)集，因此能夠在復(fù)賽正式賽和決賽正式賽更換數(shù)據(jù)集后取得不錯(cuò)的成績(jī)。
（免責(zé)聲明：本網(wǎng)站內(nè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)頁或鏈接內(nèi)容可能涉嫌侵犯其知識(shí)產(chǎn)權(quán)或存在不實(shí)內(nèi)容時(shí)，應(yīng)及時(shí)向本網(wǎng)站提出書面權(quán)利通知或不實(shí)情況說明，并提供身份證明、權(quán)屬證明及詳細(xì)侵權(quán)或不實(shí)情況證明。本網(wǎng)站在收到上述法律文件后，將會(huì)依法盡快聯(lián)系相關(guān)文章源頭核實(shí)，溝通刪除相關(guān)內(nèi)容或斷開相關(guān)鏈接。 ）
