optimize sensor sweep

wrote in message news: snipped-for-privacy@g14g2000cwa.googlegroups.com...

I have a few questions right away. First, when your robot is exploring a cell, is the cell logically divided into two partitions; namely north and south? And if so, are all subsequent cells also divided into partitions? This is an important piece of information. Next, how does the robot know what the cell boundary is? Is it the arbitrary result of the scan, limited to its range? Or is the scan clipped at some predetermined distance, or the first encountered obstable? I get the feeling that by "floodfill" (which I know as an old and venereable graphics algorithm, among other things) that you are "painting in" an area up to the boundaries, and that this might constitute a cell, but I am not really sure of this. It is a doable job to assign arbitrary cells of roughly the same geometry and piece them together in an internal map. The question of accuracy is important, but in limited scope applications not really hard to cope with. In an unknown territory, your sweep algorithm will be dictated by the goals- are you actively seeking walls and obstacles? In this case, you may want to proceed in a straight line until you encounter a boundary, and then follow the left-hand rule, or something of that sort. Look into maze navigation and you will see what I am referring to. Conversely. if you are looking for open territory or open paths, then sweep for areas with no obstacles and once again, use a following rule such as the left-hand rule. But understand that the drunkard's walk is also very effective when you are looking for traversable paths and not just the limits of the territory. In the end, you are more than likely going to apply some simple Monte Carlo rule and save the results as you go. Be aware that it is often prudent to go back and navigate the known paths that you have already covered, just to verify and refine what picture you have already created in the navigation routines "mind". Sweep the most complex intersections and they will yield the greatest density of information per cell, by definition.

Cheers!

Sir Charles W. Shults III, K. B. B. Xenotech Research

Thanks for the reply,

partitions?

a cell is a BYTE in RAM representing 6" BY 6" in an occupancy grid.

The flood fill algorithm searches N,S,E,W,NE,NW,SE,SW when it is filling.

Scan is clipped at predetermined distance, but this shouldn't have any bearing on the solution to my problem.

FloodFill, looking for Unexplored. Find Unexplored cell- keep track of X,Y, continue flood fill do this 50 times

now "compile data".... Figure out which cells are part of the largest group of unexplored cells. This will add most data to global map. (I can do this, but it would be nice to look at other code)

Determine WHERE to scan this group of unexplored cells FROM, so a single scan will determine the state of the most unexplored cells. (This one I think I'll need help on)

Rich

"Scan is clipped at predetermined distance, but this shouldn't have any bearing on the solution to my problem. "

The clipping of the scan will affect the "where to scan" algorithm because you have to get within X ammount of distance from a cell to be able to sense it with sonar.

Rich

Okay, your description helps a lot. So in essence, you scan a cell from outside the cell- that was one clue that was important but not immediately obvious. When your bot is in a cell, such as Cartesian (10,10), it looks north and south to determine what the neighboring cells might have within them, and assigns the results to corresponding array cells in memory. So the north scan sweeps through (9,9), (10,9), (11,9) and the south scan sweeps through (11,11), (10,11), and (9,11) and then you have those cells filled in as to whether there is an obstacle or not. Of course, my address assignments and order of scan may not be correct, but the principle remains the same. And it appears that since you are scanning 180° at a time, you also read the far right and far left cells twice- so that the north scan catches half of (9,10) and then half of (11,10), but so does the south scan (although in the opposite order). Once again, the order is not important but the concept is. Now, in some manner, your bot decides to pick a path and advance to the next cell. Once there, it orients itself and performs the scan operation once more and saves the resulting data in its map. Is the stored value a binary "hit strength" such as signal strength for a scanned cell, or is it a time delay representing distance to the obstacle? It seems that hit strength would be a better parameter, because as you said earlier, you clip the distance in your scans. Then clearly the diagonal cells will show a shorter scan for its cells (by a factor of 1/2 square root of two) unless you compensate for this in software by altering your clip distance based on the scan angle. In other words, when scanning NE, you would only scan roughly 71% of the cell distance because you are approaching it from the corner, while the N or W cell (for example) would be 100%- or at least enough to give you good confidence data. Now, you wrote:

To me, that seems to indicate that you know about this and have compensated perhaps. All well and good. In essence you are making a "maze builder" in memory. But, there are mazes and there are mazes. I am going to assume for sake of argument that we can represent an occupied cell by a large pole in the center of the cell rather than a solid block. I don't know if you are creating a "wall outline" for each face of a given cell (which is simple and logical, and would only take four bits to represent) or if you are simple saying "sorry, whole cell is impassable." This might sound like nit-picking, but for a dumb bot, we have to assume nothing and make absolutely certain that we understand how the obstacles are represented and whether a bot assumes it can occupy a cell when the south edge says "wall". I will give you credit for understanding that and consider that you are doing this. So you scan and set bits in each byte meaning that there are walls at certain points, and then immediately I see that walls that are dividing two cells will appear in both cells as set bits. Nothing wrong with that- it actually means that you can sort of look ahead on the data for adjacent cells. And, when your bot occupies some arbitrary cell, it will have four bits to interrogate and see (without resorting to a scan) where it is legal or possible to proceed. This now raises a question- how are you maintaining your north? Do you have something such as the Dinsmore compass or are you simply counting wheel rotations? Orientation is going to be paramount to success. One solution, if you have not thought of this, is to use the signal strength to determine when you are perpendicular to a wall. Also, if you do a slow scan of an area and pulse many times, you can get a radial profile that will yield a sort of "Aha! Shortest return time means I am perpendicular now!" This can be invaluable to calibrating your compass- whether it is a real compass or simply a conceptual software model. But now we also have gained another insight- by comparing radial sonar returns we can find dead center of a cell, another fine aid to calibration. I realize that this is "nuts and bolts" programming and has little to do with the actual maze learning and running, but your overall performance is only as good as the details you invest in the software. At this point I am going to break and wait to see if I am off base or actually being helpful.

Cheers!

Sir Charles W. Shults III, K. B. B. Xenotech Research