Is there any navigational software available for boebot or hexcrawler which can plot a graph of the robots navigation, also·have indication of the object detected in the path, also show the actual position of the robot
There is no released navigation code per se. Though I and others would be glad to help you design one. Are you looking for a maze navigation or freeform navigation system (maze navigation is 100x easier). I wont go into detail until I know what type you are looking for.
Your main obstacle using either method will be lack of data space on a BS.
If all you are looking for is a bread crumb trail that is uploaded to your PC (ie your not using the info to generate bot's next movement, the data space problem goes away)
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔ ·1+1=10
Post Edited (Paul Baker) : 7/22/2005 12:16:40 PM GMT
it would be freeform navigation, with·few·obtacles scattered all around. (area to be covered may be a room or·within a particular boundary)
code for the robot to achieve above navigation is not required.
But, a software(made with VB or any other) loaded on PC which will receive data from the robot(thru RF), that will keep on ploting a graph/line of the robots path and also·indicate the obstatcle detected in the path.
The robot can send data thru RF module to the PC.
Offcource another issue will arise "how or·what data will be send by the robot so that the software in PC design·the trajectory·"
See the other post about vectors, in this situation you would store each vector seperately, you can see how you'll quickly run out of memory. Im not familiar with the HexCrawlers method of locomotion, Ill have to contemplate how to do navigation using a leg based locomotion.
seperable issue, another topic, you may not realize it but between these two posts you asked about 5 different and seperable topics, some are interrelated some not. Professonal programmers sepearate each and every function and decompose functions into subfunctions, because if you try to design an entire system all lumped together, you're not going to be able to debug it.
Ill discuss each in more depth after work.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔ ·1+1=10
Post Edited (Paul Baker) : 7/22/2005 2:25:53 PM GMT
Sorry was too busy to reply last night, today is the regional pool tournament (in less than an hour) I will reply when done (which depends on how well I do). I haven't forgotten.
I think it would be best to concentrate on a core issue before worrying about other issues. For instance, if your robot cant do navigation, theres no need for a PC program to interpret non-existant data. So lets focus on your navigation before worrying the other things, if for no other reason, that I dont have time to sit down and write on each topic for an hour regularly.
Here is a more consise description of vectors, the Hexcrawler will be collecting location information in polar form. Once you understand vectors we can start discussing navigation.
OK good, Ill start writing up an article (will wait until home to write a Word Document, enough people ask about this topic that I want to create a permanent document for future questions on navigation)
Hey sumeet, just a quick note that I haven't forgotten. Its a fairly complex topic and Ive only been able to dedicate an hour towards it for the last couple of days.
Ok here it is, it's an overview. I started to loose steam toward the end, so we can flesh it out further through our discussion.
Navigation in a Crawling Robot.
This is assuming you have a means for determining the direction of your crawler, a digital compass is the simplest route but other solutions exist.
A robot will typically travel in a straight line, change direction, travel straight, etc. This movement can easily be expressed as a 2D vector which is comprised of distance and direction, or the distance traveled in a certain direction. If you keep a record of these vectors you can return to where you started. Here is a simple example:
[img]http://forums.parallax.com/attachment.php?attachmentid=38421[/img]
The crawler travels northeast 5 feet then northwest 7 feet, to return back to where it started it need to travel approximately 9 feet at 280°.
Expressing vectors in distance and direction is called polar form; another way of expressing vectors is called Cartesian, where a vector is express in displacement along the X and Y axis. For instance the vector NE 5 ft is expressed as 3.53, 3.53 or 3.53 feet in the X direction, 3.53 feet in the Y direction. To convert a vector in polar form into Cartesian form we use a couple of trig functions; x = d · sin(α) and y = d · cos(α), where d is the distance and α is the direction. To convert a vector expressed in Cartesian form to polar form we use the equations α = arctan(y/x) and d=SQRT(x[sup]2[/sup]+y[sup]2[/sup]). Adding Cartesian vectors is easier than adding polar vectors, so you’ll want to decompose the polar vector you acquire into its Cartesian form, and then you simply add the Xs and Ys to get the resultant vector (resulting in the blue vector above but pointing away from the origin).
Now you can just collect vectors to keep a history of the bot’s path or keep just an accumulated vector if you want to remember how to get back to your starting position. Because of the limited data space and low processing power, attempting to do anything beyond remembering how to get back to your starting position is nearly impossible. First you only have space for 13 vectors in RAM and that’s if you have no other data to store. Clearly keeping a log of your vectors is inefficient both on data space and processing power (I won’t go into the particulars of why it’s computationally inefficient). To do things such as obstacle recording we need to come up with a better scheme.
It would be much easier to keep track of obstacles if we were able to keep a map of the area, marking locations of obstacles on the map. The simplest means for showing a location has an obstacle is using a single bit, a 0 means the location is free from obstacles, a 1 means there is an obstacle in that location. We will represent the map grid in memory as a series of bytes organized into a 2D grid. Since the stamp handles words, bytes and nibs, we should choose a grid which is either 16, 8 or 4 cells in a direction.
At this point we have discussed all the generalized preliminary information except how to correspond vectors traveled into traversing the obstacle map. For this point on, assumptions will be made for the sake of providing a concrete example of how to implement the navigation, as such you are free to modify things to more closely fit your desired application. Only one assumption would dramatically change the complexity, and I will clearly point that out when discussing it. So any time you see “assuming” know that this was just a design choice I made and you can change it if you desire.
Ok the Stamp has 26 bytes of data space, if your version has scratchpad RAM you are less constrained for data space and therefore could accommodate a larger map. If each bit represents whether a cell has an obstacle or not, a byte is 8 cells. A 16x16 map would take 32 bytes of data space and therefore wouldn’t fit in the data space, so we’ll assume we have an 8x8 space, which will take 8 bytes of storage. A cell clearly cannot represent a step; otherwise we wouldn’t be able to go beyond an 8 step by 8 step area. So a cell needs to be multiple steps (I am defining a step to be an entire cycle of moving all the crawler’s legs). We will assume a cell to be 16 steps, the number of steps per cell should be a power of 2 as I will now explain. By choosing 16 steps per cell we can use a single byte to express position in the X and Y direction. The first 4 bits in the byte are the cell (1[sup]st[/sup] bit is always 0 since there are only 8 cells) and the last four bits are the fraction of a cell. By choosing a power of two steps per cell, the division of cell and the fraction of a cell occurs at a bit boundary and therefore its easy to extract either part (you could use 32 steps per cell and split the boundary at 3 bits and 5 bits to use the entire 8 bits).
Having to compute trig functions in a processor not well suited for floating point number is usually best to be avoided, the errors that creep in will cause havoc to the reliability of the data you accumulate. So to avoid this we will assume that the bot is restricted to the 8 cardinal directions (N, E, W, S, NE, NW, SE, SW), this way we only need one number to figure out translating steps in any direction (This is the critical assumption I spoke of, keeping a “any direction” scheme makes things more complex and less accurate). This number is the X and Y displacement when traveling diagonally; 1/SQRT(2) or 0.7071068. Using this number we know when traveling diagonally from one corner to the other that it will take 22.6 steps. Another restriction placed on the bot to simplify calculations is the bot can only change directions when it is in the center of a cell, otherwise the calculations become much more complex when you are traveling diagonally but not corner to corner, on the fly calculations of how many steps to cross the current cells are required since they would be less than 22.6 steps. The 0.6 steps can be accomplished a couple of ways: the first is to figure out how to generate a .6 step with the crawler; the second is to count out 22 steps then 23 steps alternating to achieve an average of 22.5 steps, this is still off by 0.1 step but since the grid is 8x8 the error is less than a step when traveling the entire grid.
So now we have an 8x8 grid map, and have constrained the movement enough to keep calculations relatively simple. And we have 2 bytes to express the current location within the grid. When traveling diagonally it is easiest to count off 22 steps then add or subtract 16 from the location, this needs to be considered if you are trying to do sub-cell calculations.
When an obstacle is encountered, whatever the current cell is mark the bit for that cell as a 1, back up to the center of the previous cell and proceed. If traveling diagonally you will need to determine if you traveled into the next cell, if you traveled 12 or more steps you’re the next cell.
This is only meant as a generalized outline on how to maintain an obstacle map, other issues will likely arise when putting this concept to practice.
I have a quick question... · Is it possible to track the location of the obstacles in memory without populating the rest of the matrix with "empty" zeros. I am playing with navigation after I have located obstacles using a video capture system with a sweeping line laser. · here is my thought.... · Each obstacle “is labeled” in polar coordinates with a distance and an angle (and maybe a width or arc length???). Each object gets its own byte - or two). ·Rather than populate a rectangular coordinate world with empty space (bad for memory), one would only need to track "obstacles" R and Theta. Movement of the robot in this “space” would of course move the R and Theta of the obstacles. (I’m working on the math for this now) A robot could move forward (or navigate) about these locations.· In theory, it could “calculate” if there is enough “room” between obsticals and steer to the farthest available “R”. then trace back… This of course would not work well for mazes ·
· My Math and thoughts may be way off in this regard … if so, someone stop me before I do serious damage to my free time ...
I can see why you would want to recalculate you path back as you go - rather than save our path.
Certainly you could keep object vectors in memory, but like I said; you'll only have space for 13 objects (Θ and r in 26 bytes), unless you use scratchpad or external memory. Also keeping polar variables are fine unless your origin is moving (like a bot), each time a movement is made, translation of origins is required on all previously aquired data, not too big a deal for Cartesian, but in polar it's not the simplest calculations. Other aspects fall into play such as hidden objects and object merging (object A @ 2 feet transitions into another object @ 4 feet, are these the same object whose connection point is hidden or are these two seperate objects. IOW when are two measurements of adjacent angles considered to be the same object or two seperate objects).
I've spent a good deal of thinking time, on and off, over he last 6-8 years, considering this very "mapping problem" you've been discussing, so I've been watching this thread with a good deal of interest. I'm of the beleif that it CAN be done, and without all that much difficulty, with almsot any micorporcessor, with just a few added thoughts. I'm not here to contribute all that much at the moment, since you seem to be following the same path of logic that drove my thinking as well. I'd just as soon not confuse your present course with mine at the moment. However, here are a couple of thoughts which you might want to consider, which fall directly in line with some of the most recent questions and thinking.
As nice as it would be to be able to keep all the working variables and the "map" in the RAM or EEPROM of the microprocessor (read Stamp in this case), it's pretty obvious that plays into one of the few deficiencies of the Pbasic Stamp platform, or any similar microprocessor as well. Perhaps it would be better to avoid that altogether, by using a high access speed, no wait state, non volatile, high endurance external EEPROM in lieu of internal RAM, since those just mentioned characteistics bring it right in line with why RAM is so dear and desirable! Does such a non volatile, external memory exist? It sure does; take a look at FRAM by Ramtron. here is FRAM defined: http://www.ramtron.com/doc/AboutFRAM/overview.asp
This will give you the method and means for storage of the "map" and/or any other necessary, operational data and parameters off-board, yet highly accessible. The advent of FRAM, just a few years back, changed my thinking about this problem entirely!
So too, since it is high speed, non volatile, and high endurance, "garbage collection" now becomes possible which partly answers the question of null or blank data within the "map". Consider the "map" is nothing more or less than a large array or matrix. Any array/matrix, as well as it's inverse, are just as valid when it comes to mathematics. In a sense, so long as you know which copy you're using (inverted or non-inverted) few if any changes need to be made during the mathematical processing. One BIT is all you need as an indicator as to whether the current "map" is inverted or non inverted! Now the question may be, why have it inverted?
The goal here is to minimize the overall physical size, yet maintain the same logical size, which maximizes the overall speed of access using a minimum amount of physical memory space. A matrix with many "hits" will have a fair amount of data within. One with few "hits" will have very little data within. That matrix which has the fewest "hits" will also have the largest amount of null data. Null data is very easily compressed or compacted using rather simple compression techniques! If/when this ever comes to fruition, just ask me for thoughts on this issue.
There is also no Earthly reason why a co-processor couldn't or shouldn't be responsible for the background maintenance of the "map" (as well as other similar functions), thus relieving the primary, foreground processor of this unnecessary burden. If one chose to do that, it might be wise to also let the co-processor be the "gatekeeper" for "map" accessability. With that in mind, it would probably be real easy to even keep TWO "MAPS" on board the co-processor daughterboard; one inverted and one non-inverted. The co-processor only accesses the "current" map, while it concurrently and asynchronously does "garbage collection" on the "mirror map". Is that sweet?
This co-processor is probably totally independent, has mini-UPS capability, runs at the same or a faster clock speed than the foreground processor, yet it is easily able to maintain synchronicity with the foreground processor.
It is wholly invisible to the foreground processor, since it will be accessed via SHIFTIN/SHIFTOUT or SERIN/SEROUT (at max baud rates) which is effectively the same as how the foreground processor would entertain any other sort of ordinary, external EEPROM with less desirable characteristics than the FRAM.
I'm hoping these thoughts have blossomed the amount of high speed memory available to you, which will hopefully remove one of the greatest creativity contraints I ran across in thinking this whole thing through. So too, I hope it has brought to mind the thought of the possibility of multiple "maps", "mirror maps", and multi-dimensional "maps" (due to the assignment of "map" manipulation to a closely linked co-processor without the constraints of uni-dimensional arrays as Pbasic is unfortunately burdened with.) with little additional overhead to the operational processor.
Thanks Bruce, all of you ideas and comments are welcome and you have very valid points to make. The addition of external RAM (Im a big fan of FRAM myself, I even issued a few patents on the technology) and compression are advanced topics for navigation. A smartly designed system would use a polymorphic map by starting with a single cell (bot's starting point); and as the bot moved, it would add cells to the map as it traveled into these new cells. Using this method, you could start the bot near a wall and it would never create cells that lay beyond the wall, since it cannot travel to those cells. Compression can become a bit tricky since it is well suited for sparse matricies but becomes inefficent as the matrix becomes filled so it is desirable to provide a non-compressed format for areas of the matrix well filled.
But like I said these are advanced topics and it is nessesary to walk before running, theres no sense in worring about interfacing with external memory if you cannot get the core algorithm working properly. It is easiest to pair a problem down to its mininimal incarnation and build up from there. For instance, navigation using only the 8 cardinal directions should be implemented and tested before attempting an "any direction" scheme, the same holds true for enabling the bot to change direction at any point in its movement rather than limiting direction changes to the center of a cell.
I have extensive experience writing code that models sediment flow in non-euclidean·estuarine systems (looks good on resume, since noone seems to completely understand what that means). IOW tracking particles influenced by tidal flows which move through non-rectangular cells in a freeform flow. I spent several years deriving all the equations and proofs, anyways the point is this can be done, even on more complex systems (3D, non-euclidean, unlimited number of particles tracked (equivalent to tracking an army of bots)), though my system was developed on a 4 processor SGI machine, so complex systems = complex solutions and more required processing power.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔ ·1+1=10
Post Edited (Paul Baker) : 8/1/2005 2:57:14 PM GMT
Bruce, BTW Ill add sections to the paper discussing the issues you've mentioned. I have a feeling this can quickly escalate into a small book, with the addition of some code samples it could probably be published.
Nice read, thanks for the link Bruce. I especially like using Bayes' Theorem to calculate cell occupancy, something I didn't use as an undergrad student assistant (programmer) at the Coastal Engineering college, but something I did use extensivley in grad school working on phoneme mapping and data mining projects.
Beuler...Beuler? It has been a week since I posted the article and I haven't heard a word from you. I took the better part of my free time last weekend writing that up for you and all I have heard is crickets chirping in response. Have you given up on the idea? Are you on vacation? Its rather rude to not acknowledge someone's effort when they have spent a considerable amount of time trying to help you. If I were at work, I would have netted over $100 in wages for the amount of time I spent on the article, the least you can do is say a simple thank you. My blacklist has no names on it, and Id rather not start it with yours. If some extraordinary circumstance has arose, thats understandable and forgivable, but laziness and bad manners are not. I was actually looking forward to fleshing out a fairly detailed write up on the subject through our conversation, but that interest has all but evaporated. Let's just say I am quite disappointed with this situation.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔ ·1+1=10
Post Edited (Paul Baker) : 8/7/2005 5:46:02 AM GMT
Paul, ·· I just wanted to let you know that·I greatly appreciate your input on these forums. I·think it·is·great·when someone takes time out of their own life to help others out. I am still learning but have saved this thread for·a project I have in mind in the future.
Thanks Al, I try to take things in stride. When I don't receive a response I typically don't care, because most of my posts are just a couple paragraphs long. Its just when extra effort isn't acknowledged I get irked. If and when you want to pursue a project along these lines, Ill be happy to help you work out the details.
Paul,
I know that you have replied to some of my other posts, in case I overlooked a thanks, well thanks. I looked at your little write up and I will be keeping that info in mind. I am working on my own robot project, and will be getting into the navigation aspect of it in a short time. So, I am thinking that when I am at that point, then I will do a re-post in the sandbox.
Very well, Im sorry I came down so hard on you. Your appology is accepted and all is forgotten. I hope you are feeling better, and that no serious long term issues with your health have occured. When you are feeling back up to snuff and want to continue with this, let me know and we will proceed. I will be leaving on vacation tomorrow and will be gone likely to the middle of next week if Huricane Irene doesn't cut it short.
Comments
Your main obstacle using either method will be lack of data space on a BS.
If all you are looking for is a bread crumb trail that is uploaded to your PC (ie your not using the info to generate bot's next movement, the data space problem goes away)
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
·1+1=10
Post Edited (Paul Baker) : 7/22/2005 12:16:40 PM GMT
it would be freeform navigation, with·few·obtacles scattered all around. (area to be covered may be a room or·within a particular boundary)
code for the robot to achieve above navigation is not required.
But, a software(made with VB or any other) loaded on PC which will receive data from the robot(thru RF), that will keep on ploting a graph/line of the robots path and also·indicate the obstatcle detected in the path.
The robot can send data thru RF module to the PC.
Offcource another issue will arise "how or·what data will be send by the robot so that the software in PC design·the trajectory·"
help.............................
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
·1+1=10
how can i get that or design one
Ill discuss each in more depth after work.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
·1+1=10
Post Edited (Paul Baker) : 7/22/2005 2:25:53 PM GMT
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
·1+1=10
Here is a more consise description of vectors, the Hexcrawler will be collecting location information in polar form. Once you understand vectors we can start discussing navigation.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
·1+1=10
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
·1+1=10
· Can we·begin with the basic. I'll learn more from you as we proceed.
·thanks
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
·1+1=10
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
·1+1=10
Navigation in a Crawling Robot. This is assuming you have a means for determining the direction of your crawler, a digital compass is the simplest route but other solutions exist. A robot will typically travel in a straight line, change direction, travel straight, etc. This movement can easily be expressed as a 2D vector which is comprised of distance and direction, or the distance traveled in a certain direction. If you keep a record of these vectors you can return to where you started. Here is a simple example: [img]http://forums.parallax.com/attachment.php?attachmentid=38421[/img] The crawler travels northeast 5 feet then northwest 7 feet, to return back to where it started it need to travel approximately 9 feet at 280°. Expressing vectors in distance and direction is called polar form; another way of expressing vectors is called Cartesian, where a vector is express in displacement along the X and Y axis. For instance the vector NE 5 ft is expressed as 3.53, 3.53 or 3.53 feet in the X direction, 3.53 feet in the Y direction. To convert a vector in polar form into Cartesian form we use a couple of trig functions; x = d · sin(α) and y = d · cos(α), where d is the distance and α is the direction. To convert a vector expressed in Cartesian form to polar form we use the equations α = arctan(y/x) and d=SQRT(x[sup]2[/sup]+y[sup]2[/sup]). Adding Cartesian vectors is easier than adding polar vectors, so you’ll want to decompose the polar vector you acquire into its Cartesian form, and then you simply add the Xs and Ys to get the resultant vector (resulting in the blue vector above but pointing away from the origin). Now you can just collect vectors to keep a history of the bot’s path or keep just an accumulated vector if you want to remember how to get back to your starting position. Because of the limited data space and low processing power, attempting to do anything beyond remembering how to get back to your starting position is nearly impossible. First you only have space for 13 vectors in RAM and that’s if you have no other data to store. Clearly keeping a log of your vectors is inefficient both on data space and processing power (I won’t go into the particulars of why it’s computationally inefficient). To do things such as obstacle recording we need to come up with a better scheme. It would be much easier to keep track of obstacles if we were able to keep a map of the area, marking locations of obstacles on the map. The simplest means for showing a location has an obstacle is using a single bit, a 0 means the location is free from obstacles, a 1 means there is an obstacle in that location. We will represent the map grid in memory as a series of bytes organized into a 2D grid. Since the stamp handles words, bytes and nibs, we should choose a grid which is either 16, 8 or 4 cells in a direction. At this point we have discussed all the generalized preliminary information except how to correspond vectors traveled into traversing the obstacle map. For this point on, assumptions will be made for the sake of providing a concrete example of how to implement the navigation, as such you are free to modify things to more closely fit your desired application. Only one assumption would dramatically change the complexity, and I will clearly point that out when discussing it. So any time you see “assuming” know that this was just a design choice I made and you can change it if you desire. Ok the Stamp has 26 bytes of data space, if your version has scratchpad RAM you are less constrained for data space and therefore could accommodate a larger map. If each bit represents whether a cell has an obstacle or not, a byte is 8 cells. A 16x16 map would take 32 bytes of data space and therefore wouldn’t fit in the data space, so we’ll assume we have an 8x8 space, which will take 8 bytes of storage. A cell clearly cannot represent a step; otherwise we wouldn’t be able to go beyond an 8 step by 8 step area. So a cell needs to be multiple steps (I am defining a step to be an entire cycle of moving all the crawler’s legs). We will assume a cell to be 16 steps, the number of steps per cell should be a power of 2 as I will now explain. By choosing 16 steps per cell we can use a single byte to express position in the X and Y direction. The first 4 bits in the byte are the cell (1[sup]st[/sup] bit is always 0 since there are only 8 cells) and the last four bits are the fraction of a cell. By choosing a power of two steps per cell, the division of cell and the fraction of a cell occurs at a bit boundary and therefore its easy to extract either part (you could use 32 steps per cell and split the boundary at 3 bits and 5 bits to use the entire 8 bits). Having to compute trig functions in a processor not well suited for floating point number is usually best to be avoided, the errors that creep in will cause havoc to the reliability of the data you accumulate. So to avoid this we will assume that the bot is restricted to the 8 cardinal directions (N, E, W, S, NE, NW, SE, SW), this way we only need one number to figure out translating steps in any direction (This is the critical assumption I spoke of, keeping a “any direction” scheme makes things more complex and less accurate). This number is the X and Y displacement when traveling diagonally; 1/SQRT(2) or 0.7071068. Using this number we know when traveling diagonally from one corner to the other that it will take 22.6 steps. Another restriction placed on the bot to simplify calculations is the bot can only change directions when it is in the center of a cell, otherwise the calculations become much more complex when you are traveling diagonally but not corner to corner, on the fly calculations of how many steps to cross the current cells are required since they would be less than 22.6 steps. The 0.6 steps can be accomplished a couple of ways: the first is to figure out how to generate a .6 step with the crawler; the second is to count out 22 steps then 23 steps alternating to achieve an average of 22.5 steps, this is still off by 0.1 step but since the grid is 8x8 the error is less than a step when traveling the entire grid. So now we have an 8x8 grid map, and have constrained the movement enough to keep calculations relatively simple. And we have 2 bytes to express the current location within the grid. When traveling diagonally it is easiest to count off 22 steps then add or subtract 16 from the location, this needs to be considered if you are trying to do sub-cell calculations. When an obstacle is encountered, whatever the current cell is mark the bit for that cell as a 1, back up to the center of the previous cell and proceed. If traveling diagonally you will need to determine if you traveled into the next cell, if you traveled 12 or more steps you’re the next cell. This is only meant as a generalized outline on how to maintain an obstacle map, other issues will likely arise when putting this concept to practice.▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
·1+1=10
·
Is it possible to track the location of the obstacles in memory without populating the rest of the matrix with "empty" zeros. I am playing with navigation after I have located obstacles using a video capture system with a sweeping line laser.
·
here is my thought....
·
Each obstacle “is labeled” in polar coordinates with a distance and an angle (and maybe a width or arc length???). Each object gets its own byte - or two). ·Rather than populate a rectangular coordinate world with empty space (bad for memory), one would only need to track "obstacles" R and Theta. Movement of the robot in this “space” would of course move the R and Theta of the obstacles. (I’m working on the math for this now) A robot could move forward (or navigate) about these locations.· In theory, it could “calculate” if there is enough “room” between obsticals and steer to the farthest available “R”. then trace back… This of course would not work well for mazes
·
·
My Math and thoughts may be way off in this regard … if so, someone stop me before I do serious damage to my free time ...
I can see why you would want to recalculate you path back as you go - rather than save our path.
see
http://www-users.cs.umn.edu/~gini/papers/dars04_morlok.pdf
and
http://sky.fit.qut.edu.au/~taylort2/Confirmation_Revised2.pdf
(I don’t want to interrupt your lesson - maybe I should start a new thread??? … )
·
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
·1+1=10
I've spent a good deal of thinking time, on and off, over he last 6-8 years, considering this very "mapping problem" you've been discussing, so I've been watching this thread with a good deal of interest. I'm of the beleif that it CAN be done, and without all that much difficulty, with almsot any micorporcessor, with just a few added thoughts. I'm not here to contribute all that much at the moment, since you seem to be following the same path of logic that drove my thinking as well. I'd just as soon not confuse your present course with mine at the moment. However, here are a couple of thoughts which you might want to consider, which fall directly in line with some of the most recent questions and thinking.
As nice as it would be to be able to keep all the working variables and the "map" in the RAM or EEPROM of the microprocessor (read Stamp in this case), it's pretty obvious that plays into one of the few deficiencies of the Pbasic Stamp platform, or any similar microprocessor as well. Perhaps it would be better to avoid that altogether, by using a high access speed, no wait state, non volatile, high endurance external EEPROM in lieu of internal RAM, since those just mentioned characteistics bring it right in line with why RAM is so dear and desirable! Does such a non volatile, external memory exist? It sure does; take a look at FRAM by Ramtron. here is FRAM defined:
http://www.ramtron.com/doc/AboutFRAM/overview.asp
This will give you the method and means for storage of the "map" and/or any other necessary, operational data and parameters off-board, yet highly accessible. The advent of FRAM, just a few years back, changed my thinking about this problem entirely!
So too, since it is high speed, non volatile, and high endurance, "garbage collection" now becomes possible which partly answers the question of null or blank data within the "map". Consider the "map" is nothing more or less than a large array or matrix. Any array/matrix, as well as it's inverse, are just as valid when it comes to mathematics. In a sense, so long as you know which copy you're using (inverted or non-inverted) few if any changes need to be made during the mathematical processing. One BIT is all you need as an indicator as to whether the current "map" is inverted or non inverted! Now the question may be, why have it inverted?
The goal here is to minimize the overall physical size, yet maintain the same logical size, which maximizes the overall speed of access using a minimum amount of physical memory space. A matrix with many "hits" will have a fair amount of data within. One with few "hits" will have very little data within. That matrix which has the fewest "hits" will also have the largest amount of null data. Null data is very easily compressed or compacted using rather simple compression techniques! If/when this ever comes to fruition, just ask me for thoughts on this issue.
There is also no Earthly reason why a co-processor couldn't or shouldn't be responsible for the background maintenance of the "map" (as well as other similar functions), thus relieving the primary, foreground processor of this unnecessary burden. If one chose to do that, it might be wise to also let the co-processor be the "gatekeeper" for "map" accessability. With that in mind, it would probably be real easy to even keep TWO "MAPS" on board the co-processor daughterboard; one inverted and one non-inverted. The co-processor only accesses the "current" map, while it concurrently and asynchronously does "garbage collection" on the "mirror map". Is that sweet?
This co-processor is probably totally independent, has mini-UPS capability, runs at the same or a faster clock speed than the foreground processor, yet it is easily able to maintain synchronicity with the foreground processor.
It is wholly invisible to the foreground processor, since it will be accessed via SHIFTIN/SHIFTOUT or SERIN/SEROUT (at max baud rates) which is effectively the same as how the foreground processor would entertain any other sort of ordinary, external EEPROM with less desirable characteristics than the FRAM.
I'm hoping these thoughts have blossomed the amount of high speed memory available to you, which will hopefully remove one of the greatest creativity contraints I ran across in thinking this whole thing through. So too, I hope it has brought to mind the thought of the possibility of multiple "maps", "mirror maps", and multi-dimensional "maps" (due to the assignment of "map" manipulation to a closely linked co-processor without the constraints of uni-dimensional arrays as Pbasic is unfortunately burdened with.) with little additional overhead to the operational processor.
Regards,
Bruce Bates
But like I said these are advanced topics and it is nessesary to walk before running, theres no sense in worring about interfacing with external memory if you cannot get the core algorithm working properly. It is easiest to pair a problem down to its mininimal incarnation and build up from there. For instance, navigation using only the 8 cardinal directions should be implemented and tested before attempting an "any direction" scheme, the same holds true for enabling the bot to change direction at any point in its movement rather than limiting direction changes to the center of a cell.
I have extensive experience writing code that models sediment flow in non-euclidean·estuarine systems (looks good on resume, since noone seems to completely understand what that means). IOW tracking particles influenced by tidal flows which move through non-rectangular cells in a freeform flow. I spent several years deriving all the equations and proofs, anyways the point is this can be done, even on more complex systems (3D, non-euclidean, unlimited number of particles tracked (equivalent to tracking an army of bots)), though my system was developed on a 4 processor SGI machine, so complex systems = complex solutions and more required processing power.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
·1+1=10
Post Edited (Paul Baker) : 8/1/2005 2:57:14 PM GMT
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
·1+1=10
I found this to be a very interesting read, and perhaps you will too:
······ <!--StartFragment -->http://www-cgi.cs.cmu.edu/~cyberscout/new-www/localization.html
Just don't get too bogged down in the math!
Regards,
Bruce Bates
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
·1+1=10
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
·1+1=10
Post Edited (Paul Baker) : 8/7/2005 5:46:02 AM GMT
·· I just wanted to let you know that·I greatly appreciate your input on these forums. I·think it·is·great·when someone takes time out of their own life to help others out. I am still learning but have saved this thread for·a project I have in mind in the future.
Al
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
·1+1=10
I know that you have replied to some of my other posts, in case I overlooked a thanks, well thanks. I looked at your little write up and I will be keeping that info in mind. I am working on my own robot project, and will be getting into the navigation aspect of it in a short time. So, I am thinking that when I am at that point, then I will do a re-post in the sandbox.
Thanks
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
·1+1=10
i am very very sorry, i could not reply.
Actually i gotta severe fever these days and still not that well.
I thank you for all your efforts·and time you had put to help me and
all those who visit this thread.
I'am really very sorry but it was not in my hand.
take care
sumeet
·
Have a quick and full recovery,
Paul
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
·1+1=10