第一次参加华为软挑，问了周围一圈人没人组队，看了眼题目，感觉挺有意思的，就打算自己写来跑一下，不求分数，主要是想学点东西，顺便记录一下。（最后跑了195w+，自己的能力也就到这了）菜 捞捞
@[toc]

1. 题目概述

本次比赛模拟了多机器人的运行环境以及真实机器人的状态信息。选手需要操控4个机器人执行前进、后退、旋转、购买、出售等动作来完成物品递送任务，同时赚取差价获得利润。在3分钟时间内，选手最后拥有的资金数（初始200000）即为最终分数，所获资金越高越好。
比赛官方术语说明
篇幅有限，题目就介绍到这里了，还有很多细节方面的介绍没写出来，想了解具体题目的朋友可以自行百度搜索也可以私信我。

2. 输入输出 & 判题流程

选手程序与判题器交互过程
大致流程如图，我们需要和判题器进行多次交互，判题器负责发送地图数据以及每一帧的信息（场上机器人、工作台的实时参数），我们需要给判题器发送机器人控制指令，双方都以”OK”来作为信息发送的结束标志。来结合官方给的demo代码来理解一下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import sys
def read_util_ok():	
    while input() != "OK":  #从标准输入中读取一行数据直至读到"OK"
        pass


def finish():
    sys.stdout.write('OK\n')  #选手发送"OK"指令
    sys.stdout.flush()


if __name__ == '__main__':
    read_util_ok()	#此处为读取地图数据
    finish()	#选手发送OK表示已接收到地图数据
    while True:	#循环直至时间结束
        line = sys.stdin.readline()	#读取第一行（为帧序号以及当前金钱数）
        if not line:	#3分钟倒计时结束后判题器不再发送任何信息
            break
        parts = line.split(' ')
        frame_id = int(parts[0])	#获取当前帧序号（1-9000）
        read_util_ok()	#继续获取剩余行数据
#以下是官方写的一部分操作（其实就是让机器人原地旋转...）
        sys.stdout.write('%d\n' % frame_id)
        line_speed, angle_speed = 3, 1.5
        for robot_id in range(4):
            sys.stdout.write('forward %d %d\n' % (robot_id, line_speed))
            sys.stdout.write('rotate %d %f\n' % (robot_id, angle_speed))
        finish()	#选手发送"OK"表示控制命令结束

3. 思路分析

这是一个多对象多决策的程序，涉及到机器人运动学和运筹学，对我来说都是全新领域，只能从头开始探索了。我打算化繁为简，先关注以下几个问题：

  • 如何构建地图网络？如何分析判题器发送给你的数据？
  • 如何让机器人移动（前进后退旋转）到指定工作台？
  • 如何设计寻路、调度策略使得资金最大化？

这几个问题是最基本也是最核心的问题，不过光想没有用，一定要结合本地地图数据和判题器来进行模拟调试，才知道具体的交互过程是怎么样的。

小弟使用VSCode来进行程序编写，由于是需要通过外部判题器来执行python程序，因此调试需要将python附加到具体的判题器进程中，才能够断点debug，可以参考：
VSCode Python程序附加到进程debug

4. 详细分析

4.1 地图类构建以及读取地图、更新场上信息

我考虑的是先构建一个全局控制的类，记录地图信息，包括机器人和工作台的各种信息等，通过这个类可以读取到任何物体的所有信息，我取名为Map类：

1
2
3
4
5
6
7
8
9
10
11
12
class Map():
    def __init__(self):
        self.worktable_num = 0	#工作台总数
        self.robots = []	#机器人实体（按地图初始读入顺序排序）
        self.worktables_list = []  # 工作台实体（按地图初始读入顺序排序）
        
        #每种类别的物品当前时刻可以添加到指定工作台的编号，如1:[2,4,6]表示编号2、4、6号工作台当前原材料需要1号物品
        self.wt_to_be_added = {1:[], 2:[], 3:[], 4:[], 5:[], 6:[], 7:[]}	
        #原材料工作台已生产出成品的编号，如[2,4,6]表示第2、4、6号工作台当前已生产出原材料（1-3号的一种）
        self.wt_to_be_purchased_123 = []
        #加工工作台已生产出成品的编号，值含义同上
        self.wt_to_be_purchased_4567 = []

