電子科技大學 劉露

4月23日，2023第九屆華為軟件精英挑戰(zhàn)賽-“普朗克計劃”全球總決賽及頒獎典禮圓滿落幕。大賽吸引了來自全球645所高校、3887支隊伍、23078名大學生報名參賽，歷時一個多月的激烈角逐，經(jīng)過八大賽區(qū)區(qū)域初賽、區(qū)域復賽、全球總決賽等環(huán)節(jié)的層層考驗。最終，成渝賽區(qū)來自電子科技大學的“_______”隊(“下劃線隊”)獲得全球總決賽冠軍。作為兩次獲得全球總冠軍的軟挑老兵，劉露撰文分享其賽隊參賽體驗，包括解題思路及對抗策略、比賽收獲等。

華為軟件精英挑戰(zhàn)賽是華為公司面向全球在校大學生舉辦的大型軟件編程競賽，向來有趣且具有挑戰(zhàn)性，受到眾多參賽選手的青睞。2021年我獲得軟挑冠軍后，開始忙于考研及科研等事情，因此遺憾于未能參加2022年的比賽。到了今年，我終于又有空參加軟挑，早在比賽正式開始前，我就和兩位隊友組好了隊共同備戰(zhàn)。

賽題介紹

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

圖為總決賽地圖之一

初賽

初賽我們隊打得挺狼狽的，最終是以賽區(qū)第31名的成績茍進了復賽。原因在于我們出現(xiàn)了策略上的失誤，期望能通過一個較通用的算法在四張公開的地圖上得到一個不錯的分數(shù)，但實際上，在數(shù)據(jù)集公開且數(shù)量較少的情況下，針對每個數(shù)據(jù)集分別設計擬合的算法是更容易拿到高分的。我們在初賽快結束時才意識到這個問題和著手設計擬合數(shù)據(jù)集的算法，但由于時間比較緊迫，分數(shù)提升得比較有限，最終只是勉強搭上了進入復賽的末班車。但塞翁失馬，焉知非福，我們在初賽設計的較通用的調(diào)度算法，雖然在初賽作用不大，卻成為了我們在復賽和決賽中均取得第一的重要因素。

復賽

復賽增加了障礙物，要求機器人具有尋路及讓路功能，難度一下子增加了不少。復賽前期我們主要在實現(xiàn)機器人尋路及讓路功能并優(yōu)化機器人的運動，后期發(fā)現(xiàn)我們的尋路算法具有嚴重的bug，會將一些可達的工作臺判定為不可達(之前我們判定一個工作臺可達時會要求機器人能夠站在工作臺中心而不與障礙物碰撞，但實際上只要機器人離工作臺較近就能進行買賣)，因此修復該bug就成為了一個極其緊急的任務。這個bug在復賽正式賽當天凌晨4點才被一位隊友修復完，凌晨5點我就起床進行代碼審查并進行一些細微的調(diào)整，以確保剛大改完的代碼在復賽現(xiàn)場能按預期運行。

由于復賽正式賽只有三個小時，并且地圖為兩張公開兩張隱藏，選手不易編寫擬合數(shù)據(jù)的策略，因此我們使用了初賽準備的通用的調(diào)度策略，配合我們最終實現(xiàn)的尋路和讓路算法，我們較為順利地拿下了復賽全國第一名。

決賽

決賽引入紅藍雙方對抗，敵方機器人作為己方機器人的移動障礙，難度大幅增加。但我們沒有在決賽初期就設計針對決賽的策略，而是重構了我們復賽階段最終的代碼，提升其簡潔性、可維護性和可拓展性，以便于在決賽階段我們能夠方便地修改代碼。重構完畢后，我們便著手設計決賽策略，通過四張公開的練習地圖評估了讓機器人占領敵方工作臺和追蹤敵方機器人兩種攻擊策略的效果，也嘗試了一些避免被敵方機器人卡死的策略。事實證明，決賽初期的重構確實是很有幫助的，我們嘗試的各種策略在重構后的代碼上都能較為方便地實現(xiàn)。

