using a probability grid for map representation. flood fill then backtracking to find quickest path doesn't take into consideration physical dimensions of robot. if you follow the path, the robot will be riding walls the whole way.
is there a simple solution? I was thinking of a pre-process algorithm for the global map matrix, (before flood fill/backtrack) where obstructions would be thickened so that the search and path planning algorithms wouldn't think the robot could get so close to things.
or an algorithm to look at path data (list of n/s/e/w/ne/nw/se/sw directions the robot must get to unexplored area)... when the direction of the path changes, the robot needs to go farther forward to avoid clipping the wall. I should be able to make something to process it this way.
what code or information is available on this subject?
Check out the code for autorouters. Routing a path for a trace on PCB is a very similar problem, because the trace has a non-zero width. Do a Google search for the "Lee-Maze" algorithm.
I've been thinking about this too. If the robot is the only thing that ever "sees" the map, then why bother with preprocessing it at every step? Why not build the map in such a way that areas close to the wall are considered "occupied". Then the robot never even things about getting too close, and also won't consider a path through too narrow an opening.
for a map pre-processin algorithm, how do I "bleed" the obstructions into adjacent cells to thicken them?
cycle through cells if cell = unexplored and adjacent cell = explored then cell = obstructed.
I think this will just fill all unobstructed areas with obstructions.
an alternative is to find the quickest path(riding the walls), then start search at beginning of path, move away from any near obstructions by X ammount of cells, follow path instructions, making sure that (cells landed on according to path instructions) don't have any adjacent obstructions in X cells in any direction. modify the path instructions accordingly
so it would be a two process path planning system.
it might be possible to to do this as you are planning the quickest path the first time. do the same process, in one loop instead of two.
In order to use a grid based flood-fill algorithm, such as "Lee-Maze", you need to start with a list of obstructions, and generate a grid.
But before you generate the grid, update the dimensions of each obstruction to increase the size of each by half the width of the robot. Then make the grid, just like before, but using the "expanded" obstacles. Then the robot should fit through any path that you find.
You expand the obstacles before you generate the grid, not after.
Actually, it's quite feasible to grow obstacles in a grid. Just mark as black every cell within N pixels of a black cell. (Once, not iteratively).
Read "Robot Motion Planning" by Jean-Claude Latoumbe for more than you ever wanted to know about this kind of configuration-space approach. There's an extension to higher dimensions that handles robots that aren't round.
It's not that effective an approach in the real world. In two decades under Latoumbe, Stanford Robotics accomplished very little.
Speaking of navigation and path planning, how is Team Overbot doing? I am kind of routing for you guys... your entry seems to have a higher "common sense" factor than a lot of the others. No 23,000 lbs truck or 3 million dollar war chest required. Do you think you'll be able to field an entry for the next competition?
What Chris said. But it certainly shows you're thinking along the same lines as some of the "movers and shakers" on this topic!
FYI, handy are the lecture notes (and books) by Hans Moravec of Carnegie Mellon. A Google search on that name brings up some pretty nice collection of links. The following is one of the main papers on 3D occupancy grids, something of the latest wrinkle:
ok. the only way I can think of to do this once per cell:
I would have to use a specific flag to mark cells which have been checked. I am using 8 bit byte to represent cells.
my occupancy grid uses 0-127 for unoccupied cells, the farther you get from 128, the more likely it is unoccupied.
128 = unexplored
129-255 = probably occupied, the farther you get from
128, the more likely it is occupied.
the flag could be the number 255 if I reduce any cells by 1 if they are 255 prior to thickening map.
so I will mark checked cells as 255. I will mark cells adjacent to (occupied cell(x,y)) as 255. as I cycle through cells, if a cell is =255 I go to next cell. if a cell is > 128 and < 255, it is a cell which hasn't been considered yet.
first, to reduce all 255's by one, so I have a number (255) to mark checked cells with.
*255to254 for x = 0 to 19 for y = 0 to 19 if GlobalMatrix (x,y) = 255 then GlobalMatrix (x,y)=254 next y next x
now to cycle through cells and make them bleed into adjacent cells, or thicken obstacles. occupied cells which haven't been checked have the surrounding cells (n,s,e,w,ne,nw,se,sw) marked as occupied and checked.
*thickenobstacles for x = 0 to 19 for y = 0 to 19 if GlobalMatrix (x,y) = 255 goto *next ;cell has been searched if GlobalMatrix (x,y) < 128 goto *next ;cell isn't occupied if GlobalMatrix (x,y) > 128 then GlobalMatrix (x+1,y) = 255 ;mark adjacent cells as GlobalMatrix(x+1,y+1) = 255 ;occupied/checked GlobalMatrix(x+1,y-1) = 255 GlobalMatrix (x-1,y) = 255 GlobalMatrix(x-1,y+1) = 255 GlobalMatrix(x-1,y-1) = 255 GlobalMatrix (x,y) = 255 ;mark current cell as occupied ;and checked
ok. the only way I can think of to do this once per cell:
I would have to use a specific flag to mark cells which have been checked. I am using 8 bit byte to represent cells.
my occupancy grid uses 0-127 for unoccupied cells, the farther you get from 128, the more likely it is unoccupied.
128 = unexplored
129-255 = probably occupied, the farther you get from
128, the more likely it is occupied.
the flag could be the number 255 if I reduce any cells by 1 if they are 255 prior to thickening map.
so I will mark checked cells as 255. I will mark cells adjacent to (occupied cell(x,y)) as 255. as I cycle through cells, if a cell is =255 I go to next cell. if a cell is > 128 and < 255, it is a cell which hasn't been considered yet.
first, to reduce all 255's by one, so I have a number (255) to mark checked cells with.
*255to254 for x = 0 to 19 for y = 0 to 19 if GlobalMatrix (x,y) = 255 then GlobalMatrix (x,y)=254 next y next x
now to cycle through cells and make them bleed into adjacent cells, or thicken obstacles. occupied cells which haven't been checked have the surrounding cells (n,s,e,w,ne,nw,se,sw) marked as occupied and checked.
*thickenobstacles for x = 0 to 19 for y = 0 to 19 if GlobalMatrix (x,y) = 255 goto *next ;cell has been searched if GlobalMatrix (x,y) < 128 goto *next ;cell isn't occupied if GlobalMatrix (x,y) > 128 then GlobalMatrix (x+1,y) = 255 ; e mark adjacent cells as GlobalMatrix(x+1,y+1) = 255 ;ne occupied/checked GlobalMatrix(x+1,y-1) = 255 ;se GlobalMatrix (x-1,y) = 255 ; w GlobalMatrix(x-1,y+1) = 255 ;nw GlobalMatrix(x-1,y-1) = 255 ;sw GlobalMatrix (x,y+1) = 255 ; n GlobalMatrix (x,y-1) = 255 ; s GlobalMatrix (x,y) = 255 ;mark current cell as occupied ;and checked
PolyTech Forum website is not affiliated with any of the manufacturers or service providers discussed here.
All logos and trade names are the property of their respective owners.