ComputerCraft具有这些称为Turtles的机器人，它们能够在基于Minecraft的网格世界中移动。 。它们还配备了传感器，使它们能够检测与其相邻的块（障碍物）。 Turtles执行玩家编写的Lua程序。
作为一个业余项目，我想为自己的Turtles编写
goto(x, y, z)函数。有些海龟实际上具有清除障碍物的设备，但我想让它们避开障碍物，从而防止破坏游戏中的环境。理学学士我进行了一些研究，发现了一些基本策略，即基于网格和基于四叉树。由于我在这方面没有经验，因此这些策略可能比较老套。
请注意，海龟可以在三个维度上移动（甚至可以悬停在任何高度）。我可以在一个公共数据库中共享障碍物和无障碍坐标，因为发现它们对我有帮助，因为一旦放置障碍物，大多数障碍物便会静止。
我最好的选择是什么这件事？有没有简单的解决方法？我在哪里可以找到其他资源？
非常感谢！ :-)
编辑：谢谢您的反馈！
我开始阅读《人工智能：现代方法》第三版，以尽快掌握基础理论。伊恩建议。感谢指向其他教育资源的指针。
我也开始开发一种基本的导航算法，用于在未探索的区域中移动，类似于Cube的建议。
对我来说，优先考虑的是尽可能少的动作，因为这会花费时间和燃料电池，每增加一个动作（在任一方向上每个动作大约需要0.8秒和1个燃料电池）。我计划在Greedy Best-First Search中使用欧几里得启发式函数来计算一条路径，如果从先前的探索中可以从共享数据库中获得足够的数据，则该路径在减少达到目标的移动次数方面将是非常理想的。
每次遇到障碍时，我计划使用以下非常基本的算法，以利用海龟能够垂直移动的事实：
1. Calculate direct horizontal path to the goal.
2. Turn to the direction of the next step of the path.
3. If an obstacle is detected in front of the Turtle go to 5. If this is the 4th time that an obstacle is detected in front of the Turtle after moving up, go to 6.
4. Move forward, go to 2.
5. If no obstacle is detected above the Turtle, move up and go to 3, else go to 7.
6. Backtrack to the coordinates the Turtle was in before moving upwards.
7. Turn left, go to 3.
使用此算法时，记录将保留探索的坐标并上传到共享数据库。但是，在某些情况下，我并未考虑：
- When should it move down?
- What if the goal is not reachable from a coordinate directly above it?
- If no horizontal move in any direction is possible, how long should it backtrack?
- How to detect unreachable goals (obstacles can then be removed if requested)
也许如果该地区有足够的勘探数据，则可以执行跳转点搜索来计算最佳路径。但是，这假设为2D地图。如何考虑三维空间？
此外，什么是存储勘探数据的良好数据结构？
#1 楼
我首先想到的是某种错误算法。这是一种路径查找算法，仅具有少量恒定的内存，并且只能看到世界的（很小）局部。 >直接进入目标如果有障碍，请选择一个方向并开始绕行
一旦再次有自由路径，请转到1
因为存在一些问题，我不确定这是否可以在3D模式下正常工作。选择绕过障碍物的方法比说“总是向右走”要复杂一些。
这些幻灯片可能会帮助您提供一些细节。
评论
$ \ begingroup $
3d世界的本质是“越过”障碍物总是比“绕过”更好。当然，除非您在隧道中。似乎在飞行中没有能量损失...
$ \ endgroup $
– Mhz4.77
2014年1月4日在16:36
$ \ begingroup $
感谢您的建议。您说得对，Mhz4.77。请参阅我的草稿中更新的问题。
$ \ endgroup $
– Lars Gyrup Brink Nielsen
2014年1月5日12:02
#2 楼
看来您在这里的研究有点太具体了-您需要在实践层面上进行研究，然后才能加快理论学习的速度。进一步了解运动计划和避障的更高级概念。极其简化的过程是：
表达高级目标机器人
基于描述当前环境的数据，创建一组满足目标的计划动作（使用A *搜索等路径计划算法）
随着时间的流逝，收集有关环境的新数据（例如当前位置，新障碍）和重新规划路径
四叉树和网格只是代表环境本身的两种方式；机器人技术涉及的实际问题之一是可能会传入大量数据，而四叉树提供了该数据的内存空间效率更高的表示形式（另请参见3D空间的八叉树），以换取一些额外的CPU时间和复杂。您可以进行许多这样的优化，但是听起来您在设计过程中就考虑得太早了。
评论
如果我想这样做，我会看一下A * ...的某些变体。很高兴我的回答对您有所帮助，我建议您将您的编辑内容分解为一个全新的问题，以便我们可以更直接地解决。
我也想过，伊恩。我发现了很多有关这些主题的有用的书。随着我研究更多的理论并思考我希望机器人代理具有的功能，我需要回答的问题变得越来越清晰。