遥控车算法
我正在寻找一种算法，但我不知道从哪里开始！
我正在尝试从笛卡尔图中的 A 点到达 B 点。运动仅限于遥控汽车的运动：向后、向前、左前和右前（恒定的转弯半径；汽车要么完全转弯，要么根本不转弯）。
我将如何构建一个算法，该算法采用以下步骤：
turningRadius, initialPosition, initialOrientation, finalPosition
并产生一组有序的步骤来到达 FinalPosition？
请注意，我不在乎最终的方向是什么。
谢谢！
编辑：请注意，这不是在具有离散节点的图中，而是在连续的坐标系中
I'm looking for an algorithm, and I have no idea where to start!
I'm trying to get from point A to point B in a cartesian graph. Movement is restricted to that of a RC car: backward, forward, forward-left, and forward-right (constant turning radius; car is either turning completely, or it is not turning at all).
How would I construct an algorithm which takes the following:
turningRadius, initialPosition, initialOrientation, finalPosition
And yields an ordered set of steps to get to finalPosition?
Note that I don't care what the final orientation is.
Thanks!
EDIT: Note that this is not in a graph with discreet nodes, but a continuous coordinate system
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
按照您描述问题的方式，该算法很简单，只需要两个简单的步骤：1）在转弯（左或右）时向前移动，直到汽车直接指向 B，2）向前直行，直到撞到 B。完成。
唯一相对棘手的部分是第一步。如果 B 在初始位置位于汽车纵轴的左侧，则自然的方法是从左转开始。这将起作用，除非 B 点位于此类左转（半径为
turningRadius）产生的圆形轨迹内。在后一种情况下，汽车会绕圈行驶，但永远无法直接瞄准 B。在这种情况下，正确的策略实际上是从右转开始，然后继续转弯，直到瞄准 B。 右转因此，如果您对轨迹没有任何最优性要求，第一步最简单的算法就是无条件地“远离”该点：如果 B 位于则 位于汽车纵轴的左侧，如果 B 位于右侧，则向左转。继续转动，直到汽车直接瞄准 B。这听起来有点不自然，但它总是有效的，即您始终能够最终瞄准汽车。
如果您关心更优化（更短）的轨迹，那么您需要分析 B 相对于汽车的初始位置/方向的位置（“B 是在转弯圆内还是在转弯圆外？”）并选择 B 的方向相应地进行第一个转弯。
The way you problem is described, the algorithm is straightforward and requires only two simple steps: 1) move forward while turning (left or right) until the car is pointed directly at B, 2) move straight forward until you hit B. Done.
The only relatively tricky part is the first step. If B lies to the left from the longitudinal axis of the car in its initial position, the natural approach would be to start by turning left. This will work, unless point B lies inside the circular trajectory produced by such a left turn (of radius
turningRadius). In the latter case the car will run in circles, but will never be able to aim directly at B. In such cases the proper strategy is actually to start with a right turn and keep turning until you aim the car at B.So, if you don't have any optimality requirements for your trajectory, the simplest algorithm for the first step would be to unconditionally turn "away" from the point: turn right if B lies to the left of the longitudinal axis of the car, and turn left if B lies to the right. Keep turning until the car is aimed directly at B. This sounds a bit unnatural, but it always works, i.e. you will always be able to eventually aim the car.
If you care for a more optimal (shorter) trajectory, then you need to analyze the location of B with respect to the initial position/orientation of the car ("Is B inside the turning circle or outside?") and choose the direction of the first turn accordingly.
一般来说，这不是一个简单的问题。它属于“差异化约束下的规划”类别。 LaValle 的书的最后三章（可在线获取此处）讨论了这个问题。特别是，请查看第 14.4.2 节，它涉及“Dubins 汽车”，它类似于您的遥控汽车，只是它不会向后移动。
另搜索“杜宾斯汽车路径规划”。你会发现很多论文。
In general this is not an easy problem. It falls under the category of "Planning under differential constrains". The last three chapters of LaValle's book (available online here) deal with this. In particular, look at section 14.4.2., that deals with a "Dubins car", which is like your RC car, except that it doesn't move backwards.
Also search for "Dubins car path planning". You will find a lot of papers.
您尝试过*（a-star）吗？当你为它提供地形图时也很好。您可以为地形的不同部分分配权重，这将产生不同的路径。我相信默认情况下该算法不提供对角线方向，但您可以很容易地添加它。
此外，它默认不处理“转动”，但 a-star 会给出完整路径。您可以做的是根据 2 个点计算转弯半径。当前位置和下一个计算位置，或者最后一个位置和当前位置。然后，您可以随着角度的变化添加或减去面向方向。您可能需要对此进行一些调整。
Have your tried a* (a-star)? it is also nice when you provide it a terrain map. You can assign weights to different portions of terrain which will result in a different path. I believe the algorithm by default does not provide diagonal directions, but you can add that in pretty easily.
Also it does not by default deal with "turning" but a-star will give the full path. What you could do is calculate the turn radius based on 2 points. The current position and the next calculated position, OR the last position and the current position. You can then add or subtract the facing direction with the change in angle. You may need to tweak this some.
听起来是一个有趣又有趣的项目！要获得特定的算法建议，您可能应该提供更多详细信息……就像您希望在连接到遥控汽车的某种嵌入式控制器上运行它一样吗？或者是在工作站上运行并远程控制汽车的算法？ （或者这纯粹是一个抽象的练习，而且没有汽车……awwww。）
我对于从哪里开始的一般建议是构建问题解决者，这是对“AI”问题解决技术世界的精彩介绍。如今它可能有点过时了……但是等等，我在说什么！可能不会。 :-)
[好吧，我应该解释一下最后的评论：我在实践中看到的大多数“现代”人工智能技术实际上可以追溯到很多年前的想法......它们现在刚刚变得实用，这要归功于摩尔定律的不断进步。因此，从我个人的观察来看，1993 年写的一本书仍在讨论相当先进的技术。我很乐意指出一个反例！]
Sounds like an interesting and fun project! To get a specific algorithm recommendation, you should probably provide more detail… Like are you expecting to literally run this on some sort of embedded controller attached to an RC car? Or is the algorithm to run on a workstation and control the car remotely? (Or is this purely an abstract exercise and there is no car… awwww.)
My generic recommendation for getting a handle on where to start would be Building Problem Solvers, which is a great intro to the world of "AI" problem solving techniques. It might be a bit dated these days… but wait, what am I saying! Probably not. :-)
[Okay I should explain that last comment: Most "modern" AI techniques that I've seen in practice actually date back to ideas many years old… They've just become practical now thanks to the relentless advance of Moore's Law. So a book written in 1993 is still discussing fairly state-of-the-art techniques, from what I have personally seen. I'd love to be pointed at a counter-example!]