2023 华为软件精英挑战赛，全球总决赛亚军赛队分享解题方案

日前，2023第九届华为软件精英挑战赛-“普朗克计划”全球总决赛及颁奖典礼圆满落幕。大赛吸引了来自全球645所高校、3887支队伍、23078名大学生报名参赛，历时一个多月的激烈角逐，经过八大赛区区域初赛、区域复赛、全球总决赛等环节的层层考验。最终，9支优秀队伍凭借优异表现分享了66万元总奖金池。其中，武长赛区来自中南大学的“比赛周期怎么这么长”队获得全球总决赛亚军。作为软挑老兵，来自中南大学的优秀选手唐京撰文分享其赛队参赛体验，包括参赛初衷、解题思路及方案、比赛收获等。

图左二为唐京

比赛初衷

作为软挑老兵，去年参赛队伍“AAAAAA”的一员我和另外一位队友一起获得了2022年软件精英挑战赛决赛旅游奖。在旅游的同时也留下了不小的遗憾，于是今年决定再战一回。

赛题介绍

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

今年的软挑题目比以往的更加复杂，除了对算法具有较高的要求以外，还需要极为复杂的细节实现。

方案

我们的方案由调度、移动、防守、攻击等策略组成。

·调度

版本八

首先定义7号生产线由一系列的工作台组成，这些工作台能够完整的生产出7号物品并卖出。

决赛正式赛前夜，通过总结之前若干个版本的调度的不足，我们认为当地图中存在7号生产线时，调度策略应尽可能达到以下要求：

1.7号生产线上，物品4,5,6的生产应该尽可能均衡。

2.顺路原则，要卖出一个工作台上的物品，最好带一个物品过来放入它的材料格再卖出这个物品。

3.避免拥挤，不要让太多的机器人前往相同的工作台。

4.处于7号生产线上的1,2,3,4,5,6物品尽量不要卖给9号工作台。

5.当一些工作台上已经集齐了一些原材料，优先考虑塞满这些工作台的原材料格。

6.机器人的每单位移动获得的利润越大越好。

于是有了我们的核心调度代码，以利润除以距离为基础分数（为了防止距离过近时该式子的值过大，给距离加上了一个常数10），根据上面总结的规则来调整分数的权重，机器人会选择分数最大的任务去执行：

工作台拆点

为了使机器人在工作台处的移动更加精细，我们对工作台做了特殊处理。首先，在以工作台为中心，0.4为半径的圆内，在八个方向上每隔0.05米增加一个采样点。然后将工作台 P 附近的采样点按如下规则划分成五个集合：设采样点为 Q，向量PQ的坐标为 (x, y)。

在购买物品时，我们会将机器人导航到我们需要的区域再进行购买，这个方法能够解决复赛练习赛图3在瓶颈处工作台上方购买后绕路的问题，当然，对于那张图，需要经过计算后额外采样一些更远的点来达到这个目的。

地图点采样

根据机器人半径的设定，可以发现#..#这种格子能够让一个半径0.45的机器人恰好从中间两个格子的分界线通过，而#...#这种格子能够让一个半径0.53的机器人恰好从中间格子的中间通过，因此我们将棋盘划为成201*201的形式，所有线段的交点为棋盘采样点：

由于我们机器人导航用到了A*算法，而201*201的划分会导致采样点高达原棋盘的四倍，而实际上并不需要用到这么多采样点，我们在201*201的棋盘上进行了隔点采样，并针对一些特殊情况做出了处理，使得采样点数达到至多一万，平均只有几千的级别：

特殊情况特征：

7*7或5*5的矩形（也可以是下述情况的旋转），CD至少有一个为.，Z可以替换为任意字符，格子中心替换为X。

·移动

我们初赛采用简单旋转加移动。初赛正式赛结束后发现这样碰撞损失过高，又在复赛开始前实现了DWA算法，达到了初赛地图上几乎无碰撞的效果。复赛开始后发现DWA算法失效了，在QQ群窥探到有大佬使用ORCA算法达到非常好的效果，于是我们在复赛练习赛花了很多天实现了ORCA算法，并调整了一些参数达到了不错的效果。

