10   ANGUELOV ET AL.   UAI2002  Learning Hierarchical Object Maps Of Non-Stationary Environments With Mobile Robots  Dragomir Anguelov*   Rahul Biswas*   Daphne Koller* Benson Limketkai*   Sebastian Thrun t  *Computer Science Department Stanford University Stanford, CA 94305  Abstract  Building models, or maps, of robot environments is a highly active research area; however, most existing techniques construct unstructured maps and assume static environments.   In this paper, we present an al gorithm for learning object models of non-stationary objects found in office-type environments.   Our al gorithm exploits the fact that many objects found in office environments look alike (e.g., chairs, recycling bins). It does so through a two-level hierarchical repre sentation, which links individual objects with generic shape templates of object classes.   We derive an ap proximate EM algorithm for learning shape parame ters at both levels of the hierarchy, using local occu pancy grid maps for representing shape. Additionally, we develop a Bayesian model selection algorithm that enables the robot to estimate the total number of ob jects and object templates in the environment.   Ex perimental results using a real robot equipped with a laser range finder indicate that our approach performs well at learning object-based maps of simple office en vironments.   The approach outperforms a previously developed non-hierarchical algorithm that models ob jects but lacks class templates.  1   Introduction  Building environmental maps with mobile robots is a key prerequisite of truly autonomous robots [19]. State-of-the art algorithms focus predominantly on building maps in  static   environments [20].   Common map representations range from lists of landrnarks [3, 9, 21], fine-grained grids of numerical occupancy values [6, 15], collections of point obstacles [11], or sets of polygons [12]. These representa tions are appropriate for mobile robot navigation in static environments. Real environments, however, consist of objects. For ex ample, office environments possess chairs, doors, recycling bins, etc.   Many of these objects are non-stationary, that is, their locations may change over time. This observation motivates research on a new generation of mapping algo rithms, which represent environments as collections of ob jects. At a minimum, such object models would enable a robot to track changes in the environment. For example, a cleaning robot entering an office at night might realize that  t   School of Computer Science Carnegie Mellon University Pittsburgh, PA 15213 a recycling bin has moved from one location to another. It might do so without the need to learn a model of this recy cling bin from scratch,   as would be necessary with existing robot mapping techniques [20]. Object representations offer a second, important advan tage, which is due to the fact that many office environ ments possess large collections of objects of the same type. For example, most office chairs are instances of the same generic chair and therefore look alike, as do most doors, recycling bins, and so on. As these examples suggest, at tributes of objects are shared by entire classes of objects, and understanding the nature of object classes is of signifi cant interest to mobile robotics.   In particular, algorithms that learn properties of object classes would be able to transfer learned parameters (e.g., appearance, motion pa rameters) from one object to another in the same class. Such ability to generalize would have a profound impact on the accuracy of object models, and the speed at which such models can be acquired. If, for example, a cleaning robot enters a room it has never visited before, it might realize that a specific object in the room possesses the same vi sual appearance of other objects seen in other rooms (e.g., chairs).   The robot would then be able to acquire a map of this object much faster.   It would also enable the robot to predict properties of this newly seen object, such as the fact that a chair is non-stationary-without ever seeing this specific object move. In previous work, we developed an algorithm that has successfully been demonstrated to learn shape models of non-stationary objects [2]. This approach works by com paring occupancy grid maps acquired at different points in time.   A straightforward segmentation algorithm was developed that extracts object footprints from occupancy grid maps.   It uses these footprints to learn shape models of objects in the environment, represented by occupancy grid maps.   This algorithm is related to work on learn ing generative object models in computer vision and med ical imaging. Frey and Jojic [7] describe an unsupervised approach which infers a set of object templates and their transformations from a set of camera images. Leventon et a!. [I OJ describe an alternative shape representation based on geodesic active contours. They show how to learn ob-
UAI2002   ANGUELOV ET AL.   1 1  (a)   (b) Figure   I:   (a) Generative hierarchical model of environ ments with non-stationary objects. (b) Representation as a graphical model. ject shape priors using the representation and how to use the object priors for tissue segmentation in tomography scans. This paper goes one step further by proposing an al gorithm that identifies classes of objects, in addition to learning plain object models. In particular, our approach learns shape models of individual object classes, from mul tiple occurrences of objects of the same type. By learning shape models of object types-in addition to shape models of individual objects--our approach is able to generalize across different object models that belong to the same ob ject class. This approach follows the hierarchical Bayesian framework (see [1,   8,   13]).   We show that our approach leads to significantly more accurate models in real-world environments with multiple objects of the same type. The specific learning algorithm proposed here is an in stance of the popular EM algorithm [14]. We develop a closed-form solution for learning at both levels of the hi erarchy, which simultaneously identifies object models and shape templates for entire object classes. On top of this, we propose a Bayesian procedure for determining the appro priate number of object models, and object class models. We tested our algorithm on data gathered by a physical robot, which was equipped with a laser range finder. Our results suggest that our approach succeeds in learning ac curate shape and class models.   A systematic comparison with our previous, non-hierarchical approach [2] illustrates that the use of class models yields significantly better re sults, both in terms of predictive power (as measured by the log-likelihood over testing data) and in terms of con vergence properties (measured by the number of times each algorithm is trapped in a local maximum of poor quality).  2   The Generative Hierarchical Model  We begin with a description of the hierarchical model. The object level generalizes the approach of [2] to maps with continuous occupancy. The central innovation is the intro duction of a template level.  2.1   The Object Hierarchy  Our object hierarchy (Figure Ia) is composed of two levels, the   object template level   at the top, and the   physical object level   at the bottom. The object template level consists of a set of   M   shape templates, denoted   <p = <p 1,  ... , <p M.   Each template   'Pm   is represented by an occupancy grid map [6, 15, 20], that is, an array of values in [0, 1 J that represent the occupancy of a grid cell. The object level contains shape models of concrete ob jects in the world, denoted:   ()   =   01, ...  ,   () N,   where N is the total number of objects (with N 2:   M).   Each object model () n is represented by an occupancy grid map, just like at the template level. The key difference between object models On and templates   'Pm   is that each On corresponds to ex actly one object in the world, whereas a template   'Pm   may correspond to more than one object. If, for example, all non-stationary objects were to look alike, () would contain multiple models (one for each object), whereas   <p   would contain only a single shape template. To learn a hierarchy, we assume that the robot maps its environments at   T   different points in time, between which the configuration of the environment may have changed. Each map is obtained from laser sensor readings and is rep resented as a (static) occupancy grid map. The sequence of maps is denoted   J.l   =   J.l1,   ...   , J.lT.  Objects may or may not be present at any timet, and they may be located anywhere in the free space of the environ ment. The number of object snapshots present in the map  J.lt   is denoted   K1.   The set of object snapshots extracted from the map   J.lt   are denoted   J.lt   =   J.l1,t, ... , J.lK,,t·  Each object snapshot   J.lk,t   is--once again-represented by an occupancy grid map, constructed from robot sensor measurements [6, 15, 20]. The exact routines for extraction of object snapshots from maps are described in [2] and will be reviewed briefly below. Finally, we notice that objects may be observed in any orientation. Since aligning object snapshots with objects in the model is an important step in the learning procedure, we will make the alignment parameters explicit. In particular, we will use   8k,t   to denote the alignment of snapshot   J.lk,t  relative to the generative model. In our implementation, each   8k,t   consists of two translational and one rotational parameters.  2.2   Probabilistic Model  To devise a sound algorithm for inferring an object hier archy from data, we have to specifY probabilistic models of how snapshots are generated from objects and how ob jects are generated from object templates.   An   graphical overview for our probabilistic model is shown in Figure lb. Let On be a concrete object, and   J.lk,t   be a single snapshot of this object. Recall that each grid cell On[j] in On is a real number in the interval [0,   1 J.   We interpret each occupancy value as a probability that a robot sensor would detect an occupied grid cell. However, when mapping an environ ment, the robot typically takes multiple scans of the same object, each resulting in a binomial outcome.   By aggre gating the individual binary variables into a single aggre gate real value, we can approximate this fairly cumbersome
12   ANGUELOV ET AL.   UA12002  model into a much cleaner Gaussian distribution of a single real-valued observation. Thus, the probability of observing a concrete snapshot f.Lk,t of object   Bn   is given by  P(ll.   I()   0   )   Q(   e-¢ L:;U(I'k,t,Ok,t)[j]-9n[J])2   (I) rk,t   n1   k,t  The function   f ( f.L k,t   .   ok,t)   denotes the aligned snapshot  Jlk,t.   and   f( J.L k ,t,&k,t)[i]   denotes its j-th grid cell. The ro tation and translation parameters of the alignment are spec ified by   o k, t ·   The parameter   p2   is the variance of the noise. It is useful to make explicit the correspondence between objects   Bn   and object snapshots   J.Lk,t,   by introducing   corre spondence variables   a   =   a  1   ,a2, . .. ,ar.   Since each   J.Lt  is an entire set of snapshots, each   a1   is in fact a function:  at   :   {1, .. .   , Kt}   ---+   {1,   .. .   , N}.  A similar model governs the relationship between tem plates and individual objects. Let () n be a concrete object generated according to object template   '{Jm,   for some nand  m.   The probability that a grid cell   0  n [j]   takes on a value  r   E   [0, 1] is a function of the corresponding grid cell 'P m   [j ]. We assume that the probability of a grid cell value   ()   n[j]   is normally distributed with variance   u   2: p(Bn[J]I 'P m [ j ])   - 1   -   e-,.;,(en[j]-'P=IJIJ2   (2) .../27i0'  Equation   (2)   defines a probabilistic model for individual grid cells, which is easily extended to entire maps:  p(On I   'Pm)   II p(Bn[J]I 'Pm[j])  j  Q(   e -,.;, I:;(9n(j]-<p=(j])2   (3) Again, we introduce explicit variables for the correspon dence   between   objects   On   and   templates   'Pm:   (3   =  (31,   .. .   , f3N withf3n   E   {1,   ... , M}.   The statementf3n   = m  means that object   On   is an instantiation of the template  'Pm.   The correspondences   (3   are   unknown   in the hierarchi cal learning problem, which is a key complicating factor in our attempt to learn hierarchical object models. There is an important distinction between the correspon dence variables a's and (J's, arising from the fact that each object   Bn   can only be observed once when acquiring a local map   J.Lt.   This induces a   mutual exclusivity constraint   on the set of valid correspondences at the object level: If   k   =J   k ' , then   at(k)   =J   a1(k').   Thus, we see that the physical ob jects, modeled in the object level, can only be observed at most once in any given map, whereas the class level object templates might be instantiated more than once. For ex ample, an object at the class level might be a prototypical chair, which might be mapped to multiple concrete chairs at the object level-and usually multiple observations over time of any of those concrete chairs at the snapshot level.  3   Hierarchical EM  Our goal in this paper is to learn the model   iii =   (0,   <p,   o)  given the data   f.L   using EM [5).   Unlike many EM im plementations, however, we do not simply want to maxi mize the probability of the data given the model. We also want to take into consideration the probabilistic relation ships between the two levels of the hierarchy.   Thus, we want to maximize the joint probability over the data   f.L   and the model   iii:  argmaxp(ili,J.L)   =   a r g m a x   p(B, <p,  o, J.L) (4)  w   9,<p,!J  Note that we treat the latent alignment parameters   /j   as model parameters, which we maximize during learning. EM is an iterative procedure that can be used to max imize a   likelihood   function.   Starting   with   some   ini tial model, EM generates a sequence of models of non decreasing likelihood: (5) Let   i[t[i]   =   (Biil,<plil,olil)   be the i-th such model. Our de sire is to find an (i   +   1)st model   i[t[i+l]   for which  (6)  As is common in the EM literature [14],   this goal is achieved by maximizing the expected log likelihood Here   Ea,/3   is the mathematical expectation over the latent correspondence variables   a   and   (3,   relative to the distribu tionp(a,/31   i[t(il,J.L).  The probability inside the logarithm in   (7)   factors into two terms, one for each level of the hierarchy (multiplied by a constant): p(a,/3,   ili,J.L)   =   p(a,(J,<p,B,o,J.L)   (8)  Exploiting the independencies shown in Figure   I   b, and the uniform priors over   ¢,   a, and   f3,   we obtain:  =   p(<p) p(/3) p(OI   (3,   'P) p(a) p(o) p(J.LI o,a, 0) oc   p( B I   (3,   <p)   p(J.LI o,a,B)   (9) The probability logp(B   I   (3,   <p) of the objects() given the object templates <p and the correspondences   (3   is essen tially defined via (3). Here we recast it using a notation that makes the conditioning on   (3   explicit:  p(B   I (3,   <p)   (10) N  II   -=21   L;M   1   I(/3n=m)   I;   (9n[j]-'P=[j])' �   e   u   m=   J  n=l  where   I ( )   is an indicator function which is I if its argu ment is true, and 0 otherwise. Similarly, the probability p(J.LI   a,B,o)   is based on (I) and conveniently written as: p(J.L I a, o,   &)   oc   (II)  T   Kt  II II   -:;-::2"1   L;N   1   I(at(k)=n)   I;   .(f(l'k,t.O.,t)[j]-9n[j])2 e   p   n=:   ' t=1   k=1
UAI2002   ANGUELOV ET AL.   13  Substituting the product   (9)   with   (10)   and   (II)   into the ex pected log likelihood   (7)   gives us:  q,li+!J   =   argmax  <p,B,c  -t, {t  p(/3n= :�   q,lil,JL)   � (l:ln[j]- 'Pm[j])2   (J2)  +   t,�  p(a,(k)= p�   I   q,lil,JL)   � (f(JLk,tAt)[j]- l:ln[j])2   }  In deriving this   expression,   we exploit the   linearity   of the expectation,   which allows us to replace the indicator variables through probabilities (expectations).   It is easy to see that the expected Jog-likelihood in   (12)   consists of two main terms.   The first enforces consistency between the template and the object level, and the second between the object and the data level.  4   The Implementation of the EM Algorithm  The standard implementation of EM requires the M-step to find the parameter assignment   (w[i+l])   which maximizes  (12).   A variation of EM called   Generalized EM   [5]   re quires only that the M-step finds an assignment for   (iii   [HI])  which   increases,   but does not necessarily maximize, the ex pected log-likelihood in   (7).   Generalized EM has the con vergence guarantees of EM, while possibly taking more it erations to converge. In our case, it allows us to avoid solv ing a complex joint optimization problem for the model pa rameters in the M-step. Our Generalized EM starts with a random model and ran dom alignment parameters. It then alternates an E-step, in which the expectations of the correspondences are calcu lated given the i-th model and alignment, and two M-steps, one that generates a new hierarchical model   (II   [HI], <p[i+1l)  and one for finding new alignment parameters   o [i+l].   Each of the two M-steps does not decrease the expected log likelihood.   If at least one of them increases it, we have a guarantee of improving the original likelihood in   (4 ).   If both result in   no change in the expected log-likelihood, then our algorithm has converged.   As our objective func tion is not convex (because of the non-linear projection   f),  it is possible in principle that our implementation of Gen eralized EM converges to a ridge point, where optimizing only for   (ll[i+IJ,<p[i+1l)   or for   o[i+IJ   does not increase the log-likelihood, while jointly optimizing all the above pa rameters does. Nevertheless, our experiments show that the algorithm converges rapidly to a good result.  4.1   E-Step  In our case, the E-step can easily be implemented exactly:  b[i] n,m  =  p(f3n=m Ill[i], 'P[i]) p(ll[i]   I   f3n=m,<p[i]) p(f3n=m l,<p[i])  (13)  and, similarly,  a1'1   = p(a,(k) =   n   I   JL1'1,e1'1,ok,t) k,t,n   (14)  L:.,   I(a,(k)=n)   e  -�   L:; L:.,(f(p�},,IJJ,c.,,,)-B��(k'JliD'  " e  -�   L:i L:,.,U(J.t�J.t[j],o,.,,t)-B�!<r.'>[j])2  L-a,  The summation over   a   k   in calculating the expectations  a � ] t   n   is necessary because of the mutual exclusion con straint described above, namely that no object can be seen twice in the same map.   The summation is exponential in the number of observed objects K t-however, Kt is rarely larger than   10.   If s umm ing over Gt (because of its expo nential domain) becomes too costly, efficient (and provably polynomial) sampling schemes can be applied for approxi mating the desired expectations   [4, 16].  4.2   Model M-Step  Our M-step first generates a new hierarchical model   II,   <p   by maximizing   (12)   under fixed expectations   b�!m   and   a � ! t , n  and fixed alignment parameters   o.   It   is an appealing prop erty of our model that this part of the M-step can be exe cuted efficiently in closed form. Our first observation is that the expression in   (12)   de composes into a set of decoupled optimization problems over individual pixels, that can be optimized for each pixel  j   individually:  (11�+1 l   [j],  <p � +1l [j])   =   argmin  e.[iJcp�[iJ  N   M   [i]  L L bn�m (lln[j] - 'Pm[j])2   (15)  n=lm=l   a  N   T   K,   a[i] +  :L: :L: :L:   k  , � , n   U(J.Lk,t,   at!tl[jJ- 11n[iD2  n=l t=l  k=l   p  We then observe that ( 15)   is a quadratic optimization prob lem, which therefore possesses a convenient closed-form solution   [18].   In particular, we can reformulate   (15)   as a standard least-squares optimization problem: argmin   (A·   x[j] - w[j])2  x[j]  (16)  where   x[j]   =   (ll[j], <p[j])   is a vector comprising the j-th cell value of all models at both levels. The constraint matrix  A   has the form  A   =   (   -IE   ·II   -IE   ·   ) a   n,m·   -   cr   n,m·IP  P-I  Ak,t,n   0   ( 17 )
14   ANGUELOV ET AL.   UAI2002  Figure 2: (a) The Pioneer robot used to collect laser range data.   (b) The robotics lab where the second data set was collected. (c) Actual images of dynamic objects used in the second data set. where Bn,m:B, Bn,m:'P and   Ak,t,n   are submatrices gener ated from the expectations calculated in the E-step. Gener ating such matrices from a quadratic optimization problem such as (15) is straightforward, and the details are omitted here due to space limitations. The vector   w[j]   is of the form  w[j]   (18) where J.l1  [j]   is a vector constructed from the aligned j-th map cell values of the snapshots J.l. The solution to (15) is  x[j]   (19) Thus, the new model   ()�+I], <pi:,+Il   is the result of a se quence of simple matrix operations, one for each pixel   j.  4.3   Alignment M-Step  A final step of our M-step involves the optimization of the alignment parameters   8.   Those are obtained by maximizing the relevant parts of the expected log likelihood (12).   Of significance is the fact that the alignment variables depend only on the object level(), and not on the template level   <p.  This leads to a powerful decomposition by which each   8 k,t  can be calculated separately, by minimizing:  8� -;-I ]   =   argmin '   O:k,t N  L e�!t,n LU(J.tk,t, 8k,t)[j]-   ()�+!]  [j])2  n=l   j  (20) We represent the   8   for each snapshot as a discrete set of possible transformation values and pick the value of   8  which minimizes the above term. We can use gradient de scent to additionally refine the estimate.  4.4   Improving Global Convergence  Our approach inherits from EM the property that it is a hill climbing algorithm, subject to local maxima.   In our ex periments, we found that a straightforward implementation Figure   3:   (a) Four maps from the   Study Room   dataset. Each map contains the same set of non-stationary objects.   (b) Overlay of optimally aligned maps. (c) A particular differ ence map   before   low-pass filtering. of EM frequently led to suboptimal maps.   Our algorithm therefore employs   deterministic annealing   [17] to smooth the likelihood function and improve convergence.   In   our case, we anneal by varying the noise variance   a   and   p   in the sensor noise model.   Larger variances induce a smoother likelihood function, but ultimately result in fuzzier shape models. Smaller variances lead to crisper maps, but at the expense of an increased number of sub-optimal local max ima.   Consequently, our approach anneals the covariance slowly towards the desired values of   a   and   p,   using large values for   a0   and   p0   that are gradually annealed down with an annealing factor   1   <   1 : ali]   a+ 1iao pliJ   =   p + liPo  (21) (22) The values   ali]   and   plil   are used in the i-th iteration of EM.  4.5   Determining the Number of Objects  A final and important component of our mapping algorithm determines the number of class templates   M   and the num ber of objects   N.   So far, we have silently assumed that both  M   and   N   are given.   In   practice, both values are unknown and have to be estimated from the data. The number of objects is bounded below by the number of objects seen in each individual map, and above by the
UAI2002   ANGUELOV ET AL.   15  ,, ��  ·1.-   .   ,.,._  .s�   ·. :¥   l. '�   .   � I   ...  •  oJ:<••   ,_.::,   I'!   f... """   '·   '  .   '!' ·'·r...,.  r��? '�   ..   \. �-:   •  '¥-f . .....   •'  •  \,,.�;:,   r )'�!' _,   •   ' ;  t:r  l.  . .  , ..,  !>:� ";..,. .J:   ·-�   l.. .   �.   .   .  •  -J  ..   . ,. "'c:r   r, ,...  . ....   .   .   .   ' ..   ·r \•  �'�·   If.'   r   r ..  ,.   .. .   . r;_..,'   '  Figure 4: Nine maps from the   Robotics Lab   dataset. The number of objects present varies. sum of all objects ever seen: The number of class templates   M   is upper-bounded by the number of objects   N.  Our approach applies a Bayesian prior for selecting the right   N   and   M,   effectively transforming the learning prob lem into a   maximum a posteriori (MAP)   estimation prob lem. At both levels, we use an exponential prior, which in log-form penalizes the log-likelihood in proportion to the number of objects   N   and object templates   M:  Ea,iJ[logp(J.L,   a,   ,8 I 0, <p) I   J.L,   () , 'P]   -   ce N- c'PM   (24) with appropriate constant penalties   ce   and   c'P.   Hence, our approach applies EM for plausible values of   N   and   M.   It finally selects those values for   N   and   M   that maximize (24), through a separate EM optimization for each value of  N   and   M.   At first glance this exhaustive search procedure might appear computationally wasteful, but in practice   N  is usually small (and   M   is even smaller), so that the optimal values can be found quickly.  5   Experimental Results  Our algorithm was evaluated extensively using data col lected by a Pioneer robot equipped with a laser range finder. As in [2], maps were acquired in two different office en vironments:   the   Study Room   and the   Robotics Lab.   Fig ure 2 shows the robot, and some of the non-stationary ob jects encountered by the robot. Figures 3a and 4 show four and nine example maps extracted in these environments, re spectively. Each static map of the   Study Room   always con tained the same objects, while in the maps of the   Robotics Lab   all the objects were not necessarily present. The maps were generated by the concurrent mapping and localization algorithm described in [20].   The individual object snapshots were extracted from regular occupancy grid maps using   map differencing,   a technique closely re lated to image differencing, which is commonly used in the field of computer vision.   In   particular, our approach identifies occupied grid cells which, at other points in time, were free. Such cells are candidates of snapshots of mov ing objects.   A subsequent low-pass filter removes arti facts that occur along the boundary of occupied and free space.   Finally, a flood-filling technique identifies distinct object snapshots [22].   Empirically, our approach found all non-stationary objects with high reliability as long as they are spaced apart by at least one grid cell (5 em). Fig ure 3b shows a typical overlay of the individual maps, and Figure 3c provides examples of object snapshots extracted from those maps. Clearly, more sophisticated methods are needed if objects can touch each other. In a first series of experiments, we trained our hierar chical model from data collected in the two robot environ ments. Figure Sa shows an example run of EM for the   Study Room   environment, using the correct number of   N   = 4   ob jects and   M   =   3   shape templates.   As is easily seen, the final object models are highly accurate--in fact, they are more accurate than the individual object snapshots used for their construction. In a series of 20 experiments using dif ferent starting points, we found that the hierarchical model converges in all cases to a model of equal quality, whose result is visually indistinguishable from the one presented here.   We also tested the ability of our algorithm to cor rectly associate object snapshots with their object models, and object models with their templates. Figure 5b shows a graph of the probabilities for   a   and ,8 correspondence vari ables, over iterations of the EM algorithm. As we can see, the model rapidly converges to a definite correspondence, which is the right one. These results are typical for other correspondences. We   then   compared   our   approach   with   the   non hierarchical technique described in [2].   The purpose of these experiments was to quantifY the relative advantage of our hierarchical object model over a shallow model that does not allow for cross-object transfer. We noticed several deficiencies of the non-hierarchical model.   The resulting object models were systematically inferior to those gener ated using our hierarchical approach. Figure 5c shows two examples of results, obtained with different initial random seeds.   While the first of these results looks visually ade quate, the second does not- it contains an incorrect col lection of objects (three circles, one box).   Unfortunately, in   II   out of 20 runs, the flat approach converged to such a suboptimal solution. Moreover, even the visually accurate non-hierarchical models   turn   out to be inferior. Figure 7 plots log-likelihood
16   ANGUELOV ET AL.   UA12002  (i) Hierarchical learning, template models  �•t<omphote   r<Jt.oottemplato   &Oiato•<vl"t.o  -·   -   '"«<ei   {i) Assoctahon Probabilities for a Robot   2   Sna   p shot  •   •   • •   •   • •   •   • •   •   • •   •   I  •   •   a  •   •  0.9 0.8 0.7 0.6  l   05 ..   0.4 0:: 0.3 0.2 0.1 0 1  (i) Flat learning, good result  •   •   •   • •   •   •   • II   •   •   �  I   •   •   � a   Iteration of EM Algorithm  I   •   •   ' I   •   •   '-  1   •   •   ,..  (ii) Association Probabilities for Robot   2   Model  (ii) Hierarchical leaming, object models  ' ""' .:.:""'   ""::: "" --·  "":.Z" •   •   •   • •   •   •   I  •   •   •   I  •   •   •   a  •   •   •   I  0.8 0   0.6  £ Q..   0.4 0.2 Box   Template Model   -----=---··  Robot Template Model   ::�···   (ii) Flat learning, poor local maximum  •   •   •   •  .   .   �   .  .   .   '   . .   .   �   .  •   •   • •   •   •  a II  ,;� o1L--�--�--�--�--�--�  .   .   �   . .   .   �   . .   .   �   . Iteration of EM Algorithm  Figure 5: Convergence over seven iterations of EM: (a) Results of the hierarchical learning: (i) templates models, and (ii) object models. (b) Correspondence probabilities (i) between a robot snapshot and different object models (ii) between a robot object model and different template models. (c) Results of the flat model: (i) successful convergence, (ii) unsuccessful convergence to a poor model; 11 out of 20   runs   converged poorly. results on training and testing data for each environment. We perform leave-one-out cross-validation, where we train  T   different models by leaving one of the   T   maps in the dataset out. For each model we compute the log-likelihood of both the   training   and test data and plot these log likelihood values averaged over the   T   models. Even in the case when the non-hierarchical approach produces visually adequate results, their actual accuracy lags significantly be hind that of the models generated by our hierarchical algo rithm. We attribute this difference to the fact that the non hierarchical approach lacks cross-object generalization. Finally, we evaluated our approach to model selection, estimating how well our approach can determine both the right number of objects and class templates.   Throughout all of our experiments we used the penalty term   35N + 15M.   For both data sets, we found that the log posterior shows a clear peak at the correct values. The results for the  Robotics Lab   are shown in Figure 6, with the correct values shown in bold face. Note that the algorithm converged to the correct value of   N   =   4,   although none of the training maps possessed all the   4   objects.   The number had to be estimated exclusively based on the fact that, over time, the robot faced 4 different objects with 3 different shapes. In s umm ary, our experiments indicate that our algorithm learns highly accurate shape models at both levels of the hierarchy, and it consistently identifies the 'right' number of objects and object templates.   In comparison with the flat approach described in [2], it yields significantly more accurate object models and also converges more frequently  M -1 M=2 M=3 M=4 M=5 M=6 M=7 N=3 -636.2 -603.2 -612.5 N=4 -603.1 -551.5 -535.7 -550.7 N=5   N=6 -635.5   -663.9 -568.7   -580.7 -567.5   -586.9 -587.4   -567.6 -595.0   -585.4 -621.3 N=7 702.4 -615.2 -623.2 -618.5 -599.2 -643.1 -608.9  Figure 6: Model selection results for the Robotics Lab to an accurate solution.  6   Conclusion  We have presented an algorithm for learning a hierarchy of object models of non-stationary objects with mobile robots.   Our approach is based on a generative model which assumes that objects are instantiations of object tem plates, and are observed by mobile robots when acquir ing maps of its environments.   An   approximate EM algo rithm was developed, capable of learning models of ob jects and object templates from snapshots of non-stationary objects, extracted from occupancy grid maps acquired at different points in time.   Systematic experiments using a physical robot illustrate that our approach works well in practice, and that it outperforms a previously developed non-hierarchical algorithm for learning models of non stationary objects. Our approach possesses several limitations that warrant
UAI2002   ANGUELOV ET AL.   17  /I----1----I----I i ....,  I /   <  /   �  ,   :;   - 500 ltvation EM '   .  I/   3  ,...... " Iteration EM   Iteration EM   Iteration EM  Figure   7:   Log-likelihood of the training and testing (leave-one-out) data from both real-world data sets. The dashed line is the result of the shallow, non-hierarchical approach, which performs significantly worse than the hierarchical approach (solid line). future research. For identifying non-stationary objects, our present segmentation approach mandates that objects do not move during robotic mapping, and that they are spaced far enough apart from each other (e.g.,   5   em). Beyond that, our approach currently does not learn attributes of objects other than shape, such   as   persistence, relations between multiple objects, and non-rigid object structures.   Finally, exploring different generative models involving more com plex transformations (e.g., scaling of templates) constitutes another worthwhile research direction. Nevertheless,   we   believe   that   this   work   is   unique   in its   ability   to learn hierarchical   object models   in mobile robotics.   We   believe   that   the   framework   of   hierarchi cal   models   can   be   applied   to   a broader   range   of   map ping   problems   in   robotics,   and   we   conjecture   that   cap turing the object nature of robot environments will ulti mately lead to much superior perception algorithms in mo bile robotics,   along with more appropriate symbolic de scriptions of physical environments.  Acknowledgements.  The   work   of   Dragomir   Anguelov   and   Daphne   Koller   was supported   the Office   of Naval Research,   Young   Investigator (PECASE) grant N00014-99-l-0464.   Sebastian Thrun's work was s1.1pported by DARPA's MARS Program (Contract number N66001-0l-C-6018) and the National Science Foundation (CA REER grant number IIS-9876136 and regular grant number IIS- 9877033). This work was done while Sebastian Thrun was visit ing Stanford University.  References  [I]   J. Berger.   Statistical Decision Theory and Bayesian analy sis.   Springer Verlag, 1985. [2]   R. Biswas, B. Limketkai, S. Sanner, and S. Thrun.   To wards object mapping in dynamic environments with mo bile robots. In   Proc. IROS,   2002. [3]   J.A. Castellanos, J.M.M. Montiel, J. Neira, and J.D. Tardos. The SPmap:   A   probabilistic framework for   simultane ous localization and map building.   IEEE Transactions on Robotics and Automation,   15(5):948-953, 1999. [4]   F.   Dellaert, S. Seitz, S. Thrun, and C. Thorpe. Feature cor respondence: A Markov Chain Monte Carlo approach.   In T.K. Leen, T. Dietterich, and B. Van Roy, editors,   Proc. NIPS   13.   MIT Press, 200I. [5]   A. Dempster, N. Laird, and D. Rubin.   Maximum Likeli hood from incomplete data via the EM algorithm   Journal of the Royal Statistical Society B,   vol.39, pp.l -38, 1977. [6]   A. Elfes. Sonar-based real-world mapping and navigation.  IEEE Journal of Robotics and Automation,   RA-3(3):249- 265, June 1987. [7]   B.J. Frey and N. Jojic. Transform-Invariant Clustering and Dimensionality Reduction using EM   In IEEE Transactions on Pattern Analysis and Machine Intelligence,   Nov. 2000 [8]   A.   Gelman,   J.B.   Carlin,   H.S.   Stern,   and D.B.   Rubin.  Bayesian Data Analysis.   Chapman and Hall, 1995. [9]   J.J. Leonard and H.J.S. Feder. A computationally efficient method for large-scale concurrent mapping and localiza tion.   In   J.   Hollerbach and D. Koditschek, editors,   Proc. ISRR,   1999. [10]   M. Leventon, E. Grimson,   and   0.   Faugeras.   Statistical Shape Influence in Geodesic Active Contours   Proc. CVPR,  2000. [II]   F. Lu   and   E.   Milios.   Globally   consistent   range   scan alignment for environment mapping.   Autonomous Robots,  4:333-349, 1997. [12]   C. Martin and S. Thrun.   Real-time acquisition of compact volumetric maps with mobile robots. In   Proc. ICRA,   2002. [13]   A. McCallum, R. Rosenfeld, T. Mitchell, and A.Y. Ng. Im proving text classification by shrinkage in a hierarchy of classes. In   Proc. ICML,   1998. [14]   G.J. McLachlan and   T.   Krishnan.   The EM Algorithm and Extensions.   Wiley Series in Probability and Statistics, New York, 1997. [15]   H. P. Moravec. Sensor fusion in certainty grids for mobile robots.   AI Magazine,   9(2):61-74, 1988. [16]   H. Pasula, S. Russell, M. Ostland, and   Y.   Ritov. Tracking many objects with many sensors. In   Proc. IJCAI,   1999. [17]   K. Rose.   Deterministic annealing for   clustering,   com pression, classification, regression, and related optimization problems.   Proceedings of IEEE,   D, November 1998. [18]   G Strang.   Introduction   to Linear   Algebra.   Wellesley Cambridge P ress, 1998. [19]   C. Thorpe and H. Durrant-Whyte.   Field robots.   In   Proc. ISRR,   2001. [20]   S. Thrun.   A probabilistic online mapping algorithm for teams of mobile robots.   International Journal of Robotics Research,   20(5):335-363, 2001. [21]   S. Williams, G. Dissanayake, and H.F. Durrant-Whyte. To wards terrain-aided navigation for underwater robotics.   Ad vanced Robotics,   15(5), 2001. [22]   S.W. Zucker. Region growing: Childhood and adolescence.  Comput. Graphics Image Processing,   5:382-399, 1976.