Abstract
We propose a decentralised variant of Monte Carlo tree search (MCTS) that is suitable for a variety of tasks in multi-robot active perception. Our algorithm allows each robot to optimise its own individual action space by maintaining a probability distribution over plans in the joint-action space. Robots periodically communicate a compressed form of these search trees, which are used to update the locally-stored joint distributions using an optimisation approach inspired by variational methods. Our method admits any objective function defined over robot actions, assumes intermittent communication, and is anytime.We extend the analysis of the standard MCTS for our algorithm and characterise asymptotic convergence under reasonable assumptions. We evaluate the practical performance of our method for generalised team orienteering and active object recognition using real data, and show that it compares favourably to centralised MCTS even with severely degraded communication. These examples support the relevance of our algorithm for real-world active perception with multi-robot systems.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Amato, C.: Decision Making Under Uncertainty: Theory and Application, chap. Cooperative Decision Making. MIT Press, Cambridge and London (2015)
Auger, D.: Multiple tree for partially observable Monte-Carlo tree search. In: Proc. of EvoApplications. pp. 53–62 (2011)
Bajcsy, R.: Active perception. Proceedings of the IEEE 76(8), 966–1005 (1988)
Best, G., Faigl, J., Fitch, R.: Multi-robot path planning for budgeted active perception with self-organising maps. In: Proc. of IEEE/RSJ IROS (2016)
Browne, C., Powley, E., Whitehouse, D., Lucas, S., Cowling, P., Rohlfshagen, P., Tavener, S., Perez, D., Samothrakis, S., Colton, S.: A survey of Monte Carlo tree search methods. IEEE T. Comput. Int. AI Games 4(1), 1–43 (2012)
Charrow, B.: Information-theoretic active perception for multi-robot teams. Ph.D. thesis, University of Pennsylvania (2015)
Chaslot, G.M.J.B., Winands, M.H.M., van den Herik, H.J.: Parallel Monte-Carlo tree search. In: Proc. of CG. pp. 60–71 (2008)
Douillard, B., Quadros, A., Morton, P., Underwood, J.P., Deuge, M.D.: A 3D classifier trained without field samples. In: Proc. of ICARCV. pp. 805 – 810 (2012)
Faigl, J., Pěnička, R., Best, G.: Self-organizing map-based solution for the orienteering problem with neighborhoods. In: Proc. of IEEE SMC (2016)
Gan, S.K., Fitch, R., Sukkarieh, S.: Online decentralized information gathering with spatial–temporal constraints. Auton. Robots 37(1), 1 – 25 (2014)
Garivier, A., Moulines, E.: On upper-confidence bound policies for switching bandit problems. In: Proc. of AMA ALT. pp. 174–188 (2011)
Gunawan, A., Lau, H.C., Vansteenwegen, P.: Orienteering problem: A survey of recent variants, solution approaches and applications. Eur. J. Oper. Res. 255(2), 315 – 332 (2016)
Kocsis, L., Szepesvári, C.: Bandit based Monte-Carlo planning. In: Proc. of ECML. pp. 282–293 (2006)
Krause, A., Singh, A., Guestrin, C.: Near-optimal sensor placements in Gaussian processes: Theory, efficient algorithms and empirical studies. J. Mach. Learn. Res. 9, 235 – 284 (2008)
Kulkarni, A.J., Tai, K.: Probability collectives: A multi-agent approach for solving combinatorial optimization problems. Appl. Soft Comput. 10(3), 759 – 771 (2010)
Nemhauser, G.L., Wolsey, L.A., Fisher, M.L.: An analysis of approximations for maximizing submodular set functions–I. Math. Program. 14(1), 265 – 294 (1978)
Patten, T., Zillich, M., Fitch, R., Vincze, M., Sukkarieh, S.: Viewpoint evaluation for online 3-D active object classification. IEEE Robot. Autom. Lett. 1(1), 73–81 (2016)
Patten, T., Kassir, A., Martens, W., Douillard, B., Fitch, R., Sukkarieh, S.: A Bayesian approach for time-constrained 3D outdoor object recognition. In: ICRA 2015 Workshop on Scaling Up Active Perception (2015)
Rezek, I., Leslie, D.S., Reece, S., Roberts, S.J., Rogers, A., Dash, R.K., Jennings, N.R.: On similarities between inference in game theory and machine learning. J. Artif. Intell. Res. 33, 259–283 (2008)
Silver, D., Veness, J.: Monte-Carlo planning in large POMDPs. In: Lafferty, J.D., Williams, C.K.I., Shawe-Taylor, J., Zemel, R.S., Culotta, A. (eds.) Advances in Neural Information Processing Systems 23, pp. 2164–2172. Curran Inc. (2010)
Singh, A., Krause, A., Guestrin, C., Kaiser, W.J.: Efficient informative sensing using multiple robots. J. Artif. Int. Res. 34(1), 707 – 755 (2009)
Wolpert, D.H., Bieniawski, S.: Distributed control by Lagrangian steepest descent. In: Proc. of IEEE CDC. pp. 1562–1567 (2004)
Wolpert, D.H., Bieniawski, S.R., Rajnarayan, D.G.: Handbook of Statistics 31: Machine Learning: Theory and Applications, chap. Probability collectives in optimization, pp. 61 – 99. Elsevier (2013)
Wolpert, D.H., Strauss, C.E.M., Rajnarayan, D.: Advances in distributed optimization using probability collectives. Adv. Complex Syst. 09(04), 383–436 (2006)
Xu, Z., Fitch, R., Underwood, J., Sukkarieh, S.: Decentralized coordinated tracking with mixed discrete-continuous decisions. J. Field Robot. 30(5), 717 – 740 (2013)
Yedidia, J.S., Freeman, W.T., Weiss, Y.: Constructing free-energy approximations and generalized belief propagation algorithms. IEEE Trans. Inf. Theor. 51(7), 2282–2312 (2005)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this chapter
Cite this chapter
Best, G., Cliff, O.M., Patten, T., Mettu, R.R., Fitch, R. (2020). Decentralised Monte Carlo Tree Search for Active Perception. In: Goldberg, K., Abbeel, P., Bekris, K., Miller, L. (eds) Algorithmic Foundations of Robotics XII. Springer Proceedings in Advanced Robotics, vol 13. Springer, Cham. https://doi.org/10.1007/978-3-030-43089-4_55
Download citation
DOI: https://doi.org/10.1007/978-3-030-43089-4_55
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-43088-7
Online ISBN: 978-3-030-43089-4
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)