UoL CS Notes
Menu

Obstacle Avoidance

COMP329 Lectures

This is also known as local path planning. The goal is to avoid obstacles without the use of a map.

This is implemented as a subsumption behaviour, second to the main task.

Bug Algorithms

These are simple obstacle avoidance algorithms that assume:

  • The robo has only local knowledge and the global goal.
  • Robot modelled as a point operating on a plane.
  • Sensor is tactlie (touch).
  • Simple behaviours:
    • Follow the wall
    • Move in a straight line towards the goal

Success is guaranteed (where possible).

Bug 0

In this method it is assume we know that start and end points:

  1. Head towards the goal.
  2. If an obstacle is detected, follow the boundary (usually in a fixed direction) until you can head to the goal.

This can be foiled by certain obstacles.

Bug 1

To solve the issues in bug 0 we can remember where we have been.

  1. Follow along the obstacle to avoid it.
  2. Fully circle each encountered obstacle to be sure you know where the closest point is to the goal.
  3. Move to the point along the current obstacle boundary that is closest to the goal.
  4. Move towards the goal.

This can result in the following distances:

\[D\leq L_\text{Bug1}\leq D+1.5\sum_i P_i\]

where:

  • $D$ - straight line distance from start to goal.
  • $P_i$ - perimeter of the $i^\text{th}$ obstacle.

This method performs an exhaustive search to find the optimal leave point.

Bug 2

We can modify on the bug 1 algorithm:

  1. Assume a straight path from start to the end goal.

    Call this the $m$-line.

  2. Head to the goal on the $m$-line.
  3. If an obstacle is encountered, follow around the boundary until the $m$-line is encountered.
  4. Leave the obstacle and move towards the goal along the $m$-line.

This will result in the following distance:

\[D\leq L_\text{Bug2}\leq D+\frac 12\sum_i^n n_iP_i\]

where:

  • $D$ - straight line distance from start to goal.
  • $P_i$ - perimeter of the $i^\text{th}$ obstacle.
  • $n_i$ - number of intersection points of the $i^\text{th}$ obstacle.

$L_\text{Bug2}$ can be arbitrarily longer than $L_\text{Bug2}$ if an obstacle has many intersecting points with the $m$-line.

This method performs an opportunistic approach. It is greedy and opts for the first promising approach found.

This is better for simple obstacles.