当然，还得创建机器人和工作台两个类，顾名思义，类里面记录他们所有参数信息以及定义了一些功能函数（比如机器人的移动、工作台的判断机制等）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#篇幅所限，不把全部的代码粘上来了
class Robot():
	def __init__(self):
		self.id = -1
		self.on_task_dest = -1	#当前去往的工作台编号
		self.task = 0	#当前执行任务的信息：1 buy, 2 sell, 3 destory
		#还有机器人的位置、运动参数等属性不一一列出了
    def forward(self, line_speed):
        sys.stdout.write('forward %d %f\n' % (self.id, line_speed))
    def rotate(self, angle_speed):
        sys.stdout.write('rotate %d %f\n' % (self.id, angle_speed))
    def buy(self):
        sys.stdout.write('buy %d\n' % self.id)
    def sell(self):
        sys.stdout.write('sell %d\n' % self.id)
    def destroy(self):
        sys.stdout.write('destroy %d\n' % self.id)
class Worktable():
	def __init__(self):
		self.id = -1
		self.on_task_robot = -1	#当前占用此工作台的机器人编号
		self.get_info(type)
		#还有工作台的位置、生产状态等属性不一一列出了
	def get_info(self, type):	#通过工作台的类型来初始化一些信息（如需要的原材料类型、生产出来的物品类型、工作周期等等）
		pass

看了一眼地图，是100行*100列的txt数据，里面工作台用数字1-9表示，机器人用A表示，其余区域用.表示。直接写个函数循环读取就完事了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def read_map():
    map_info = Map()	#创建Map对象
    row = 0
    worktable_num = 0
    robot_count = 0
    while True:	#按行读取
        col = 0
        line = input()
        if line == "OK":
            map_info.worktable_num = worktable_num
            return map_info	#返回初始地图信息
        for char in line:
            if char >= "1" and char <= "9":	#工作台
                worktable = Worktable(int(char))
                worktable.id = worktable_num	#跟判题器发送的顺序同步，即按照地图读取的顺序依次给工作台编号
                worktable.loc = np.array([0.25+col*0.5, 49.75-row*0.5])	#中心点坐标
                map_info.worktables_list.append(worktable)
                worktable_num += 1
            elif char == "A":	#机器人
                robot = Robot()
                robot.id = robot_count
                robot.loc = np.array([0.25+col*0.5, 49.75-row*0.5])	#中心点坐标
                map_info.robots.append(robot)
                robot_count += 1
            col += 1
        row += 1

地图创建好了，接下来就可以正式开始读取每一帧的数据了，我最后的主函数是这个样子的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
if __name__ == '__main__':
    map_info = read_map()	#接受返回的地图读取数据信息
    finish()
    while True:	#读取每一帧信息
        line = sys.stdin.readline()
        if not line:
            break
        parts = line.split(' ')
        frame_id = int(parts[0]) #帧序号
        map_info.money = int(parts[1])
        read_util_ok()	#读取剩余信息
        sys.stdout.write('%d\n' % frame_id)
        task_manager()	#任务分配函数
        action()	#命令控制函数
        finish()

