Drake
Relationship Between Collision Filter Implementations
Collaboration diagram for Relationship Between Collision Filter Implementations:


This browser is not able to show SVG: try Firefox, Chrome, Safari, or Opera instead.

In principle, collision cliques and collision filter groups are equivalent implementations of filtering.

In theory, there is no filtering scenario that can be represented by one that cannot be represented by the other. This might suggest that a single representation is sufficient. For example, collision filter groups can easily be used to represent cliques; simply add all of the clique's collision elements to a single group and have that group ignore itself.

However, in practice the implementation of the two filtering mechanisms introduces differences. Each representation has its particular strengths and weaknesses. The two mechanisms work well in concert to implement an overall collision filtering policy.

This can best be illustrated through several examples of mapping filtering scenarios to the two representations.

In the discussion of collision cliques, we have seen that we want to filter collisions between collision elements that belong to adjacent bodies.

Collision Cliques As previously indicated, we can simply instantiate a unique clique identifier and assign it to all of the two bodies collision elements.

Collision Filter Groups The simplest way to implement this using collision filter groups is to create a new group which ignores itself and make all of the collision elements of both bodies members of that group.

Comparision Both representations offer a straightforward implementation. However, because of the fixed-width bitmask, we have a finite number of collision filter groups. For a single robot with k links, we would need, on the average, k - 1 groups to handle this case. If we extend this to multiple instances of that robot, we can easily consume the majority of the available collision filter groups, just in accounting for link adjacency.

Verdict Prefer cliques.

# Example 2: Disallow Model Self-collision

In this case, we want to implement the sdf semantics and turn off self collision for the whole robot.

Collision Cliques Similar to example 1. Create a unique clique identifier and assign all collision elements in the model to that clique.

Collision Filter Groups Again, same as example 1. Assign all collision elements in the model to a unique group that ignores itself.

Comparison This scenario is very similar to the one before. Both cases deal with a clique, in the mathematical sense. A set of collision elements where all pair-wise combinations of elements are filtered. It is unsurprising that there is an obvious mapping between these cases and the clique filtering mechanism.

Verdict For the same reasons as before, collision cliques are preferred.

# Example 3: URDF Specifies Two Non-colliding Groups

In this case, the filtering policy is not automatic. It is specified by definitions of groups in a URDF file. In this case, we'll deal with a theoretical file with two groups (assuming all bodies/links have been properly defined prior to this XML snippet).

    <collision_filter_group name="groupA">
<ignored_collision_filter_group collision_filter_group="groupB">
</collision_filter_group>
<collision_filter_group name="groupB">
<ignored_collision_filter_group collision_filter_group="groupA">
</collision_filter_group>


The filtering implications of these groups is that we filter collisions between all the collision elements of the bodies (1, 3), (1, 4), (2, 3), and (2, 4) (i.e., the Cartesian product of the two groups).

Collision Cliques There is a simple mapping from these groups to cliques. For each member in groupA, create a clique id and assign it to that member and all the members in groupB. We are essentially implementing the Cartesian product. This greedy approach will instantiate N different cliques (where N = |groupA|). And the number of cliques that each member of of groupB has will increase by that same number N. Remember that the evaluation of cliques for filtering is linear in the number of cliques to which a collision element belongs.

Ideally, we would want to reduce the number of cliques to which a body belongs. To do so, we would have to look at the full graph of vertices and edges. The optimal number of cliques is related to finding the maximal cliques of the graph. This is known to be an NP-complete problem.

Collision Filter Groups The collision filter implementation of this is straightforward. Two groups are created (we'll call them A and B). The collision elements of body1 and body2 belong to group A. The collision elements of body3 and body4 belong to group B. A is set to ignore B and vice versa. This would be represented by the following bitmasks:

A membership 0...0011
A ignore 0...0100
B membership 0...0101
B ignore 0...0010

In this representation, the right-most bit is the low-order bit. Remember that all elements belong to the universal group (bit 0). It should be clear that groupA and groupB` were assigned to bits 1 and 2, respectively.

Comparision Collision filtering based on classes of bodies fits naturally with the collision filter group model. Its representation is compact and its runtime cost remains unchanged. The efficacy of the clique approach depends on the size of the groups and, handled greedily, could lead to an explosion in redundant clique assignments.

Verdict Prefer collision filter groups.

These relative strengths and weaknesses are the reasons we maintain both systems simultaneously. Collision cliques provide an (in practice) unbounded set of filter parameters and are well suited for mutually exclusive sets of bodies. Collision filter groups offer a compact representation with O(1) computation costs and are ideally suited for excluding large classes of bodies from collision computation.

Next topic: Input File Collision Semantics