Go to Post Each poster can bring respect to the topic, whether agreeing with it or not. - JaneYoung [more]
Home
Go Back   Chief Delphi > Technical > Programming
CD-Media   CD-Spy  
portal register members calendar search Today's Posts Mark Forums Read FAQ rules

 
Closed Thread
Thread Tools Rating: Thread Rating: 2 votes, 5.00 average. Display Modes
  #1   Spotlight this post!  
Unread 25-06-2015, 14:51
faust1706's Avatar
faust1706 faust1706 is offline
Registered User
FRC #1706 (Ratchet Rockers)
Team Role: College Student
 
Join Date: Apr 2012
Rookie Year: 2011
Location: St Louis
Posts: 498
faust1706 is infamous around these partsfaust1706 is infamous around these parts
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.
__________________
"You're a gentleman," they used to say to him. "You shouldn't have gone murdering people with a hatchet; that's no occupation for a gentleman."

Last edited by faust1706 : 25-06-2015 at 15:20.
  #2   Spotlight this post!  
Unread 25-06-2015, 15:37
GeeTwo's Avatar
GeeTwo GeeTwo is online now
Technical Director
AKA: Gus Michel II
FRC #3946 (Tiger Robotics)
Team Role: Mentor
 
Join Date: Jan 2014
Rookie Year: 2013
Location: Slidell, LA
Posts: 3,565
GeeTwo has a reputation beyond reputeGeeTwo has a reputation beyond reputeGeeTwo has a reputation beyond reputeGeeTwo has a reputation beyond reputeGeeTwo has a reputation beyond reputeGeeTwo has a reputation beyond reputeGeeTwo has a reputation beyond reputeGeeTwo has a reputation beyond reputeGeeTwo has a reputation beyond reputeGeeTwo has a reputation beyond reputeGeeTwo has a reputation beyond repute
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.
__________________

If you can't find time to do it right, how are you going to find time to do it over?
If you don't pass it on, it never happened.
Robots are great, but inspiration is the reason we're here.
Friends don't let friends use master links.
  #3   Spotlight this post!  
Unread 25-06-2015, 15:58
faust1706's Avatar
faust1706 faust1706 is offline
Registered User
FRC #1706 (Ratchet Rockers)
Team Role: College Student
 
Join Date: Apr 2012
Rookie Year: 2011
Location: St Louis
Posts: 498
faust1706 is infamous around these partsfaust1706 is infamous around these parts
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
__________________
"You're a gentleman," they used to say to him. "You shouldn't have gone murdering people with a hatchet; that's no occupation for a gentleman."

Last edited by faust1706 : 25-06-2015 at 16:19.
  #4   Spotlight this post!  
Unread 25-06-2015, 17:06
GeeTwo's Avatar
GeeTwo GeeTwo is online now
Technical Director
AKA: Gus Michel II
FRC #3946 (Tiger Robotics)
Team Role: Mentor
 
Join Date: Jan 2014
Rookie Year: 2013
Location: Slidell, LA
Posts: 3,565
GeeTwo has a reputation beyond reputeGeeTwo has a reputation beyond reputeGeeTwo has a reputation beyond reputeGeeTwo has a reputation beyond reputeGeeTwo has a reputation beyond reputeGeeTwo has a reputation beyond reputeGeeTwo has a reputation beyond reputeGeeTwo has a reputation beyond reputeGeeTwo has a reputation beyond reputeGeeTwo has a reputation beyond reputeGeeTwo has a reputation beyond repute
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.)
__________________

If you can't find time to do it right, how are you going to find time to do it over?
If you don't pass it on, it never happened.
Robots are great, but inspiration is the reason we're here.
Friends don't let friends use master links.
  #5   Spotlight this post!  
Unread 25-06-2015, 17:23
faust1706's Avatar
faust1706 faust1706 is offline
Registered User
FRC #1706 (Ratchet Rockers)
Team Role: College Student
 
Join Date: Apr 2012
Rookie Year: 2011
Location: St Louis
Posts: 498
faust1706 is infamous around these partsfaust1706 is infamous around these parts
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.
__________________
"You're a gentleman," they used to say to him. "You shouldn't have gone murdering people with a hatchet; that's no occupation for a gentleman."
  #6   Spotlight this post!  
Unread 25-06-2015, 17:39
GeeTwo's Avatar
GeeTwo GeeTwo is online now
Technical Director
AKA: Gus Michel II
FRC #3946 (Tiger Robotics)
Team Role: Mentor
 
Join Date: Jan 2014
Rookie Year: 2013
Location: Slidell, LA
Posts: 3,565
GeeTwo has a reputation beyond reputeGeeTwo has a reputation beyond reputeGeeTwo has a reputation beyond reputeGeeTwo has a reputation beyond reputeGeeTwo has a reputation beyond reputeGeeTwo has a reputation beyond reputeGeeTwo has a reputation beyond reputeGeeTwo has a reputation beyond reputeGeeTwo has a reputation beyond reputeGeeTwo has a reputation beyond reputeGeeTwo has a reputation beyond repute
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".
__________________

