[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content

Advertisement

Springer Nature Link
Log in

Monte Carlo planning for active object classification

  • Published:
Autonomous Robots Aims and scope Submit manuscript

Abstract

Classifying objects in complex unknown environments is a challenging problem in robotics and is fundamental in many applications. Modern sensors and sophisticated perception algorithms extract rich 3D textured information, but are limited to the data that are collected from a given location or path. We are interested in closing the loop around perception and planning, in particular to plan paths for better perceptual data, and focus on the problem of planning scanning sequences to improve object classification from range data. We formulate a novel time-constrained active classification problem and propose solution algorithms that employ a variation of Monte Carlo tree search to plan non-myopically. Our algorithms use a particle filter combined with Gaussian process regression to estimate joint distributions of object class and pose. This estimator is used in planning to generate a probabilistic belief about the state of objects in a scene, and also to generate beliefs for predicted sensor observations from future viewpoints. These predictions consider occlusions arising from predicted object positions and shapes. We evaluate our algorithms in simulation, in comparison to passive and greedy strategies. We also describe similar experiments where the algorithms are implemented online, using a mobile ground robot in a farm environment. Results indicate that our non-myopic approach outperforms both passive and myopic strategies, and clearly show the benefit of active perception for outdoor object classification.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16
Fig. 17
Fig. 18
Fig. 19

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

Notes

  1. t-Tests with respect to balanced MCAP.

References

  • Aloimonos, J., Weiss, I., & Bandopadhay, A. (1988). Active vision. International Journal of Computer Vision, 1(4), 333–356.

    Article  Google Scholar 

  • Andrieu, C., Doucet, A., & Holenstein, R. (2010). Particle Markov chain Monte Carlo methods. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 72(3), 269–342.

    Article  MathSciNet  MATH  Google Scholar 

  • Atanasov, N., Sankaran, B., Le Ny, J., Pappas, G., & Daniilidis, K. (2014). Nonmyopic view planning for active object classification and pose estimation. IEEE Transactions on Robotics, 30(5), 1078–1090.

    Article  Google Scholar 

  • Auer, P., Cesa-Bianchi, N., & Fischer, P. (2002). Finite-time analysis of the multiarmed bandit problem. Machine Learning, 47(2–3), 235–256.

    Article  MATH  Google Scholar 

  • Bac, C. W., Henten, E. J., Hemming, J., & Edan, Y. (2014). Harvesting robots for high-value crops: State-of-the-art review and challenges ahead. Journal of Field Robotics, 31(6), 888–911.

    Article  Google Scholar 

  • Bajcsy, R. (1988). Active perception. Proceedings of the IEEE, 76(8), 966–1005.

    Article  Google Scholar 

  • Bargoti, S., Underwood, J. P., Nieto, J. I., & Sukkarieh, S. (2015). A pipeline for trunk detection in trellis structured apple orchards. Journal of Field Robotics, 32(8), 1075–1094.

    Article  Google Scholar 

  • Becerra, I., Valentín-Coronado, L. M., Murrieta-Cid, R., & Latombe, J. C. (2016). Reliable confirmation of an object identity by a mobile robot: a mixed appearance/localization-driven motion approach. International Journal of Robotics Research, 35(10), 1207–1233.

    Article  Google Scholar 

  • Binney, J., Krause, A., & Sukhatme, G. (2013). Optimizing waypoints for monitoring spatiotemporal phenomena. International Journal of Robotics Research, 32(8), 873–888.

    Article  Google Scholar 

  • Blaer, P. S., & Allen, P. K. (2007). Data acquisition and view planning for 3-D modeling tasks. In: Proceedings of IEEE/RSJ IROS (pp. 417–422)

  • Bourgault, F., Makarenko, A., Williams, S., Grocholsky, B., & Durrant-Whyte, H. (2002). Information based adaptive robotic exploration. In Proceedings of IEEE/RSJ IROS (pp. 540–545).

  • Brier, G. W. (1950). Verification of forecasts expressed in terms of probability. Monthly Weather Review, 78(1), 1–3.

    Article  Google Scholar 

  • Browne, C. B., Powley, E., Whitehouse, D., Lucas, S. M., Cowling, P. I., Rohlfshagen, P., et al. (2012). A survey of Monte Carlo tree search methods. IEEE Transactions on Computational Intelligence and AI in Games, 4(1), 1–43.

    Article  Google Scholar 

  • Chen, S., Li, Y., & Kwok, N. (2011). Active vision in robotic systems: A survey of recent developments. International Journal of Robotics Research, 30(11), 1343–1377.

    Article  Google Scholar 

  • Cliff, O., Fitch, R., Sukkarieh, S., Saunders, D., & Heinsohn, R. (2015). Online localization of radio-tagged wildlife with an autonomous aerial robot system. In Proceedings of RSS.

  • Collet, A., Xiong, B., Gurau, C., Hebert, M., & Srinivasa, S. (2015). Herbdisc: Towards lifelong robotic object discovery. International Journal of Robotics Research, 34(1), 3–25.

    Article  Google Scholar 

  • Denzler, J., & Brown, C. (2002). Information theoretic sensor data selection for active object recognition and state estimation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 24(2), 145–157.

    Article  Google Scholar 

  • Doucet, A., Smith, A., de Freitas, N., & Gordon, N. (2001). Sequential Monte Carlo methods in practice. Information science and statistics. Berlin: Springer.

    Book  Google Scholar 

  • Douillard, B., Underwood, J., Vlaskine, V., Quadros, A., & Singh, S. (2014). A pipeline for the segmentation and classification of 3D point clouds. In Experimental robotics (Vol. 79, pp. 585–600). Springer, STAR.

  • Eidenberger, R., & Scharinger, J. (2010). Active perception and scene modeling by planning with probabilistic 6D object poses. In Proceedings of IEEE/RSJ IROS (pp. 1036–1043).

  • Faulhammer, T., Aldoma, A., Zillich, M., & Vincze, M. (2015). Temporal integration of feature correspondences for enhanced recognition in cluttered and dynamic environments. In Proceedings of IEEE ICRA (pp. 3003–3009).

  • Fentanes, J.P., Zalama, E., & Gómez-García-Bermejo, J. (2011). Algorithm for efficient 3D reconstruction of outdoor environments using mobile robots. In Proceedings of IEEE ICRA (pp. 3275–3280).

  • Fischler, M. A., & Bolles, R. C. (1981). Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography. Communications of the ACM, 24(6), 381–395.

    Article  MathSciNet  Google Scholar 

  • Gan, S., Fitch, R., & Sukkarieh, S. (2014). Online decentralized information gathering with spatial-temporal constraints. Autonomous Robots, 37(1), 1–25.

    Article  Google Scholar 

  • Gschwandtner, M., Kwitt, R., Uhl, A., & Pree, W. (2011). BlenSor: Blender sensor simulation toolbox. In Advances in visual computing (Vol. 6939, pp. 199–208), . Springer.

  • Guestrin, C., Krause, A., & Singh, A. (2005). Near-optimal sensor placements in Gaussian processes. In Proceedings of ICML (pp. 265–272).

  • Hollinger, G., Englot, B., Hover, F., Mitra, U., & Sukhatme, G. (2013). Active planning for underwater inspection and the benefit of adaptivity. International Journal of Robotics Research, 32(1), 3–18.

    Article  Google Scholar 

  • Huber, M., Dencker, T., Roschani, M., & Beyerer, J. (2012). Bayesian active object recognition via Gaussian process regression. In Proceedings of fusion (pp. 1718–1725).

  • Hung, C. C., Nieto, J., Taylor, Z., Underwood, J., & Sukkarieh, S. (2013). Orchard fruit segmentation using multi-spectral feature learning. In Proceedings of IEEE/RSJ IROS (pp. 5314–5320).

  • Johnson, A. E. (1997). Spin-images: A representation for 3-D surface matching. Ph.D. thesis, Carnegie Mellon University.

  • Jolliffe, I. (2002). Principal component analysis. Wiley StatsRef: Statistics Reference Online.

  • Karasev, V., Chiuso, A., & Soatto, S. (2012). Controlled recognition bounds for visual learning and exploration. In Advances in neural information processing systems 25 (pp. 2915–2923). Curran Associates, Inc..

  • Kocsis, L., & Szepesvári, C. (2006). Bandit based Monte-Carlo planning. In Proceedings of ECML (pp. 282–293). Springer.

  • Krause, A., Singh, A., & Guestrin, C. (2008). Near-optimal sensor placements in Gaussian processes: Theory, efficient algorithms and empirical studies. Journal of Machine Learning Research, 9, 235–284.

    MATH  Google Scholar 

  • Lauri, M. (2016). Sequential decision making under uncertainty for sensor management in mobile robotics. PhD thesis, Tampere University of Technology.

  • Lauri, M., & Ritala, R. (2014). Stochastic control for maximizing mutual information in active sensing. In Proceedings of IEEE ICRA, workshop on robots in homes and industry: Where to look first?

  • Lauri, M., Atanasov, N., Pappas, G. J., & Ritala, R. (2015). Active object recognition via Monte Carlo tree search. In Proceedings of IEEE ICRA, workshop on beyond geometric constraints.

  • Lindsten, F., & Schön, T. B. (2013). Backward simulation methods for Monte Carlo statistical inference. Foundations and Trends in Machine Learning, 6(1), 1–143.

    Article  MATH  Google Scholar 

  • Meger, D., Gupta, A., & Little, J. (2010). Viewpoint detection models for sequential embodied object category recognition. In Proceedings of IEEE ICRA (pp. 5055–5061).

  • Nemhauser, G., Wolsey, L., & Fisher, M. (1978). An analysis of approximations for maximizing submodular set functions—I. Mathematical Programming, 14(1), 265–294.

    Article  MathSciNet  MATH  Google Scholar 

  • Nguyen, J. L., Lawrance, N. R. J., Fitch, R., & Sukkarieh, S. (2016). Real-time path planning for long-term information gathering with an aerial glider. Autonomous Robots, 40(6), 1017–1039.

    Article  Google Scholar 

  • Patten, T., Kassir, A., Martens, W., Douillard, B., Fitch, R., & Sukkarieh, S. (2015). A Bayesian approach for time-constrained 3D outdoor object recognition. In Proceedings of IEEE ICRA, workshop on scaling up active perception.

  • Patten, T., Zillich, M., Fitch, R., Vincze, M., & Sukkarieh, S. (2016). Viewpoint evaluation for online 3-D active object classification. IEEE Robotics and Automation Letters, 1(1), 73–81.

    Article  Google Scholar 

  • Paul, R., Triebel, R., Rus, D., & Newman, P. (2012). Semantic categorization of outdoor scenes with uncertainty estimates using multi-class Gaussian process classification. In Proceedings of IEEE/RSJ IROS (pp. 2404–2410).

  • Pineda, L., Takahashi, T., Jung, H. T., Zilberstein, S., & Grupen, R. (2015). Continual planning for search and rescue robots. In Proceedings of IEEE RAS humanoids (pp. 243–248).

  • Potthast, C., Breitenmosero, A., Sha, F., & Sukhatme, G. (2015). Active multi-view object recognition and online feature selection. In Proceedings of ISRR.

  • Quigley, M., Conley, K., Gerkey, B. P., Faust, J., Foote, T., Leibs, J., Wheeler, R., & Ng, A. Y. (2009). ROS: an open-source robot operating system. In Proceedings of IEEE ICRA, workshop on open source software.

  • Rasmussen, C. E., & Williams, C. K. I. (2006). Gaussian processes for machine learning. Cambridge, MA: MIT Press.

    MATH  Google Scholar 

  • Rosell, J., & Sanz, R. (2012). A review of methods and applications of the geometric characterization of tree crops in agricultural activities. Computers and Electronics in Agriculture, 81, 124–141.

    Article  Google Scholar 

  • Rusu, R., & Cousins, S. (2011). 3D is here: Point Cloud Library (PCL). In Proceedings of IEEE ICRA (pp. 1–4).

  • Rusu, R. B., Bradski, G., Thibaux, R., Hsu, J. (2010). Fast 3D recognition and pose using the viewpoint feature histogram. In Proceedings of IEEE/RSJ IROS (pp. 2155–2162).

  • Silver, D., & Veness, J. (2010). Monte-Carlo planning in large POMDPs. In Advances in neural information processing systems 23 (pp. 2164–2172). Curran Associates, Inc.

  • Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., van den Driessche, G., et al. (2016). Mastering the game of Go with deep neural networks and tree search. Nature, 529(7587), 484–489.

    Article  Google Scholar 

  • Sutton, R. S., & Barto, A. G. (1998). Introduction to reinforcement learning (1st ed.). Cambridge, MA: MIT Press.

    Google Scholar 

  • Tang, J., Miller, S., Singh, A., & Abbeel, P. (2012). A textured object recognition pipeline for color and depth image data. In Proceedings of IEEE ICRA (pp. 3467–3474).

  • Underwood, J. P., Hill, A., Peynot, T., & Scheding, S. J. (2010). Error modeling and calibration of exteroceptive sensors for accurate mapping applications. Journal of Field Robotics, 27(1), 2–20.

    Article  Google Scholar 

  • Underwood, J. P., Calleija, M., Taylor, Z., Hung, C., Nieto, J., Fitch, R., & Sukkarieh, S. (2015). Real-time target detection and steerable spray for vegetable crops. In Proceedings of IEEE ICRA, workshop on robotics in agriculture.

  • Vander Hook, J., Tokekar, P., & Isler, V. (2015). Algorithms for cooperative active localization of static targets with mobile bearing sensors under communication constraints. IEEE Transactions on Robotics, 31(4), 864–876.

    Article  Google Scholar 

  • Vélez, J., Hemann, G., Huang, A. S., Posner, I., & Roy, N. (2012). Modelling observation correlations for active exploration and robust object detection. Journal of Artificial Intelligence Research, 44, 423–453.

    MATH  Google Scholar 

  • Wong, L. L. S., Kaelbling, L. P., & Lozano-Prez, T. (2015). Data association for semantic world modeling from partial views. International Journal of Robotics Research, 34(7), 1064–1082.

    Article  Google Scholar 

  • Wu, K., Ranasinghe, R., & Dissanayake, G. (2015). Active recognition and pose estimation of household objects in clutter. In Proceedings of IEEE ICRA (pp. 4230–4237).

  • Xie, Z., Singh, A., Uang, J., Narayan, K. S., & Abbeel, P. (2013). Multimodal blending for high-accuracy instance recognition. In Proceedings of IEEE/RSJ IROS (pp. 2214–2221).

  • Xu, Z., Fitch, R., Underwood, J., & Sukkarieh, S. (2013). Decentralized coordinated tracking with mixed discrete-continuous decisions. Journal of Field Robotics, 30(5), 717–740.

    Article  Google Scholar 

  • Zhong, Y. (2009). Intrinsic shape signatures: A shape descriptor for 3D object recognition. In Proceedings of ICCV workshops (pp. 689–696).

Download references

Acknowledgements

This research is supported in part by the Australian Centre for Field Robotics, the New South Wales State Government, the Australian Research Council’s Discovery Projects funding scheme (Project Number DP140104203), and the Faculty of Engineering and Information Technologies at The University of Sydney under the Faculty Research Cluster Program. We thank Joel Veness, Oliver Cliff, and Graeme Best for helpful discussions. Thanks to Andrew Bate, Jocie Bate, Lasitha Piyathilaka, and Grant Louat at SwarmFarm Robotics for use of the robot and assistance with the hardware experiments. Thanks also to James Underwood and Alen Alempijevic for assistance with sensor calibration.

Author information

Authors and Affiliations

  1. Australian Centre for Field Robotics (ACFR), The University of Sydney, Sydney, NSW, 2006, Australia

    Timothy Patten & Wolfram Martens

  2. Centre for Autonomous Systems (CAS), University of Technology Sydney, Ultimo, NSW, 2007, Australia

    Robert Fitch

Authors
  1. Timothy Patten
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Wolfram Martens
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Robert Fitch
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Timothy Patten.

Additional information

This is one of several papers published in Autonomous Robots comprising the Special Issue on Active Perception.

Electronic supplementary material

Below is the link to the electronic supplementary material.

Supplementary material 1 (mpeg 55018 KB)

Appendix 1: Calculating entropy

Appendix 1: Calculating entropy

The state vector of an object is given by \(b = (\mathcal {N}({\varvec{\mu }}, \varSigma ), {\varvec{p}})\) where the components of the pose are assumed to be normally distributed with mean vector \({\varvec{\mu }} = [\mu _x, \mu _y, \mu _{\theta }]\) and covariance matrix \(\varSigma = \text {diag}(\sigma _x, \sigma _y, \sigma _{\theta })\) for the x location , y location, and orientation angle. The class of the object is represented by the probability vector \({\varvec{p}} = [p_{\ell }]_{\ell =1}^{N_L}\).

For the state vector of an object, the entropy of the joint state can be expressed as

$$\begin{aligned} H(b) = -\int \limits _{x} \int \limits _{y} \int \limits _{\theta } \sum _{\ell =1}^{N_L} p(x,y,\theta ,\ell ) \log \big ( p(x,y,\theta ,\ell ) \big ) \, dx \, dy \, d\theta , \end{aligned}$$

which can be decomposed up into the continuous variable (pose) and the discrete class label to give

$$\begin{aligned} H(b) = -\int \limits _{{\varvec{x}}} \sum _{\ell =1}^{N_L} p({\varvec{x}},\ell ) \log \big ( p({\varvec{x}},\ell ) \big ) d{\varvec{x}}, \end{aligned}$$

where \({\varvec{x}} = (x,y,\theta )\).

From the definition of conditional entropy

$$\begin{aligned} H(b) = H({\varvec{X}}, L) = H(L) + H({\varvec{X}}|L), \end{aligned}$$

where \({\varvec{X}} = [X, Y, \varTheta ]\) is a continuous random vector for the pose components, and L is a discrete random variable for the class label. The first term is the probability over the classes which is simply given by

$$\begin{aligned} H(L) = -\sum _{\ell =1}^{N_L} p_{\ell } \log \big (p_{\ell }\big ). \end{aligned}$$

Expanding the second term yields

$$\begin{aligned} H({\varvec{X}}|L) = \sum _{\ell =1}^{N_L} p_{\ell } H({\varvec{X}}|L = \ell ). \end{aligned}$$

For the estimation method described in this paper, the conditional entropy \(H({\varvec{X}}|L = \ell )\) is computed from the particles with class label \(\ell \) and calculating the entropy of a multivariate Gaussian distribution

$$\begin{aligned} H({\varvec{X}}|L = \ell ) = \frac{1}{2} \log \big ( (2 \pi e)^3 |\varSigma | \big ), \end{aligned}$$

where \(|\cdot |\) is the determinant of the matrix, and the power 3 comes from the dimension of \({\varvec{x}}\). We simplify this expression and assume each dimension \((x,y,\theta )\) to be independent, therefore, \(|\varSigma | = \sigma _{x}^2 \sigma _{y}^2 \sigma _{\theta }^2\).

1.1 Appendix 2: Proof of Lemma 1

In this proof we show that the recursive reward value for a node is equivalent to the empirical average of all rollout reward values for all simulations beginning at the node.

Let \(T = \tau _{\text {max}}\) represent the maximum depth of the tree. For a leaf node, that has no children or rollout reward, the average reward is given by \(\bar{Q}_T = \eta ^T R_T = \eta ^T \frac{1}{W_T} \sum _{i=1}^{W_T} R^i_T\).

Now consider a node one level above the leaf nodes at depth \(T-1\). The immediate reward is the average of all sample rewards \(Q_{T-1} = \frac{1}{W_{T-1}} \sum _{i=1}^{W_{T-1}} r^i_{T-1}\). The rollout reward consists of one step such that \(r_{T-1} = \eta ^{T} r^r_T\). Expanding the recursive definition gives

$$\begin{aligned} \bar{Q}_{T-1}= & {} \eta ^{T-1} R_{T-1} + \frac{1}{W_{T-1}} \left( r_{T-1} + \sum \limits _{{{v_c \in \textsc {Children}(v)}}} W_{v_c}\bar{Q}_{v_c} \right) , \\= & {} \eta ^{T-1} \frac{1}{W_{T-1}} \sum _{i=1}^{W_{T-1}} r^i_{T-1} + \frac{1}{W_{T-1}} \left( \eta ^{T} r^r_T + \sum \limits _{{{v_c \in \textsc {Children}(v)}}} W_{v_c}\bar{Q}_{v_c} \right) , \\= & {} \frac{1}{W_{T-1}} \left( \sum _{i=1}^{W_{T-1}} \eta ^{T-1} r^i_{T-1} + \sum _{i=1}^{W_{T-1}} \eta ^T r^i_T \right) , \\= & {} \frac{1}{W_{T-1}} \sum _{i=1}^{W_{T-1}} R^i_{T-1}, \end{aligned}$$

where the cumulative reward \(R^i_{T-1} = \sum _{j=T-1}^{T} \eta ^j r^i_j = \eta ^{T-1} r^i_{T-1} + \eta ^T r^i_T\) is the sum of the immediate reward and the immediate reward of the leaf node. The third line is obtained by moving the rollout reward into the last summation and using the definition of MCTS that the visit count of a parent equals the sum of the visit counts of its children plus one for the rollout. In other words, \(W_{T-1} = 1 + \sum \limits _{{{v_c \in \textsc {Children}(v)}}} W_{v_c}\). By induction, the result holds for all higher-level nodes. \(\square \)

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Patten, T., Martens, W. & Fitch, R. Monte Carlo planning for active object classification. Auton Robot 42, 391–421 (2018). https://doi.org/10.1007/s10514-017-9626-0

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10514-017-9626-0

Keywords

Search

Navigation