这里的逻辑其实挺简单，地图数据读取完后，开始读取每一帧的数据，我是想着4个机器人，要在这么多个工作台之间往返，进行多种操作，那必须得有一个总的任务分配机制，用于调度具体的机器人去哪一个工作台干什么，所以写了一个task_manager()。分配完成以后，action()函数就是用来根据具体任务来控制机器人的移动的，然后这一帧就结束了。
且慢， 我们先来看看read_util_ok()里面写了啥：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
def read_util_ok():
    while True:
        worktable_total = int(input())
        for worktable_id in range(worktable_total):	#先遍历每一个工作台
            line = input()
            parts = line.split(' ')
            map_info.worktables_list[worktable_id].remaining_time = int(
                parts[3])	#剩余生产时间
            map_info.worktables_list[worktable_id].raw_material_status = bin(int(parts[4]))[
                ::-1][:-2].ljust(8, "0")	#原材料格状态
            map_info.worktables_list[worktable_id].production_status = int(
                parts[5])	#产品格状态
            # 更新空闲工作台（待添加材料or待被购买成品）
            if map_info.worktables_list[worktable_id].on_task_robot == -1:	#-1指当前工作台没有被机器人占用
            	#先更新待添加材料的工作台（也就是4-9号）
                if parts[0] not in ['1', '2', '3']:
                    map_info.worktables_list[worktable_id].to_be_added()
                #再更新待被购买成品的工作台（这里4-7号优先级高于1-3号）	
                if parts[0] in ['1', '2', '3']:
                    if worktable_id not in map_info.wt_to_be_purchased_123:	#先判断是否已经在待购买的列表里了（其实这里也可以用set之类的确保不重复）
                        if map_info.worktables_list[worktable_id].to_be_purchased(): #判断是否可以购买了
                            map_info.wt_to_be_purchased_123.append(worktable_id)
                elif parts[0] in ['4', '5', '6', '7']:
                    if worktable_id not in map_info.wt_to_be_purchased_4567:	#含义同上
                        if map_info.worktables_list[worktable_id].to_be_purchased():	#含义同上
                            map_info.wt_to_be_purchased_4567.append(worktable_id)
        for robot_id in range(4):	#再遍历每一个机器人
            line = input()
            parts = line.split(' ')
            map_info.robots[robot_id].worktableID = int(parts[0])	#所处工作台ID
            map_info.robots[robot_id].goods_type = int(parts[1])	#携带物品类型
            map_info.robots[robot_id].time_coef = float(parts[2])	#时间价值系数
            map_info.robots[robot_id].collision_coef = float(parts[3])	#碰撞价值系数
            map_info.robots[robot_id].angle_speed = float(parts[4])	#角速度
            map_info.robots[robot_id].line_speed = (
                float(parts[5]), float(parts[6]))	#线速度
            map_info.robots[robot_id].orientation = float(parts[7])	#朝向
            map_info.robots[robot_id].loc = np.array(
                [float(parts[8]), float(parts[9])])	#坐标
        line = input()
        if line == "OK":
            break

其实就是读取每一帧工作台和机器人的实时信息。需要注意的是，工作台这边有一个原材料格状态是用二进制位表来描述的，为了方便读取状态，我这里每个工作台统一初始化状态为：

1
2
class Worktable():
	self.raw_material_status = '00000000'

因为原材料物品只有1-7，为方便操作，0号位就空出来，1-7号位分别代表1-7号物品的状态，0是待添加，1是已添加 （注意要对应具体类型的工作台需要的原材料类别）
工作台类型说明
到此为止，我们已经把每一帧场上的信息读取完成并更新了，当然，上面贴的代码是最终的版本，刚开始写肯定没有这么复杂，尤其是工作台那几个判断…

4.2 任务分配机制

这一步是整个比赛最关键的两个步骤之一，小弟不才，感觉这一步应该有很多很牛的分配调度算法，这里我只讲讲我自己的想法吧~

首先前面在读取每一帧信息后，其实我已经把空闲工作台放列表里了（其实严谨一点应该用队列，官方除了numpy不让调其他库，故只能用list简单模拟一下queue），对于每一个空闲的机器人，你无非就只能给它分配三个任务：
1. 去工作台购买材料，前提是机器人手上没有物品且该工作台已有成品；
2. 去工作台出售材料，前提是机器人手上有物品且该工作台原材料格对应的材料状态为”0”；
3. 销毁机器人当前手中的物品。

对于第1个任务，高级一点的算法可以计算机器人到工作台的距离和剩余生产时间的关系，比如差不多生产完了机器人就可以直接出发等等，但是对我来说太复杂了于是就把这个过程简化了，即当工作台产品格状态为”1”时，我才会让机器人出发去购买。
当分配了购买材料的任务后，需要马上进行以下信息的更新：

①将该工作台从待被购买列表中移除，即self.wt_to_be_purchased_123 or 4567；
②更新机器人当前去往的工作台编号，即self.on_task_dest；
③更新机器人当前执行任务的信息，即self.task = 1；
④更新工作台当前被占用的机器人编号，即self.on_task_robot

对于第2个任务，先看看机器人手上拿着什么物品，然后去对应的工作台队列提取一个空闲的出来，因此在机器人类里面，我写了一个映射的函数，即机器人持有物品类型应该去哪几个工作台出售：

1
2
3
4
5
6
def get_optional_wt(self):
        ori_material = [0, 1, 2, 3, 4, 5, 6, 7]	#持有物品类型
        optional_worktables = [
            [], [4, 5, 9], [4, 6, 9], [5, 6, 9], [7, 9], [7, 9], [7, 9], [8, 9]
        ]	#对应的可选择工作台（0号位置空）
        self.optional_wt = optional_worktables[ori_material[self.goods_type]]