If you can't find time to do it right, how are you going to find time to do it over?
If you don't pass it on, it never happened.
Robots are great, but inspiration is the reason we're here.
Friends don't let friends use master links.
  #7   Spotlight this post!  
Unread 25-06-2015, 17:43
faust1706's Avatar
faust1706 faust1706 is offline
Registered User
FRC #1706 (Ratchet Rockers)
Team Role: College Student
 
Join Date: Apr 2012
Rookie Year: 2011
Location: St Louis
Posts: 498
faust1706 is infamous around these partsfaust1706 is infamous around these parts
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.
__________________
"You're a gentleman," they used to say to him. "You shouldn't have gone murdering people with a hatchet; that's no occupation for a gentleman."
  #8   Spotlight this post!  
Unread 25-06-2015, 21:31
RyanCahoon's Avatar
RyanCahoon RyanCahoon is offline
Disassembling my prior presumptions
FRC #0766 (M-A Bears)
 
Join Date: Dec 2007
Rookie Year: 2007
Location: Mountain View
Posts: 689
RyanCahoon has a reputation beyond reputeRyanCahoon has a reputation beyond reputeRyanCahoon has a reputation beyond reputeRyanCahoon has a reputation beyond reputeRyanCahoon has a reputation beyond reputeRyanCahoon has a reputation beyond reputeRyanCahoon has a reputation beyond reputeRyanCahoon has a reputation beyond reputeRyanCahoon has a reputation beyond reputeRyanCahoon has a reputation beyond reputeRyanCahoon has a reputation beyond repute
Re: Inaugural Programming Challenge

Quote:
Originally Posted by faust1706 View Post
A sample input for obstacles (n=3):

0-5
1-3
2-7

1.2-4
-.2-0
10-11.4
Quote:
Originally Posted by faust1706 View Post
There can be M obstacles presented in the N dimensional space. Yes, the example objects given were 2 3 dimensional rectangles.
Quote:
Originally Posted by faust1706 View Post
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,
__________________
FRC 2046, 2007-2008, Student member
FRC 1708, 2009-2012, College mentor; 2013-2014, Mentor
FRC 766, 2015-, Mentor
  #9   Spotlight this post!  
Unread 25-06-2015, 21:37
faust1706's Avatar
faust1706 faust1706 is offline
Registered User
FRC #1706 (Ratchet Rockers)
Team Role: College Student
 
Join Date: Apr 2012
Rookie Year: 2011
Location: St Louis
Posts: 498
faust1706 is infamous around these partsfaust1706 is infamous around these parts
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.
__________________
"You're a gentleman," they used to say to him. "You shouldn't have gone murdering people with a hatchet; that's no occupation for a gentleman."
  #10   Spotlight this post!  
Unread 30-06-2015, 15:22
Marlow Marlow is offline
Junior Member
FRC #0125
 
Join Date: Jun 2015
Location: Boston
Posts: 7
Marlow is on a distinguished road
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.
  #11   Spotlight this post!  
Unread 30-06-2015, 15:34
faust1706's Avatar
faust1706 faust1706 is offline
Registered User
FRC #1706 (Ratchet Rockers)
Team Role: College Student
 
Join Date: Apr 2012
Rookie Year: 2011
Location: St Louis
Posts: 498
faust1706 is infamous around these partsfaust1706 is infamous around these parts
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.
__________________
"You're a gentleman," they used to say to him. "You shouldn't have gone murdering people with a hatchet; that's no occupation for a gentleman."
  #12   Spotlight this post!  
Unread 30-06-2015, 15:52
Bernini Bernini is offline
Junior Member
no team
 
Join Date: Mar 2015
Rookie Year: 2002
Location: St Louis
Posts: 11
Bernini has a little shameless behaviour in the past
Re: Inaugural Programming Challenge

Quote:
Originally Posted by faust1706 View Post
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.
  #13   Spotlight this post!  
Unread 30-06-2015, 16:03
Marlow Marlow is offline
Junior Member
FRC #0125
 
Join Date: Jun 2015
Location: Boston
Posts: 7
Marlow is on a distinguished road
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.
  #14   Spotlight this post!  
Unread 30-06-2015, 16:06
faust1706's Avatar
faust1706 faust1706 is offline
Registered User
FRC #1706 (Ratchet Rockers)
Team Role: College Student
 
Join Date: Apr 2012
Rookie Year: 2011
Location: St Louis
Posts: 498
faust1706 is infamous around these partsfaust1706 is infamous around these parts
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).
__________________
"You're a gentleman," they used to say to him. "You shouldn't have gone murdering people with a hatchet; that's no occupation for a gentleman."
  #15   Spotlight this post!  
Unread 30-06-2015, 16:53
Marlow Marlow is offline
Junior Member
FRC #0125
 
Join Date: Jun 2015
Location: Boston
Posts: 7
Marlow is on a distinguished road
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!
Closed Thread


Thread Tools
Display Modes Rate This Thread
Rate This Thread:

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Forum Jump


All times are GMT -5. The time now is 10:02.

The Chief Delphi Forums are sponsored by Innovation First International, Inc.


Powered by vBulletin® Version 3.6.4
Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.
Copyright © Chief Delphi