电子科技大学 刘露

4月23日，2023第九届华为软件精英挑战赛-“普朗克计划”全球总决赛及颁奖典礼圆满落幕。大赛吸引了来自全球645所高校、3887支队伍、23078名大学生报名参赛，历时一个多月的激烈角逐，经过八大赛区区域初赛、区域复赛、全球总决赛等环节的层层考验。最终，成渝赛区来自电子科技大学的“_______”队（“下划线队”）获得全球总决赛冠军。作为两次获得全球总冠军的软挑老兵，刘露撰文分享其赛队参赛体验，包括解题思路及对抗策略、比赛收获等。

华为软件精英挑战赛是华为公司面向全球在校大学生举办的大型软件编程竞赛，向来有趣且具有挑战性，受到众多参赛选手的青睐。2021年我获得软挑冠军后，开始忙于考研及科研等事情，因此遗憾于未能参加2022年的比赛。到了今年，我终于又有空参加软挑，早在比赛正式开始前，我就和两位队友组好了队共同备战。

赛题介绍

今年赛题抽象自华为云智能机器人的真实业务，模拟了多机器人的运行环境以及真实机器人的状态信息，由参赛者通过代码操控机器人完成特定任务以实现收益最大化。大赛赛题还原物理引擎、激光雷达、真实操控接口等机器人业务真实场景，引入业界热门算法难题，包括最优调度问题、多机器人路径协调规划问题、动态避障算法等，在初赛、复赛、决赛进行有层次的难度递进。

图为总决赛地图之一

初赛

初赛我们队打得挺狼狈的，最终是以赛区第31名的成绩苟进了复赛。原因在于我们出现了策略上的失误，期望能通过一个较通用的算法在四张公开的地图上得到一个不错的分数，但实际上，在数据集公开且数量较少的情况下，针对每个数据集分别设计拟合的算法是更容易拿到高分的。我们在初赛快结束时才意识到这个问题和着手设计拟合数据集的算法，但由于时间比较紧迫，分数提升得比较有限，最终只是勉强搭上了进入复赛的末班车。但塞翁失马，焉知非福，我们在初赛设计的较通用的调度算法，虽然在初赛作用不大，却成为了我们在复赛和决赛中均取得第一的重要因素。

复赛

复赛增加了障碍物，要求机器人具有寻路及让路功能，难度一下子增加了不少。复赛前期我们主要在实现机器人寻路及让路功能并优化机器人的运动，后期发现我们的寻路算法具有严重的bug，会将一些可达的工作台判定为不可达（之前我们判定一个工作台可达时会要求机器人能够站在工作台中心而不与障碍物碰撞，但实际上只要机器人离工作台较近就能进行买卖），因此修复该bug就成为了一个极其紧急的任务。这个bug在复赛正式赛当天凌晨4点才被一位队友修复完，凌晨5点我就起床进行代码审查并进行一些细微的调整，以确保刚大改完的代码在复赛现场能按预期运行。

由于复赛正式赛只有三个小时，并且地图为两张公开两张隐藏，选手不易编写拟合数据的策略，因此我们使用了初赛准备的通用的调度策略，配合我们最终实现的寻路和让路算法，我们较为顺利地拿下了复赛全国第一名。

决赛

决赛引入红蓝双方对抗，敌方机器人作为己方机器人的移动障碍，难度大幅增加。但我们没有在决赛初期就设计针对决赛的策略，而是重构了我们复赛阶段最终的代码，提升其简洁性、可维护性和可拓展性，以便于在决赛阶段我们能够方便地修改代码。重构完毕后，我们便着手设计决赛策略，通过四张公开的练习地图评估了让机器人占领敌方工作台和追踪敌方机器人两种攻击策略的效果，也尝试了一些避免被敌方机器人卡死的策略。事实证明，决赛初期的重构确实是很有帮助的，我们尝试的各种策略在重构后的代码上都能较为方便地实现。

需要指出的是，在决赛练习赛阶段，我们排名大多数时间都是第十几名，这是因为我们没有过多地拟合练习赛数据，而是将精力放到准备通用的策略上，我认为这也是我们最终夺冠的关键。在决赛正式赛的天梯赛阶段，我们队排名始终靠前，我们分析了少数几场我们失败的对局，稍微修改了机器人的运动控制，最终成功获得天梯赛第一名，为我们在PK淘汰赛中争取了一个占据优势的分组，进而最终在PK淘汰赛中完胜，勇夺总冠军。

决赛有一件比较有趣的事：由于我们的笔记本电脑本地跑测试太慢了，一位队友直接将自己的台式机背到了决赛现场，这台机器大大加快了我们的测试速度，让我们在修改代码后能够快速验证其有效性，这也是我们能够夺冠的不可忽略的因素。

