A* pathfinder obstacle collision problem

Question

I am working on a project with a robot that has to find its way to an object and avoid some obstacles when going to that object it has to pick up.

The problem lies in that the robot and the object the robot needs to pick up are both one pixel wide in the pathfinder. In reality they are a lot bigger. Often the A* pathfinder chooses to place the route along the edges of the obstacles, sometimes making it collide with them, which we do not wish to have to do.

I have tried to add some more non-walkable fields to the obstacles, but it does not always work out very well. It still collides with the obstacles, also adding too many points where it is not allowed to walk, results in that there is no path it can run on.

Do you have any suggestions on what to do about this problem?

Edit:

So I did as Justin L suggested by adding a lot of cost around the obstacles which results in the folling:

Here you can see the cost around the obstacles, initially the middle two obstacles should look just like the ones in the corners, but after running our pathfinder it seems like the costs are overridden:

Picture above shows what things are found on the picture.

This is the path found which as our problem also was before is hugging the obstacle.

And another picture with the cost map with the path on.

So what I find strange is why the A* pathfinder is overriding these field costs, which are VERY high.

Would it be when it evaluates the nodes inside the open list with the current field to see whether the current fields path is shorter than the one inside the open list?

And here is the code I am using for the pathfinder:

Pathfinder.cs: http://pastebin.org/343774

Field.cs and Grid.cs: http://pastebin.org/343775

Answer 1

I've done one such physical robot. My solution was to move one step backward whenever there is a left and right turn to do.

The red line is as I understand your problem. The Black line is what I did to resolve the issue. The robot can move straight backward for a step then turn right.

Answer 2

Have you considered adding a gradient cost to pixels near objects?

Perhaps one as simple as a linear gradient:

C = -mx + b

Where x is the distance to the nearest object, b is the cost right outside the boundary, and m is the rate at which the cost dies off. Of course, if C is negative, it should be set to 0.

Perhaps a simple hyperbolic decay

C = b/x

where b is the desired cost right outside the boundary, again. Have a cut-off to 0 once it reaches a certain low point.

Alternatively, you could use exponential decay

C = k e^(-hx)

Where k is a scaling constant, and h is the rate of decay. Again, having a cut-off is smart.

---

Second suggestion

I've never applied A* to a pixel-mapped map; nearly always, tiles.

You could try massively decreasing the "resolution" of your tiles? Maybe one tile per ten-by-ten or twenty-by-twenty set of pixels; the tile's cost being the highest cost of a pixel in the tile.

Also, you could try de-valuing the shortest-distance heuristic you are using for A*.

Answer 3

You might try to enlarge the obstacles taking size of the robot into account. You could round the corners of the obstacles to address the blocking problem. Then the gaps that are filled are too small for the robot to squeeze through anyway.