我们的路径规划算法采用最短路预处理+局部导航机制+Astar 算法相结合的方式，每一帧都用 Astar 算法计算出每个机器人到目标点的路径，并找到最后一个可以不经障碍直线到达的路径点移动过去。

在复赛时，由于没有可移动障碍（即敌方机器人）的存在，我们仅使用最短路算法事先预处理好路径。而决赛加入了移动障碍后，我们加入了 Astar 算法。

在 Astar 算法中，我们考虑了敌方机器人和障碍的距离惩罚，距离越大，惩罚越大，这会使我们的机器人稍微绕一下路，但是尽可能地减少了与敌方机器人和障碍的碰撞，也使得我们的机器人在被敌方机器人追逐时显得十分灵活。

在 Astar 搜索过程中，我们减少了敌人的半径，这使得我们在一些极端情况也能避开敌人，机器人看起来会非常灵活。

局部导航用来为机器人规划一个局部目标，机器人会认为从当前位置到局部目标一定是可达的（不会与任何物体碰撞），ORCA算法会驱动机器人向局部目标进行移动。局部导航带有一定的避让策略，当A*搜索不到路径时，会启用局部导航作为保底机制。

·进攻

我们分为两种进攻型机器人，一种进攻型机器人直接追着敌人跑，在运气好的情况下能达到卡死敌方运输型机器人的效果。

另一种是防守型，防守型机器人会占用敌人7号生产线上的同类工作台，从而达到阻断敌人的7号生产线的效果，防守型机器人在一些狭窄的工作台附近效果非常好（这部分实现得不够好，导致在对战时浪费了两个蓝色机器人但没有达到阻断敌方7号生产线的效果）。

·防守

在路径上避开敌人的工作由A*算法完成，但会存在一些敌人站在我方的工作台不动，且难以撞开。因此在尝试到一些工作台无法到达时，我们会将这个工作台禁用一段时间，当禁用结束后再尝试仍然无法到达工作台，我们会将工作台的禁用时间翻倍... ...

我们将工作台分为了三类，用一个变量rushAble表示。rushAble=0表示工作台位于墙角，当敌人处于这样，我方机器人难以将器撞开。rushAble=1表示能够将敌人撞开，但进入这样的工作台有被敌人卡死的风险。rushAble=2表示这样的工作台附近是空旷的，可以被状态，并且不存在被卡死的风险。在进入rushAble<= 1的工作台，如果周围有敌人能使得我方机器人卡死，则机器人会被禁用购买任务，防止机器人购买了物品但卖不出去（如果买了一个物品7没有卖出去，很可能成为PK赛中决胜的关键）。

有时候机器人难免会被敌人卡住，我们设置了卡死判定机制，并且采用低速旋转+全速移动让机器人脱离被卡死的状态。

总结

此次软挑，我们队并非一帆风顺，复赛险遭淘汰。在复赛的前一天的时候，我们三个才第一次真正的开始讨论，在此之前各自都有各自的想法以及解法(此处必须要感谢我们武长赛区工作人员，中午一点给我们联系自习室，晚上12点还在熬夜关注我们)。终于，在距离复赛只有9个小时的时候，我们找到了一个新的解法并且帮助我们晋级了决赛。决赛前一晚，我们在测试2p和4p地图以及一些自制地图时，突然发现了代码里存在一万个bug(当时待解决问题的列表列了十项有余，还有几个要新加的策略)，于是我又拉着我的两个队友开肝，其实当时已经心态有点不稳了，好在队友们互相都没给压力，互相没有怪罪(虽然嘴上说着没拿奖有这个过程也很值得，但是其实心里想的都是必须拿奖)。于是我们开启了第n个通宵。尽管第二天的正式赛我们策略还是出现了失误，但好在付出有了回报。 这次软挑，可以说有笑有泪，有成长有沉淀，有认识志同道合的新朋友，更有旧友重逢。这次与以往不一样，我们三个真正感受到了团队三个人的力量，少了任何人都无法拿到亚军。非常感谢武长赛区工作组对我们的关心和鼓励，更要感谢张元龙老师等赛题组专家对我们时时刻刻每件事情都有回应，当然最感谢的还是我们三个一起熬过的每一个夜，和多少次凌晨因为想到了新想法爬起来的自己。希望未来的旅途能再与软挑相遇！