### Author Topic: pathfinding algorithms  (Read 1264 times)

0 Members and 1 Guest are viewing this topic.

#### [email protected] /* <![CDATA[ */!function(){try{var t="currentScript"in document?document.currentScript:function(){for(var t=document.getElementsByTagName("script"),e=t.length;e--;)if(t[e].getAttribute("cf-hash"))return t[e]}();if(t&&t.previousSibling){var e,r,n,i,c=t.previousSibling,a=c.getAttribute("data-cfemail");if(a){for(e="",r=parseInt(a.substr(0,2),16),n=2;a.length-n;n+=2)i=parseInt(a.substr(n,2),16)^r,e+=String.fromCharCode(i);e=document.createTextNode(e),c.parentNode.replaceChild(e,c)}}}catch(u){}}();/* ]]> */

• Jr. Member
• Posts: 40
##### pathfinding algorithms
« on: February 02, 2013, 06:24:44 AM »
hey guys ......... i am not a engineering student.....
i am 13 years old now .....
i started getting into the world of engineering from when i was 10 years old....
i started getting into  analog circuits and then microcontrollers.... etc
now i can possibly program microcontrollers for I/O ......
now i just had a plan to make a quad copter so did a long research n found out that i need to learn whats a PID controller
i learnt whats PID n now trying to implement it on a  line follower ........ n then i would probably start working on d quad copter.......
now as u can see internet was my teacher..... so i dont know advanced maths(as i am not a engineering student)  ....... but pathfinding algorithms seem to have advance maths.......
so can you guys tell me a list of maths topics that i have to learn......
i dont need to implement it on any robot..... but just wanna learn ....
if u point out what  topics  would i have to learn
i would slowly start learning........

#### jwatte

• Supreme Robot
• Posts: 1,343
##### Re: pathfinding algorithms
« Reply #1 on: February 03, 2013, 05:32:27 PM »
First make sure you're really good with multiplication and division *in your head*. It helps a lot when doing steps of the next parts.
Factoring numbers *in your head* is an example of something very helpful.
Then make sure you understand algebra. Parentheses, simplification, extraction of terms.
Move on to algebraic equations -- solve for one variable in linear and quadratic equations. Solve for two variables in a two-equation system.
Then do trigonometry -- sine, cosine, tangent, and the inverse of those functions. Understanding trig is super important, but once you're into linear algebra and do 3D math, it's actually not *used* much, just a good grounding to understand.
A traditional curriculum would then lead you through limits, derivatives, and integrals -- classical calculus of one variable. On the one hand, that's useful for later areas. On the other hand, it's not useful for much *real*.
I'd rather just do linear algebra at that point. Vectors, matrices, quaternions as they pertain to 3D geometry.
Another useful set of math is the intersection with computer science you get in computational geometry. Anything from graph theory, set geometry, to spatial indexing. This requires the linear algebra to become efficient.
If you have calculus you can move on to differential equations, and multi-variable calculus. Diffs are useful for motion systems and other continuously evolving systems -- analog electric circuits, mechanical motion, etc.
Finally, the red-headed step children of applied mathematics: numerical methods, and statistics. Both are actually important, and neither gets much love from the mainstream.
After that, you're approximately OK for a BS in math. From there, you can go into applications (which typically intersect with computer science, and/or perhaps EE or Mech) or specialize into theoretical math.

Good sites:
http://mathworld.wolfram.com/

#### [email protected] /* <![CDATA[ */!function(){try{var t="currentScript"in document?document.currentScript:function(){for(var t=document.getElementsByTagName("script"),e=t.length;e--;)if(t[e].getAttribute("cf-hash"))return t[e]}();if(t&&t.previousSibling){var e,r,n,i,c=t.previousSibling,a=c.getAttribute("data-cfemail");if(a){for(e="",r=parseInt(a.substr(0,2),16),n=2;a.length-n;n+=2)i=parseInt(a.substr(n,2),16)^r,e+=String.fromCharCode(i);e=document.createTextNode(e),c.parentNode.replaceChild(e,c)}}}catch(u){}}();/* ]]> */

• Jr. Member
• Posts: 40
##### Re: pathfinding algorithms
« Reply #2 on: February 20, 2013, 05:45:22 AM »
in pathfinding algorithms .... say wavefront how does the robot plan its path???
for example,
if  it wants to navigate  from my room to kitchen and there is a obstacle in between..... how does it plan it's path to go around the obstacle???

