1
$\begingroup$

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:

enter image description here

This is the route given by the algorithm where you can see the diagonal step:

enter image description here

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

$\endgroup$
  • $\begingroup$ What is the problem to add collision check? If you have a diagonal step and an obstacle nearby then check whether obstacle box intersects your robot's box $\endgroup$ – Long Smith Jul 14 at 8:42
1
$\begingroup$

The simplest solution is not to allow your A* program to make diagonal steps.

$\endgroup$
  • $\begingroup$ Thanks. But, is it an attached feature to A* algorithm? Maybe I can't use it in robotics as is, and I have to do not allow diagonal steps. $\endgroup$ – VansFannel Jul 13 at 13:53
  • $\begingroup$ A* is a graph traversal algorithm. There is nothing intrinsic about square grids in A*. Every grid cell in your algorithm is actually a node that you have connected to its 8 neighbors. @holmeski is suggesting you change it so that each node is only 4-connected. I understand that this 8-connected assumption might be very much baked into your implementation. But this is an implementation detail, and not part of the A* algorithm. $\endgroup$ – Ben Jul 19 at 1:42
1
$\begingroup$

ROS's costmap_2d allows you to inflate obstacles. Typically, you inflate obstacles by at least half of the robot's width.

For example: enter image description here Inflated obstacles in light grey. New path in blue.

Typically, occupancy grids like these are much finer resolution because they are obtained with a LIDAR sensor. The map is stored as an array in memory similar to an image which allows you to perform operations like erosion and dilation in OpenCV.

Inflating obstacles manually shouldn't be too hard or costly if your grid isn't too large. You should first increase the resolution of your map as shown.

$\endgroup$
  • $\begingroup$ Thanks for your answer but I have no idea how I'm going to use it because the A* implementation is mine and I don't know how I'm going to inflate the obstacles. Thanks a lot! $\endgroup$ – VansFannel Jul 14 at 6:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.