View unanswered posts | View active topics It is currently Wed Nov 26, 2014 11:12 am






Reply to topic  [ 5 posts ] 
Multiple Destinations 
Author Message
Rookie

Joined: Sun May 10, 2009 3:10 am
Posts: 2
Post Multiple Destinations
Hi all!
I'm working on my first robot for a project and it involves solving a maze with multiple destination points.

The first time the robot "explores" the maze and finds all the destinations and then returns to the starting position. The robot remembers the path that takes it to all the destination cells and the second time it executes an informed run of the maze going to only the destination cells of the maze.

I've managed to get the logic of that part together but now I need to enhance the project further and find the shortest path from the starting position to the destination cells.

I've searched for shortest path algorithms involving multiple destination points but haven't found any.

Any ideas how this can be achieved?


Sun May 10, 2009 3:25 am
Profile
Guru
User avatar

Joined: Sat Mar 01, 2008 12:52 pm
Posts: 1030
Post Re: Multiple Destinations
hi,
that's a AI problem known as Traveling Salesman Problem (TSP), google for that or look into the Wikipedia.
HTH!

_________________
regards,
HaWe aka Ford
#define S sqrt(t+2*i*i)<2
#define F(a,b) for(a=0;a<b;++a)
float x,y,r,i,s,j,t,n;task main(){F(y,64){F(x,99){r=i=t=0;s=x/33-2;j=y/32-1;F(n,50&S){t=r*r-i*i;i=2*r*i+j;r=t+s;}if(S){PutPixel(x,y);}}}while(1)}


Sun May 10, 2009 4:36 am
Profile
Rookie

Joined: Sun May 10, 2009 3:10 am
Posts: 2
Post Re: Multiple Destinations
Hi!
Thank you for the help,
But doesn't the Traveling Salesman problem require some sort of weights? Or heuristics of some sort?
I don't have any of those. At least i don't think i do.
Alternative?


Thu May 21, 2009 5:59 am
Profile
Guru
User avatar

Joined: Sat Mar 01, 2008 12:52 pm
Posts: 1030
Post Re: Multiple Destinations
hi,
not necessarily, and notice that there are several quite different algorithms or approachs for this TSM (e.g.,:
Trial and Error,
Nearest Neighbour Heuristic (NNH),
Best Search Heuristic,
astar,
Self Organizing Maps (SOM),
Hopfield nets/ Auto Associative Nets (AAN),
Boltzmann Machine ...)

when you'll use a heuristic approach, it's with the weights like with the basic astar: you may use weights, but if all path nodes have the same weight you may neglect them (sry for my poor English).

_________________
regards,
HaWe aka Ford
#define S sqrt(t+2*i*i)<2
#define F(a,b) for(a=0;a<b;++a)
float x,y,r,i,s,j,t,n;task main(){F(y,64){F(x,99){r=i=t=0;s=x/33-2;j=y/32-1;F(n,50&S){t=r*r-i*i;i=2*r*i+j;r=t+s;}if(S){PutPixel(x,y);}}}while(1)}


Thu May 21, 2009 9:00 am
Profile
Rookie

Joined: Thu Dec 10, 2009 2:07 pm
Posts: 1
Post Re: Multiple Destinations
hello, we are making that project with two sonar sensors(front and left)
but we cant making the algorithm and the code.
if you send the code to us we can pay its worth to you.
yours sincerely


Thu Dec 10, 2009 2:11 pm
Profile
Display posts from previous:  Sort by  
Reply to topic   [ 5 posts ] 

Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  



Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group.
Designed by ST Software for PTF.