宇宙飞船推进的 AI:在 position=0 和 angle=0 处降落一艘 3D 飞船
AI of spaceship's propulsion: land a 3D ship at position=0 and angle=0
对于 space 游戏,这是一个非常困难的问题,关于如何操纵可以在 3D 中平移和旋转的 space 飞船。
space飞船有 n
喷气机,分布在不同的位置和方向。
第 i
喷气机相对于 space 船的 CM 的变换是常数 = Ti
。
- Transformation 是位置和方向的元组(四元数或矩阵 3x3,或者更不理想的欧拉角)。
- 变换也可以用单个 4x4 矩阵表示。
换句话说,所有喷气机都粘在船上,不能旋转。
喷气式飞机只能在其轴线方向(绿色)向space飞船施加力。
由于胶合,轴随 spaceship 一起旋转。
所有射流都可以施加一定大小(标量,fi
)的力(矢量,Fi
):
i
-th jet 只能在 min_i<= fi <=max_i
.
范围内施加力 (Fi
= axis
x fi
)
min_i
和 max_i
都是已知值的常量。
需要说明的是,min_i
、fi
、max_i
的单位是牛顿。
例如如果范围不包括0,则表示无法关闭喷射。
space飞船的质量 = m
和惯性张量 = I
.
space飞船的当前变换 = Tran0
、速度 = V0
、angularVelocity = W0
.
space飞船物理体遵循众所周知的物理规则:-
Torque=r x F
F=ma
angularAcceleration = I^-1 x Torque
linearAcceleration = m^-1 x F
I
每个方向都是不同的,但是为了简单起见,它对每个方向(球状)都有相同的值。因此,I
可以被认为是标量而不是矩阵 3x3。
问题
如何控制所有喷气机(全部fi
)让position=0,angle=0的船着陆?
类似数学的规范: 查找 fi(time)
的函数,该函数用最短时间达到 position=(0,0,0)
、orient=identity
,最终 angularVelocity
和 velocity
= 零。
更具体地说,解决这个问题的技术或相关算法的名称是什么?
我的研究(1维)
如果宇宙是一维的(因此没有旋转),问题就很容易解决了。
(谢谢Gavin Lock, )
首先,找到值 MIN_BURN=sum{min_i}/m
和 MAX_BURN=sum{max_i}/m
。
其次,反过来想,假设x=0
(位置)和v=0
在t=0
,
然后用 x''=MIN_BURN
和 x''=MAX_BURN
创建两个抛物线。
(假设二阶导数在一段时间内是常数,所以是抛物线。)
唯一剩下的工作就是将两条抛物线连接在一起。
红色虚线是他们加入的地方。
在x''=MAX_BURN
的时间段内,全部fi=max_i
。
在x''=MIN_BURN
的时间段内,所有fi=min_i
.
它在 1D 中工作得很好,但在 3D 中,问题要难得多。
注:
非常感谢能为我指明正确方向的粗略指南。
我不需要完美的人工智能,例如它可能需要比最佳时间多一点的时间。
想了1个多星期,还是没头绪。
其他尝试/意见
- 我认为像神经网络这样的机器学习不适合这种情况。
- 边界约束最小二乘优化可能有用,但我不知道如何使我的两个超抛物线适合那种形式的问题。
- 这可以通过使用多次迭代来解决,但是如何解决?
- 我搜索了 NASA 的网站,但没有找到任何有用的东西。
- 该功能可能存在于 "Space Engineer" 游戏中。
- Logman 评论: 机械工程方面的知识可能会有所帮助。
- AndyG评论: 是nonholonomic constraints. It could be solved by Rapidly exploring random tree (RRTs), theory around Lyapunov equation, and Linear quadratic regulator的运动规划问题。
- John Coleman 评论: 这看起来更像 optimal control 而不是 AI。
编辑:"Near-0 assumption"(可选)
- 在大多数情况下,AI(待设计)运行连续(即调用每个时间步)。
- 因此,通过AI的调整,
Tran0
通常接近同一,V0
和W0
是通常 与 0 没有太大区别,例如|Seta0|<30 degree
,|W0|<5 degree per time-step
。
- 我认为基于这个假设的 AI 在 大多数 情况下都可以正常工作。虽然不完美,但也算是一个正确的解法(我开始觉得如果没有这个假设,这道题可能太难了)。
- 我隐约觉得这个假设可能会启用一些使用一些"linear"-近似的技巧。
第二个备选问题 - "Tune 12 Variables"(更简单)
上面的问题也可以这样看:-
我想使用最少的时间步长将所有六个 values
和六个 values'
(一阶导数)调整为 0。
这里是table展示AI可能面临的情况:-
乘数 table 存储原始问题中的 inertia^-1 * r
和 mass^-1
。
乘数和范围是常数。
每个时间步,AI 将被要求选择一个值 fi
的元组,对于每个 i+1
-th 喷气机,该元组必须在 [min_i,max_i]
范围内。
Ex.从table,AI可以挑(f0=1,f1=0.1,f2=-1)
.
然后,调用者将使用fi
乘以乘数table得到values''
。
Px'' = f0*0.2+f1*0.0+f2*0.7
Py'' = f0*0.3-f1*0.9-f2*0.6
Pz'' = ....................
SetaX''= ....................
SetaY''= ....................
SetaZ''= f0*0.0+f1*0.0+f2*5.0
之后,调用者将用公式values' += values''
更新所有values'
。
Px' += Px''
.................
SetaZ' += SetaZ''
最后,调用者将用公式 values += values'
.
更新所有 values
Px += Px'
.................
SetaZ += SetaZ'
每个时间步只会询问 AI 一次。
AI的objective是对fi
的return个元组(不同时间步可以不同),使得Px
,Py
,Pz
,SetaX
,SetaY
,SetaZ
,Px'
,Py'
,Pz'
,SetaX'
, SetaY'
,SetaZ'
= 0(或非常接近),
尽可能使用最少的时间步长。
我希望提供对问题的另一种看法会更容易。
这不是完全相同的问题,但我觉得可以解决这个版本的解决方案可以使我非常接近原始问题的答案。
这个备选问题的答案可能非常有用。
第三个备选问题 - "Tune 6 Variables"(最简单)
这是上一个替代方案的有损简化版本。
唯一的区别是世界现在是二维的,Fi
也是二维的(x,y)。
因此我只需要调整 Px
,Py
,SetaZ
,Px'
,Py'
,SetaZ'
=0, 通过尽可能使用最少的时间步长。
这个最简单的替代问题的答案可以被认为是有用的。
对于这类问题,有两种技术可用:暴力搜索和启发式。 Bruteforce 是指将问题识别为具有输入和输出参数的黑盒,目的是获得正确的输入参数以赢得比赛。为了编写这样的强力搜索程序,游戏物理在模拟循环(物理模拟)中运行,并通过随机搜索(minimax,alpha-beta-prunning)尝试每一种可能性。暴力搜索的缺点是cpu消耗大
其他技术利用有关游戏的知识。有关运动原语和评估的知识。这些知识是用 C++ 或 Java 等普通计算机语言编写的。这种想法的缺点是,知识往往难以掌握。
解决宇宙飞船导航的最佳实践是将这两种想法结合到一个混合系统中。对于这个具体问题的编程源代码,我估计需要将近 2000 行代码。此类问题通常在大型项目中由许多程序员完成,大约需要 6 个月。
这不是答案,但太长了,不适合作为评论。
首先,真正的解决方案将涉及linear programming (for multivariate optimization with constraints that will be used in many of the substeps) as well as techniques used in trajectory optimization and/or 控制理论。这是一个非常复杂的问题,如果你能解决它,你就可以在你选择的任何公司找到一份工作。唯一可能使这个问题变得更糟的是摩擦(阻力)效应或外部物体引力效应。理想的解决方案还可以使用 Verlet 积分或四阶 Runge Kutta,它们对您在此处实施的 Euler 积分进行了改进。
其次,我相信你上面问题的“第二个替代版本” 忽略了旋转对你在每个时间步添加到位置的位移矢量的影响。虽然喷气轴相对于飞船的参照系保持固定,但它们 而不是 相对于您用于降落飞船的全球坐标系保持固定(在全球坐标 [0, 0, 0]
).因此,[Px', Py', Pz']
矢量(根据船舶的参考系计算)在应用于全局位置坐标之前必须在所有 3 个维度上进行适当的旋转。
第三,您有一些隐含的假设没有说明。例如,一个维度应该被定义为 "landing depth" 维度并且应该禁止负坐标值(除非你接受一个火热的崩溃)。我为此开发了一个模型模型,其中我假设 z
维度是着陆维度。这个问题对初始状态和对射流的约束非常敏感。我在上面使用您的示例初始条件的所有尝试都失败了。例如,在我的模型中(没有上面提到的 3d 位移矢量旋转),射流约束只允许在 z 轴上的一个方向上旋转。因此,如果 aZ
在任何时候变为负值(通常是这种情况),飞船实际上被迫在该轴上完成另一次完整旋转,然后它甚至可以尝试再次接近 0 度。此外,如果没有 3d 位移矢量旋转,您会发现 Px
只会使用您的示例初始条件和约束变为负值,并且船舶被迫坠毁或在负 x 轴上越来越远地偏离作为它试图操纵。解决这个问题的唯一方法是真正结合旋转或允许足够的正负喷射力。
然而,即使我放松了你的 min/max 力限制,我也无法让我的模型成功着陆,这表明这里可能需要多么复杂的计划。除非有可能在线性规划中完全表述此问题 space,否则我相信您将需要结合高级规划或随机决策树,这些树足以 "smart" 持续使用旋转方法重新定向最灵活的喷气机到当前最必要的坐标轴上。
最后,正如我在评论部分指出的那样,"On May 14, 2015, the source code for Space Engineers was made freely available on GitHub to the public." 如果您认为该游戏已经包含此逻辑,那应该是您的起点。但是,我怀疑您一定会失望的。大多数 space 游戏着陆序列只是简单地控制飞船,而不模拟 "real" 力向量。一旦您控制了 3-d 模型,就可以很容易地预先确定带有旋转的 3d 样条曲线,这将使船舶在预定时间以完美的方位平稳着陆。为什么任何游戏程序员都要为着陆序列进行这种级别的工作?这种逻辑可以控制 ICBM 导弹或行星漫游车再入飞行器,恕我直言,这对于游戏来说简直是矫枉过正(除非游戏的真正目的是看看您是否可以使用任意喷气式飞机降落损坏的 space 飞船和约束而不会崩溃)。
我会尽量保持简短。
在模拟中经常用来解决这些问题的一种方法是 Rapidly-Exploring Random Tree。为了至少让我的 post 有一点可信度,我承认我研究了这些,运动规划是我研究实验室的专业领域(概率运动规划)。
要阅读的关于这些的规范论文是 Steven LaValle 的 Rapidly-exploring random trees: A new tool for path planning,从那以后已经发表了一百万篇论文,都在某种程度上改进了它。
首先,我将介绍 RRT 的最基本描述,然后我将描述它在具有动态约束时如何变化。之后我会把它留给你:
术语
Spaces
你的 spaceship 的状态可以用它的 3 维位置 (x, y, z) 和它的 3 维旋转 (alpha, beta, gamma) 来描述(我使用那些希腊名字因为那些是 Euler angles).
状态 space 是您的 spaceship 可以停留的所有可能位置和旋转。当然这是无限的。
碰撞space都是“无效”状态。即现实中不可能的位置。这些是您的 spaceship 与某些障碍物发生碰撞的状态(对于其他物体,这也包括与自身的碰撞,例如规划一段链条)。缩写为C-Space.
free space 是任何不冲突的东西 space.
一般方法(无动力学约束)
对于没有动力学约束的物体,该方法相当简单:
- 采样状态
- 找到该州的最近邻居
- 尝试规划邻居与州之间的路线
我将简要讨论每个步骤
采样状态
在最基本的情况下对状态进行抽样意味着为状态中的每个条目选择随机值 space。如果我们对您的 space 飞船执行此操作,我们将随机抽样 x、y、z、alpha、beta、gamma 的所有可能值(均匀随机抽样)。
当然,您的 space 障碍 space 比免费 space 通常要多得多(因为您通常将相关对象限制在您想要移动的某个“环境”中代替)。所以最常见的做法是获取环境的边界立方体并在其中采样位置 (x, y, z),现在我们有更高的机会在免费 space.
在 RRT 中,您将在 大部分时间 中随机抽样。但是有一定的可能性你实际上会选择你的下一个样本作为你的目标状态(玩它,从 0.05 开始)。这是因为您需要定期测试以查看从开始到目标的路径是否可用。
寻找采样状态的最近邻居
您选择了某个 > 0 的固定整数。我们称该整数为 k
。您的 k
个最近的邻居在 space 州附近。这意味着您有一些 距离度量 可以告诉您状态之间的距离。最基本的距离度量是Euclidean distance,它只考虑物理距离而不关心旋转角度(因为在最简单的情况下你可以在一个时间步内旋转360度)。
最初你只有你的起始位置,所以它将是最近邻居列表中唯一的候选者。
规划州际路线
这叫做局部规划。在真实场景中,您知道自己要去哪里,并且沿途需要躲避其他人和移动的物体。我们不会在这里担心那些事情。在我们的计划世界中,我们假设宇宙是静止的,但对我们来说。
最常见的是假设采样状态与其最近的邻居之间存在某种线性插值。邻居(即已经在树中的节点)沿着此线性插值一点一点地移动,直到它到达采样配置,或者它行进某个最大 distance (回忆你的距离度量) .
这里发生的事情是你的树正朝着样本生长。当我说你“一点一点”地步进时,我的意思是你定义了一些“增量”(一个非常小的值)并沿着线性插值移动每个 timestep。在每个点,您都检查新状态是否与某些障碍物发生碰撞。如果你遇到障碍,你将最后一个有效的配置保留为树的一部分(不要忘记以某种方式存储边缘!)所以你需要的本地规划器是:
- 碰撞检查
- 如何在两个状态之间“插值”(对于您的问题,您不必担心这个,因为我们会做一些不同的事情)。
- 时间步进的物理模拟(Euler integration is quite common, but less stable than something like Runge-Kutta。幸运的是你已经有了一个物理模型!
动态约束修改
当然,如果我们假设您可以在状态之间进行线性插值,我们将违反您为 spaceship 定义的物理学。所以我们修改RRT如下:
- 我们不是对随机状态进行采样,而是对随机控件进行采样,并在固定时间段(或直到发生碰撞)应用所述控件。
以前,当我们对随机状态进行采样时,我们真正做的是选择一个方向(在状态 space 中)移动。现在我们有了约束,我们随机抽样我们的控制,这实际上是一回事,除了我们保证不违反我们的约束。
在固定时间间隔(或直到发生碰撞)应用控件后,您向树中添加一个节点,控件存储在边上。你的树会长得非常快去探索 space。此控制应用程序取代了树状态和采样状态之间的线性插值。
对控件进行采样
您有 n
个喷气机,它们各自具有可以施加的最小和最大力。在每个射流.
的最小和最大力 范围内采样
我要将控件应用于哪些节点?
你可以随机选择,或者你可以偏向选择最接近你的目标状态的节点(需要距离度量)。随着时间的推移,这种偏差将尝试使节点更接近目标。
现在,使用这种方法,您不太可能完全达到您的目标,因此您需要定义一些“足够接近”的定义。也就是说,您将使用您的距离度量来找到离您的目标状态最近的邻居,然后测试它们是否“足够接近”。这个“足够接近”的指标可能与您的距离指标不同,也可能不同。如果您使用的是欧氏距离,但目标配置也正确旋转非常重要,那么您可能需要修改“足够接近”指标以查看角度差异。
什么是“足够接近”完全取决于您。还有一些东西供您调整,有一百万篇论文首先试图让您更接近。
结论
这种随机抽样听起来可能很荒谬,但您的树会很快长大以探索您的免费 space。在 RRT 上查看一些关于路径规划的 youtube 视频。我们不能保证具有动态约束的所谓“概率完整性”,但它通常“足够好”。有时可能不存在解决方案,因此您需要在其中放置一些逻辑以在一段时间后停止生长树(例如 20,000 个样本)
更多资源:
从这些开始,然后开始调查他们的引用,然后开始调查谁在引用他们。
我可以在提出的(很棒的)答案组合中引入另一种技术。
更多的是AI,提供接近最优的解决方案。它被称为Machine Learning, more specifically Q-Learning。实施起来出奇地容易,但很难做到正确。
优点是学习可以离线,所以算法在使用时可以超快。
您可以在船舶建造时或发生事故时(推进器损坏、大块撕裂...)进行学习。
最优性
我发现您正在寻找接近最优的解决方案。您使用抛物线的方法有利于最佳控制。你所做的是这样的:
- 观察系统状态。
- 对于每个状态(进入太快、太慢、离开、接近等),您设计了一个操作(应用策略),使系统进入更接近目标的状态。
- 重复
这对于 3D 中的人类来说非常棘手(太多的情况,会让你发疯)但是机器可能会学习在每个维度上在哪里分割抛物线,并且自行设计最优策略
Q-learning 的工作原理与我们非常相似:
- 观察系统的(保密)状态
- Select 一个基于策略的动作
- 如果此操作使系统进入理想状态(更接近目标),则将 action/initial 状态标记为更理想
- 重复
离散化系统的状态。
对于每个状态,都有一个准随机初始化的映射,它将每个状态映射到一个动作(这是 策略 )。还为每个状态分配一个合意性(最初,到处都是零,目标状态为 1000000(X=0,V=0)。
- 你的状态就是你的3个位置,3个角度,3个平移速度,3个旋转速度。
- 你的动作可以是推进器的任意组合
培训
训练 AI(离线阶段):
- 生成许多不同的情况[=98=]
- 应用策略
- 评估新状态
- 让算法(见上面的链接)加强所选策略的合意性值。
游戏中的实时使用
一段时间后,全球导航策略出现了。然后你存储它,在你的游戏循环中,你只需对你的策略进行采样,并在它们出现时将其应用于每种情况。
该策略可能仍会在此阶段学习,但可能会更慢(因为它是实时发生的)。 (顺便说一句,我梦想有一款游戏,AI 可以从每个用户的反馈中学习,这样我们就可以共同训练它 ^^)
在一个简单的一维问题中试试这个,它可以非常快速地(几秒钟)设计出一个策略。
在2D中,我相信一个小时就可以得到很好的结果。
对于 3D...您正在查看一夜之间的计算。有几件事可以尝试加速这个过程:
尝试从不'forget'以前的计算,并将它们作为初始'best guess'策略提供。将其保存到文件中!
你可能会放弃一些状态(比如船摇?)而不会失去太多的导航优化,但会大大提高计算速度。也许更改参考,使飞船始终位于 X 轴上,这样您将降低 x 和 y 尺寸!
更频繁遇到的状态将有一个可靠且非常优化的策略。也许将状态标准化以使您的船舶状态始终接近 'standard' 状态?
通常可以安全地限制旋转速度间隔(您不希望船疯狂翻滚,因此策略始终是 "un-wind" 该速度)。当然旋转角度也是有限制的。
您也可以非线性离散化位置,因为离 objective 越远,精度不会对策略产生太大影响。
对于 space 游戏,这是一个非常困难的问题,关于如何操纵可以在 3D 中平移和旋转的 space 飞船。
space飞船有 n
喷气机,分布在不同的位置和方向。
第 i
喷气机相对于 space 船的 CM 的变换是常数 = Ti
。
- Transformation 是位置和方向的元组(四元数或矩阵 3x3,或者更不理想的欧拉角)。
- 变换也可以用单个 4x4 矩阵表示。
换句话说,所有喷气机都粘在船上,不能旋转。
喷气式飞机只能在其轴线方向(绿色)向space飞船施加力。
由于胶合,轴随 spaceship 一起旋转。
所有射流都可以施加一定大小(标量,fi
)的力(矢量,Fi
):
i
-th jet 只能在 min_i<= fi <=max_i
.
范围内施加力 (Fi
= axis
x fi
)
min_i
和 max_i
都是已知值的常量。
需要说明的是,min_i
、fi
、max_i
的单位是牛顿。
例如如果范围不包括0,则表示无法关闭喷射。
space飞船的质量 = m
和惯性张量 = I
.
space飞船的当前变换 = Tran0
、速度 = V0
、angularVelocity = W0
.
space飞船物理体遵循众所周知的物理规则:-
Torque=r x F
F=ma
angularAcceleration = I^-1 x Torque
linearAcceleration = m^-1 x F
I
每个方向都是不同的,但是为了简单起见,它对每个方向(球状)都有相同的值。因此,I
可以被认为是标量而不是矩阵 3x3。
问题
如何控制所有喷气机(全部fi
)让position=0,angle=0的船着陆?
类似数学的规范: 查找 fi(time)
的函数,该函数用最短时间达到 position=(0,0,0)
、orient=identity
,最终 angularVelocity
和 velocity
= 零。
更具体地说,解决这个问题的技术或相关算法的名称是什么?
我的研究(1维)
如果宇宙是一维的(因此没有旋转),问题就很容易解决了。
(谢谢Gavin Lock,
首先,找到值 MIN_BURN=sum{min_i}/m
和 MAX_BURN=sum{max_i}/m
。
其次,反过来想,假设x=0
(位置)和v=0
在t=0
,
然后用 x''=MIN_BURN
和 x''=MAX_BURN
创建两个抛物线。
(假设二阶导数在一段时间内是常数,所以是抛物线。)
唯一剩下的工作就是将两条抛物线连接在一起。
红色虚线是他们加入的地方。
在x''=MAX_BURN
的时间段内,全部fi=max_i
。
在x''=MIN_BURN
的时间段内,所有fi=min_i
.
它在 1D 中工作得很好,但在 3D 中,问题要难得多。
注:
非常感谢能为我指明正确方向的粗略指南。
我不需要完美的人工智能,例如它可能需要比最佳时间多一点的时间。
想了1个多星期,还是没头绪。
其他尝试/意见
- 我认为像神经网络这样的机器学习不适合这种情况。
- 边界约束最小二乘优化可能有用,但我不知道如何使我的两个超抛物线适合那种形式的问题。
- 这可以通过使用多次迭代来解决,但是如何解决?
- 我搜索了 NASA 的网站,但没有找到任何有用的东西。
- 该功能可能存在于 "Space Engineer" 游戏中。
- Logman 评论: 机械工程方面的知识可能会有所帮助。
- AndyG评论: 是nonholonomic constraints. It could be solved by Rapidly exploring random tree (RRTs), theory around Lyapunov equation, and Linear quadratic regulator的运动规划问题。
- John Coleman 评论: 这看起来更像 optimal control 而不是 AI。
编辑:"Near-0 assumption"(可选)
- 在大多数情况下,AI(待设计)运行连续(即调用每个时间步)。
- 因此,通过AI的调整,
Tran0
通常接近同一,V0
和W0
是通常 与 0 没有太大区别,例如|Seta0|<30 degree
,|W0|<5 degree per time-step
。 - 我认为基于这个假设的 AI 在 大多数 情况下都可以正常工作。虽然不完美,但也算是一个正确的解法(我开始觉得如果没有这个假设,这道题可能太难了)。
- 我隐约觉得这个假设可能会启用一些使用一些"linear"-近似的技巧。
第二个备选问题 - "Tune 12 Variables"(更简单)
上面的问题也可以这样看:-
我想使用最少的时间步长将所有六个 values
和六个 values'
(一阶导数)调整为 0。
这里是table展示AI可能面临的情况:-
乘数 table 存储原始问题中的 inertia^-1 * r
和 mass^-1
。
乘数和范围是常数。
每个时间步,AI 将被要求选择一个值 fi
的元组,对于每个 i+1
-th 喷气机,该元组必须在 [min_i,max_i]
范围内。
Ex.从table,AI可以挑(f0=1,f1=0.1,f2=-1)
.
然后,调用者将使用fi
乘以乘数table得到values''
。
Px'' = f0*0.2+f1*0.0+f2*0.7
Py'' = f0*0.3-f1*0.9-f2*0.6
Pz'' = ....................
SetaX''= ....................
SetaY''= ....................
SetaZ''= f0*0.0+f1*0.0+f2*5.0
之后,调用者将用公式values' += values''
更新所有values'
。
Px' += Px''
.................
SetaZ' += SetaZ''
最后,调用者将用公式 values += values'
.
更新所有 values
Px += Px'
.................
SetaZ += SetaZ'
每个时间步只会询问 AI 一次。
AI的objective是对fi
的return个元组(不同时间步可以不同),使得Px
,Py
,Pz
,SetaX
,SetaY
,SetaZ
,Px'
,Py'
,Pz'
,SetaX'
, SetaY'
,SetaZ'
= 0(或非常接近),
尽可能使用最少的时间步长。
我希望提供对问题的另一种看法会更容易。
这不是完全相同的问题,但我觉得可以解决这个版本的解决方案可以使我非常接近原始问题的答案。
这个备选问题的答案可能非常有用。
第三个备选问题 - "Tune 6 Variables"(最简单)
这是上一个替代方案的有损简化版本。
唯一的区别是世界现在是二维的,Fi
也是二维的(x,y)。
因此我只需要调整 Px
,Py
,SetaZ
,Px'
,Py'
,SetaZ'
=0, 通过尽可能使用最少的时间步长。
这个最简单的替代问题的答案可以被认为是有用的。
对于这类问题,有两种技术可用:暴力搜索和启发式。 Bruteforce 是指将问题识别为具有输入和输出参数的黑盒,目的是获得正确的输入参数以赢得比赛。为了编写这样的强力搜索程序,游戏物理在模拟循环(物理模拟)中运行,并通过随机搜索(minimax,alpha-beta-prunning)尝试每一种可能性。暴力搜索的缺点是cpu消耗大
其他技术利用有关游戏的知识。有关运动原语和评估的知识。这些知识是用 C++ 或 Java 等普通计算机语言编写的。这种想法的缺点是,知识往往难以掌握。
解决宇宙飞船导航的最佳实践是将这两种想法结合到一个混合系统中。对于这个具体问题的编程源代码,我估计需要将近 2000 行代码。此类问题通常在大型项目中由许多程序员完成,大约需要 6 个月。
这不是答案,但太长了,不适合作为评论。
首先,真正的解决方案将涉及linear programming (for multivariate optimization with constraints that will be used in many of the substeps) as well as techniques used in trajectory optimization and/or 控制理论。这是一个非常复杂的问题,如果你能解决它,你就可以在你选择的任何公司找到一份工作。唯一可能使这个问题变得更糟的是摩擦(阻力)效应或外部物体引力效应。理想的解决方案还可以使用 Verlet 积分或四阶 Runge Kutta,它们对您在此处实施的 Euler 积分进行了改进。
其次,我相信你上面问题的“第二个替代版本” 忽略了旋转对你在每个时间步添加到位置的位移矢量的影响。虽然喷气轴相对于飞船的参照系保持固定,但它们 而不是 相对于您用于降落飞船的全球坐标系保持固定(在全球坐标 [0, 0, 0]
).因此,[Px', Py', Pz']
矢量(根据船舶的参考系计算)在应用于全局位置坐标之前必须在所有 3 个维度上进行适当的旋转。
第三,您有一些隐含的假设没有说明。例如,一个维度应该被定义为 "landing depth" 维度并且应该禁止负坐标值(除非你接受一个火热的崩溃)。我为此开发了一个模型模型,其中我假设 z
维度是着陆维度。这个问题对初始状态和对射流的约束非常敏感。我在上面使用您的示例初始条件的所有尝试都失败了。例如,在我的模型中(没有上面提到的 3d 位移矢量旋转),射流约束只允许在 z 轴上的一个方向上旋转。因此,如果 aZ
在任何时候变为负值(通常是这种情况),飞船实际上被迫在该轴上完成另一次完整旋转,然后它甚至可以尝试再次接近 0 度。此外,如果没有 3d 位移矢量旋转,您会发现 Px
只会使用您的示例初始条件和约束变为负值,并且船舶被迫坠毁或在负 x 轴上越来越远地偏离作为它试图操纵。解决这个问题的唯一方法是真正结合旋转或允许足够的正负喷射力。
然而,即使我放松了你的 min/max 力限制,我也无法让我的模型成功着陆,这表明这里可能需要多么复杂的计划。除非有可能在线性规划中完全表述此问题 space,否则我相信您将需要结合高级规划或随机决策树,这些树足以 "smart" 持续使用旋转方法重新定向最灵活的喷气机到当前最必要的坐标轴上。
最后,正如我在评论部分指出的那样,"On May 14, 2015, the source code for Space Engineers was made freely available on GitHub to the public." 如果您认为该游戏已经包含此逻辑,那应该是您的起点。但是,我怀疑您一定会失望的。大多数 space 游戏着陆序列只是简单地控制飞船,而不模拟 "real" 力向量。一旦您控制了 3-d 模型,就可以很容易地预先确定带有旋转的 3d 样条曲线,这将使船舶在预定时间以完美的方位平稳着陆。为什么任何游戏程序员都要为着陆序列进行这种级别的工作?这种逻辑可以控制 ICBM 导弹或行星漫游车再入飞行器,恕我直言,这对于游戏来说简直是矫枉过正(除非游戏的真正目的是看看您是否可以使用任意喷气式飞机降落损坏的 space 飞船和约束而不会崩溃)。
我会尽量保持简短。
在模拟中经常用来解决这些问题的一种方法是 Rapidly-Exploring Random Tree。为了至少让我的 post 有一点可信度,我承认我研究了这些,运动规划是我研究实验室的专业领域(概率运动规划)。
要阅读的关于这些的规范论文是 Steven LaValle 的 Rapidly-exploring random trees: A new tool for path planning,从那以后已经发表了一百万篇论文,都在某种程度上改进了它。
首先,我将介绍 RRT 的最基本描述,然后我将描述它在具有动态约束时如何变化。之后我会把它留给你:
术语
Spaces
你的 spaceship 的状态可以用它的 3 维位置 (x, y, z) 和它的 3 维旋转 (alpha, beta, gamma) 来描述(我使用那些希腊名字因为那些是 Euler angles).
状态 space 是您的 spaceship 可以停留的所有可能位置和旋转。当然这是无限的。
碰撞space都是“无效”状态。即现实中不可能的位置。这些是您的 spaceship 与某些障碍物发生碰撞的状态(对于其他物体,这也包括与自身的碰撞,例如规划一段链条)。缩写为C-Space.
free space 是任何不冲突的东西 space.
一般方法(无动力学约束)
对于没有动力学约束的物体,该方法相当简单:
- 采样状态
- 找到该州的最近邻居
- 尝试规划邻居与州之间的路线
我将简要讨论每个步骤
采样状态
在最基本的情况下对状态进行抽样意味着为状态中的每个条目选择随机值 space。如果我们对您的 space 飞船执行此操作,我们将随机抽样 x、y、z、alpha、beta、gamma 的所有可能值(均匀随机抽样)。
当然,您的 space 障碍 space 比免费 space 通常要多得多(因为您通常将相关对象限制在您想要移动的某个“环境”中代替)。所以最常见的做法是获取环境的边界立方体并在其中采样位置 (x, y, z),现在我们有更高的机会在免费 space.
在 RRT 中,您将在 大部分时间 中随机抽样。但是有一定的可能性你实际上会选择你的下一个样本作为你的目标状态(玩它,从 0.05 开始)。这是因为您需要定期测试以查看从开始到目标的路径是否可用。
寻找采样状态的最近邻居
您选择了某个 > 0 的固定整数。我们称该整数为 k
。您的 k
个最近的邻居在 space 州附近。这意味着您有一些 距离度量 可以告诉您状态之间的距离。最基本的距离度量是Euclidean distance,它只考虑物理距离而不关心旋转角度(因为在最简单的情况下你可以在一个时间步内旋转360度)。
最初你只有你的起始位置,所以它将是最近邻居列表中唯一的候选者。
规划州际路线
这叫做局部规划。在真实场景中,您知道自己要去哪里,并且沿途需要躲避其他人和移动的物体。我们不会在这里担心那些事情。在我们的计划世界中,我们假设宇宙是静止的,但对我们来说。
最常见的是假设采样状态与其最近的邻居之间存在某种线性插值。邻居(即已经在树中的节点)沿着此线性插值一点一点地移动,直到它到达采样配置,或者它行进某个最大 distance (回忆你的距离度量) .
这里发生的事情是你的树正朝着样本生长。当我说你“一点一点”地步进时,我的意思是你定义了一些“增量”(一个非常小的值)并沿着线性插值移动每个 timestep。在每个点,您都检查新状态是否与某些障碍物发生碰撞。如果你遇到障碍,你将最后一个有效的配置保留为树的一部分(不要忘记以某种方式存储边缘!)所以你需要的本地规划器是:
- 碰撞检查
- 如何在两个状态之间“插值”(对于您的问题,您不必担心这个,因为我们会做一些不同的事情)。
- 时间步进的物理模拟(Euler integration is quite common, but less stable than something like Runge-Kutta。幸运的是你已经有了一个物理模型!
动态约束修改
当然,如果我们假设您可以在状态之间进行线性插值,我们将违反您为 spaceship 定义的物理学。所以我们修改RRT如下:
- 我们不是对随机状态进行采样,而是对随机控件进行采样,并在固定时间段(或直到发生碰撞)应用所述控件。
以前,当我们对随机状态进行采样时,我们真正做的是选择一个方向(在状态 space 中)移动。现在我们有了约束,我们随机抽样我们的控制,这实际上是一回事,除了我们保证不违反我们的约束。
在固定时间间隔(或直到发生碰撞)应用控件后,您向树中添加一个节点,控件存储在边上。你的树会长得非常快去探索 space。此控制应用程序取代了树状态和采样状态之间的线性插值。
对控件进行采样
您有 n
个喷气机,它们各自具有可以施加的最小和最大力。在每个射流.
我要将控件应用于哪些节点?
你可以随机选择,或者你可以偏向选择最接近你的目标状态的节点(需要距离度量)。随着时间的推移,这种偏差将尝试使节点更接近目标。
现在,使用这种方法,您不太可能完全达到您的目标,因此您需要定义一些“足够接近”的定义。也就是说,您将使用您的距离度量来找到离您的目标状态最近的邻居,然后测试它们是否“足够接近”。这个“足够接近”的指标可能与您的距离指标不同,也可能不同。如果您使用的是欧氏距离,但目标配置也正确旋转非常重要,那么您可能需要修改“足够接近”指标以查看角度差异。
什么是“足够接近”完全取决于您。还有一些东西供您调整,有一百万篇论文首先试图让您更接近。
结论
这种随机抽样听起来可能很荒谬,但您的树会很快长大以探索您的免费 space。在 RRT 上查看一些关于路径规划的 youtube 视频。我们不能保证具有动态约束的所谓“概率完整性”,但它通常“足够好”。有时可能不存在解决方案,因此您需要在其中放置一些逻辑以在一段时间后停止生长树(例如 20,000 个样本)
更多资源:
从这些开始,然后开始调查他们的引用,然后开始调查谁在引用他们。
我可以在提出的(很棒的)答案组合中引入另一种技术。
更多的是AI,提供接近最优的解决方案。它被称为Machine Learning, more specifically Q-Learning。实施起来出奇地容易,但很难做到正确。
优点是学习可以离线,所以算法在使用时可以超快。
您可以在船舶建造时或发生事故时(推进器损坏、大块撕裂...)进行学习。
最优性
我发现您正在寻找接近最优的解决方案。您使用抛物线的方法有利于最佳控制。你所做的是这样的:
- 观察系统状态。
- 对于每个状态(进入太快、太慢、离开、接近等),您设计了一个操作(应用策略),使系统进入更接近目标的状态。
- 重复
这对于 3D 中的人类来说非常棘手(太多的情况,会让你发疯)但是机器可能会学习在每个维度上在哪里分割抛物线,并且自行设计最优策略
Q-learning 的工作原理与我们非常相似:
- 观察系统的(保密)状态
- Select 一个基于策略的动作
- 如果此操作使系统进入理想状态(更接近目标),则将 action/initial 状态标记为更理想
- 重复
离散化系统的状态。
对于每个状态,都有一个准随机初始化的映射,它将每个状态映射到一个动作(这是 策略 )。还为每个状态分配一个合意性(最初,到处都是零,目标状态为 1000000(X=0,V=0)。
- 你的状态就是你的3个位置,3个角度,3个平移速度,3个旋转速度。
- 你的动作可以是推进器的任意组合
培训
训练 AI(离线阶段):
- 生成许多不同的情况[=98=]
- 应用策略
- 评估新状态
- 让算法(见上面的链接)加强所选策略的合意性值。
游戏中的实时使用
一段时间后,全球导航策略出现了。然后你存储它,在你的游戏循环中,你只需对你的策略进行采样,并在它们出现时将其应用于每种情况。
该策略可能仍会在此阶段学习,但可能会更慢(因为它是实时发生的)。 (顺便说一句,我梦想有一款游戏,AI 可以从每个用户的反馈中学习,这样我们就可以共同训练它 ^^)
在一个简单的一维问题中试试这个,它可以非常快速地(几秒钟)设计出一个策略。
在2D中,我相信一个小时就可以得到很好的结果。
对于 3D...您正在查看一夜之间的计算。有几件事可以尝试加速这个过程:
尝试从不'forget'以前的计算,并将它们作为初始'best guess'策略提供。将其保存到文件中!
你可能会放弃一些状态(比如船摇?)而不会失去太多的导航优化,但会大大提高计算速度。也许更改参考,使飞船始终位于 X 轴上,这样您将降低 x 和 y 尺寸!
更频繁遇到的状态将有一个可靠且非常优化的策略。也许将状态标准化以使您的船舶状态始终接近 'standard' 状态?
通常可以安全地限制旋转速度间隔(您不希望船疯狂翻滚,因此策略始终是 "un-wind" 该速度)。当然旋转角度也是有限制的。
您也可以非线性离散化位置,因为离 objective 越远,精度不会对策略产生太大影响。