需要指出的是，在決賽練習賽階段，我們排名大多數(shù)時間都是第十幾名，這是因為我們沒有過多地擬合練習賽數(shù)據(jù)，而是將精力放到準備通用的策略上，我認為這也是我們最終奪冠的關鍵。在決賽正式賽的天梯賽階段，我們隊排名始終靠前，我們分析了少數(shù)幾場我們失敗的對局，稍微修改了機器人的運動控制，最終成功獲得天梯賽第一名，為我們在PK淘汰賽中爭取了一個占據(jù)優(yōu)勢的分組，進而最終在PK淘汰賽中完勝，勇奪總冠軍。

決賽有一件比較有趣的事：由于我們的筆記本電腦本地跑測試太慢了，一位隊友直接將自己的臺式機背到了決賽現(xiàn)場，這臺機器大大加快了我們的測試速度，讓我們在修改代碼后能夠快速驗證其有效性，這也是我們能夠奪冠的不可忽略的因素。

總決賽現(xiàn)場圖

整體方案

此處我們以一種自頂向下的方式介紹我們隊的整體方案。我們首先介紹最高層的對抗策略，然后介紹中層的調(diào)度算法、尋路算法、讓路算法，最后介紹最底層的運動控制算法。

對抗策略

決賽地圖分為四種類型，賽題組在決賽前已經(jīng)公布了四種類型的特征，相當于劃定了考試范圍，我們只需要分別考慮四種地圖對應的策略即可，而不必考慮各種復雜又不一定會出現(xiàn)的情況。

我們先介紹四種地圖的共同點以及我們隊在每種地圖上都使用的共同策略。決賽地圖保證資源足夠豐富，避免了出現(xiàn)敵方卡住某些工作臺導致己方被完全卡住的情況，因此占領敵方工作臺在決賽中收益不高，我們隊無論作為紅方還是藍方，都不會采用該策略，我們采用的(但不是每張圖都采用)唯一攻擊策略就是追隨敵方機器人，以限制其移動或?qū)⑵渫耆ㄗ　５覀冞€是需要考慮敵方占領我們的工作臺的情況，應對措施為：如果發(fā)現(xiàn)某個己方機器人的目標工作臺被敵方占領了，就切換目標工作臺(由于決賽地圖保證資源足夠豐富，這是可行的)。

接下來介紹我們針對四種地圖各自的特征設計的策略。

·類型一：相對開闊的地形，各自的資源點都比較豐富，雙方運輸路徑存在交錯。策略：對于這種類型，我們采取了最佛系的做法，無論我們是藍方還是紅方，我們都不會去進攻(占領敵方工作臺或追隨敵人)。這是因為地圖較開闊時，難以將敵方機器人卡住，而由于資源點又比較豐富，讓機器人去從事生產(chǎn)會更加劃算。

·類型二：相對開闊的地形，各自的資源點都比較豐富，地圖被分割為兩個不連通區(qū)域，其中一個區(qū)域為紅色基地，只有紅色工作臺，機器人初始為3紅1藍，另一個區(qū)域為藍色基地，只有藍色工作臺，機器人初始為3藍1紅。策略：賽題組設計這樣的地圖的目的很明確，就是讓選手必須控制在敵方基地的己方機器人去進攻。在這種地圖上，無論在紅方還是藍方，我們都是讓在敵方基地的那個己方機器人去跟隨敵人機器人，以干擾其生產(chǎn)。