注意，还需要判断这个空闲的工作台是否真的“空闲”，即原材料格对应物品的状态为”0”。如果遍历完所有工作台没有符合的，则更改为第3个任务，即销毁，在下一帧重新进入空闲池，重新分配任务。只需要将self.task赋值为3即可。
否则，当分配了出售物品的任务后，需要马上进行以下信息的更新：

①将该工作台从待被购买列表中移除，即self.wt_to_be_added；
②更新机器人当前去往的工作台编号，即self.on_task_dest；
③更新机器人当前执行任务的信息，即self.task = 2；
④更新工作台当前被占用的机器人编号，即self.on_task_robot

可以看到，同一个工作台只能被一个机器人占用，占用结束后（出售完成or购买完成）才能被其他机器人占用。我知道这样子效率肯定大打折扣，但目前来说，可以先这样子执行，后面有时间可以进一步优化，毕竟如果同时有多个机器人占用工作台，可能会出现大量机器人聚集在同一个工作台附近，无法操作~

4.3 控制机器人移动、执行任务和重置

这一步同样是非常重要的一步，涉及到大量的有关物理引擎方面的知识，网上也有很多现成的算法可以拿来用，不过我还是选择先自己研究一下~
机器人控制运动指令
通过replayer大量回放，我发现当输出一个指令时，比如forward，机器人的速度不是突变的，而是在极短时间内通过恒定加速度从初速度$V_0$变到末速度$V_t$，再去看一眼官方文档，可以发现：
在这里插入图片描述
机器人一些属性定义
有最大牵引力这么一个玩意，这就说明机器人从$V_0$到$V_t$所经过的位移其实是要用积分去算的…哈哈，此处忽略，尽可能简化！我们先来看看机器人最大加速度是多少（如有计算错误请在评论区指出，感激不尽！)。

物体质量 = 面积*密度，即$m=\pi R^2\times\rho=12.72kg$（未携带物品）or $17.65kg$（携带物品）；
$F=ma$，不考虑阻力，则$F$为牵引力；
$a_{max}=F_{max}/m=19.65(m/s^2)$ （未携带物品）or $14.16(m/s^2)$（携带物品）

加速度有啥用呢？比如机器人正全速朝一个工作台飞奔过去，当快到的时候，就可以算出当距离工作台还有多少米的时候可以开始减速以至于到达工作台的时候，速度降为0（或者低速，因为官方demo是低速经过工作台并完成买卖操作的，没有完全停下）。我们来考虑这样一个情况：

已知机器人初速度为$6m/s$，末速度是$0m/s$（模拟减速的过程）；
最大加速度为$-19.65(m/s^2)$ or $-14.16(m/s^2)$；
根据$V_t^2=V_0^2+2as$，机器人需要经过0.92米（未携带物品）或1.27米（携带物品）才能够停下来；
根据$V_t=V_0+at$，机器人停下来所需时间为0.31秒（未携带物品）或0.42秒（携带物品）

因此，我们可以预留1.27米以上的距离来让机器人进行减速，所需时长为16~21帧左右。

在看最大力矩之前，我们先来看看机器人导航的问题。一开始笔者以为需要用到类似迪杰斯特拉或者A*这一类的寻路算法，但后来发现由于地图没有障碍物，而且物理引擎模拟运动的时候朝向是可以360°的，因此可以简化问题，我们只需要算出机器人和工作台的航向角，就可以通过控制角速度让机器人转到合适的角度，然后全速直线前进！

因此，我写了一个计算两个物体之间距离以及航向角的函数，比较简单粗暴，大家可以先看看这位大佬的分析：https://zhuanlan.zhihu.com/p/612863940
航向角计算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def dist(ori, dest):	#ori是源坐标，dest是目标坐标
    dist = np.sqrt(np.sum(np.square(dest - ori)))	#欧式距离
    delta_x = dest[0] - ori[0]
    delta_y = dest[1] - ori[1]
    if delta_x * delta_y == 0:
        if delta_x:
            ori_to_dest_radian = 0 if delta_x > 0 else np.pi
        elif delta_y:
            ori_to_dest_radian = np.pi / 2 if delta_y > 0 else -np.pi/2
        else:
            ori_to_dest_radian = 0
    elif delta_x > 0:
        ori_to_dest_radian = np.arctan(delta_y/delta_x)
    elif delta_x < 0:
        tmp_radian = np.arctan(delta_y/delta_x)
        ori_to_dest_radian = tmp_radian + np.pi if tmp_radian < 0 else tmp_radian - np.pi
    return dist, ori_to_dest_radian

