Dynamic Probabilistic Relational Models

1 Introduction

Sequential phenomena abound in the world, and uncertainty is a common feature of them. Currently the most power­ ful representation available for such phenomena is dynamic Bayesian networks, or DBNs [Dean and Kanazawa, 1989]. DBNs represent the state of the world as a set of variables, and model the probabilistic dependencies of the variables within and between time steps. While a major advance over previ­ ous approaches, DBNs are still unable to compactly represent many real-world domains. In particular, domains can contain multiple objects and classes of objects, as well as multiple kinds of relations among them; and objects and relations can appear and disappear over time. For example, manufactur­ ing plants assemble complex artifacts (e.g., cars, computers, aircraft) from large numbers of component parts, using mul­ tiple kinds of machines and operations. Capturing such a do­ main in a DBN would require exhaustively representing all possible objects and relations among them. This raises two problems. The first one is that the computational cost of us­ ing such a DBN would likely be prohibitive. The second is that reducing the rich structure of the domain to a very large, "flat" DBN would render it essentially incomprehensible to human beings. This paper addresses these two problems by introducing an extension of DBNs that exposes the domain's relational structure, and by developing methods for efficient inference in this representation.

Formalisms that can represent objects and relations, as op­ posed to just variables, have a long history in AI. Recently, significant progress has been made in combining them with a principled treatment of uncertainty. In particular, probabilis­ tic relational models or PRMs [Friedman eta!., 1999] are an extension of Bayesian networks that allows reasoning with classes, objects and relations. The representation we intro­ duce in this paper extends PRMs to sequential problems in the same way that DBNs extend Bayesian networks. We thus call it dynamic probabilistic relational models, or DPRMs. We develop an efficient inference procedure for DPRMs by adapting Rao-Blackwellised particle filtering, a state-of-the­ art inference method for DBNs [Murphy and Russell, 2001]. We introduce abstraction trees as a data structure to reduce the computational cost of inference in DPRMs.

Early fault detection in complex manufacturing processes can greatly reduce their cost. In this paper we apply DPRMs to monitoring the execution of assembly plans, and show that our inference methods scale to problems with over a thou­ sand objects and thousands of steps. Other domains where we envisage DPRMs being useful include robot control, vi­ sion in motion, language processing, computational modeling of markets, battlefield management, cell biology, ecosystem modeling, and the Web.

The rest of the paper is structured as follows. The next two sections briefly review DBNs and PRMs. We then introduce DPRMs and methods for inference in them. The following section reports on our experimental study in assembly plan monitoring. The paper concludes with a discussion of related and future work.

2 Dynamic Bayesian Networks

A Bayesian network encodes the joint probability distribu­ tion of a set of variables, {Z1 , ... , Zd} , as a directed acyclic graph and a set of conditional probability models. Each node corresponds to a variable, and the model associated with it allows us to compute the probability of a state of the vari­ able given the state of its parents. The set of parents of Z;, denoted Pa(Z;), is the set of nodes with an arc to Z; in the graph. The structure of the network encodes the assertion that each node is conditionally independent of its non-descendants given its parents. The probability of an ar­ bitrary event Z = (Z1, ... , Zd) can then be computed as P(Z) = ll~= l P(ZiiPa(Zi)).

Dynamic Bayesian Networks (DBNs) are an extension of Bayesian networks for modeling dynamic systems. In a DBN, the state at time t is represented by a set of random variables Zt = {Z1,t, ... , Zd,t }· The state at timet is dependent on the states at previous time steps. Typically, we assume that each state only depends on the immediately preceding state (i.e., the system is first-order Markovian), and thus we need to represent the transition distribution P(Zt+IIZt)· This can be done using a two-time-slice Bayesian network fragment (2TBN) Bt+I, which contains variables from Zt+I whose parents are variables from Zt and/or Zt+I. and variables from Zt without any parents. Typically, we also assume that the process is stationary, i.e., the transition models for all time slices are identical: B1 = B2 = ... = Bt = B_,. Thus a DBN is defined to be a pair of Bayesian networks (B0 , B_,), where B0 represents the initial distribution P(Z0 ), and B_, is a two-time-slice Bayesian network, which as discussed above defines the transition distribution P( Zt+II Zt).

