Actions of the hyperoctahedral group to compute minimal contractors

摘要

The hyperoctahedral group Bn is the group of symmetries of the hypercube [−1,1]n of Rn. For instance permutations, or symmetries along each of the n canonical planes of Rn all belong to Bn. Now, many sets of equations contain symmetries in Bn. This is the case of the addition constraint: x1+x2=x3 or the multiplication x1⋅x2=x3. In robotics, many specific geometrical constraints such as for instance constraints involving distances or angles used for localization also have these symmetries. This paper shows the fundamental role of the hyperoctahedral group for interval-based methods. These methods use operators, called contractors, which contract axis-aligned boxes, without removing any point of the solution set defined by a conjunction of constraints (typically equations, or inequalities). More precisely, the paper presents an algorithm which allows us to build minimal contractors associated to constraints with symmetries in Bn. As an application, we will consider the geometrical constraint associated to the angle between vectors. The corresponding contractor will then be used in a constraint propagation framework in order to localize a robot using several radars.