Inaugural Programming Challenge

[faust1706]

Inspired by the DARPA Robotics competition.

You have a robot with N degrees of freedom. Compute a discrete path in the robot's state space such that it goes from its original state, A, to a specified goal state, B, while avoiding obstacles.

A sample input for A and B: (A1, A2, A3, ... , An), (B1, B2, B3,...,Bn)
A sample input for obstacles (n=3):

0-5
1-3
2-7

1.2-4
-.2-0
10-11.4

You may use any language you desire. Not only will you be scored on completion of this task, but also efficiency of the program and code organization.

[GeeTwo]

I'm not planning to submit an entry, but I am trying to understand the problem.

Do I understand correctly that the obstacles are given in the robot's state space, rather than in a physical space? Does the sample obstacle set refer to two rectangular prisms in that three-dimensional state space?

Is there an assumption that the order in which state space is traversed does not matter? (Except to avoid obstacles)

For example, If I had a robot with one swerve wheel (and casters out on the corners so it doesn't fall over), and I started with the wheel facing north: If I were to have it drive forward five wheel revolutions and turn 90 degrees to the right, I'd wind up north of my initial position. If I turned 90 degrees to the right and drove five revolutions forward, I'd wind up east of my initial position. I'm at the same position in robot state space, but a different location in physical space.

[faust1706]

There can be M obstacles presented in the N dimensional space. Yes, the example objects given were 2 3 dimensional rectangles.

Distance of the path may also be taken into consideration.

One of the most trivial applications of this would be making a robot go from (x1, y1) to (x2, y2). It would be a 2 dimensional space.

I had not considered motors with this problem. The scope I viewed this problem was an advanced robotic arm trying to go from one position to another by stepping through positions that would arrive at the goal position.

State space was the wrong term. What I am asking for is an N dimensional *kinodynamic motion planning algorithm. There will be limitations as to how far in space the robot may move each iteration, but I have yet to decide on the exact restrictions

*The most famous problem is the piano mover's problem (http://mathworld.wolfram.com/PianoMoversProblem.html)

[GeeTwo]

Is the intention for this to be a "blind" robot that follows a single path to the end point that we're trying to optimize, or a "planner" that virtually follows many routes and then selects the "shortest" one?
If a planner, does the planning algorithm "know" a priori where the obstacles are (that is, it can directly access the table of obstacle positions, rather than having to virtually bump in to them)?

How large does this have to scale? That is, are you looking at "Big O" performance of robots with 100 degrees of freedom and 10,000 obstacles, or are we more likely to be solving problems with 2 to 7 DoF and a dozen obstacles? Optimizing for these cases is very different.

Are we considering a cost function, or just trying to find some route? If so, is the cost only a function of "distance" traveled, number of "course changes", or are speed/acceleration taken into account? Is cost a function of "location"? Is the cost isotropic (are the dimensions scaled so that moving 1 unit in each dimension has the same constant cost)? If you move in multiple dimensions at the same time, how do you calculate the cost? (e.g.: sum of distances along each axis, pythagorean distance, or something else)?

If two obstacles in n-space share a "face segment" of n-1 dimensions, can the robot move along that interface? For example, in 2-space, if one obstacle is (0-1, 1-3), and another is (1-2,0-2), can we move along the path (1,1) to (1,2)? (My guess is not, but I wanted to check.)

[faust1706]

Each algorithm is to return a single list of points going from A to B that avoids the obstacles, how the programmer computes that path is up to him/her.

The algorithm will know where the obstacles are beforehand.

I wasn't going to get too crazy with expanding the problem. Perhaps a 7 dimensional search space with a somewhat dense "field" of obstacles.

The maximum movement between steps will be a based off a combination of radians turned and distance traveled. As an example, a robot can move 7 rad + feet, so it can turn 7 radians, go 7 units, or some combination thereof <= 7. The exact number will be scaled with the size of the problem presented.

If two obstacles are touching one cannot move between them.

[GeeTwo]

If space is bounded by a "rectangle", the easiest way to specify this is to have the first "obstacle" be space. Then, as long as the algorithm is insensitive to "inside" vs "outside" intersections, it's not a special case. If the algorithm is sensitive, you can just break it down into 2n separate obstacles and carry on.

Calculating angles in n-space.. I suppose the law of cosines applies, so that the dot product of two vectors divided by the product of their magnitudes is the cosine of the angle between them. That means that the greatest "turn" (an about face) is still pi radians, right?

And I understand that we're optimizing on "number of single turns + single segments that add up to no more than seven".

[faust1706]

Yes, the dot product will be used to measure the validity of a future point.

And yes, but not necessarily 7.

[RyanCahoon]

A sample input for obstacles (n=3):

0-5
1-3
2-7

1.2-4
-.2-0
10-11.4

There can be M obstacles presented in the N dimensional space. Yes, the example objects given were 2 3 dimensional rectangles.

The algorithm will know where the obstacles are beforehand.

Maybe I missed you saying it somewhere, but in order to choose an efficient algorithm, we'll need to know the specific classes of obstacles that will be presented. Are they all going to be axis-aligned boxes? balls? polytopes? do we only get an arbitrary occupancy function? something else?

Thanks,

[faust1706]

For now, they are simply axis aligned n dimensional boxes that can have decimal precision. I don't see much of a reason to add more complex shaped obstacles, but if you give a good one then I may add them.

[Marlow]

I am having a hard time computing the computational complexity of this problem. A path planning algorithm seems to be the "easiest" algorithm to implement to solve this problem, so that is what I did. I solved this problem for the case of 2 dimensions, but it does not scale nicely with larger inputs, meaning it is most likely not the best solution. I still need to adjust is to take inputs how you want, but here (https://github.com/Marlow125/Programming-Challenge) it is.

It isn't optimized to go "7 radian units" per move, and the grid is only contains lattice points. I do not know of a way to obtain "floating point" values without making the grid have millions of points.

[faust1706]

I will rigorously test your solution after work today.

Your approach to the problem certainly is valid, but, as you have pointed out, it has inherent flaws with how you constructed the problem.

I solved the problem by searching the space, instead of iteratively marching one point at a time.

Bonus points if you can prove that your algorithm will find a solution given a solution exists.

[Bernini]

the space

@faust1706 has been careful with his wording in this thread. Space is very ambiguous. @Marlow, instead of viewing this space as a lattice point only Cartesian grid, view it as a topological space.

[Marlow]

I'm only in precalculus...topology isn't even in my projected course load...I'll see what I can understand.

Here is the new algorithm I am working through.

Start at init point
Add init point to list of points
While (!explorable_space.contains(end))
Take a random point "7 radian units" away from my list of points
Add new point to list of points
end while
Search list of points for path from init to end.

[faust1706]

Instead of organizing your points as a "list" (vector? linkedlist? arraylist?), you may want to organize them in terms of a tree (http://interactivepython.org/courselib/static/pythonds/Trees/trees.html). It will make finding the path you have contained in your search easier to find (tree traversal).

[Marlow]

I'm thinking of a few things that will help with code cleanliness and perhaps optimization, such as containing the obstacles in an object that contains the potentially hyper-dimensional rectangles.

Instead of only searching within the "7 radian units" from the all points, would simply exploring the obstacle free space as efficiently and thoroughly as possible work? Then, when you are traversing the tree from from the start the finish, if a child is > "7 radian units" away from its parent, inject children between the original parent and child to meet the robot's needs.

In order for a point to be added to the search tree, the line from parent -> new child must be a partition of the space, tree, and the obstacle space.

This is turning into a really interesting and challenging problem!

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


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 (https://github.com/faust1706/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.