The set Zt is commonly divided into two sets: the unob­ served state variables Xt and the observed variables yt. The observed variables yt are assumed to depend only on the cur­ rent state variables Xt. The joint distribution represented by a DBN can then be obtained by unrolling the 2TBN:

Various types of inference in DBNs are possible. One of the most useful is state monitoring (also known as filtering or tracking), where the goal is to estimate the current state of the world given the observations made up to the present, i.e., to compute the distribution P(XriYo, Y1, ... , Yr). Proper state monitoring is a necessary precondition for rational decision­ making in dynamic domains. Inference in DBNs is NP­ complete, and thus we must resort to approximate meth­ ods, of which the most widely used one is particle filter­ ing [Doucet et al., 2001]. Particle filtering is a stochas­ tic algorithm which maintains a set of particles (samples) xi, XF, ... , x{" to approximately represent the distribution of possible states at time t given the observations. Each parti­ cle x~ contains a complete instance of the current state, i.e., a sampled value for each state variable. The current distribution is then approximated by

where £5 ( x~ = x) is 1 if the state represented by x~ is same as x, and 0 otherwise. The particle filter starts by generating N particles according to the initial distribution P(X0 ) . Then, at each step, it first generates the next state x~+l for each parti­ cle i by sampling from P(Xf+11Xf). It then weights these samples according to the likelihood they assign to the ob­ servations, P(Yt+11Xf+l), and resamples N particles from this weighted distribution. The particles will thus tend to stay clustered in the more probable regions of the state space, ac­ cording to the observations.

Although particle filtering has scored impressive successes in many practical applications, it also has some significant limitations. One that is of particular concern to us here is that it tends to perform poorly in high-dimensional state spaces. This is because the number of particles required to main­ tain a good approximation to the state distribution grows very rapidly with the dimensionality. This problem can be greatly attenuated by analytically marginalizing out some of the vari­ ables, a technique known as Rao-Blackwellisation [Murphy and Russell, 2001]. Suppose the state space X t can be divided into two subspaces Ut and vt such that P(VtiUt. Y1 , ... , yt) can be computed analytically and efficiently. Then we only need to sample from the smaller space Ut, requiring far fewer particles to obtain the same degree of approximation. Each particle is now composed of a sample from P(UtiY1, ... , yt) plus a parametric representation of P(vt I Ut , Y1 , ... , yt) . For example, if the variables in vt are discrete and independent of each other given Ut, we can store for each variable the vector of parameters of the corresponding multinomial distribution (i.e., the probability of each value).

3 Probabilistic Relational Models

A relational schema is a set of classes C = { C 1, C2 , .. . , C k}, where each class C is associated with a set of propositional attributes A( C) and a set of relational attributes or refer­ ence slots R(C) . The propositional attribute A of class C is denoted C.A, and its domain (assumed finite) is denoted V(C.A) . The relational attribute R of C is denoted C.R, and its domain is the power set 2°' of a target class C' E C. In other words, C.R is a set of objects belonging to some class C'. 1 For example, the Aircraft schema might be used to represent partially or completely assembled aircraft, with classes corresponding to different types of parts like metal sheets, nuts and bolts. The propositional attributes of a bolt might include its color, weight, and dimensions, and its rela­ tional attributes might include the nut it is attached to and the two metal sheets it is bolting. An instantiation of a schema is a set of objects, each object belonging to some class C E C, with all propositional and relational attributes of each object specified. For example, an instantiation of the aircraft schema might be a particular airplane, with all parts, their properties and their arrangement specified.

A probabilistic relational model (PRM) encodes a proba­ bility distribution over the set of all possible instantiations I of a schema [Friedman eta!., 1999]. The object skeleton of an instantiation is the set of objects in it, with all attributes unspecified. The relational skeleton of an instantiation is the set of objects in it, with all relational attributes specified, and all propositional attributes unspecified. In the simplest case, the relational skeleton is assumed known, and the PRM spec­ ifies a probability distribution for each attribute A of each class C. The parents of each attribute (i.e., the variables it depends on) can be other attributes of C, or attributes of classes that are related to C by some slot chain. A slot chain is a composition of relational attributes. In general, it must be used together with an aggregation function that reduces a variable number of values to a single value. For example, a parent of an attribute of a bolt in the aircraft schema might be avg(bolt.plate.nut. weight), the average weight of all the nuts on the metal plates that the bolt is attached to.

1 C.R can also be defined as a function from C to 2°', but we choose the simpler convention here.

Definition 1 A probabilistic relational model (PRM) II for a relational schema Sis defined as follows. For each class C and each propositional attribute A E A( C), we have:

• A set of parents Pa(C.A) = {Pa1 , Pa2 , ... , Pa1}, where each Pa; has the form C.B or "Y(C.T.B), where Tis a slot chain and 'YO is an aggregation function.
• A conditional probability model for P(C.AIPa(C.A)). 0

Let 0 be the set of objects in the relational skeleton. The probability distribution over instantiations I of S represented by the PRM is then

A PRM and relational skeleton can thus be unrolled into a large Bayesian network with one variable for each attribute of each object in the skeleton. 2 Only PRMs that correspond to Bayesian networks without cycles are valid.

More generally, only the object skeleton might be known, in which case the PRM also needs to specify a distribution over the relational attributes [Getoor et al., 2001]. In the air­ craft domain, a PRM might specify a distribution over the state of assembly of an airplane, with probabilities for differ­ ent faults (e.g., a bolt is loose, the wrong plates have been bolted, etc.).

4 Dynamic Probabilistic Relational Models

In this section we extend PRMs to modeling dynamic sys­ tems, the same way that DBNs extend Bayesian networks. We begin with the observation that a DBN can be viewed as a special case of a PRM, whose schema contains only one class z with propositional attributes zl' ... 'zd and a single rela­ tional attribute previous. There is one object Zt for each time slice, and the previous attribute connects it to the object in the previous time slice. Given a relational schema S, we first extend each class C with the relational attribute C.previous, with domain C. As before, we initially assume that the re­ lational skeleton at each time slice is known. We can then define two-time-slice PRMs and dynamic PRMs as follows.

Definition 2 A two-time-slice PRM (2TPRM) for a relational schema S is defined as follows. For each class C and each propositional attribute A E A( C), we have:

• AsetofparentsPa(C.A) = {Pai.Pa2 , ·· . ,Pal},where each Pa; has the form C.B or f(C.T.B), where Tis a slot chain containing the attribute previous at most once, and f () is an aggregation function.
• A conditional probability model for P(C.AIPa(C.A)). 0

2 Plus auxiliary (deterministic) variables for the required aggre­ gations, which we omit from the formula for simplicity.

Definition 3 A dynamic probabilistic relational model (DPRM) for a relational schemaS is a pair (M0 , M_,), where Mo is a PRM over !0 , representing the distribution Po over the initial instantiation of S , and M_, is a 2TPRM represent­ ing the transition distribution P(Itllt-d connecting succes­ sive instantiations of S. 0

For any T, the distribution over !0 , .. . , Iris then given by

DPRMs are extended to the case where only the object skeleton for each time slice is known in the same way that PRMs are, by adding to Definition 2 a set of parents and con­ ditional probability model for each relational attribute, where the parents can be in the same or the previous time slice. When the object skeleton is not known (e.g., if objects can appear and disappear over time), the 2TPRM includes in ad­ dition a Boolean existence variable for each possible object, again with parents from the same or the previous time slice. 3 As with DBNs, we may wish to distinguish between observed and unobserved attributes of objects. In addition, we can con­ sider an Action class with a single attribute whose domain is the set of actions that can be performed by some agent (e.g., painting a metal plate, or bolting two plates together). The distribution over instantiations in a time slice can then de­ pend on the action performed in that time slice. For example, the action Bolt(Partl, Part2) may with high probability pro­ duce Partl.mate = {Part2}, and with lower probability set Partl.mate to some other object of Part2's class (i .e., be im­ properly performed, resulting in a fault) .

Just as a PRM can be unrolled into a Bayesian network, so can a DPRM be unrolled into a DBN. (Note, however, that this DBN may in general contain different variables in dif­ ferent time slices.) In principle, we can perform inference on this DBN using particle filtering. However, the filter is likely to perform poorly, because for non-trivial DPRMs its state space will be huge. Not only will it contain one variable for each attribute of each object of each class, but relational attributes will in general have very large domains. We over­ come this by adapting Rao-Blackwellisation to the relational setting. We make the following (strong) assumptions:

1. Relational attributes with unknown values do not appear anywhere in the DPRM as parents of unobserved at­ tributes, or in their slot chains.
2. Each reference slot can be occupied by at most one object.

Proposition 1 Assumptions 1 and 2 imply that, given the propositional attributes and known relational attributes at times t and t - 1, the joint distribution of the unobserved relational attributes at time t is a product of multinomials, one for each attribute.

Notice also that, by Assumption 1, unobserved proposi­ tional attributes can be sampled without regard to unobserved relational ones. Rao-Blackwellisation can now be applied with Ut as the propositional attributes of all objects and Vi as their relational attributes. A Rao-Blackwellised particle is composed of sampled values for all propositional attributes of all objects, plus a probability vector for each relational at­ tribute of each object. The vector element corresponding to obj.R[i] is the probability that relation R holds between obj and the ith object of the target class, conditioned on the values of the propositional attributes in the particle, etc.

3 Notice that the attributes of nonexistent objects need not be specified, because by definition no attributes of any other objects can depend on them [Getoor eta/., 2001].

Rao-Blackwellising the relational attributes can vastly re­ duce the size of the state space which particle filtering needs to sample. However, if the relational skeleton contains a large number of objects and relations, storing and updating all the requisite probabilities can still become quite expen­ sive. This can be ameliorated if context-specific independen­ cies exist, i.e., if a relational attribute is independent of some propositional attributes given assignments of values to oth­ ers [Boutilier et at., 1996]. We can then replace the vector of probabilities with a tree structure whose leaves represent probabilities for entire sets of objects. More precisely, we de­ fine the abstraction tree data structure for a relational attribute obj.R with target class C' as follows. A node v of the tree is composed of a probability p and a logical expression ¢ over the propositional attributes of the schema. Let Ov(C') be the set of objects in C' that satisfy the ¢'s of v and all of v's ancestors. Then p ~£ Lobj'EO.,(C') P(obj' E (obj.R)t I Ut)· The root of an abstraction tree contains ¢ = true. The chil­ dren vi of a node v contain expressions ¢i such that the Ov, (C') form a partition of Ov(C'). Each leaf of the tree stores a parametric distribution giving the probability that each object in the leaf is a member of obj.R, as a function of the object's propositional attributes. The probability that an arbitrary object obj' E C' is a member of obj.R is found by starting at the root of the abstraction tree for obj.R, going to the child whose condition is satisfied by obj', and so on recursively until a leaf is reached and the object's probability is read from the leaf distribution.

Initially, the abstraction tree consists only of the root, and as inference progresses it is gradually refined as dictated by the attributes that C.R depends on. For example, suppose the first action to be performed is Bolt(Partl, Part2), and with probability P! the action is performed incorrectly. The faulty action consists of attaching Part] to some other object of Part2's class C', with uniform probability over C'. Then two children v1 and v2 of the root of Partl.mate's abstraction tree are created, with ¢1 specifying the singleton set {Part2} and ¢2 its complement in C', and with Pl = 1 - p f and p2 = p f. The uniform distribution in leaf v2 has a single pa­ rameter, the probability p = p f / (I C'l - 1) that a given object in it is attached to Partl. This takes 0(1) space to store and 0(1) time to update, as opposed to O(IC'I). If objects with different attributes have different probabilities of being bolted to Part], a node for each relevant combination of attributes is created. Thus, if nc is the number of such combinations, the storage and update time required for Partl.mate are O(nc) in­ stead of O(IC'I). By design, nc ~ (IC'I); in the worst case, the tree will have one leaf per element of C'. As we will see in the next section, the use of abstraction trees can greatly reduce the computational cost ofRao-Blackwellised particle filtering in DPRMs.

5 Experiments

In this section we study the application of DPRMs to fault detection in complex assembly plans. We use a modified ver­ sion of the Schedule World domain from the AIPS-2000 Plan­ ning Competition. 4 The problem consists of generating a plan for assembly of objects with operations such as painting, pol­ ishing, etc. Each object has attributes such as surface type, color, hole size, etc. We add two relational operations to the domain: bolting and welding. We assume that actions may be faulty, with fault model described below. In our experi­ ments, we first generate a plan using the FF planner [Hoff­ mann and Nebel, 2001]. We then monitor the plan's execu­ tion using particle filtering (PF), Rao-Blackwellised particle filtering (RBPF) and RBPF with abstraction trees.

We consider three classes of objects: Plate, Bracket and Bolt. Plate and Bracket have propositional attributes such as weight, shape, color, surface type, hole size and hole type, and relational attributes for the parts they are welded to and the bolts bolting them to other parts (e.g., Plate73.bolt4 corre­ sponds to the fourth bolt hole on plate 73). The Bolt class has propositional attributes such as size, type and weight. Propo­ sitional actions include painting, drilling and polishing, and change the propositional attributes of an object. The rela­ tional action Bolt sets a bolt attribute of a Plate or Bracket object to a Bolt object. The Weld action sets a welded-to at­ tribute of a Plate or Bracket object to another Plate or Bracket object.

The fault model has a global parameter, the fault proba­ bility P!· With probability 1 - P!, an action produces the intended effect. With probability p f, one of several possible faults occurs. Propositional faults include a painting oper­ ation not being completed, the wrong color being used, the polish of an object being ruined, etc. The probability of dif­ ferent propositional faults depends on the properties of the object being acted on. Relational faults include bolting the wrong objects and welding the wrong objects. The proba­ bility of choosing a particular wrong object depends on its similarity to the intended object. Similarity depends on dif­ ferent propositional attributes for different actions and differ­ ent classes of objects. Thus the probability of a particular wrong object being chosen is uniform across all objects with the same relevant attribute values.

The DPRM also includes the following observation model. There are two instances of each attribute: the true one, which is never observed, and the observed one, which is observed at selected time steps. Specifically, when an action is per­ formed, all attributes of the objects involved in it are ob­ served, and no others. Observations are noisy: with proba­ bility 1 - Po the true value of the attribute is observed, and with probability Po an incorrect value is observed. Incorrect values for propositional observations are chosen uniformly. Incorrect values for relational observations are chosen with a probability that depends on the similarity of the incorrect object to the intended one.

Notice that, if the domain consisted exclusively of the propositional attributes and actions on them, exact inference might be possible; however, the dependence of relational at­ tributes and their observations on the propositional attributes creates complex dependencies between these, making ap­ proximate inference necessary.

4 URL: http://www.cs.toronto.edu/aips2000

A natural measure of the accuracy of an approximate infer­ ence procedure is the K-L divergence between the distribu­ tion it predicts and the actual one [Cover and Thomas, 2001]. However, computing it requires performing exact inference, which for non-trivial DPRMs is infeasible. Thus we estimate the K-L divergence by sampling, as follows. Let D(piiP) be the K-L divergence between the true distribution p and its approximation p, and let X be the domain over which the distribution is defined. Then

The first term is simply the entropy of X, H(X), and is a constant independent of the approximation method. Since we are mainly interested in measuring differences in perfor­ mance between approximation methods, this term can be ne­ glected. The K-L divergence can now be approximated in the usual way by taking S samples from the true distribution:

where p(xi) is the probability of the ith sample according to the approximation procedure, and the H subscript indi­ cates that the estimate of D(pii.P) is offset by H(X). We thus evaluate the accuracy of PF and RBPF on a DPRM by generating S = 10, 000 sequences of states and observations from the DPRM, passing the observations to the particle fil­ ter, inferring the marginal probability of the sampled value of each state variable at each step, plugging these values into the above formula, and averaging over all variables. Notice that b H (PII.P) = oo whenever a sampled value is not rep­ resented in any particle. The empirical estimates of the K-L divergence we obtain will be optimistic in the sense that the true K-L divergence may be infinity, but the estimated one will still be finite unless one ofthe values with zero predicted probability is sampled. This does not preclude a meaningful comparison between approximation methods, however, since on average the worse method should produce b H (pii.P) = oo earlier in the time sequence. We thus report both the average K-L divergence before it becomes infinity and the time step at which it becomes infinity, if any.

Figures 1 and 2 show the results of the experiments per­ formed. The observation noise parameter Po was set to the same value as the fault probability p f throughout. One action is performed in each time step; thus the number of time steps is the length of the plan. The graphs show the K-L divergence of PF and RBPF at every 1 OOth step (it is the same for RBPF with and without abstraction trees). Graphs are interrupted at the first point where the K-L divergence became infinite in any of the runs (once infinite, the K-L divergence never went back to being finite in any of the runs), and that point is labeled with the average time step at which the blow-up oc­ curred. As can be seen, PF tends to diverge rapidly, while the K-L divergence of RBPF increases only very slowly, for all combinations of parameters tried. Abstraction trees reduced RBPF's time and memory by a factor of 30 to 70, and took on average six times longer and 11 times the memory of PF, per particle. However, note that we ran PF with 40 times more particles than RBPF. Thus, RBPF is using less time and memory than PF, and performing far better in accuracy.

We also ran all the experiments while measuring the K-L divergence of the full joint distribution of the state (as op­ posed to just the marginals). RBPF performed even better compared to PF in this case; the latter tends to blow up much sooner (e.g., from around step 4000 to less than 1000 for p f = 1% and 1000 objects), while RBPF continues to de­ grade only very slowly.

6 Related Work

Dynamic object-oriented Bayesian networks (DOOBNs) [Friedman eta/., 1998] combine DBNs with OOBNs, a pre­ decessor of PRMs. Unfortunately, no efficient inference methods were proposed for DOOBNs, and they have not been evaluated experimentally. DPRMs can also be viewed as ex­ tending relational Markov models (RMMs) [Anderson et a!., 2002] and logical hidden Markov models (LOHMMs) [Ker­ sting eta/., 2003] in the same way that DBNs extend HMMs. Downstream, DPRMs should be relevant to research on re­ lational Markov decision processes (e.g., [Boutilier et a!., 200 1]).

Particle filtering is currently a very active area of research [Doucet eta!., 2001]. In particular, the FastSLAM algorithm uses a tree structure to speed up RBPF with Gaussian vari­ ables [Montemerlo et a!., 2002]. Abstraction trees are also related to the abstraction hierarchies in RMMs [Anderson et a!., 2002] and to AD-trees [Moore and Lee, 1997]. An alter­ nate method for efficient inference in DBNs that may also be useful in DPRMs was proposed by Boyen and Koller [1998] and combined with particle filtering by Ng eta!. [2002]. Ef­ ficient inference in relational probabilistic models has been studied by Pasula and Russell [2001].

7 Conclusions and Future Work

This paper introduces dynamic probabilistic relational mod­ els (DPRMs), a representation that handles time-changing phenomena, relational structure and uncertainty in a prin­ cipled manner. We develop efficient approximate inference methods for DPRMs, based on Rao-Blackwellisation of rela­ tional attributes and abstraction trees. The power of DPRMs and the scalability of these inference methods are illustrated by their application to monitoring assembly processes for fault detection.

Directions for future work include relaxing the assump­ tions made, further scaling up inference, formally studying the properties of abstraction trees, handling continuous vari­ ables, learning DPRMs, using them as a basis for relational MDPs, and applying them to increasingly complex real-world problems.

8 Acknowledgements

This work was partly supported by an NSF CAREER Award to the second author, by ONR grant N00014-02-l-0932, and by NASA grant NAG 2-1538. We are grateful to Mausam for helpful discussions.