Energy functions defined on higher order cliques can model complex interactions between groups of random variables. They have the capability of modelling the rich statistics of natural scenes which can be used for many applications in computer vision. However, these energies are seldom used in practice, primarily due to the lack of efficient algorithms for minimizing them. In this paper we introduce a novel family of higher order potentials called the Robust P n model. This family is a generalization of the P n Potts model class of potentials which was recently introduced in computer vision. We show that energy functions containing such potentials can be solved using the expansion and swap move algorithms for approximate energy minimization. Specifically, we prove that the optimal swap and expansion moves for energy functions composed of these potentials can be computed by solving a st-mincut problem. For functions of binary variables, our method is able to produce the globally optimal solution in polynomial time. Further, it is extremely efficient and can handle energies defined on cliques involving thousand of variables.