EMERGENCY! please help! Cartography algorithm

cartography robot euclidean shortest path help!!!?

please help me solving this simple example in robot cartography…

i dont know exactly how the algorithm works!!

lets say we placed a robot in a room and the robot took these measurements for 6 spots:

a = [3 5 9 8 2]
b = [4 6 6 9 9]
c = [1 2 2 3 1]
d = [8 9 2 8 2]
e = [6 3 7 8 3]
f = [9 9 9 9 9]
in order to go from a to e, how the algorithm of euclidean distance will work??

lets assume that spot A connects to B and C, and B connects to D and E, and also C connects to D and E.
and finally D connect to F and also E connect to F

can you please tell me step by step what calculations will the robot do to go from A to F???

please help me!!!

I don’t think you have defined the problem enough (at least for me).

What is that matrix of measurements that you posted? Are they locations of points in a 5-dimensional space? Are they relative distances between points? Are they basketball scores?

What kind of answer are you looking for–an algorithm, a sequence of letters, a number, or what? What characteristic would a correct answer have?


Lets assume there is a robot in a room, and for every position in the room (a,b,c,d,e,f) the robot performs a scanning around it with a sonar to see if there is any obstacles. if the value is low, then there is an obstacle (low value means the sound from the sonar got back quickly, high value means that the sound from the sonar traveled longer distance before it went back to robot so there is not obstacle). the robot took 5 measurements for every position (a,b,c,d,e,f) . at the end there is that array i wrote, and then you place the robot at the position a, and you want to go to position f. so the robot must calculate which path to choose. i know that euclidean distance is used to see what point “looks similar” to the target in order to choose the correct path, but i dont know how exatcly it works. if you need more explanation i will respond as quickly as i can, i really need this help!!!

p.s. robot is in 2 dimensional space
p.s.2 an answer will be like “ABEF” like that

p.s. 3 for example the array of position a, a = [3 5 9 8 2] means that in the first measurement which could be e.g. north, the value “3” means there is an obstacle near… the third value “9” could be e.g. “SOUTHEAST” and means there is not obstacle near…

It sounds like you are still missing something here. The sonar measurements do not tell you anything about the distance from A to B. For example, if I did a sonar measurement sitting at my desk, it would look approximately the same as the measurement David gets sitting at his desk, since our desks are approximately the same, even though his desk is all the way down the hall. Perhaps you are supposed to just remember how long the trip was from A to B the first time you did it, or use some other measurement of where A and B are? Do you have encoders on your robot?

However, if you are talking about an abstract Euclidean distance for comparing two arrays for similarity, rather than an actual distance through space, the formula is generally sqrt((x0-x0’)^2+(x1-x1’)^2+(x2-x2’)^2+…). Maybe that is what you are after?


Thank you very much for the reply Paul. Let me explain it more lets hope you can help me i am desperate for help!!

The robot goes for example in the position A, and it makes 5 sonar measurements and sees if there are any obstacles around the position A. So, these 5 measurements are a “fingerprint” for the position A. the same for B,C,D,E,F.

The problem is, knowing these “fingerprints” the robot must go from A to F choosing his path by following the most “similar” fingerprints like target’s (F) fingerpint. (which is f = [9 9 9 9 9])

I know this is solved by using the euclidean distance or something that has to do with euclides! (i know the formula of euclidean distance thnx anyway :slight_smile: )

i hope i made it more clear for you with this explanation!! Lets hope you can help me guys!! I really need this help!!

Thank you in advance!!!

Well, like I said, it does not seem like knowing the “fingerprints” tells you anything about the actual distance from A to B. Do you have an actual robot? It sounds more like you are just asking for help with your homework when you do not even understand the question being asked.


So, you want to find a path from A to F, i.e. a sequence of letters that starts with A and ends with F. You’ve also given some constraints by stating which letters connect to which other letters. Now you need to clarify what characteristic you want the path to have. Basically, you need to better define the sentence below:

My hunch is that the problem defines “distance” between two points to be the 5D Euclidean distance between the “fingerprint” vectors, and you’re supposed to minimize the sum of these “distances” on your path.

Since there are only 6 points, you could probably solve this by hand, but if there were more points you could implement Dijkstra’s algorithm.