太空船推进的人工智能:在位置=0和角度=0处着陆3D飞船

35

这是一个关于如何操纵一艘能够在三维空间中进行平移和旋转的宇宙飞船的非常困难的问题,用于太空游戏。

该飞船有n个喷气装置,位于各种位置和方向。

i号喷气装置相对于飞船质心的变换是恒定的=Ti

  • 变换是一个位置和方向的元组(四元数或3x3矩阵或不太优选的欧拉角)。
  • 变换也可以用单个4x4矩阵表示。

换句话说,所有的喷气装置都附着在飞船上,不能旋转。

喷气装置只能朝着其轴(绿色)的方向对飞船施加力。由于粘合作用,轴随着飞船一起旋转。

enter image description here

所有喷射器都可以施加力(向量,Fi)以一定的大小(标量,fi):
i个喷射器只能在范围min_i<= fi <=max_i内施加力(Fi= axis x fi)。
min_imax_i均为已知常数。

需要明确的是,min_ifimax_i的单位均为牛顿。
例如:如果范围不包括0,则表示不能关闭喷射器。

飞船的质量=m,惯性张量=I
飞船当前的变换=Tran0,速度=V0,角速度=W0

The spaceship's physical body follows well-known physics rules: - Torque=r x F - F=ma - angularAcceleration = I^-1 x Torque - linearAcceleration = m^-1 x F
I is different for each direction, but for simplicity, it has the same value for every direction (sphere-like). Thus, I can be thought of as a scalar instead of a matrix 3x3.
Question: How to control all jets (all fi) to land the ship with position=0 and angle=0? Mathematically, find a function of fi(time) that takes minimum time to reach position=(0,0,0), orient=identity with final angularVelocity and velocity = zero. What are the names of the techniques or related algorithms to solve this problem?
My research (1 dimension):
如果宇宙是一维的(因此没有旋转),问题将很容易解决。 (感谢Gavin Lockhttps://dev59.com/F5zha4cB1Zd3GeqPAB1W#40359322
首先,找到值MIN_BURN=sum{min_i}/mMAX_BURN=sum{max_i}/m
其次,反过来思考,假设x=0(位置)和v=0t=0, 然后创建两个抛物线,其中x''=MIN_BURNx''=MAX_BURN。 (二阶导数被假定为在一段时间内恒定,因此是抛物线。)
唯一剩下的工作就是将两个抛物线连接起来。 红色虚线是它们连接的地方。

enter image description here

x''=MAX_BURN 的时间段内,所有的 fi=max_i。 在 x''=MIN_BURN 的时间段内,所有的 fi=min_i
这对于一维问题非常有效,但在三维问题中,问题要难得多。
注意: 只需给我一个大致的指导方向即可。 我不需要完美的人工智能,例如它可以比最优解花费更多的时间。 我思考了1周以上,仍然没有头绪。
其他尝试/意见
我不认为像神经网络这样的机器学习方法适用于这种情况。
边界约束最小二乘优化可能有用,但我不知道如何将我的两个双曲线拟合到该问题的形式中。
这可以通过使用许多迭代来解决,但是怎么做呢?
我已经在NASA的网站上搜索过了,但没有找到任何有用的信息。
这个功能可能存在于“太空工程师”游戏中。 Logman的评论: 机械工程方面的知识可能有所帮助。 AndyG的评论: 这是一个非完整约束的运动规划问题。它可以通过快速探索随机树(RRTs)李雅普诺夫方程理论以及线性二次调节器来解决。 John Coleman的评论: 这似乎更像最优控制而不是人工智能。

编辑: "近似为0的假设"(可选)

  • 大多数情况下,AI(待设计)会持续运行(即每个时间步调用一次)。
  • 因此,随着AI的调整,Tran0通常接近于恒等,V0W0通常与0不太不同,例如|Seta0|<30度|W0|<每个时间步5度
  • 我认为基于这种假设的AI在大多数情况下都能正常工作。虽然不完美,但可以视为正确的解决方案(我开始认为如果没有这个假设,这个问题可能太难了)。
  • 我模糊地感觉这个假设可能会使用一些“线性”逼近的技巧。


第二个备选问题 - "调整12个变量"(更容易)

上述问题也可以理解为:

我想要将所有六个和六个值'(一阶导数)都调整为0,使用最少的时间步长。

下面是一个表格,展示了AI可能会面临的情况:

enter image description here

The Multiplier table存储了原始问题中的惯性^-1 * r质量^-1MultiplierRange是常数。
每个时间步长,AI将被要求选择一个元组值fi,该值必须在每个i+1喷口的范围[min_i,max_i]内。
例如,从表中,AI可以选择(f0=1,f1=0.1,f2=-1)

然后,调用者将使用fi乘数表相乘,得到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的目标是返回fi元组(对于不同的时间步可以不同),使得PxPyPzSetaXSetaYSetaZPx'Py'Pz'SetaX'SetaY'SetaZ' = 0(或非常接近),
并尽可能少地使用时间步数。
我希望提供问题的另一个视角能够使它更容易理解。
虽然这不是完全相同的问题,但我觉得一个能够解决这个版本的解决方案可以让我离答案更近一步。
这个替代问题的答案可能非常有用。

第三种替代方案 - “调整6个变量”(最简单)

这是前一个替代方案的简化版本,但会有信息损失。

唯一的区别是世界现在是二维的,Fi也是二维的(x,y)。

因此,我只需要调整PxPySetaZPx'Py'SetaZ'=0,尽可能少地使用时间步骤。

对于这个最简单的替代问题的答案可以被认为是有用的。


1
可能一些拥有机械工程学位的人可以解决你的问题,因为他们研究这样的运动。 - Logman
1
喷气式发动机是否有最小燃烧时间?由于脉冲率调制可以克服“min_i”限制,因此我还要补充说可能有许多配置没有解决方案,并且至少需要两个喷嘴才能有解决方案。 - Blindman67
1
这就是所谓的具有非完整约束的运动规划问题。您可以使用一些简单的方法,例如快速探索随机树,或者更复杂的控制理论解决方案来执行李亚普诺夫方程。 - AndyG
1
没问题。我可以在这篇文章中写一整篇关于RRT的解释,但是你自己阅读文献可能更好。控制理论方面对我来说有点超纲,但与你提供的数学陈述更加契合。为此,你可以了解一些叫做线性二次调节器的东西。 - AndyG
2
@javaLover 我认为这会成为一个有趣的研究问题,适合追求高级学位的研究生。大多数拥有计算机科学本科学位的人可能没有必要的技能组合。我猜这更像是最优控制而不是人工智能:https://en.wikipedia.org/wiki/Optimal_control - John Coleman
显示剩余23条评论
4个回答

7
我会尽量简短明了。
解决仿真问题的常用方法之一是快速探索随机树。为了让我的帖子更有说服力,我承认我研究过这些内容,运动规划是我们研究实验室的专业领域(概率运动规划)。
关于这些问题,可以阅读 Steven LaValle 的经典论文 快速探索随机树:一种新的路径规划工具,自那以后已经发表了数百万篇论文,都在某种程度上对其进行了改进。
首先,我将介绍 RRT 的最基本描述,然后再描述当您拥有动态约束时它如何改变。之后的调整留给您自行处理。

术语

"空间"

您的太空船状态可以由其三维位置(x,y,z)和三维旋转(alpha,beta,gamma)描述(我使用这些希腊名字是因为它们是欧拉角)。 状态空间是您的太空船可能存在的所有位置和旋转。当然,这是无限的。 碰撞空间是所有“无效”状态。即实际上不可能的位置。这些状态下,您的太空船与某些障碍物相撞(对于其他物体,这还包括与自身的碰撞,例如计划一段链的长度)。简称为C-Space。 自由空间是任何不是碰撞空间的空间。

通用方法(没有动态约束)

对于没有动力学约束的物体,方法相当简单:
  1. 采样一个状态
  2. 找到最近邻状态
  3. 尝试在邻居和状态之间规划路径
我将简要讨论每个步骤

采样状态

在最基本的情况下,采样状态意味着随机选择状态空间中每个条目的值。如果我们针对您的太空飞船进行此操作,我们将在它们所有可能的值(均匀随机采样)之间随机取样x、y、z、alpha、beta、gamma。
当然,通常情况下,您的空间中的障碍空间要比自由空间多得多(因为您通常会将所涉及的对象限制在您想要在其中移动的“环境”中)。因此,通常要做的是取环境的包围立方体并在其中采样位置(x、y、z),现在我们有更高的机会在自由空间中采样。
在RRT中,大部分时间你会随机采样。但是有一定的概率你实际上会选择你的下一个样本作为目标状态(可以尝试一下,从0.05开始)。这是因为您需要定期测试是否有从起点到终点的路径。
寻找与采样状态最近的邻居
你选择了一个大于0的固定整数,我们称之为k。在状态空间中,你的k个最近邻居是附近的。这意味着你有一些距离度量可以告诉你状态之间有多远。最基本的距离度量是欧几里得距离,它只考虑物理距离,不关心旋转角度(因为在最简单的情况下,你可以在一个时间步内旋转360度)。
最初,你只有起始位置,所以它将是最近邻列表中唯一的候选项。

规划状态之间的路径

这被称为局部规划。在现实世界中,你知道自己要去哪里,在路上需要躲避其他人和移动物体。但在这里我们不会考虑这些问题。在我们的规划世界中,我们假设宇宙对我们来说是静态的。
最常见的方法是假设采样状态和其最近邻之间存在一些线性插值。邻居(即树中已经存在的节点)沿着这种线性插值逐步移动,直到它达到采样配置,或者它行进了一些最大的距离(回忆你的距离度量)。
这里的情况是,你的树正在向样本生长。当我说你一步一步地走时,我的意思是要定义一些“delta”(一个非常小的值),并沿着线性插值移动那么多每个时间步骤。在每个点上,您都会检查新状态是否与某些障碍物发生碰撞。如果遇到障碍物,则将最后一个有效配置保留为树的一部分(不要忘记以某种方式存储边缘!)。因此,局部规划器需要:

  • 碰撞检测
  • 如何在两种状态之间“插值”(对于您的问题,您不需要担心这个问题,因为我们将采用不同的方法)。
  • 用于时间步进的物理模拟(Euler积分相当常见,但比龙格-库塔等方法不稳定。幸运的是,您已经有了物理模型!

针对动态约束的修改

当然,如果我们假设你可以在状态之间进行线性插值,那么我们将违反您为宇宙飞船定义的物理规律。因此,我们对RRT进行如下修改:
  • 不再随机采样状态,而是随机采样控制并应用该控制一段固定时间(或直到发生碰撞)。

以前,当我们随机采样状态时,实际上是在选择一个方向(在状态空间中)进行移动。现在我们有了约束条件,我们随机采样控制,这实际上是相同的事情,只不过我们保证不会违反约束条件。

在应用控制一段固定时间间隔(或直到发生碰撞)后,您将添加一个节点到树中,并在边缘上存储控制。您的树将快速增长以探索空间。此控制应用替换了树状态和采样状态之间的线性插值。

采样控件

您有n个喷气推进器,每个喷气推进器都有一些最小和最大力量可以施加。在每个喷气推进器的最小和最大力范围内进行采样。

我应该将控件应用于哪个节点?

您可以随机选择节点,或者偏向于选择距离目标状态更近的节点(需要距离度量)。这种偏向会尝试随着时间推移使节点更接近目标。
现在,采用这种方法,您不太可能完全达到目标,因此您需要定义一些“足够接近”的定义。也就是说,您将使用距离度量来查找最接近目标状态的邻居,然后测试它们是否“足够接近”。这个“足够接近”的度量可以与您的距离度量不同,也可以相同。如果您正在使用欧几里得距离,但非常重要的是您的目标配置也正确旋转,则可能希望修改“足够接近”度量以查看角度差异。
“足够接近”是完全由您决定的。这也是您调整的内容,有数百万篇论文试图让您更接近第一步。

结论

这种随机采样可能听起来很荒谬,但是你的树会很快地在自由空间中生长。可以观看一些关于RRT路径规划的YouTube视频。我们无法保证在动力学约束下的“概率完备性”,但通常“足够好”。有时可能不存在解决方案,因此您需要在那里放置一些逻辑以在一段时间后停止生长树(例如20,000个样本)。
更多资源:
从这些资源开始,然后开始查阅它们的引用,然后开始查阅引用它们的人。
- Kinodynamic RRT* - RRT-Connect

感谢您提供这个惊人的答案。虽然需要时间来消化,但我相信它最终会带领我走向我一直梦寐以求的传奇人工智能之路。感谢您为此付出了大量的努力。您无疑是该领域的专家。(四张A4纸:D) - javaLover
+1.这是一个非常好的答案,正是我在提到“随机决策树”时自己答案中所指的。如果你想比随机抽样做得更好,那么“本地规划器”中仍然存在相当复杂的问题。通过对控制进行采样而不是状态空间,可以避免直接解决物理问题,但您可以预期会有极大的树大小。我很想看到运行时间和收敛速率;如果您将其实现,请与我们分享。 - Special Sauce
@SpecialSauce:谢谢!我完全同意你关于本地规划器的看法。事实上,我认为求解器的任何部分都可以是任意复杂的,而且事实上,在我作为研究生期间,所有的研究都集中在这里;有人会使某个部分更加复杂,以查看增加的计算是否使其更快地进行规划(这实际上都是启发式算法)。大多数情况下,由于数量庞大,简单的方法胜出。收敛速度,正如您可能知道的那样,非常依赖于问题和参数。通常,您需要针对特定问题调整求解器。继续... - AndyG
@SpecialSauce:对于RRT来说,运行速度出奇的快。就像是可怕的快。当然,这也取决于问题本身(在实际空间中具有非常狭窄入口的Bug-trap式问题总是会带来问题),但总体而言它很快(我的意思是,现在我们可以在短时间内完成一百万个随机样本,更不用说将物理空间分区进行并行化处理的工作了)。当然,树可以变得很大。求解器的停止条件之一通常是树达到某个最大节点数。 - AndyG
@AndyG:非常有趣,非常感谢你分享这些见解。 - Special Sauce

5

这不是一个答案,但是太长了无法作为评论。

首先,一个真正的解决方案将涉及到线性规划(用于带约束的多元优化,将在许多子步骤中使用),以及轨迹优化和/或控制理论中使用的技术。这是一个非常复杂的问题,如果你能解决它,你可以在任何你选择的公司找到工作。唯一可能使这个问题更加复杂的是摩擦(阻力)效应或外部重力效应。一个真正的解决方案还应该使用Verlet积分或四阶Runge-Kutta,它们比你在这里实现的欧拉积分提供了改进。

其次,我认为你上面的问题的“第二种备选版本”忽略了旋转对于每个时间步长添加到位置的位移向量的影响。虽然喷气轴相对于飞船的参考系保持不变,但它们相对于你用来将飞船降落在全局坐标[0, 0, 0]处的全局坐标系并不保持不变。因此,从飞船的参考系计算出的向量[Px', Py', Pz']必须在三个维度上经过适当的旋转,然后应用于全局位置坐标。
第三,你没有明确说明一些隐含的假设。例如,一个维度应该被定义为“着陆深度”维度,并且负坐标值应该被禁止(除非你接受火爆的撞击)。我为此开发了一个模拟模型,在其中我假设 z 维度是着陆维度。这个问题对初始状态和喷气机所施加的限制非常敏感。在使用你上面提供的初始条件进行尝试时,我的所有尝试都失败了。例如,在我的模拟中(没有上面提到的 3D 位移向量旋转),喷气机的限制只允许在 z 轴上的一个方向上旋转。因此,如果 aZ 在任何时候变为负数(这通常是情况),飞船实际上被迫在该轴上完成另一个完整的旋转,然后才能再次尝试接近零度。此外,如果没有 3D 位移向量旋转,你会发现使用你提供的初始条件和约束,Px 只会变成负数,而飞船在试图操纵时被迫要么坠毁,要么越来越远地偏离负 x 轴。唯一解决这个问题的方法是真正地融合旋转或允许足够的正负喷气力。
然而,即使我放宽了你的最小/最大力约束,我仍无法成功地让我的模型着陆,这表明这里可能需要复杂的规划。除非能够完全在线性规划空间中阐述这个问题,否则我认为你需要纳入先进的计划或随机决策树,这些树足够“聪明”,可以不断使用旋转方法将最灵活的喷气式发动机重新定向到当前最必要的轴上。
最后,请注意我的注释中提到:“2015年5月14日,Space Engineers的源代码已经在GitHub上免费向公众发布。”如果你认为这个游戏已经包含了这个逻辑,那么这应该是你的起点。然而,我怀疑你会感到失望。大多数太空游戏着陆序列只是控制飞船,并不模拟“真实”的力向量。一旦你掌控了一个三维模型,就很容易预先确定一个具有旋转的3D样条,使飞船在预定时间平稳降落并具有完美的方向。为什么任何游戏程序员都会为着陆序列付出这种程度的工作?这种逻辑可以控制洲际弹道导弹或行星探测车再入大气,并且在我的意见中只是过度的杀伤力(除非游戏的目的就是看看你是否能够在没有崩溃的情况下用任意的喷气和约束着陆损坏的太空飞船)。

通常情况下,我们会删除以“这不是一个答案”开头的回答,但是这里所有的答案都可能注定要被删除,因为问题可能太过宽泛。 - Russia Must Remove Putin
@Aaron Hall 我把问题改成了“解决这个问题的技术或相关算法的名称是什么?”你认为这样是否变得不那么宽泛了? - javaLover
我会听取更有经验的管理员的意见,因为我是新手,我不想搞砸这个。我已经通知了他们。 - Russia Must Remove Putin

2
我可以将另一种技术引入到提出的(很棒的)答案中。
它更多地涉及人工智能,并提供接近最优解决方案。它被称为机器学习,更具体地说是Q学习。实现起来非常简单,但要做好却很难。
优点在于学习可以离线完成,因此在使用时算法可以超级快速。
你可以在飞船建造或发生某些事情时(推进器损坏、大块物质撕裂...)进行学习。

最优性

我发现你正在寻找接近最优解。你使用抛物线的方法对于最优控制是很好的。你所做的是:

  • 观察系统的状态
  • 针对每个状态(过快、过慢、远离、接近等),你设计一个行动方案(应用策略),使系统更接近目标状态。
  • 重复以上步骤

这在3D环境中对人类来说几乎是不可行的(太多情况,会让你发疯),但机器可以学习到如何在每一个维度上划分抛物线,并自行设计最优策略。

Q-learning的工作方式与我们非常相似:

  • 观察(隐私化)系统的状态
  • 基于一种策略选择一个行动
    • 如果该行动使系统进入了一个理想状态(更接近目标),则将该行动/初始状态标记为更理想的状态
  • 重复以上步骤

将您的系统状态离散化。
对于每个状态,都有一个准随机初始化的映射表,将每个状态映射到一个操作(这是策略)。还为每个状态分配一个期望值(最初,在所有地方都为零,在目标状态(X=0,V=0)处为1000000)。
  • 您的状态将是您的3个位置、3个角度、3个平移速度和3个旋转速度。
  • 您的操作可以是任何推进器的组合。

训练

训练人工智能(离线阶段):

  • 生成许多不同的情况
  • 应用策略
  • 评估新状态
  • 让算法(参见上面的链接)加强所选择的策略的可取性值。

游戏中的实时应用

经过一段时间,全局导航策略会逐渐形成。然后您将其存储,在游戏循环中只需对策略进行采样,并在每个情况下应用它。

在此阶段,策略可能仍会学习,但可能会更慢(因为它是实时发生的)。 (顺便说一句,我梦想着有一个游戏,AI可以从每个用户的反馈中学习,这样我们就可以共同训练它^^)


在一个简单的一维问题中尝试一下,它能够快速设计出一种策略(仅需几秒钟)。
在二维问题中,我认为可以在一个小时内得到优异的结果。
对于三维问题......您需要进行一夜计算。有一些方法可以尝试加速这个过程:
1.尽量不要“忘记”以前的计算,并将其作为初始“最佳猜测”策略输入。保存到文件! 2.您可能会放弃一些状态(例如Ship Roll?),而不会失去太多的导航优化,但可以大大提高计算速度。也许改变参考系,使船始终在X轴上,这样你就可以丢弃x&y维度! 3.更频繁遇到的状态将具有可靠且非常优化的策略。也许标准化状态,使您的船始终接近“标准”状态? 4.通常旋转速度间隔可能是安全的(您不希望船只狂乱地翻滚,因此策略总是“解除绕组”那种速度)。当然,旋转角度也被限制。 5.您还可以通过非线性离散化位置,因为远离目标,精度不会对策略产生太大影响。

1
针对这类问题,有两种技术可用:暴力搜索和启发式算法。暴力搜索意味着将问题视为具有输入和输出参数的黑盒子,并旨在获取获胜游戏的正确输入参数。要编程这样的暴力搜索,游戏物理运行在模拟循环(物理模拟)中,并通过随机搜索(最小化搜索,alpha-beta-prunning)尝试每种可能性。暴力搜索的缺点是高CPU消耗。
另一种技术利用了对游戏的了解。了解运动基元和评估知识。这些知识使用像C ++或Java这样的普通计算机语言进行编程。这个想法的缺点是,通常很难掌握这些知识。
解决太空船导航的最佳实践是将两种思路结合成混合系统。为此具体问题编写源代码,我估计需要近2000行代码。这种类型的问题通常在许多程序员参与的大型项目中完成,需要约6个月的时间。

这是一篇很好的文章,作为人工智能教材某些章节的介绍。它非常广泛。如果我问如何编写2D平台游戏或实时策略游戏中的敌人AI,这个答案仍然是兼容的。如果这个答案能更加专注于这个问题就更好了。例如,在我看来,极小化算法不适用于这种情况。感谢这个图! - javaLover
你说得对,答案更为普遍。详细的回答应该包括可运行的代码,不仅模拟了太空飞船游戏,还实现了该游戏的求解器。我认为在这里讨论编码本身是不相关的... - Manuel Rodriguez
不需要可运行的代码,我同意这可能是期望过高了。如果您没有时间起草伪算法,一些特定的关键词或大致的想法仍然非常有用。例如,包含类似于https://dev59.com/F5zha4cB1Zd3GeqPAB1W#40359322的大致想法的答案是回答我的问题的非常好的方式。:) - javaLover

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接