Inaugural Programming Challenge
 

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.

Re: Inaugural Programming Challenge
 

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.

Re: Inaugural Programming Challenge
 

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

Re: Inaugural Programming Challenge
 

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

Re: Inaugural Programming Challenge
 

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.

Re: Inaugural Programming Challenge
 

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".

Re: Inaugural Programming Challenge
 

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

And yes, but not necessarily 7.

Re: Inaugural Programming Challenge
 

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,

Re: Inaugural Programming Challenge
 

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.

Re: Inaugural Programming Challenge
 

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

Re: Inaugural Programming Challenge
 

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.

Re: Inaugural Programming Challenge
 

@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.

Re: Inaugural Programming Challenge
 

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.

Re: Inaugural Programming Challenge
 

Instead of organizing your points as a "list" (vector? linkedlist? arraylist?), you may want to organize them in terms of a tree. It will make finding the path you have contained in your search easier to find (tree traversal).

Re: Inaugural Programming Challenge
 

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!