·類型三：相對狹窄的地形，雙方有各自獨立基地，基地之間存在多條路徑連通，并且基地外部存在一些分散的紅藍工作臺可使用。策略：由于地圖比較狹窄，如果己方機器人去跟隨的話，容易將敵方機器人卡在墻角，此時其他敵方機器人的路也可能被擋住，因此很有可能實現(xiàn)一換一甚至一換多的效果。所以，在這種圖上，無論我們是紅藍哪方，我們都選擇讓一個機器人去跟隨敵方機器人，其他三個機器人從事生產(chǎn)。此處的一個關鍵點是千萬別讓己方負責追隨的機器人在自己基地追隨敵人，因為敵方機器人也可能來到己方基地搗亂，如果在己方基地追隨它的話，容易卡住自己的基地。

·類型四：極為開闊的地形，整張地圖完全沒有藍色工作臺，只有紅色工作臺，且紅色工作臺點比較豐富。策略：在這種地圖上，作為藍方時，由于沒有藍色工作臺，只能去攻擊敵人，我們采取的策略是讓每個機器人都去追隨最近的敵方機器人，但我們會保證每個機器人追隨不同的敵人(否則極端情況下可能所有藍色機器人都去圍堵一個紅色機器人，四換一就太虧了)，這樣就容易出現(xiàn)每個藍色機器人各自卡死一個紅色機器人，完全阻礙敵方生產(chǎn)的情況;作為紅方時，我們讓每個機器人都從事生產(chǎn)，期望獲得較高的收益。

調(diào)度算法

調(diào)度算法的總體邏輯為，每次為每個空閑的機器人分配一個買賣任務，該任務指定了機器人先去哪個工作臺買然后去哪個工作臺賣。為了避免出現(xiàn)所有購買的產(chǎn)品被其他機器人買掉和所有售賣物品賣不掉的情況，需要對購買的工作臺和售賣的工作臺加鎖。加鎖就需要考慮鎖的粒度，我們不是對整個工作臺加鎖，而是對購買的工作臺的產(chǎn)品格和售賣的工作臺的原料格加鎖。但如果購買的物品為1、2或3的話，我們不會對工作臺的產(chǎn)品格加鎖，這樣做是考慮到1、2和3號物品生產(chǎn)較快且不需要原料，即使被其他機器人先買掉了也能快速生產(chǎn)出來。

一個空閑的機器人可選擇的買賣任務可能有多個，選擇哪一個呢?我們總是選擇性價比最高的任務。具體地，我們評估每個任務能帶來的收益，并估計完成該任務需要的時間，選擇其中收益除以時間最大的那個。估計完成一個任務所需的時間較為容易，只需要計算機器人從當前位置移動到購買工作臺的路徑長度加上從購買工作臺移動到售賣工作臺的長度得到總移動距離，再除以運動速度即可。關鍵是估計一個任務的價值，最簡單的估價方式就是用物品的售出價格減去購買價格，但這個估價方式忽略了很多需要考慮的因素。

我們來考慮完成一個買賣任務會帶來哪些直接或間接的收益：

·物品本身買賣會有一個直接的利潤;

·如果一個工作臺生產(chǎn)被阻塞(生產(chǎn)所需的原料都有了，但由于產(chǎn)品格非空，無法消耗掉這些原料)，則無法將任何物品賣給它，此處如果我們購買了它的產(chǎn)品，其材料格中的材料就能被消耗，我們就能賣物品給它了;

·將一個物品賣給一個工作臺，可以促進該工作臺的生產(chǎn)，工作臺生產(chǎn)又帶來兩方面的好處：1、已有的材料被消耗，可以將更多的材料賣給它;2、生產(chǎn)出的產(chǎn)品可以被進一步賣給其他工作臺促進物品7的合成(如果工作臺的類型為4、5或6的話)。

為了體現(xiàn)以上這些考慮，我們實現(xiàn)了以下代碼所示的任務估值函數(shù)：

代碼中，direct_profit 表示買賣物品帶來的直接收益，unblocking_profit表示消除阻塞帶來的間接收益，sell_profit表示將一個物品賣給給定工作臺能夠帶來的間接收益，以下我們給出計算sell_profit的方法：

