# Obstacle Avoidance while Navigating

I need some ideas for strategies or algorithms to apply on these strategies to perform obstacle avoidance while navigating.

At the moment I'm doing offline path planning and obstacle avoidance of known obstacles with an occupancy grid. And running the A* algorithm over the created matrix. After that my robot follows along the resulting trajectory. This is done by splitting the whole trajectory into sub-path. The robot adjust it's heading to the new target and follows the straight line. The robot is controlled by a fuzzy logic controller to correct deviations from the ideal line (steering) and adjusting the velocity according to the steering action and distance to the target. So far so good. And it's working very well.

As sensor system, I solely use the Google Project Tango (Motion Tracking and Area Learning for proper path following). Now I want to use the depth perception capability of the device. Getting the appropriate depth information and extracting a possible obstacle is done with a quite simple strategy. The robot analyses the depth information in front of the robot and if any object is in between the robot and the target point of the sub-path, an obstacle must be there.

Now I'm wondering how to bypass this obstacle most efficiently. The robot is only aware of the height and width of the obstacle, but has no clue about the depth (only the front of the obstacle is scanned). Feeding the occupancy grid with this new obstacle and running again the A* algorithm is not effective, because of the missing depth. One possible strategy I could imagine is estimating a depth of the length of the grid cell, re-plan and continue the navigation. If the robot faces the same obstacle again, the depth is increased by the size of one additional grid cell length. But I think this is extremely ineffective.

The requirement is to only use the Google Project Tango and no additional sensors, such as ultrasonic to sense the sides.

Update 1

The first picture illustrates the given trajectory from the path planning (orange). The gray and blue data points are the sensed obstacles in front of the robot. The notch behind the blue obstacle is actually the wall, but is shadowed by the blue obstacle. Image 2 shows the same scene just from a different perspective.

The issue I have to treat is, how to optimally bypass the blue obstacle even I don't know how deep it is. Driving to the left and to the right only to capture better data points (to generate a 3D model) is not possible.

Update 2 Yes, I'm using a depth sensor, the one integrated in Google Project Tango. It's a visual measurement. A infra-red laser beams a grid onto the objects and a RGB-IR camera capture these information and evaluates the appropriate depth information.

• I'm not sure I understand - you, "want to use ... depth perception," and, "[g]etting the appropriate depth information and extracting a possible obstacle is ... quite simple," but, "[t]he robot ... has no clue about the depth"? Are you using a depth sensor or not? Can you attach any images that show what you're talking about? It sounds like maybe you're looking for structure from motion to help get the missing information, but I can't tell from your terminology what you're actually missing.
– Chuck
Jul 11, 2016 at 13:55
• @Chuck "the robot .. has no clue about the depth" - means the robot has no clue about the depth of the object. The sensor reveals that there is an object, but the sensor can only see the face of the object nearest the robot and not the furthest face. Jul 12, 2016 at 12:03
• Okay, so you mean that the robot knows how far the object is, but it doesn't know how "deep" the object is, where "deep" means length along the visual axis.
– Chuck
Jul 12, 2016 at 12:14
• @Chuck, exactly what I meant ;) Jul 12, 2016 at 13:11
• "Driving to the left and to the right only to capture better data points (to generate a 3D model) is not possible." Why is that? You have to go to the left or right eventually anyway to go around the obstacle. Jul 13, 2016 at 11:22

It sounds like you need a costmap. I would project the 3D points down onto a 2D plane. (At least the points that correspond to the height of your robot). Then make an occupancy grid where each cell is labeled as either "free space", "obstacle", or "unknown". You'll get something like this:

Where white is free space, blue is obstacle, and grey is unknown.

Points from your point cloud become the "obstacle" class obviously. Use simple ray tracing so that points between the robot and obstacle are "free space". And everything else is unknown. (i.e. points beyond the obstacle or max distance of your sensor). Then use these as costs in your A* path planner. Allow the robot to plan paths through unknown space, but make it cost more than free space.

Other notes:

• Typically, you bloat the obstacle cells by at least the robot's radius so it doesn't get too close to them.
• You can do this probabilisticly if your robot/sensor has noise, or you are in a dynamic environment. Here, "free", "obstacle", and "unknown" are now floating values based on a number of past sensor readings.
• I accepted your solution, because it's simpler to implement and enough for the purpose of application. Jul 21, 2016 at 10:40

I think that vector field histogram method should be a good solution here. It's a method of local motion planning (avoiding local obstacles while navigating to a global target). It involves mapping measurements into cartesian occupancy grid, and making a polar obstacle density histogram from that grid. Later the direction with lowest obstacle density and closest to the desired target is selected.

• Sounds quote interesting. Is there a full sample implementation in any language available? Jul 13, 2016 at 13:26
• @dannyyy you can have a look at implementation in player/stage project, or ROS. Jul 14, 2016 at 6:38