宇宙飞船推进的AI:在位置= 0和角度= 0的情况下着陆3D船
jav*_*ver 33 artificial-intelligence path-finding game-physics
对于太空游戏来说,这是一个非常困难的问题,即如何操纵可以在3D中平移和旋转的宇宙飞船.
宇宙飞船有n各种位置和方向的喷气式飞机.
i相对于宇宙飞船的CM ,-th jet的变换是常数= Ti.
- 变换是位置和方向的元组(四元数或矩阵3x3或更不优选的欧拉角).
- 转换也可以用单个矩阵4x4表示.
换句话说,所有喷射器都粘在船上并且不能旋转.
射流只能沿其轴线方向(绿色)向太空船施加力.
由于胶水,轴与飞船一起旋转.
所有喷射都可以Fi在一定幅度(标量)上施加力(矢量fi):
i- 喷射可以仅在范围内施加力(Fi= axisx fi)min_i<= fi <=max_i.
两个min_i和max_i与已知值恒定.
需要明确的是,单位min_i,fi,max_i是牛顿.
防爆.如果范围不包括0,则表示无法关闭喷嘴.
宇宙飞船的质量= m和惯性张量= I.
宇宙飞船的当前变换= Tran0,velocity = V0,angularVelocity = W0.
宇宙飞船物理学家遵循众所周知的物理规则: -
Torque=r x F
F=ma
angularAcceleration = I^-1 x Torque
linearAcceleration = m^-1 x F
I每个方向都有所不同,但为了简单起见,每个方向都有相同的值(球形).因此,I可以认为是标量而不是矩阵3x3.
题
如何控制所有喷气机(全部fi)以位置= 0和角度= 0降落船舶？
数学类规格:查找的功能fi(time)是需要的最短时间到达position=(0,0,0),orient=identity与最终angularVelocity和velocity=零.
更具体地说,解决这个问题的技术名称或相关算法是什么？
我的研究(1维)
如果宇宙是1D(因此,没有旋转),问题将很容易解决.
(感谢 Gavin Lock,/sf/answers/2825152571/)
首先,找到价值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中,问题要困难得多.
注意:
只是一个粗略的指导指向我正确的方向非常感谢.
我不需要完美的AI,例如它可能需要更多的时间而不是最佳.
我想了一个多星期,仍然没有发现任何线索.
其他尝试/意见
- 我认为机器学习不像神经网络那样适合这种情况.
- 边界约束最小二乘优化可能是有用的,但我不知道如何使我的两个超抛物线适应这种形式的问题.
- 这可以通过使用多次迭代来解决,但是如何？
- 我搜索过美国宇航局的网站,但没有找到任何有用的东西.
- 该特征可能存在于"太空工程师"游戏中.
- Logman评论:机械工程知识可能有所帮助.
- AndyG评论说:这是一个带有非完整约束的运动规划问题.它可以通过快速探索随机树(RRT),围绕 Lyapunov方程的理论和线性二次调节器来解决.
- John Coleman评论说:这看起来更像是AI的最佳控制.
编辑:"近0假设"(可选)
- 在大多数情况下,AI(待设计)连续运行(即每个时间步都称为).
- 因此,与AI的调整,
Tran0是平时的近身份,V0并且W0是通常不是从0如此不同,例如|Seta0|<30 degree,|W0|<5 degree per time-step. - 我认为基于这个假设的AI在大多数情况下都可以正常工作.虽然不完美,但它可以被认为是一个正确的解决方案(我开始认为没有这个假设,这个问题可能太难了).
- 我有点觉得这个假设可能会使一些使用"线性"近似的技巧.
第二个替代问题 - "调整12个变量"(更简单)
上述问题也可能如下: -
我想使用最少的时间步长将所有六和values六values'(一阶导数)调到0.
这张表格显示了AI可能面临的可能情况: -
该乘数表店inertia^-1 * r,并mass^-1从原来的问题.
该乘数和范围是恒定的.
每个时间步,AI都会被要求选择一个fi必须在[min_i,max_i]每个i+1喷射范围内的值元组.
防爆.从表中,AI可以选择(f0=1,f1=0.1,f2=-1).
然后,调用者将使用Multiplier表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(可以是不同的时间步长不同的),以使Px,Py,Pz,SetaX,SetaY,SetaZ,Px',Py',Pz',SetaX',SetaY',SetaZ'= 0(或非常接近),
通过使用至少的时间步长量为可能.
我希望提供另一个问题的观点将使其更容易.
这不是完全相同的问题,但我觉得可以解决这个版本的解决方案可以让我非常接近原始问题的答案.
这个替代问题的答案非常有用.
第三个替代问题 - "调整6个变量"(最简单)
这是前一替代方案的有损简化版本.
唯一的区别是世界现在是2D,Fi也是2D(x,y).
因此,我必须只调Px,Py,SetaZ,Px',Py',SetaZ'= 0,通过使用的时间步长尽可能最少.
对这个最简单的替代问题的答案可以被认为是有用的.
我会尽量保持这简短而甜蜜.
在模拟中经常用于解决这些问题的一种方法是快速探索随机树.为了给我的帖子至少提供一点可信度,我承认我研究了这些,并且运动规划是我的研究实验室的专业领域(概率运动规划).
阅读这些的规范性论文是Steven LaValle的快速探索随机树:一种新的路径规划工具,自那以后,已经有一百万篇论文以某种方式对其进行了改进.
首先,我将介绍RRT的最基本描述,然后我将描述当你有动态约束时它是如何改变的.之后我会随便摆弄它:
术语
"空间"
你的宇宙飞船的状态可以用它的三维位置(x,y,z)和它的三维旋转(alpha,beta,gamma)来描述(我使用那些希腊名称,因为它们是欧拉角).
国家空间是你的飞船可以居住的所有可能的位置和旋转.当然这是无限的.
碰撞空间都是"无效"状态.即实际上不可能的立场.这些是你的飞船与某些障碍相撞的状态(与其他机构相比,这也包括与自身的碰撞,例如规划一段链条).缩写为C-Space.
自由空间是任何不是碰撞空间的东西.
一般方法(无动力学约束)
对于没有动态约束的身体,这种方法相当简单:
- 采样一个州
- 找到该州最近的邻居
- 尝试规划邻居和州之间的路线
我将简要讨论每一步
采样一个州
在最基本的情况下采样状态意味着为状态空间中的每个条目选择随机值.如果我们使用您的太空飞船执行此操作,我们会随机抽取所有可能值的x,y,z,alpha,beta,gamma(均匀随机抽样).
当然,你的空间通常比自由空间更多是障碍空间(因为你通常将你的对象限制在你想要移动的某个"环境"内).因此,常见的做法是采用环境的边界立方体并在其中采样位置(x,y,z),现在我们有更高的机会在自由空间中进行采样.
在RRT中,您将在大多数时间随机抽样.但有一些概率你实际上会选择你的下一个样本作为你的目标状态(玩它,从0.05开始).这是因为您需要定期测试以查看从开始到目标的路径是否可用.
寻找采样状态的最近邻居
你选择了一些> 0的固定整数k.让我们调用那个整数.你k最近的邻居在州空间附近.这意味着您有一些距离指标可以告诉您各州之间的距离.最基本的距离度量是欧几里德距离,它只考虑物理距离而不关心旋转角度(因为在最简单的情况下,你可以在一个时间步长内旋转360度).
最初你只有你的起始位置,因此它将是最近邻居列表中的唯一候选者.
规划州之间的路线
这称为地方规划.在现实世界的场景中,你知道你要去哪里,以及你需要躲避其他人和移动物体的方式.我们不会在这担心这些事情.在我们的规划世界中,我们假设宇宙是静态的,但对我们而言.
最常见的是假设采样状态与其最近邻居之间存在一些线性插值.邻居(即已经在树中的节点)逐位沿着该线性插值移动,直到它到达采样配置,或者它行进一些最大距离(调用您的距离度量).
这里发生的是你的树正在向样本生长.当我说你"一点一滴"时,我的意思是你定义一些"delta"(一个非常小的值)并沿着线性插值移动每个时间步长.在每个点上,您检查新状态是否与某个障碍物碰撞.如果遇到障碍物,则将最后一个有效配置保留为树的一部分(不要忘记以某种方式存储边缘!)因此,本地规划人员需要的是:
- 碰撞检查
- 如何在两个状态之间"插入"(对于你的问题,你不必担心这个,因为我们会做一些不同的事情).
- 用于时间步长的物理模拟(欧拉积分很常见,但不像Runge-Kutta那样稳定.幸运的是你已经有了物理模型!
动态约束的修改
当然,如果我们假设您可以在状态之间进行线性插值,那么我们将违反您为宇宙飞船定义的物理特性.所以我们修改RRT如下:
- 我们不是对随机状态进行采样,而是对随机控制进行采样,并将所述控制应用于固定的时间段(或直到碰撞).
之前,当我们对随机状态进行采样时,我们真正在做的是选择一个方向(在状态空间中)来移动.现在我们有了约束,我们随机地对控件进行采样,这实际上是相同的,除非我们保证不会违反我们的约束.
在固定时间间隔(或直到碰撞)应用控件后,将节点添加到树中,控件存储在边缘上.你的树会快速生长,探索空间.该控制应用程序取代了树状态和采样状态之间的线性插值.
采样控件
你有n喷气机,它们可以单独使用一些最小和最大力量.每个喷嘴的最小和最大力范围内的样品.
我将控件应用到哪个节点？
那么你可以随意选择,或者你可以偏向选择以选择最接近目标状态的节点(需要距离度量).随着时间的推移,这种偏向将尝试使节点更接近目标.
现在,通过这种方法,您不太可能完全达到目标,因此您需要定义"足够接近"的定义.也就是说,您将使用距离度量来查找目标状态的最近邻居,然后测试它们"足够接近".这种"足够接近"的指标可能与您的距离指标不同.如果您正在使用欧几里德距离,但是目标配置也正确旋转非常重要,那么您可能需要修改"足够接近"的指标来查看角度差异.
什么是"足够接近"完全取决于你.还有一些东西可供您调整,而且有一百万篇论文试图让您在第一时间更加接近.
结论
这种随机抽样可能听起来很荒谬,但是你的树会很快地探索你的自由空间.在RRT上查看一些有关路径规划的YouTube视频.我们不能保证具有动态约束的"概率完整性",但它通常"足够好".有时候解决方案可能不存在,所以你需要在那里放一些逻辑以在一段时间后停止生长树(例如20,000个样本)
更多资源:
从这些开始,然后开始查看他们的引用,然后开始研究谁在引用他们.
这不是一个答案,但作为评论放置太久了.
首先,真正的解决方案将涉及线性编程(用于具有将在许多子步骤中使用的约束的多变量优化)以及用于轨迹优化和/或控制理论的技术.这是一个非常复杂的问题,如果你能解决它,你可以在你选择的任何公司找到一份工作.唯一可以使这个问题变得更糟的是摩擦(阻力)效应或外部人体引力效应.一个真正的解决方案也可以理想地使用Verlet集成或4阶Runge Kutta,它提供了对您在此处实现的Euler集成的改进.
其次,我相信你上面提到的问题的"第二替代版本"已经省略了对你在每个时间步长添加到位置的位移矢量的旋转影响.虽然喷射轴相对于船舶的参照系保持固定,但它们相对于您用于降落船舶的全球坐标系(全局坐标)不会保持固定[0, 0, 0].因此,[Px', Py', Pz']矢量(根据船舶的参照系计算)必须在应用于全球位置坐标之前在所有3个维度上进行适当的旋转.
第三,您未能指定一些隐含的假设.例如,应将一个维度定义为"着陆深度"维度,并禁止使用负坐标值(除非您接受火灾崩溃).我为此开发了一个模型模型,其中我假设z维度为着陆维度.这个问题对初始状态和喷射器上的约束非常敏感.我使用上述示例初始条件的所有尝试均无法降落.例如,在我的模型中(没有上面提到的3d位移矢量旋转),喷射约束仅允许在z轴上沿一个方向旋转.因此,如果aZ在任何时候变为负值(通常是这种情况),船舶实际上必须在该轴上完成另一次完整旋转,然后才能再次接近零度.此外,如果没有三维位移矢量旋转,您将发现Px只会使用您的示例初始条件和约束来消极,并且当船舶试图操纵时,船舶被迫在更远和更远的方向上飞向负X轴.解决这个问题的唯一方法是真正结合旋转或允许足够的正和负喷射力.
然而,即使我放松了你的最小/最大力限制,我也无法让我的模型成功降落,这表明这里可能需要复杂的规划.除非可以在线性编程空间中完全解决这个问题,否则我认为你需要结合高级"智能"的高级规划或随机决策树,以便不断使用旋转方法将最灵活的喷嘴重新定向到当前最必要的轴上.
最后,正如我在评论部分所述,"2015年5月14日,太空工程师的源代码在GitHub上向公众免费提供." 如果你认为游戏已经包含了这个逻辑,那应该是你的起点.但是,我怀疑你一定很失望.大多数太空游戏着陆序列只是控制船只而不模拟"真实"力矢量.一旦你控制了一个三维模型,就可以很容易地预先确定一个旋转的三维样条,这样可以使船在预定的时间内轻柔地降落并具有完美的方位.为什么任何游戏程序员都会通过这个级别的工作来完成着陆序列？这种逻辑可以控制ICBM导弹或行星漫游车再入飞行器,这对游戏来说简直过分嘲讽(除非游戏的目的是为了看看你是否可以使用任意喷气式飞机降落受损太空船而不会发生碰撞) .