3D Routing算法的设计

发表于 | 分类于

前言

环境

将物理位置离散为一个[x, y, nlayers]的三维空间，每个坐标点代表一个位置。

layer共有五层，第一层是pin层，只能选择向上运动。第二、四层只能允许垂直及水平方向的运动（x轴与z轴）。第三层允许垂直及前后方向的运动（x轴与z轴）。第五层只允许向下及前后方向的运动。

Notation定义

  • 智能体（agent）$a_i$：一个可以在三维空间运动的对象。其初始位置为一个pin的位置。
  • 轨迹：一个agent走过的位置的集合。
  • agent的类型：许多个agent被定义为同一类型，表示它们对应的pin需要被连接在一起。
  • 线网（net）：同一类型的agent的轨迹的集合。
  • 线网的长度：一个线网所占用的位置数目（对应于真实世界电线的长度）
  • $O_{i}$：$agent_i$所观察到的observation。

优化目标

  • 同一个net的长度越短越好
  • net之间不能交叉

P网络

  • decentalized
  • 一个agent一个P网络

  • 输入：ob

  • centralized

  • 只要重名即可
  • 同一个net用同一种P。

Q网络

  • centralized
  • 一个agent一个Q网络

问题：Reward的设计

如果我们采取的策略是：让所有的agents在完成连接的时候，即达到全局最优（轨迹最短），那么Reward（也就是每一步所获得的奖励）应该包含以下信息：

  • 走这一步，对全局轨迹长度造成了什么伤害，即如果走这一步让轨迹变长了，则应该给予一个值作为Penalty。显然，这个很容易定义。
  • 走这一步，对于“此net内所有的轨迹相互连通”这个目标，提供了什么帮助Help。这个很难定义！
  • 不同网络之间，绝对不能接触，ShortcutPenalty
  • 最终成功了，给予巨大的奖励！ConnectReward
  • 最终的Reward应该设计成：
    1
    Reward = ConnectReward + Help - Penalty - ShortcutPenalty

主意

Help

其中$\vec{n}$是由Agent目前所在位置指向其余Agent的质心的单位向量。$\vec{act}$为此Agent能够选择的方向的单位向量。等于说，这个值表示agent这一步能向质心靠近多少。显然$Help\leq 1$

问题：这似乎违反了马尔科夫过程的假设，因为Reward与其他Agent的位置挂钩，等于说这会导致从一个状态transition到另一个状态带来的Reward不定。

反驳：由于其他Agent被Encode进了状态里面，作为Q函数的输入，等于说在给定目前Agents的所有位置的情况下，所有Agent的这个位置分布，才是一个状态。因此说从这个状态跳转到下一个状态，并没有违反马尔科夫假设。因为Reward实际上是和此状态挂钩，而不是与其他不可捉摸的东西挂钩。

问题：为什么这么设计？

答案：不知道。无法证明每一步都向着质心走有什么好处。

Penalty

$Penalty = -1 or -2$若选择Undo。

$Penalty = 0$若不动，【或做出了违反规定的动作】（待议）。

$Penalty = 1$若在平面内运动，如左右或前后

$Penlaty = 2$若上下运动

如果还没构成连通集，则显然让agent继续运动比留在原地好。所以不能够造成这种现象：让agent原地不动得到的奖励比走别的任何动作的奖励多。

但是如果构成了连通集，则agent是否运动已无大碍。但要保证，乱走的penalty大于原地不动。

* 问题：若在只允许上下左右的平面内，做出了前后的动作，该如何处理？是选择按兵不动，还是选择输出值中，允许的那几个动作中，值最大的？

* 回答：还是选择按兵不动吧，总感觉人为干预输出值会有什么不可预料的事情发生。

ShortcutPenalty

这个值一定要巨大。如选择shortcut，则惩罚-100，若Undoshortcut，则恢复+99（也许是为了防止乘上Decay Factor之后有正值，让agent找到漏洞）。

ConnectReward

这个值一定要巨大。最终连接成功，则+100。平时为0。遇到自己人+10

问题：如果构成了连通集，这些奖励还有意义吗？

Env提供的Obs的数据结构

[N+1, x, y, nlayers]
obs[-1]为全局走过的地方。
每个agent还要维护一个路径栈。
但是最好能把走过的路径encode进obs，提交给P网络。

Action的数据结构

在第一层，只能上。
在第二层，只能上下左右（x）。
第三层，只能上下前后（y）。
第四层，只能上下左右（x）。
第五层，只能上下前后（y）。

第一层只能上Undo。（停前后左右下无效，初始状态Undo无效）
第二层开始，agent可以选择上下左右Undo。（停前后无效）
第三层可以选择上下前后Undo。（停左右无效）
第四层可以选择上下左右Undo。（停前后无效）
同理……
所以总共需要

  • 停
  • 上
  • 下
  • 前
  • 后
  • 左
  • 右
  • Undo

8种动作

Agents数目可变的问题

在训练阶段，由于buffer中存储的是一组(old state, action, reward, new state)的数据。

在decentralized的P网络中，一个trainer对应一个网络、一个buffer，所有不能存在可变Agents数目的现象。这是因为训练Q网络的时候，需要把所有的(state, action) pair传入。（等会再讨论我们目前的Q网络）如果可变数目的话，那么在生成的pin比较少的场景之中，有的Trainer（P网络，Q网络，buffer）会缺失这个场景中的训练内容。但是在这个场景的训练Q的过程之中，却要输入（在原代码的实现中）所有agent的(state, action)，而这个trainer并没有对应的这个pair啊，所以会报错。同样的，在训练这个agent的P网络的时候，输入state，label为action，也会因为在这个trainer之中不存在这类数据而报错。

下面分类讨论。

先讨论agents数目不可变的情况对于目前设计的改造。有没有办法实现同一套网络，适配不同的agents输入呢？在执行阶段，agents数目变化，对应的仅仅是P网络的执行次数变化。不会有任何影响。在训练阶段，每个trainer会提取所有agents的buffer，然后训练自己的P、Q网络。

如果只要bench

传递给Q网络的GOB设计

目的是把ob,act传递进Q，让它揣测这个ob->ob`的过程的reward。
可以有几种设计方法。
第一种，把ob和new_pos 写在一起。new_pos设为class_ind+0.2。
而倒数第二个位置写成[1.1]

Tipping