在这里，我列举出8个目标方位dest来计算和源坐标ori的关系，通过x和y维度距离差和arctan函数计算出源坐标朝向目标坐标的朝向角，结合图片看代码应该比较好理解。

至此，我们算出了朝向角α（弧度），通过每一帧的信息读取我们能获取每个机器人当前的朝向β（弧度），范围[-π,π]。接下来要算的就是怎么让机器人从β转到α，可以顺时针（角速度为负）转也可以逆时针转（角速度为正）。显然，为了时间效率，我们要算出朝哪个方向转用时更少：

1
2
3
4
delta_radian = dest_radian - ori_radian
	if abs(delta_radian) > np.pi:
		delta_radian = delta_radian + \
   		2 * np.pi if delta_radian < 0 else delta_radian - 2 * np.pi

当二者朝向弧度绝对值相差不超过π时，那么就取它原来的值，如果是正数就逆时针转，如果是负数就顺时针转。而如果弧度相差超过π时，我们就要算出朝另一个方向转相差的弧度，比如机器人当前面向y轴正方向（也就是90°，π/2弧度），工作台在它的左下角45°位置，即朝向角为225°（-3π/4弧度），此时二者相差弧度delta_radian为|-5π/4| > π，那么只需要让delta_radian加上2π也就是等于3π/4就行。即相同旋转速度下机器人逆时针旋转3π/4（135°）比顺时针旋转5π/4（225°）要更快。同理，当相差弧度delta_radian为正数时，就要让它减去2π。

根据角速度的定义，我们知道相差弧度，只需要将其除以时间就能够得到对应的角速度，但这个时间怎么确定呢？简单粗暴一点的方法是，由于一帧是0.02秒，那么我只需要让它在这0.02秒内旋转到我想要的方向就可以了呀！但是！ 别忘了前面提到的最大力矩，这其实是跟转动角加速度有关系的。（如有错误烦请指正）

记力矩为M，角加速度为β，I为转动惯量，则$M=I\times β$；
对于二维平面的圆形物体（当作薄圆盘），不考虑高度，则$I=1/2\times m\times r^2$. 其中m是物体质量，r是质点和转轴的垂直距离，此处为0.45米 or 0.53米。则$I=1.29 (kg\cdot m^2)$ or $2.48 (kg\cdot m^2)$；
最大角加速度为$β_{max}=M/I=38.76 (rad/s^2)$（未携带物品） or $20.16(rad/s^2)$（携带物品）

跟直线运动类似，我们也可以计算出调整角速度合适的时机。比如，机器人初始面向x轴正方向，现在要旋转到y轴正方向，所需旋转的弧度为π/2，如果用最大角加速度旋转，则需耗时0.28秒（未携带物品）或0.39秒（携带物品），等等。在这里我简化了旋转的场景，毕竟每一帧我都要判断当前朝向是否对着工作台，所以我就忽略了角加速度，统一以delta_radian / 0.02作为旋转速度，这样子的后果就是如果旋转的角度过大，会出现左右轻微甩头现象，会损失一定的时间。

因此我的逻辑就比较简单，首先判断机器人和朝向和目标朝向相差的绝对值是否大于π/2，若是，则低速旋转直至小于π/2（如线速度可以设置为$3.5m/s$）；如果小于π/2则设置$6m/s^2$的线速度。当离工作台距离还有1.27米的时候，设置线速度为$2m/s$，当离工作台距离小于0.4米时（进入可操作距离范围），线速度设置为$0.8m/s$，并执行买卖操作。

买卖完成后（如何确保完成？ 详见下方优化部分），我们需要重置一些参数：

①将机器人前往的工作台编号复位为-1，即self.on_task_dest = -1；
②将机器人当前任务复位为0，即self.task = 0；
对于任务1和2，还需要重置：
③将工作台被占用的机器人编号复位为-1，即self.on_task_robot = -1

至此，action()函数执行完毕，同时当前帧的所有操作已完成。通过以上步骤，能确保写出一个能跑分的程序，只不过分数比较低！

5. 程序优化与提升

显然，上述各个步骤都会选择性地忽略一些东西，这样会导致时间效率比较低，在这里，我们可以针对性地去优化一些问题以提升所获资金。

