华为软挑赛2023-初赛笔记

前言

比赛介绍

官方链接: 2023华为软件精英挑战赛——普朗克计划 (huaweicloud.com)

赛题介绍

场景介绍

官方赛题介绍: 2023华为软件精英挑战赛初赛赛题及相关材料发布_2023华为软件精英挑战赛_华为云论坛 (huaweicloud.com)

比赛场景如图所示
在这里插入图片描述

简单来说，在一张50m*50m的地图上，分布着许多固定的工作台和可以移动的机器人（4个）。机器人通过前进，后退，旋转等操作进行移动，当移动到工作台后，可以购买产品、出售产品，此外在携带产品时可以随时销毁产品。

开始时，系统会基于一笔初始资金（20万），通过调度机器人在各个工作台之间进行购买、出售产品，从而赚取差价获利。不同的产品购买和出售价格不同，可获取的利润也不同，且有的产品必须基于其他产品作为原料才可以生产。各类产品的购买和出售价格以及合成路线如下表所示：

在这里插入图片描述

此外，物品的价值会随着时间的流逝和机器人与其他机器人或墙壁的碰撞而减少，因此应当以尽快的速度卖出物品并尽量减少碰撞。

输入输出

本次比赛最大的两点就是把判题器直接提供给了选手下载，给了选手更方便灵活的本机测试机会。

判题器与用户之间通过标准输入输出进行交互，每一帧判题器都会向选手程序更新地图和机器人状态，选手需要根据当前状态，决定每个机器人的输入输出。

比赛心得

首先，首次参赛，三位队友也是首次组队的情况下（实验室还有一堆其他任务，以及有人生病等一系列客观原因），能走到决赛也属实不易，但这其中也多多少少有些运气因素。

经验教训方面，主要总结了一下几点：

有严格时间限制的这类比赛，尽量避免使用python，虽然初赛的计算量，使用python的游刃有余，但随着比赛难度的增加和我们新功能的加入，python这种龟速语言就显得力不从心了，以至于复赛时我们不得不选用效果更差但事件复杂度更低的方法，决赛时我们一半的时间都在掉帧。
在没有什么试错成本的前提下，要勇于尝试。比如我们在初赛的最后一晚疯狂调参提交，硬生生调出了10万多分，而之前的时间基本没怎么提交，白白浪费了每天的提交次数。又比如，官方服务器提供了两核的计算资源，但我们想当然的认为这两个核一个是给选手程序用另一个是给判题器用的，而实际上选手两个都可以使用（虽然因为GIL的原因，很难充分利用双核）。
1%的特殊情况往往要复出99%的努力去解决。一个简单的Demo可能在大多数情况下可以良好运行，但一旦遇到特殊情况无法处理会导致整个系统崩溃，例如两个机器人没有避让时迎面对撞，不但使两个机器人失去生成能力，也使得他们的目标工作台无法被使用，之后很难再得多少分。
一个好的调试方法真的能大幅提高效率。这方面Python有些优势，相比如静态语言，它可以在调试时动态执行新的代码，可以更快的定位错误。
加强代码规范，善用git（也有慎用git，有次失误差点将一天的代码都清空了），拒绝屎山。
快速实现一个demo并在此基础上优化提升远比花太久的时间空想一个看似更好的算法有效。

代码介绍

整体思路设计

整体上可以分为机器人的运动和决策两大部分。运动主要包括机器人的移动、路径规划、避障和死锁解除等功能。决策需要协调不同机器人的买卖方案，最大化利润。

架构设计

我们整体采用面向对象的思路，将划分为机器人、工作台和整体决策类，之后又根据需求衍生出放置类型无关函数的tools类，和用于动态调参的network类。

由于初赛时尝试使用向量化加速，因此实际上将所有机器人或工作台都作为了一个二维矩阵，每个机器人或工作台是其中的一行，并定义了一系列静态变量以便于索引。但实际体验下来效率没有得到提升，反而因为频繁的int和float转化拖慢的执行速度，于是代码在复赛时用传统的面向对象方式进行了重构。

机器人类设计

除了官方判题器提供的交互信息外，机器人类还包含以下成员变量。

status: 机器人状态，机器人行为决策的基础，具体包含以下几个状态
1. 空闲状态：当前无任务，可以进行决策
2. 购买途中：前往目标工作台购买物品的途中
3. 等待购买：已经到达目标工作台，等待购买物品
4. 出售途中：完成物品购买，前往目标工作台出售物品
5. 等待出售：已经到达目标工作台，等待出售物品
状态转移图如下，考虑到机器人等待购买和出售时有可能由于运动控制或其他机器人碰撞等原因超出工作台的可交互范围，因此等待状态有可能重新切换到移动状态。
target: 机器人当前目标工作台，运动控制使用
target_buy：机器人要前往购买物品的工作台
target_sell：机器人要前往出售物品的工作台

工作台类设计

除了官方判题器提供的交互信息外，工作台类还包含以下成员变量。

一些类变量，用于存储每类物品的出售和购买价格以及每类工作台的收购和产出情况。
material_pro: 材料格预定，防止多个机器人同时要把商品卖到此工作台造成死锁。
product_pro: 产品格预定，防止多个机器人同时要到此工作台购买商品造成死锁。

控制类设计

控制类是本代码的核心部分，我们将所有的控制和决策相关内容都在控制类中实现。

成员变量主要包括一些决策参数和运动模型参数具体将在下一节展开。

核心方法包括:

