pic: N Dimensional Exploring Tree

[Marlow]

loading photo ...

[SenorZ]

This visually reminds me of a research project I did in college. Trying to find out if a branched dendrimer chain (polymer) could form a hollow ball, or if it would "fill in".
Always filled in.

[faust1706]

To add context to this because I feel most people don't understand the significance of this:

Marlow (re)created a n dimensional path finding algorithm that is magnitudes times faster than the standard a* algorithm. While the path constructed is virtually never the most optimal path, it finds the path fast enough such that it can be implemented in real time and does not matter how refined the grid is because it uses a floating point grid at all times. With a trajectory smoother algorithm, a discrete path using this RRT (rapidly exploring random tree) may be found, and then smoothed using gradient descent in real time.

This is what the robots in the DARPA robotics competition were doing in real time when they were climbing over debris or getting their hand in position to turn a valve, except the search space had many more dimensions than 2.

[Marlow]

To expand on @faust1706's explaination:

My method constructs 2 RRTs, one from the initial state, the other from the goal state. The program is constructs these 2 trees independently and simultaneously. After every few iterations, the program checks to see if the shate a point, or roughly share a point, in space. It goes until they do, then the path is going down the tree based at the initial starting point and then it goes up the goal tree from the shared point.

While this method isn't the greatest for low dimensionality search spaces, it shines when the dimensions start getting big as it scales linearly with dimensions.

I'm curious to see if any team will ever actually implement this. Alas I don't think teams have the ability to given the amount of moving pieces it has. It seems like it'd be a nightmare.

[Marlow]

To expand on @faust1706's explaination:

My method constructs 2 RRTs, one from the initial state, the other from the goal state. The program is constructs these 2 trees independently and simultaneously. After every few iterations, the program checks to see if the shate a point, or roughly share a point, in space. It goes until they do, then the path is going down the tree based at the initial starting point and then it goes up the goal tree from the shared point.

While this method isn't the greatest for low dimensionality search spaces, it shines when the dimensions start getting big as it scales linearly with dimensions.

I'm curious to see if any team will ever actually implement this. Alas I don't think teams have the ability to given the amount of moving pieces it has. It seems like it'd be a nightmare.

[kylestach1678]

Originally Posted by Marlow

I don't think teams have the ability to given the amount of moving pieces it has. It seems like it'd be a nightmare.

Not to mention the fact that no game so far has called for much more than basic autonomous capability...

[Marlow]

It'd be cool to see a robot recalculate its autonomous every game, though.

[GeeTwo]

I cannot tell where the start or end points are; I thought this was searching from one point (presumably 57, 56), not two. It would be helpful if the nodes were color-coded by the iteration number. If it would not be too cluttered, displaying the obstacles would be nice, as well.

Finally, I'm not sure if I misread the original problem statement, but I understood that the goal was to optimize the route, not the search for any route. In optimizing the route, you would probably want to use the corners and edges of the obstacles as search nodes, as well as random points away from the obstacles. This tactic would also help locate paths through narrow gaps that the unconstrained exploring tree would be likely to miss.

[kylestach1678]

Originally Posted by Marlow

It'd be cool to see a robot recalculate its autonomous every game, though.

That won't really be necessary until there is a game that has an autonomous where things aren't in the same place every time. Autonomous endgame, anyone?

[kylestach1678]

Originally Posted by Marlow

It'd be cool to see a robot recalculate its autonomous every game, though.

That won't really be necessary until there is a game that has an autonomous where things aren't in the same place every time. Autonomous endgame, anyone?

[Peter Johnson]

Originally Posted by kylestach1678

That won't really be necessary until there is a game that has an autonomous where things aren't in the same place every time. Autonomous endgame, anyone?

We've had games like that. In 2008, the balls were placed in random initial positions at the start of every match and you got points for knocking yours down. The challenge was made easier with IR receivers making it a hybrid rather than pure auto mode, but with more powerful image processing available now it would be fun to have a similar auto challenge with hybrid disallowed.

[Marlow]

Originally Posted by GeeTwo

I cannot tell where the start or end points are; I thought this was searching from one point (presumably 57, 56), not two. It would be helpful if the nodes were color-coded by the iteration number. If it would not be too cluttered, displaying the obstacles would be nice, as well.

Finally, I'm not sure if I misread the original problem statement, but I understood that the goal was to optimize the route, not the search for any route. In optimizing the route, you would probably want to use the corners and edges of the obstacles as search nodes, as well as random points away from the obstacles. This tactic would also help locate paths through narrow gaps that the unconstrained exploring tree would be likely to miss.

Huh. I never thought about using the obstacles to guide the path itself. I always viewed them as disallowing certain paths (I'm here, I can't go to the right because there is an obstacle there, go somewhere else).

I am working on making the visualizer run in real time as the tree is being constructed, but I'm on holiday so I don't know when that will get done. I think that would be cool. This little demo doesn't find paths and therefore doesn't take obstacles into account. I wrote the program first and am just now getting to the visualizer.

The final demo program will be the actual program I submitted to @faust1706 with the case n = 2 (maybe another visualizer where n = 3), and it will be of the two trees growing with obstacles being displayed, with every piece of what is happening.

I wish I had the ability to actually use this on a small arduino bot or something, but I don't know how to do vision processing to find obstacles or make the robot go from (x1, y1) to (x2, y2). If I do could do that, then I'd love to see them on a quadcopter for some aerial maneuvers. I have lots to learn in terms of control theory and theoretical computer science!