优化1、距离优先/利润优先原则

此优化用上了贪心的思想。在前面所述分配任务中，工作台待买卖队列是按照读取顺序依次加入的，因此机器人读取可选择工作台队列的时候也是相当于按工作台编号顺序依次遍历判断，这样就完全没有考虑距离和利润，导致机器人满图跑。

因此，在机器人遍历工作台的时候，我们不急着直接让第一个读取到的工作台出队，而是遍历完所有可用的工作台，然后进行一个距离远近排序和利润大小排序，可以给二者赋予相应的权重，然后类似打分机制算出综合距离和利润最优的那一个工作台（当然也可以直接相除，对利润/距离进行排序并选择值最大的那一个），让其出队，再分别改变机器人和工作台相应的各个参数就好啦！（比赛中我只考虑了距离）

缺点：时间复杂度变大了，但是只要保证主程序能在15ms之内跑完就没太大问题。

优化2、任务1和2合并

在初赛正式赛的时候，跑第4张图的分数特别低，于是打开replayer回放了n遍查原因，原来是因为地图里面有若干个6号工作台（生产6号物品），但收购6号物品的工作台只有1部7号工作台，无9号工作台，这就导致如果7号工作台中原材料格里面已经有6号物品了，那么当机器人手持6号物品时，会因为找不到可用的工作台，而执行任务3，也就是销毁（至少我的程序里是这么执行的，说不定可以写个等待函数之类的，但太复杂我就没研究了），而6号物品价值不菲，而且机器人很可能会在7号工作台进入生产周期之前多次购买6号物品并销毁，这就导致资金直线下滑…

所以，我重新架构了一下，将任务2与1合并，也就是说，我将待被购买工作台与待添加工作台捆绑在一起，比如编号1工作台生产2号物品，编号10工作台是类型6工作台，即收购2和3号物品作为原材料进行生产，当编号10工作台的原材料格子里面没有2号物品时，我将编号1和编号10进行捆绑。机器人分配去编号1工作台进行购买物品，当购买完成后，立即执行任务2，也就是前往编号10工作台出售物品。 这样就能避免当场上不需要某个物品时，机器人还硬要去购买的尴尬场面…

为了能体现出距离优先原则，编号1在捆绑编号10工作台之前，其实也是进行了距离排序的，比如当编号8、9、10工作台同时满足条件时，就会计算它们分别与编号1工作台的距离，距离最近的那一个才会与编号1进行捆绑。

当然了，由于这个改动比较大，因此不仅是task_manager()，action()部分也需要改动，这里就不放代码上来了，感兴趣的朋友可以私信我~

优化3、确保机器人已购买 or 已出售

理论上，只要不发生跳帧，是不用担心操作失败的，除非你允许两个及以上机器人对同一个工作台进行操作，那可能会发生冲突。

可以写一个check函数，并设置一些变量，比如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def check(robot_id):
    if map_info.robots[robot_id].on_task_dest > -1:	#空闲机器人跳过此步骤
        if map_info.robots[robot_id].task == 1:    # buy
            if map_info.robots[robot_id].goods_type == map_info.worktables_list[map_info.robots[robot_id].on_task_dest].production:
                reset(robot_id)
                return True
            else:
                map_info.robots[robot_id].task = 3
                return False
        elif map_info.robots[robot_id].task == 2:  # sell
            if map_info.robots[robot_id].goods_type == 0:
                reset(robot_id)
            else:
                map_info.robots[robot_id].task = 3	# destroy
            return False
  • 判断机器人已完成购买操作：购买完之后的下一帧判断机器人携带物品类型是否等于对应工作台生产物品的类型。若相等则进入重置函数reset（见上），否则销毁；
  • 判断机器人已完成出售操作：出售完后的下一帧判断机器人携带物品类型是否为0，即没有携带物品。若是则进入重置函数reset（见上），否则销毁。

优化4、碰撞监测

机器人难免会发生碰撞，我就试过多次两个机器人对撞而且还保持不动了（因为质量相同且朝向刚好相差π…），所以一定要有碰撞监测函数（成熟的算法很多，比如TEB和DWA），命名为collision_detect()，在action()函数输出机器人线速度和角速度之前，执行碰撞监测：

