How to program a shortest path choosing robot?

Community General Discussions
1

How to program a robot so that it can choose shortest path between point A and B with obstacles inbetween. I am totally new to this so please please help me. I will enter the coordinates of the obstacles and the robot will have to choose the shortest path from point A to B

Thanks,

Much Appreicated.

2

Its all right here.

http://www.societyofrobots.com/programming_wavefront.shtml

3

6677 is right, your robot

6677 is right, your robot need to know it’s location to calculate the shortest way between A and B. is that accomplished then you need to write some code (see the other tips in the comments) to tell the robot what to do.

4

A searching*

Check out: http://en.wikipedia.org/wiki/A*_search_algorithm

It’s basically the same thing as what CtC posted but a bit more in-depth and technical. Might be a little over the top for your needs but the animations give you a good idea of how a search algorithm operates.

5

thanks alot.just one more

thanks alot.just one more thign any idea what audrino chip i shoud use?

6

thanks alot everybody. much

thanks alot everybody. much appreciated. just one last thing, can you tell me what arduino chip i should use?

 

7

thanks alot guys…you all

thanks alot guys…you all are life savers…lastly, does any1 know any programmer who is willing ot write the code for incse i am not able too :p…i dont want to reach till that point but every1 needs a plan b :stuck_out_tongue:

8

Yeah… My video

I don’t normally plug my own stuff, but yeah, I think you would do well watching my “I want to make a robot…” video (mentioned above). It is sounding more and more like you don’t want to get into this hobby, but instead, just want a toy to play with. Save yourself the time and heartache, just go and buy a robot toy, my man…

9

Here are a few steps to follow:

1. Objective. When you build a robot, you need to set an objective, a goal. In this case, your objective is the robot to move from point A to point B and avoid any obstacles in the way. That can be done in many ways. To make it more clear, you need:

2. Conditions. Your robot can follow a maze from point A to point B. Or a line maze. Or follow a grid map. Or follow GPS coordinates. Or build a map while moving. Or fold time/space continuum to teleport from point A to point B. So you need to find out the contitions of how the robot has to go from start to finish. After you have them, you need to determine:

3. Inputs. A robot will read some inputs and do an action depending on the pre-programmed rules. The inputs are received signals from sensors or communication lines. Depending on the conditions you have, you need one or more sensors. Even to be able to follow a RC signal, you need a sensor to receive that signal. The more sensors you have, the more precise the movement will be. After you decide what sensors are necessary, you need to determine:

4. Outputs. The outputs are generated signals that make sound, light or movement. A robot may move around using wheels or legs. Teleportation, although highly desirable, it is not possible yet. So, you need to decide how the robot will move. Add some blinking LEDs and/or a speaker for fun. Then you’ll do the:

5. Strategy. Depending on the conditions you have, you need to read the sensors and calculate a way to get to your objective. Sometimes you’ll find that you need extra sensors to make things more precise. If you’re in a maze, you need to follow the walls (or the line) and remember the intersections and which way you turned. If a the new direction you turned to went to a dead end, go back to the latest turn and turn a different way, and so on, until you reach the destination. In this case, the obstacles may be the dead ends for example, or you can actually have an obstacle in your way that you need to go arround. If you’re following a grid map, then you need to be able to turn precisely and measure the traveled distance. Then use the wavefront algorithm to determine the shortest path. Each time you find an obstacle in your way, re-calculate the shortest path. Same thing if you’re following GPS coordinates. Create a grid map, then use the wavefront algorithm. If you want to be a smart ass, use vision recognition. Scan the horrizon to find the destination point (if it’s not blocked by an obstacle) then move towards it. If you know the coordinates of start and end points, you need to determine the direction you need to travel to get closer to the destination while scanning to find an open path arround obstacles. This can be developed further. But depending on the complexity of the programming needed, you need to chose the:

6. Brain. You can follow a wall with a mechanical device that has only switches and motors. No brain needed. You can follow a line with a simple circuit that does not need programming. You can use a Basic Stamp or an Arduino for a (simple) grid map. For anything more complicated, you need a Raspberry Pi or a laptop on wheels. At this point, you can start:

7. Programming. Basic, C/C++, Python, Java… All depends on what you chose for your robot’s brain. Good news is that you can write your strategy in any program you feel more confortable. Bad news is that you need to actually do the work. Which will be good for you, don’t be affraind. And if you run into problems, then:

8. Research. Try to find on internet if others had similar problems. If you’re still stuck, then:

9. We can help. Let us know what is the objective, the inputs, the outputs, the strategy, the chosen brain and where you got stuck. All the details are important. We may even ask you for more specifications if needed. And we will guide you, at any step in your quest, but you need to do the hard work.

In the end, YOU will learn a lot.

Good luck!

 

10

Ro-Bot-X FOR THE WIN!!!

Damn dude, you nailed that one.

I am soooo cutting-and-pasting this one in to many future posts I see…

Awesome work on that comment, sir.

11

Holy frog, thats one, if not

Holy frog, thats one, if not the best explanations about that topic i ever read. Easy to understand for beginners. I will print that and keep it in close range to use that for my next project plan. Well done.

12

Thanks! Please do let them

Thanks! Please do let them know. We all hope they will learn something and became better us.

13

Thanks. Please use it as you

Thanks. Please use it as you see fit. Teaching others is verry important and I’m glad I could be of help!

14

Good tutorial.

Here’s an interesting tutorial I came across a while ago.  It’s written with respect to computer game programming, but the theory is the same.  As others have siad though, it does rely on your robot knowing where it is and being able to map its environment.

http://research.ncl.ac.uk/game/mastersdegree/gametechnologies/aipathfinding/AI%20Pathfinding%20Tutorial.pdf

15

Wavefront converted to Arduino

https://www.robotshop.com/letsmakerobots/node/35373

Just incase it comes in handy :slight_smile:

 

16

Hi SkeptiKal, how is the

Hi SkeptiKal, how is the continuation going? Were you able to complete the code? I didn’t had time to play arround with it yet. Hopefully, this winter will be less eventful and I’ll have more time. Thanks again for converting the code for Arduino!