#### newInRobotics

• Supreme Robot
• Posts: 1,015
• N.I.R.
##### Re: pathfinding algorithms
« Reply #3 on: February 20, 2013, 06:25:25 AM »
"Computer games don't affect kids; I mean if Pac-Man affected us as kids, we'd all be running around in darkened rooms, munching magic pills and listening to repetitive electronic music." - Kristian W

#### [email protected] /* <![CDATA[ */!function(){try{var t="currentScript"in document?document.currentScript:function(){for(var t=document.getElementsByTagName("script"),e=t.length;e--;)if(t[e].getAttribute("cf-hash"))return t[e]}();if(t&&t.previousSibling){var e,r,n,i,c=t.previousSibling,a=c.getAttribute("data-cfemail");if(a){for(e="",r=parseInt(a.substr(0,2),16),n=2;a.length-n;n+=2)i=parseInt(a.substr(n,2),16)^r,e+=String.fromCharCode(i);e=document.createTextNode(e),c.parentNode.replaceChild(e,c)}}}catch(u){}}();/* ]]> */

• Jr. Member
• Posts: 40
##### Re: pathfinding algorithms
« Reply #4 on: February 20, 2013, 06:34:42 AM »
hmmmm is A* easier than wavefront??
and how does a robot   plan it's path in any of the pathfinding algorithms?

#### newInRobotics

• Supreme Robot
• Posts: 1,015
• N.I.R.
##### Re: pathfinding algorithms
« Reply #5 on: February 20, 2013, 09:10:32 AM »
hmmmm is A* easier than wavefront??
Easy and difficult are terms that mean different things to different people. As I do not have a clue how Wavefront Algorithm performs and how to implement it, for me it is easier to use A* (as I had to learn and use it before). A* is shortest/fastest path search heuristic and I must say - it works very well.

and how does a robot   plan it's path in any of the pathfinding algorithms?
I bet there are many different path finding algorithms which work differently and give different results. The main idea of path planning is to get from point A to point B. One way to do it is to go from node to node (keeping track of visited nodes) until goal location is found, or until all nodes were explored (Breadth-First-Search and Depth-First-Search). This approach normally takes very long time and is computationally very expensive. To correct that some brilliant minds came up with A* algorithm which favours certain nodes over others based on price to get to certain node, total price so far to reach current state and estimated distance left to the goal node (to calculate it one may use Manhattan Distance, however there is more than one way to do it).

If You're interested, try looking for and implementing A* 8 Puzzle
"Computer games don't affect kids; I mean if Pac-Man affected us as kids, we'd all be running around in darkened rooms, munching magic pills and listening to repetitive electronic music." - Kristian W

#### [email protected] /* <![CDATA[ */!function(){try{var t="currentScript"in document?document.currentScript:function(){for(var t=document.getElementsByTagName("script"),e=t.length;e--;)if(t[e].getAttribute("cf-hash"))return t[e]}();if(t&&t.previousSibling){var e,r,n,i,c=t.previousSibling,a=c.getAttribute("data-cfemail");if(a){for(e="",r=parseInt(a.substr(0,2),16),n=2;a.length-n;n+=2)i=parseInt(a.substr(n,2),16)^r,e+=String.fromCharCode(i);e=document.createTextNode(e),c.parentNode.replaceChild(e,c)}}}catch(u){}}();/* ]]> */

• Jr. Member
• Posts: 40
##### Re: pathfinding algorithms
« Reply #6 on: February 20, 2013, 09:45:33 AM »
thnxxx a lot .....
i would be glad if you can show me some bots (or yours) which has implemented A* algorithm

#### newInRobotics

• Supreme Robot
• Posts: 1,015
• N.I.R.
##### Re: pathfinding algorithms
« Reply #7 on: February 20, 2013, 09:52:13 AM »
I've never had any bots built. A* I have used to solve 8 Puzzle as one of my uni projects. For bot it should work the same way/
"Computer games don't affect kids; I mean if Pac-Man affected us as kids, we'd all be running around in darkened rooms, munching magic pills and listening to repetitive electronic music." - Kristian W

• Jr. Member
• Posts: 40