[Question][Algorithms][Discussion] Turtle swarm management.

Hello! This is another topic from me today… I'm sorry.
I am searching for a good algorithm which helps to avoid collisions with multiple turtles moving in the same space. That's for my swarm quarry of course.
There is a master turtle which places all the mining turtles and give them orders and the module turtles controlled by master.
When the turtle is digging hole it's not a problem. All the collisions can occur while turtle is moving to the next mining spot or returning home. I was thinkinig about it a bit, and I have two ideas. First one is not very good - Only one turtle can move to the new place at the same time. It is slow and… too stupid.

Second Idea that I haven't implemented yet is to divide all the area to 4x4x4 cubes. Only one turtle can be inside that cube. Also make a common route between those cubes that all the turtles will follow, so the only thing master should check is whether the turtle is allowed to move to the next cube. The route should cover all the mining area, so turtle can reach any mining spot by following that route. I haven't figured out yet how to make that route. It's a simple zig-zag of course, but first turtles should reach the beginning of that zig-zag.

If someone have another good idea or an advise, I would be glad to read one ^_^/>

Another solution might be a "highway" structure where you can only go 1 way on half of the area where the turtles are allowed to move, and the other way on the other side of the area. Then you make the turtles always enforce their movements and make sure they are done, with this structure you wont have any position where turtles can move into each other face to face and bug out, so you will have a nonstop system. Though, the turtle will go a innefficient route, but that isn't that much of a problem

You can use the peripheral event to check for adjacent turtles. If a turtle is in the way, just wait for it to move away os.pullEvent("peripheral_detach").

Doyle3694, on 13 March 2013 - 11:36 PM said:

Another solution might be a "highway" structure where you can only go 1 way on half of the area where the turtles are allowed to move, and the other way on the other side of the area. Then you make the turtles always enforce their movements and make sure they are done, with this structure you wont have any position where turtles can move into each other face to face and bug out, so you will have a nonstop system. Though, the turtle will go a innefficient route, but that isn't that much of a problem

Yeah, that might work. So they will move in some sort of a ring pattern, right?

ChunLing, on 13 March 2013 - 11:42 PM said:

You can use the peripheral event to check for adjacent turtles. If a turtle is in the way, just wait for it to move away os.pullEvent("peripheral_detach").

Yes, I thought about that. But that's just a way to detect turtles. There are might be some deadlocks when two turtles facing each other are wainting for each other to go away.

Pretty much yes, a ring pattern. Another solution might just be the main turtle tracking each turtle and not letting 2 turtles relocate at the same time, ofcourse, that would create delays the more turtles you have

Doyle3694, on 14 March 2013 - 12:02 AM said:

Another solution might just be the main turtle tracking each turtle and not letting 2 turtles relocate at the same time, ofcourse, that would create delays the more turtles you have

That's my first solution and it is awfully slow. I don't like it. I'll think about the ring algorithm since there are some issues that can occur if it's not done carefully

A simple practice done in a lot of turtle programs is to just

repeat until turtle.forward()

and the like with other directions, rather than waiting for the turtle to go away as a peripheral.

If two turtles face each other, have them both turn right, go forward, turn left, go forward twice, left, forward, right, then forward again. Subsequently, they should both go around each other.

In the event that they collide head to bottom, both of the turtles know where they are located relative to each other in the conflict. If the turtle is conflicted moving down, go forward, down twice, and back. If the turtle is conflicted going up, the turtle on top is going to be moving out of the way anyway with the process I've described, so you can just wait until the turtle moves away using the repeat until.

You could probably have some sort of a delay before recognizing a conflict, to know for sure that neither turtle is moving anytime soon.

I would set up a gps server to track all of them and if colissions are detected, it could redirect one of the turtles

Yeah, I can resolve collisions, but now I'm more interested in algorithm that avoids collisions at all.

In that case, just assign a single forward row for turtles to mine, and not have them cris-crossing all over the damn place.

Nah, I'll just use that "highway" navigation method by Doyle3694. I like it

And here is my new navigation library. The highway navigation begins at line 352 http://pastebin.com/FqVKsDtJ

By the way, are commens in my code good? I'm not sure… I'm trying to explain everything i'm doing, but maybe noone does care about it ^_^/>'