navigation, path planning, robot's physical dimensions

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?
Rich aiiadict AT hotmail DOT com http://rich12345.tripod.com
Add pictures here
<% if( /^image/.test(type) ){ %>
<% } %>
<%-name%>
Add image file
Upload
snipped-for-privacy@gmail.com (Rich J.) wrote in message

This seems like a reasonable solution.

This seems more complicated than your first idea.

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.
Add pictures here
<% if( /^image/.test(type) ){ %>
<% } %>
<%-name%>
Add image file
Upload
snipped-for-privacy@slackware.com (Bob) wrote in message

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.
rich aiiadict AT hotmail DOT com
Add pictures here
<% if( /^image/.test(type) ){ %>
<% } %>
<%-name%>
Add image file
Upload
snipped-for-privacy@gmail.com (Rich J.) wrote in message

You don't.
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.
Add pictures here
<% if( /^image/.test(type) ){ %>
<% } %>
<%-name%>
Add image file
Upload
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.
            John Nagle
Bob wrote:

Add pictures here
<% if( /^image/.test(type) ){ %>
<% } %>
<%-name%>
Add image file
Upload
John,
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?
Gary

Add pictures here
<% if( /^image/.test(type) ){ %>
<% } %>
<%-name%>
Add image file
Upload

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 %5 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)%4 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
*next
next y next x
Do you know of a better way to do it?
Rich aiiadict AT hotmail DOT com http://rich12345.tripod.com
Add pictures here
<% if( /^image/.test(type) ){ %>
<% } %>
<%-name%>
Add image file
Upload
missed two adjacent cells in previous post:

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 %5 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)%4 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
*next
next y next x
Do you know of a better way to do it?
Rich aiiadict AT hotmail DOT com http://rich12345.tripod.com
Add pictures here
<% if( /^image/.test(type) ){ %>
<% } %>
<%-name%>
Add image file
Upload
snipped-for-privacy@gmail.com (Rich J.) wrote:

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.
--
|\/| /| |2 |<
mehaase(at)sas(dot)upenn(dot)edu
  Click to see the full signature.
Add pictures here
<% if( /^image/.test(type) ){ %>
<% } %>
<%-name%>
Add image file
Upload
: 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
This is, in fact, the standard way to do it. There are MANY papers on this subject. See http://rossum.sourceforge.net/ or a Google search on robot occupancy grid map IE:
http://www-2.cs.cmu.edu/afs/cs/project/jair/pub/volume11/fox99a-html/node23.html
--
==========================================================
Chris Candreva -- snipped-for-privacy@westnet.com -- (914) 967-7816
  Click to see the full signature.
Add pictures here
<% if( /^image/.test(type) ){ %>
<% } %>
<%-name%>
Add image file
Upload
Mark Haase wrote:

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:
http://www.frc.ri.cmu.edu/~hpm/seegrid.html
-- Gordon Author: Constructing Robot Bases, Robot Builder's Sourcebook, Robot Builder's Bonanza
Add pictures here
<% if( /^image/.test(type) ){ %>
<% } %>
<%-name%>
Add image file
Upload

Polytechforum.com is a website by engineers for engineers. It is not affiliated with any of manufacturers or vendors discussed here. All logos and trade names are the property of their respective owners.