ComputerCraft (Minecraft mod) navigation: Collision avoidance and path planning/finding in 2D/3D space

Question

I'm programming Lua for controlling computers and robots in-game in the Minecraft mod ComputerCraft.

ComputerCraft has these robots called Turtles, that are able to move around in the grid based(?) world of Minecraft. They are also equipped with sensors making them able to detect blocks (obstacles) adjacent to them. Turtles execute Lua programs written by a player.

As a hobby project I would like to program a goto(x, y, z) function for my Turtles. Some Turtles actually have equipment to remove obstacles, but I would like to make them avoid obstacles and thus prevent the destruction of the in-game environment.

I have no prior experience in robotics, but I have a B.Sc. in Computer Science and am now a lead web developer.

I did some research and found some basic strategies, namely grid based and quadtree based. As I have no experience in this area, these strategies might be old school.

Note that Turtles are able to move in three dimensions (even hover in any height). I could share the obstacles as well as obstacle free coordinates in a common database as they are discovered if that would help me out, as most obstacles are stationary once they are placed.

What are my best options in this matter? Are there any easy fixes? Where do I look for additional resources?

Thank you very much in advance! :-)

EDIT: Thank you for your feedback!

I started reading the book Artificial Intelligence: A Modern Approach, 3rd Edition to get up to speed on basic theory as suggested by Ian. Pointers to other educational resources are appreciated.

Also, I started developing a basic navigation algorithm for moving in unexplored areas, similar to what Cube suggested.

The priority for me is as few moves as possible, as it costs time and fuel cells for each additional move (approx. 0.8 seconds and 1 fuel cell per move in either direction). I plan on using the Euclidean heuristics function in a Greedy Best-First Search for computing a path that is expected to be quite optimal in reducing the number of moves to reach the goal, if enough data is available from the shared database from previous exploration.

Each time an obstacle is reached, I plan to use the following very basic algorithm, exploiting the fact that Turtles are able to move vertically:

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 using this algorithm, records are kept of the explored coordinates and uploaded to a shared database. However, there are some cases, that I did not consider:

- 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)

Maybe if enough exploration data of the area is available, a Jump Point Search is performed to calculate an optimal path. However this assumes a 2D map. How can I take the 3rd dimension into account?

Also, what would be a good data structure to store the exploration data?

Answer 1

What comes to my mind first is some sort of bug algorithm. That is a path finding algorithm that has only small constant amount of memory and only sees (small) local parts of the world.

You can imagine this as

1. Go directly to the goal
2. If there is an obstacle in a way, pick a direction and start going around it
3. Once there is a free path again, goto 1

Of cause there are some problems with this, I'm not entirely sure that this will work in 3D. Selecting a way around an obstacle will be a little trickier than just saying "always go right". Other than that, this algorithm can select a wrong direction and spend a long time going around the obstacle which it could avoid easily by going other way around it.

These slides might help you with some of the details.

Answer 2

It looks like your research here is a little too specific -- you're working on the practical level before being up to speed on the theory. Take a look at more of the higher-level concepts of motion planning and obstacle avoidance.

The extremely simplified process is:

1. Expressing a high-level objective for the robot
2. Based on data describing the current environment, creating a set of planned movements that meet the objective (using path planning algorithms like A* search)
3. As time passes, collecting new data about the environment (e.g. current position, new obstacles) and re-planning the path

Quadtrees and grids are just 2 ways of representing the environment itself; one of the practical problems involved in robotics is the sheer volume of data that can come in, and quadtrees offer a more memory-space-efficient representation of that data (see also, octrees for 3D spaces) in return for some extra CPU time and complexity. There are many such optimizations that you could make, but it sounds like you're considering them a little too early in the design process.