Implementation of wall and obstacle avoidance

Question

I have a task of developing a simulation of an adaptive robot control system but I don't seem too have anyone to discuss my uncertainties with. I want to keep the simulation as simple as possible as I have a very tight deadline and it's only a one off project that most probably will never be used in my life again.

The minimal behaviour that the agent is supposed to exhibit is wall and obstacle avoidance. It can be extended to avoiding small objects and exploring large ones.

I've decided to go with a simple feedback control system. To begin with I'm struggling to decide how to represent the map of agent's environment. What I mean is, what if I want a wall to be from coordinate [0,0] to [0.5]. I could hard code it, e.g. have a matrix with coordinates of all obstacles but how small units do I make... I.e. what if I have two neighbouring coordinates [0,0.01] and [0,0.02] but the agents gets a 'clear to go' to coordinate [0,0.05]. In this case it doesn't know that it actually is about to walk into a wall. I've heard of something called occupancy grid map but I don't exactly get how it works and how to implement it.

Another thing that I am struggling with is how do I distinct between a wall and an obstacle? And then, how do I let the agent know how big that obstacle is so that it can either avoid it or explore it.

Eh, I'm really puzzled with this project. I would really appreciate any thoughts or directions. Thank you. :-)

Answer 1

There's a lot of questions here, so I expect pushback from the peanut gallery, but I'll answer what I can.

First off, a wall is an obstacle, right? There's no difference there other than what words you use to describe "a place a robot cannot go".

So now, we just need a way to store the locations of obstacles so that we know where the robot can go. This is your map. One way of storing this map, as you mentioned, is an occupancy grid.

An occupancy grid (for two dimensional environments, like a floor) is simply an N by M matrix of numbers. In each "cell" we store the probability that an object is present. Cells that contain a zero are known to be clear (unlikely objects). Cells with a 1 are obstacles.

Here, N and M are the dimensions of the area. If your workspace is 10 meters by 10 meters, and your robot is small, then a reasonable choice of N and M is 10x10. This gives you a resolution of one square meter per cell. For higher resolution, 100x100 would give you a tenth of a meter resolution. Good enough for navigating an iRobot Create, in my experience.

How you fill these cells is up to you. If you know that a wall goes from [0,0] to [5,5], for example, you can fill each cell between those two points with ones.

Sidebar

So why wouldn't we use this representation? Well one reason is the space the map takes up. If you are navigating in a hallway, you really only need to know that it is bounded by two lines. So storing the length and position of these lines is enough. That's a small number of variables to represent any length or size of hallway. With an occupancy grid, we'd have to store all of the cells to understand the configuration of the hallway.

However, occupancy grids are probably the most modular, extensible, flexible, etc mapping techniques.

How to "fill" the cells

Great question. You'd want to fill all cells that the line touches. To see if a line goes through a certain cell, you can check if the line (ray) collides with the cell (box). Since the box is aligned with the X and Y axes, this is known as the Axis-Aligned Bounding Box intersection problem. see this question. This may not be the best way to "fill" the cells, as you may have to iterate over the whole map. here is a way to find all cells intersected by a line.