1
2
3
4
5
6
7
8
9
def collision_detect(robot_id, delta_radian, line_speed):
    for i in range(4):
        if i != robot_id:
            d, _ = dist(map_info.robots[robot_id].loc, map_info.robots[i].loc)
            if d < 2.12 and \
                abs(map_info.robots[robot_id].orientation) + abs(map_info.robots[i].orientation) > np.pi / 2:
                delta_radian = (delta_radian + (robot_id + 1) * np.pi / 4) % np.pi - np.pi
                break
    return delta_radian, line_speed

这里比较粗暴，传入要检测的机器人id，然后遍历剩余机器人并与之进行判断。判断的方式也很粗暴，首先是二者的距离不能过近，这里有一个阈值，我设为2.12米（没啥科学依据），刚好是两个机器人中间还能再塞下一个机器人的距离，主要是为了留出足够时间和空间进行避让。其次，当二者的朝向绝对值的和大于π/2时，便要主动避让，避让的方式就是在原朝向基础上随机让delta_radian发生改变，最大程度避免正面相撞！

事实上这个判断方式是有点问题的，如图所示，加入黄点和绿点同时朝y轴正方向移动，它们也会符合条件从而进行主动避让，但因为那时候比赛没顾及太多，想着这种情况几乎不可能出现。目前我有另外一个想法，就是先设置判定距离阈值，如2.12米，当机器人离另外一个机器人距离小于2.12米时进入判断，此时计算出机器人按当前速度运动一帧（0.02s）后离另一个机器人的距离是否变得更近，如果更近则采取主动避让措施。这个想法不难实现，但不知道会不会使效率更低抑或是出现新的bug……笔者也想了解更好的做法，欢迎交流噢~
碰撞监测
更新：
b站上看到有大佬用机器人相对位置和速度来重新建系考虑是否碰撞，详情戳https://www.bilibili.com/video/BV1aN411P7ov/?t=927

优化5、考虑时间和碰撞价值系数

我自始至终都没有考虑这两个系数，因为前面我用上了距离优先（确保用时不会过长）和碰撞监测（确保碰撞冲量不会过大）这两个机制。在这里，时间和碰撞价值系数最小值都是0.8，也就是说，物品售价最坏的情况就是0.8 * 0.8 * 原始售价，也就是打64折。对于1、2、3物品来说，还有得赚。但是4、5、6、7就容易出现亏损了，数字越大亏的越厉害，因此要针对4、5、6、7号物品设置亏损销毁机制。
物品售价计算公式

物品 购买价 原始售出价 最小系数之积（时间*碰撞）
4 15400 22500 0.684
5 17200 25000 0.688
6 19200 27500 0.698
7 76000 105000 0.724

不过我还是不太懂，就算7号物品打64折，也就亏个8800，如果销毁了不就直接没了76000？还是说这两个系数的存在不是为了让你销毁，而是转向其他的策略？

优化6、优先卖出7号物品（未实现）

我们知道7号物品的利润是最高的，不计时间和碰撞的损失，能达到29000！所以当7号类型工作台的原材料格未满时，我们应该优先填满并让其开始生产，这里可能需要多写几个判断，问题不大。

但要注意的是，由于机器人优先去7号类型工作台不一定是距离最优，因此时间快要结束的时候，我们需要判断机器人出发去买原材料的距离+去7号工作台出售物品的距离是否能在剩余比赛时间内走完，此时速度取最大值$6m/s$。

6. 最终结果

最终跑分
没想到是第一场分数相对来说比较低，其他几场的分数都提上去了，相比起榜上300w+的大佬我还差得远，通过这次比赛也算是对这方面有一个小小的入门吧。感觉用Python本身就没有C++有优势…

比赛中存在的问题： 首先人数上就存在劣势，毕竟三个臭皮匠赛过诸葛亮嘛~其次是开始写程序的时间太晚了，10号开始的练习赛我19号才想起来报了名，浪费了整整9天时间/(ㄒoㄒ)/~~再有，正式赛的时候我只关注了4号地图，因为只有它分数比较低，针对4号地图存在的问题进行了一些优化（优化2），但其实应该4张图的回放都要看，针对不同地图需要不断改进才行，不然的话也不会最后时刻提交上去发现1号地图的分反而还下降了不少。最后就是写代码的习惯不太好，也不够规范，有时候不得不牵一发而动全身，效率自然也没有这么高了。

欢迎大家交流想法，互相学习！！！

代码地址：https://github.com/CrixusLL/Huawei-CodeCraft-2023