Ask Your Question

Avoid to hit corners using A* algorithm

asked 2019-07-13 01:25:17 -0500

Elric gravatar image

updated 2019-07-13 09:28:33 -0500

I'm using ROS melodic with Gazebo 9.9.0 on an Ubuntu 18.04.2 LTS.

I'm implementing an autonomous node that uses A* algorithm to move a robot from one position to another. The robot will be on a Gazebo World.

My problem is when moves on diagonal, sometimes it hits a corner and can not continue moving.

For example, I want to move from cell (1,1) to cell(10,12). I'm using an ones and zeros grid that it is represented in Gazebo and I translate the cells into Gazebo world's locations. Moving from (1,1) to (10,12), I get this path:

The Path is -> (1,1) -> (2,2) -> (3,3) -> (4,4) -> (4,5) -> (5,6) -> (6,6) -> (7,6) -> (8,7) -> (9,7) -> (10,7) -> (11,7) -> (12,8) -> (11,9) -> (11,10) -> (10,11) -> (10,12)

Cell (1,1) is the top most left cell in map. The problem comes when it tries to move from (4,5) to (5,6). In the following picture, the robot is on cell (4,5) facing to cell (5,6), and if it moves, it will hit the corner.

image description

The algorithm is doing this:

image description

Is there any way to solve this problem or this is a problem attached to A* algorithm?

edit retag flag offensive close merge delete


which local planner are you using?

curi_ROS gravatar image curi_ROS  ( 2019-07-15 03:31:45 -0500 )edit

No local planner. I have implemented A*, and using Odometry and cmd_vel topics to move the robot.

Elric gravatar image Elric  ( 2019-07-15 03:32:45 -0500 )edit

1 Answer

Sort by ยป oldest newest most voted

answered 2019-07-15 04:06:28 -0500

The standard way of achieving basic obstacle avoidance in grid-map based planning is inflating the grid map's walls with the size of the robot (+ some margin), i.e. dilate the obstacles in the map.

Another option would be to implement some basic reactive obstacle avoidance that checks sensor data for close-by walls and mixes in steering commands to keep away from walls while still following the global plan.

That being said, there are many open source solutions for this kind of problem available for ROS, so those could be used as well.

edit flag offensive delete link more


Thanks for your answer. Where can I find those projects? Or, what are their names? Thanks a lot!

Elric gravatar image Elric  ( 2019-07-15 04:15:33 -0500 )edit

Where can I find those projects? Or, what are their names?

The standard navigation stack and its local planners.

gvdhoorn gravatar image gvdhoorn  ( 2019-07-15 04:35:21 -0500 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower


Asked: 2019-07-13 01:25:17 -0500

Seen: 131 times

Last updated: Jul 15 '19