View unanswered posts | View active topics It is currently Tue Jul 26, 2016 12:15 pm

 Page 1 of 1 [ 5 posts ]
 Print view Previous topic | Next topic
Multiple Destinations
Author Message
Rookie

Joined: Sun May 10, 2009 3:10 am
Posts: 2
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
Guru

Joined: Sat Mar 01, 2008 12:52 pm
Posts: 1030
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)

Sun May 10, 2009 4:36 am
Rookie

Joined: Sun May 10, 2009 3:10 am
Posts: 2
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
Guru

Joined: Sat Mar 01, 2008 12:52 pm
Posts: 1030
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)

Thu May 21, 2009 9:00 am
Rookie

Joined: Thu Dec 10, 2009 2:07 pm
Posts: 1
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
Display posts from previous:  Sort by
 Page 1 of 1 [ 5 posts ]

#### Who is online

Users browsing this forum: No registered users and 1 guest

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

Search for:
 Jump to:  Select a forum ------------------ ROBOTC Applications    ROBOTC for LEGO MINDSTORMS       Third-party sensors    ROBOTC for CORTEX & PIC    ROBOTC for VEX IQ    ROBOTC for Arduino    Robot Virtual Worlds    Multi-Robot Communications    Issues and Bugs Competitions & Partners    Mini Urban Challenge    CS2N Robot Virtual Worlds Competitions       VEX Skyrise Competition 2014-2015       VEX Toss Up 2013-2014       FTC Block Party! 2013-2014    Competitions using VEX - BEST, TSA, VEX, and RoboFest!    FTC Programming    RoboCup Junior and Other ROBOT Competitions Virtual Brick Robotics Discussions    General Discussions    Project Discussions Off-Topic ROBOTC Forum & ROBOTC.net Suggestions/Feedback    ROBOTC Forums Suggestions/Comments    ROBOTC.net Suggestions/Comments       NXT Programming: Tips for Beginning with ROBOTC       VEX Programming: Tips for Beginning with ROBOTC    2013 Robotics Summer Of Learning       VEX Toss Up Programming Challenge       FTC Ring It Up! Programming Challenge    International Forums       Spanish Forums          ROBOTC for MINDSTORMS          ROBOTC for VEX       French Forums          ROBOTC pour Mindstorms          ROBOTC pour IFI VEX       Japanese Forums （日本語のフォーラム）       German Forums    2015 Spring Carnival Event    PLTW (Project Lead The Way)    Robotics Merit Badge    2014 Robotics Academy Summer of Learning