Inaugural Programming Challenge

[faust1706]

I am not entirely certain if a big-O exists of a solution based on a probabilistic solution. I would be delighted if one existed. For now, to accompany this algorithm, try to prove mathematically that this method is guaranteed to converge (find a path from start to end that meets the robot requirements).

Originally Posted by Marlow

This is turning into a really interesting and challenging problem!

Perhaps one day something like this could be used in FRC

If you really want to get advanced, try creating a smooth path from the discrete one you are calculated (aka splines) or simply feed it into my trajectory planner.

In order for something like this to be used in FRC, the robot must be able to identify its initial state (which COULD be assumed to be (0,0,0,...,0), but global reference is preferred for me), where it wants to be (goal state), and potential obstacles (robots, walls, pyramids...).

If you have a fast enough algorithm, you could implement it with 2D LIDAR to get the environment information that you need in real time. If you have a vision algorithm that yields where you are on the field and can locate game pieces for you, it would be possible to compile all these pieces together to play the 2011, 2012, and 2013 (and maybe more) game completely autonomously.

[faust1706]

Your solution did indeed find a path for all 1000 random generated tests I ran on it. Could you test how well it scales with input size (grid size for now) and either post a graph in this thread or just as picture in media?

[faust1706]

I think @Marlow's new solution is the best anyone will come up with. It scales linearly with dimensions and logarithmically with iterations. While the number of iterations is not constant per a constant input, it allows converges faster than the standard A* algorithm and it does not matter how large the search space is.

I was hoping to do one of these challenges every few months, but it doesn't seem like it got very much interest.