Stochastic processes that involve the creation of objects and relations over time are widespread, but relatively poorly studied. For example, accurate fault diagnosis in factory assembly processes requires inferring the probabilities of erroneous assembly operations, but doing this efciently and accurately is difcult. Modeled as dynamic Bayesian networks, these processes have discrete variables with very large domains and extremely high dimensionality. In this paper, we introduce relational dynamic Bayesian networks (RDBNs), which are an extension of dynamic Bayesian networks (DBNs) to rst-order logic. RDBNs are a generalization of dynamic probabilistic relational models (DPRMs), which we had proposed in our previous work to model dynamic uncertain domains. We rst extend the Rao-Blackwellised particle ltering described in our earlier work to RDBNs. Next, we lift the assumptions associated with Rao-Blackwellization in RDBNs and propose two new forms of particle ltering. The rst one uses abstraction hierarchies over the predicates to smooth the particle lter's estimates. The second employs kernel density estimation with a kernel function specically designed for relational domains. Experiments show these two methods greatly outperform standard particle ltering on the task of assembly plan execution monitoring.