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?

hi,
that's a AI problem known as Traveling Salesman Problem (TSP), google for that or look into the Wikipedia.
HTH!

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?

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

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