As you know in Bug algorithm there is a simplifying assumption that says the robot has no size and can fit between any arbitrarily small gap in the map. How can we overcome the challenge of robot size. As we don't have any per-calculated map (in sensor based navigation), can we still tackle the problem in configuration space? For example, let's assume that the type of the sensor is Hokuyo URG-04LX Laser Rangefinder. Hence we can visualize the sensor measurements by the visualization matrix $V$: \begin{equation} V_i =\begin{pmatrix}cos(\theta_i )* d_i, \quad sin(\theta_i )* d_i\end{pmatrix}\\ \end{equation} Where $D= [d_1,d_2,\dotsc, d_n]$ is the set of distances, and $\theta_i$ can be calculated as: \begin{equation} \theta_i = \theta_{i-1} + {0.36}^\circ,\qquad \theta_1 = 0 \end{equation} All the information we have about the robot's surrounding at each moment is $V$. I strongly believe that there is no well-formed formula which can define the robot size in this configuration, and also as we don't have any map, but a simple visualization, growing the obstacles by the radius of the robot size in the configuration space just doesn't make sense.

  • $\begingroup$ I think I have an answer, but it would be helpful if you referenced the Bug algorithm and provided an image summarizing the relevance of your question. $\endgroup$
    – JSycamore
    Oct 7, 2016 at 19:36
  • $\begingroup$ @farhad, you will need to add more detail to your question. Specifically, give information about the shape/type of robot and the sensors available. $\endgroup$
    – hauptmech
    Oct 9, 2016 at 1:56
  • $\begingroup$ "I strongly believe that there is no well-formed formula which can define the robot size in this configuration" how so? To calculate the minkowski sum for the configuration space you just need the normals of each line that connects two consecutive points of yours. $\endgroup$ Oct 9, 2016 at 11:01
  • $\begingroup$ Yes, connecting consecutive points of set $D$ gives us a representation of the robot's surrounding. But this representation differs from the map. Think about the gap between two consecutive points. How would you know that whether the gap is part of an obstacle or is a free space that the robot can fit between. The problem is that we don't know anything about the gap between two consecutive laser beams. $\endgroup$
    – farhad
    Oct 9, 2016 at 11:21
  • $\begingroup$ @farhad yes, but you know how the surrounding points behave. If you have several points that jump to a higher distance value, you can assume that there's a gap. The effective resolution of the sensor will increase when you get closer to objects, which makes it easier to estimate which parts are connected and which are not. Do you have any sensor data? Please include it in your post! $\endgroup$ Oct 9, 2016 at 22:06

1 Answer 1


If you are able to sense obstacles with a sensor pattern that is circular (eg laser scanner, contact sensors on a circular body, etc), and you can rotate the robot pose without translation, then you can satisfy the assumptions of the Bug algorithm.

If you use a point model for your robot in the map, then you grow the obstacles by the radius of your robot.

If your sensors are not circular, then you will need to create an algorithm for local movement that moves the sensors in a manner that will detect the obstacles without putting the robot in a trapped position. This will probably prevent your robot sensing narrow but valid paths through the obstacles.

EDIT: You have a circular sensor. If you have differential drive, then you can pick the smallest sensor radius that your robot fits inside and use that. If you have ackerman steering then there is a radius within which you can rotate in place with forward-backward motions. You can use that radius.

All of this is focused on the Bug algorithm. You should use a different, or layered algorithm if you cannot meet the basic assumptions of the bug algorithm.

Also, you can sense the contents of the gap between consecutive points of set $D$ by rotating the robot.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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