control: 控制核心函数，每帧调用一次，用于维护机器人的状态和控制机器人的运动。
choise: 决策核心函数，机器人空闲时调用，为当前空闲机器人分配一个任务。
move2loc_new: 运动控制核心函数，控制机器人的转向、移动、避撞等。

策略模型设计

如果机器人只有一个的话，可以建模为旅行商问题，但四个机器人的情况实在过于复杂，因此只实现了一个简单的贪心算法，后续又在这个的基础上添加了一些参数优化。

最优生产模型

我们总是选择性价比最高的认为执行，性价比的定义如下：

性价比(ratio)=(售价（ $V_{sell}$ ）*价值系数( $Rate_{time}$ )-进价( $V_{buy}$ ))/总帧数(F)
$ratio=\frac{V_{sell}*Rate_{time}-V_{buy}}{F}$
对于一个买或者卖的行为，所需帧数与移动时间和物品准备时间有关。

进一步解释，买的时间就是移动到对应工作台和工作台生产时间的最大值，而买的过程中，卖的工作台也在生产，所以卖的工作台的等待时间应当减去买的过程的这段时间
$F_{buy}=max(f^{move}_{a,b},f^{wait}_{a,b})$

$F_{sell}=max(f^{move}_{b,c},(f^{wait}_{b,c}-F_{buy}))$

动作的总帧数： $F=F_{buy}+F_{sell}$

我们的模型中没有考虑碰撞因素，因为这是不可预知的。时间价值系数如下。
$Rate_{time}=\left\{\begin{matrix} \left [ 1-\sqrt{1-(1-\frac{F_{sell}}{9000})^2}\right ]*(1-0.8)+0.8 & F_{sell}<9000\\ 0.8 & F_{sell}>9000 \end{matrix}\right.$
关于移动时间的计算，我们选择使用距离去进行一次拟合。即： $f^{move}_{a,b} \approx dis_{a,b}*\theta$ （后面也试过理论上更好的拟合但结果更差了）

其中 $\theta$ 是我们的可调参数。

优化

经过观察，我们又在后序补充了以下优化方案：

由于高级产品利润很高，故会有机器人在长时间等待高级产品生成，以至于这段时间完全足够进行一些其他生产活动，于是我们通过参数限制机器人的最长等待时间。
需要鼓励机器人去尽量生产高阶产品，因此把原材料123直接买个89而不是456会有惩罚。
当有个多个相同的工作台时，我们应该鼓励机器人优先把商品卖给已经有原料格被部分占用的工作台，这里有一个奖励参数。
最后时刻有可能会有机器人买了商品而来不及出售而导致亏钱的情况，于是我们最后会判断剩余帧数是否足够出售，但这个判断往往不够准确，于是我们有添加了一个保守程度的参数，用于控制机器人最后时刻要不要操作。

最终的决策参数如下:

# 控制参数
MOVE_SPEED = 1 / 4.15 * 50  # 估算移动时间 4.1 4.2 相同
MAX_WAIT = 3.14 * 50  # 最大等待时间 3.15
SELL_WEIGHT = 1.45  # 优先卖给格子被部分占用的 1.43 1.45 相同
SELL_DEBUFF = 0.8  # 非 7 卖给89的惩罚
CONSERVATIVE = 1+1/MOVE_SPEED*4  # 保守程度 最后时刻要不要操作 比4.3和3.8好
BUY_WEIGHT = [1]*4+[1]*3+[1]  # 购买优先级，优先购买高级商品 比0.9和1.1好

运动模型设计

运动模型最开始使用了人工势场，即机器人和目标之间存在吸引力，机器人之间存在斥力，通过调节这些参数实现避撞。这一方案在练习赛阶段表现的很好，但到了正式赛阶段，因为地图的设计使得机器人之间会有完全相对前进的情况，机器人之间的斥力无法是机器人避免碰撞，因而导致了对撞死锁的情况。人工势场在对撞时表现不好的原因如下图所示。

在这里插入图片描述

为此，我们的运动模型中添加了碰撞预测方案，当预测要发生碰撞时，会根据条件指定一个机器人避让

另外，运动模型中也有一些优化方案：

平滑控制，距离目标越近时速度越慢
适当条件下倒车而不是转向再前进
等待工作台生产的过程中可以提前转向

其他补充

经过我们的观察发现，不同地图的最优参数是不同的。虽然规则里没有禁止，但我们总觉得直接硬编码地图调参可能会被当成作弊。（实际好多其他队伍都有针对性调参，甚至出现了直接输出序列的情况，万幸我们所在赛区没有那么卷，否则我们可能初赛就无法出线了）

为此我们想到了使用神经网络调参的方案。在初版的方案中，我们直接把整张地图当成了输入，输出是策略的6个参数。但官方禁止上传非python文件，于是我们使用了将权重文件直接写入python文件的放置。

由于python的格式和json的格式完全兼容，我们只需要将list json化写入py文件，读取时之间import即可。

def save(self, weight_path='src/weight.py'):file = open(weight_path, 'w')file.write(f'W1 = {json.dumps(self.W1.tolist())}\n')       file.write(f'W2 = {json.dumps(self.W2.tolist())}\n')file.write(f'W3 = {json.dumps(self.W3.tolist())}\n')file.write(f'b1 = {json.dumps(self.b1.tolist())}\n')file.write(f'b2 = {json.dumps(self.b2.tolist())}\n')file.write(f'b3 = {json.dumps(self.b3.tolist())}\n')file.close()def weight_loader(self):import weight as weightsself.W1 = weights.W1self.W2 = weights.W2self.W3 = weights.W3self.b1 = weights.b1self.b2 = weights.b2self.b3 = weights.b3