Tracking algorithms are an indispensable prerequisite for many higher-level computer vision tasks, ranging from surveillance to animation to automotive applications. A complete tracker is a complex system with many modules that need to cooperate. It is important to exploit all the sources of information, such as the appearance, the physical constraints and, though less commonly used, social factors like the walking patterns of people that belong to the same group. Given this complexity, a tracker often resorts to ad hoc solutions and scene specific customizations to improve the performance. We propose here a multi-target tracking model that succeeds in uniformly including the mentioned sources of information and is amenable to further extensions. We build our model within the Conditional Random Field framework. As the model cannot be globally optimized, we adopt an approximate inference strategy. Therefore we use a recently published sampling-based inference method that we customize to our needs and show the effectiveness of the choice in the experimental results.