总决赛现场图

整体方案

此处我们以一种自顶向下的方式介绍我们队的整体方案。我们首先介绍最高层的对抗策略，然后介绍中层的调度算法、寻路算法、让路算法，最后介绍最底层的运动控制算法。

对抗策略

决赛地图分为四种类型，赛题组在决赛前已经公布了四种类型的特征，相当于划定了考试范围，我们只需要分别考虑四种地图对应的策略即可，而不必考虑各种复杂又不一定会出现的情况。

我们先介绍四种地图的共同点以及我们队在每种地图上都使用的共同策略。决赛地图保证资源足够丰富，避免了出现敌方卡住某些工作台导致己方被完全卡住的情况，因此占领敌方工作台在决赛中收益不高，我们队无论作为红方还是蓝方，都不会采用该策略，我们采用的（但不是每张图都采用）唯一攻击策略就是追随敌方机器人，以限制其移动或将其完全卡住。但我们还是需要考虑敌方占领我们的工作台的情况，应对措施为：如果发现某个己方机器人的目标工作台被敌方占领了，就切换目标工作台（由于决赛地图保证资源足够丰富，这是可行的）。

接下来介绍我们针对四种地图各自的特征设计的策略。

·类型一：相对开阔的地形，各自的资源点都比较丰富，双方运输路径存在交错。策略：对于这种类型，我们采取了最佛系的做法，无论我们是蓝方还是红方，我们都不会去进攻（占领敌方工作台或追随敌人）。这是因为地图较开阔时，难以将敌方机器人卡住，而由于资源点又比较丰富，让机器人去从事生产会更加划算。

·类型二：相对开阔的地形，各自的资源点都比较丰富，地图被分割为两个不连通区域，其中一个区域为红色基地，只有红色工作台，机器人初始为3红1蓝，另一个区域为蓝色基地，只有蓝色工作台，机器人初始为3蓝1红。策略：赛题组设计这样的地图的目的很明确，就是让选手必须控制在敌方基地的己方机器人去进攻。在这种地图上，无论在红方还是蓝方，我们都是让在敌方基地的那个己方机器人去跟随敌人机器人，以干扰其生产。

·类型三：相对狭窄的地形，双方有各自独立基地，基地之间存在多条路径连通，并且基地外部存在一些分散的红蓝工作台可使用。策略：由于地图比较狭窄，如果己方机器人去跟随的话，容易将敌方机器人卡在墙角，此时其他敌方机器人的路也可能被挡住，因此很有可能实现一换一甚至一换多的效果。所以，在这种图上，无论我们是红蓝哪方，我们都选择让一个机器人去跟随敌方机器人，其他三个机器人从事生产。此处的一个关键点是千万别让己方负责追随的机器人在自己基地追随敌人，因为敌方机器人也可能来到己方基地捣乱，如果在己方基地追随它的话，容易卡住自己的基地。

·类型四：极为开阔的地形，整张地图完全没有蓝色工作台，只有红色工作台，且红色工作台点比较丰富。策略：在这种地图上，作为蓝方时，由于没有蓝色工作台，只能去攻击敌人，我们采取的策略是让每个机器人都去追随最近的敌方机器人，但我们会保证每个机器人追随不同的敌人（否则极端情况下可能所有蓝色机器人都去围堵一个红色机器人，四换一就太亏了），这样就容易出现每个蓝色机器人各自卡死一个红色机器人，完全阻碍敌方生产的情况；作为红方时，我们让每个机器人都从事生产，期望获得较高的收益。

调度算法

调度算法的总体逻辑为，每次为每个空闲的机器人分配一个买卖任务，该任务指定了机器人先去哪个工作台买然后去哪个工作台卖。为了避免出现所有购买的产品被其他机器人买掉和所有售卖物品卖不掉的情况，需要对购买的工作台和售卖的工作台加锁。加锁就需要考虑锁的粒度，我们不是对整个工作台加锁，而是对购买的工作台的产品格和售卖的工作台的原料格加锁。但如果购买的物品为1、2或3的话，我们不会对工作台的产品格加锁，这样做是考虑到1、2和3号物品生产较快且不需要原料，即使被其他机器人先买掉了也能快速生产出来。

一个空闲的机器人可选择的买卖任务可能有多个，选择哪一个呢？我们总是选择性价比最高的任务。具体地，我们评估每个任务能带来的收益，并估计完成该任务需要的时间，选择其中收益除以时间最大的那个。估计完成一个任务所需的时间较为容易，只需要计算机器人从当前位置移动到购买工作台的路径长度加上从购买工作台移动到售卖工作台的长度得到总移动距离，再除以运动速度即可。关键是估计一个任务的价值，最简单的估价方式就是用物品的售出价格减去购买价格，但这个估价方式忽略了很多需要考虑的因素。