將物品賣給工作臺后，會導致工作臺消耗材料進行生產(chǎn)，這樣材料格就會空出，可以收購新的物品，這就帶來一個間接的收益，我們此處用erase_profit表示。如果我們是將物品賣給類型為4、5或6的工作臺，還能促進合成4、5、6，進而促進合成7。我們通過estimate_product_profit()函數(shù)計算在當前狀態(tài)下合成4、5或6能帶來的收益，此處用progress_profit表示。接下來再看下estimate_product_profit()的實現(xiàn)：

estimate_product_profit()計算將一個類型為4、5或6的物品賣給工作臺7或9所帶來的收益，該收益類似于前面由direct_profit、erase_profit和progress_profit三部分組成，選擇三者和最大的返回。

尋路算法

我們將地圖分為0.25*0.25的格子，考慮水平線和垂直線的交點(而不是格子的中心點)，我們將這樣的點稱為格點。注意到，根據(jù)賽題設置，一開始所有工作臺和機器人的中心都落在某個格點上，一個障礙物的四個角都各是一個格點。此外，前面提到過，有些工作臺中心機器人是無法到達的，但機器人不必到達工作臺中心就能進行買賣，我們可以通過選擇一些距離工作臺中心距離小于0.4米的點作為一個工作臺的代表點來解決這個問題。實際實現(xiàn)時，我們選擇了4個距離工作臺中心距離為0.35米的點來作為代表點。尋路時，只要機器人能夠到達代表點中的任何一個，就可以認為機器人能夠到達對應工作臺。

在我們的實現(xiàn)中，機器人每幀都會進行尋路，尋路時只考慮八個方向的移動，求出最短路徑，然后計算該路徑上機器人能直接到達的最遠點，控制機器人向該點移去。

讓路算法

讓路算法分為碰撞檢測和尋找避讓點兩步。每一幀，由于我們都重新調(diào)用了尋路算法，我們可以根據(jù)計算得到的路徑預測機器人是否會碰撞，如果預測會碰撞，我們讓優(yōu)先級低的機器人尋找一個避讓點移動過去。避讓點的計算方法為：從機器人所在位置進行BFS搜索一個可達的且不靠近要避讓的機器人的路徑的點。如果一個機器人無法找到避讓點，則會提升其優(yōu)先級以讓對方來避讓。

運動控制

運動控制這邊需要用到一點基礎的物理知識。設機器人當前在點A，其最大加速度為a(可以通過賽題所給參數(shù)計算出a)，我們希望移動到并剛好停留在點B，假設機器人現(xiàn)在已經(jīng)朝向B，那么當前幀機器人的速度應該設置為多少呢?首先我們希望該速度盡可能大，這樣機器人能夠快速到達B，但速度又不能太大以至于我們無法在B處剎住車，因此我們所要的速度應該滿足：當以最大加速度a減速時，能夠在到達B前剎住車。設AB間的距離為s，則容易計算出該速度為sqrt(2as)。類似地，如果我們想讓機器人旋轉(zhuǎn)theta度，設角加速度為alpha，則將角速度設置為sqrt(2 * theta * alpha)。

最終我們的運動控制如下：每一幀我們都計算機器人當前朝向與到目標點的方向的夾角theta，如果theta大于一定閾值，則將速度設置為0，按照上述方式設置角速度校正方向;如果theta小于一定閾值，則按照上述方式設置速度和角速度。

總結

此次軟挑，我們隊并非一帆風順，初賽險遭淘汰，復賽正式賽前還在修復嚴重的bug，決賽練習賽階段排名也不靠前，但好在有驚無險，我們最終拿到了總冠軍。我認為我們?nèi)俚年P鍵在于我們設計的算法比較有通用性，沒有過分擬合數(shù)據(jù)集，因此能夠在復賽正式賽和決賽正式賽更換數(shù)據(jù)集后取得不錯的成績。

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