2
$\begingroup$

I'm trying to understand these two classic approaches to path planning in dynamic environments/with moving obstacles. According to some review papers, there seems to be quite a difference between them, e.g. so that the collision cone approach (as presented in [1]) can be used for non-circular objects as well. But to me they seem very analogous:

In my understanding, given a point robot and a circle obstacle, both moving at constant velocities $v_A$ and $v_B$, the collision cone $CC$ is defined by two rays through the robot, tangentially containing the whole obstacle. If the relative velocity $v_r = v_A - v_B$ is contained in this cone, a collision will eventually happen, otherwise they will pass without collision. Now, the velocity obstacle seems to be just the collision cone moved by $v_B$, i.e. $VO = CC \bigoplus v_B$ where $\bigoplus$ is the Minkowski sum. Therefore, any velocity of the robot in $VO$ will result in an collision, all the others won't.

Is there something I'm misunderstanding here or is it that simple? Here is a figure from [2] that seems to fit to my understandings.

enter image description here

[1]: Chakravarthy, A., & Ghose, D. (1998). Obstacle avoidance in a dynamic environment: a collision cone approach. IEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans, 28(5), 562–574. https://doi.org/10.1109/3468.709600

[2]: Wilkie, D., van den Berg, J., & Manocha, D. (2009). Generalized velocity obstacles. In 2009 IEEE/RSJ International Conference on Intelligent Robots and Systems (S. 5573–5578). IEEE. https://doi.org/10.1109/IROS.2009.5354175

$\endgroup$
1
$\begingroup$

After reading through the original collision cones paper and many others I realized that my understanding of the collision cone was wrong. The "collision cone" mentioned in the Velocity Obstacle papers refers to something completely different.

Simply said, given a point robot and an obstacle both moving at (given) constant velocities, the collision cone is the set of angles or directions, that will result in a collision if the robot chooses one of them. In the most cases it is just one range of angles, and visualized in the work- or configuration space (which are equivalent here) resembles a cone. Note that the vertex of the cone is located at the robots position, and is generally speaking not diverging exactly in the direction of the obstacle, but roughly in the direction to the path the obstacle is following. See this figure as example, where O is the robot and the CC is hatched:

Source: [1]

Now for the Velocity Obstacle the explanation given in my question seems still correct to me, and the differences are quite noticeable now. In the VO case, the "collision cone" mentioned there is just defined by the two tangential straights, and refers to the relative velocities, unlike the CC that regards the robots direction.

Another difference is the meaning of the cones in these two approaches. CCs describe forbidden directions for the robot, where both velocities are already fixed. VOs contain all forbidden velocity vectors, which may have different directions and magnitudes.

[1]: Chakravarthy, A., & Ghose, D. (1998). Obstacle avoidance in a dynamic environment: a collision cone approach. IEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans, 28(5), 562–574. https://doi.org/10.1109/3468.709600

$\endgroup$

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.