我们来考虑完成一个买卖任务会带来哪些直接或间接的收益：

·物品本身买卖会有一个直接的利润；

·如果一个工作台生产被阻塞（生产所需的原料都有了，但由于产品格非空，无法消耗掉这些原料），则无法将任何物品卖给它，此处如果我们购买了它的产品，其材料格中的材料就能被消耗，我们就能卖物品给它了；

·将一个物品卖给一个工作台，可以促进该工作台的生产，工作台生产又带来两方面的好处：1、已有的材料被消耗，可以将更多的材料卖给它；2、生产出的产品可以被进一步卖给其他工作台促进物品7的合成（如果工作台的类型为4、5或6的话）。

为了体现以上这些考虑，我们实现了以下代码所示的任务估值函数：

代码中，direct_profit 表示买卖物品带来的直接收益，unblockxing_profit表示消除阻塞带来的间接收益，sell_profit表示将一个物品卖给给定工作台能够带来的间接收益，以下我们给出计算sell_profit的方法：

将物品卖给工作台后，会导致工作台消耗材料进行生产，这样材料格就会空出，可以收购新的物品，这就带来一个间接的收益，我们此处用erase_profit表示。如果我们是将物品卖给类型为4、5或6的工作台，还能促进合成4、5、6，进而促进合成7。我们通过estimate_product_profit()函数计算在当前状态下合成4、5或6能带来的收益，此处用progress_profit表示。接下来再看下estimate_product_profit()的实现：

estimate_product_profit()计算将一个类型为4、5或6的物品卖给工作台7或9所带来的收益，该收益类似于前面由direct_profit、erase_profit和progress_profit三部分组成，选择三者和最大的返回。

寻路算法

我们将地图分为0.25*0.25的格子，考虑水平线和垂直线的交点（而不是格子的中心点），我们将这样的点称为格点。注意到，根据赛题设置，一开始所有工作台和机器人的中心都落在某个格点上，一个障碍物的四个角都各是一个格点。此外，前面提到过，有些工作台中心机器人是无法到达的，但机器人不必到达工作台中心就能进行买卖，我们可以通过选择一些距离工作台中心距离小于0.4米的点作为一个工作台的代表点来解决这个问题。实际实现时，我们选择了4个距离工作台中心距离为0.35米的点来作为代表点。寻路时，只要机器人能够到达代表点中的任何一个，就可以认为机器人能够到达对应工作台。

在我们的实现中，机器人每帧都会进行寻路，寻路时只考虑八个方向的移动，求出最短路径，然后计算该路径上机器人能直接到达的最远点，控制机器人向该点移去。

让路算法

让路算法分为碰撞检测和寻找避让点两步。每一帧，由于我们都重新调用了寻路算法，我们可以根据计算得到的路径预测机器人是否会碰撞，如果预测会碰撞，我们让优先级低的机器人寻找一个避让点移动过去。避让点的计算方法为：从机器人所在位置进行BFS搜索一个可达的且不靠近要避让的机器人的路径的点。如果一个机器人无法找到避让点，则会提升其优先级以让对方来避让。

运动控制

运动控制这边需要用到一点基础的物理知识。设机器人当前在点A，其最大加速度为a（可以通过赛题所给参数计算出a），我们希望移动到并刚好停留在点B，假设机器人现在已经朝向B，那么当前帧机器人的速度应该设置为多少呢？首先我们希望该速度尽可能大，这样机器人能够快速到达B，但速度又不能太大以至于我们无法在B处刹住车，因此我们所要的速度应该满足：当以最大加速度a减速时，能够在到达B前刹住车。设AB间的距离为s，则容易计算出该速度为sqrt(2as)。类似地，如果我们想让机器人旋转theta度，设角加速度为alpha，则将角速度设置为sqrt(2 * theta * alpha)。

最终我们的运动控制如下：每一帧我们都计算机器人当前朝向与到目标点的方向的夹角theta，如果theta大于一定阈值，则将速度设置为0，按照上述方式设置角速度校正方向；如果theta小于一定阈值，则按照上述方式设置速度和角速度。

总结

此次软挑，我们队并非一帆风顺，初赛险遭淘汰，复赛正式赛前还在修复严重的bug，决赛练习赛阶段排名也不靠前，但好在有惊无险，我们最终拿到了总冠军。我认为我们取胜的关键在于我们设计的算法比较有通用性，没有过分拟合数据集，因此能够在复赛正式赛和决赛正式赛更换数据集后取得不错的成绩。