We propose a decentralized 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 optimize its own actions by maintaining a probability distribution over plans in the joint-action space. Robots periodically communicate a compressed form of their search trees, which are used to update the joint distribution using a distributed optimization approach inspired by variational methods. Our method admits any objective function defined over robot action sequences, assumes intermittent communication, is anytime, and is suitable for online replanning. Our algorithm features a new MCTS tree expansion policy that is designed for our planning scenario. We extend the theoretical analysis of standard MCTS to provide guarantees for convergence rates to the optimal payoff sequence. We evaluate the performance of our method for generalized team orienteering and online active object recognition using real data, and show that it compares favorably to centralized MCTS even with severely degraded communication. These examples demonstrate the suitability of our algorithm for real-world active perception with multiple robots.
AlamdariSFataESmithSL (2014) Persistent monitoring in discrete environments: Minimizing the maximum weighted latency between observations. The International Journal of Robotics Research33(1): 138–154.
2.
AmatoC (2015) Cooperative decision making. In: Decision Making Under Uncertainty: Theory and Application. Cambridge, MA: MIT Press.
3.
AroraAFitchRSukkariehS (2017) An approach to autonomous science by modeling geological knowledge in a Bayesian framework. In: Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS).
4.
AtanasovNNyJLDaniilidisKPappasGJ (2015) Decentralized active information acquisition: Theory and application to multi-robot SLAM. In: Proceedings of IEEE International Conference on Robotics and Automation (ICRA), pp. 4775–4782.
5.
AuerPCesa-BianchiNFischerP (2002) Finite-time analysis of the multiarmed bandit problem. Machine Learning47(2): 235–256.
6.
AugerD (2011) Multiple tree for partially observable Monte-Carlo tree search. In: Proceedings of European Conference on the Applications of Evolutionary Computation (EvoApplications), pp. 53–62.
7.
BajcsyR (1988) Active perception. Proceedings of the IEEE76(8): 966–1005.
8.
BajcsyRAloimonosYTsotsosJK (2017) Revisiting active perception. Autonomous Robots doi: 10.1007/s10514-017-9615-3.
9.
BernsteinDSGivanRImmermanNZilbersteinS (2002) The complexity of decentralized control of Markov decision processes. Mathematics of Operations Research27(4): 819–840.
10.
BeslPJMcKayHD (1992) A method for registration of 3-D shapes. IEEE Transactions on Pattern Analysis and Machine Intelligence14(2): 239–256.
11.
BestGCliffOPattenTMettuRFitchR (2016) Decentralised Monte Carlo tree search for active perception. In: Proceedings of International Workshop on the Algorithmic Foundations of Robotics (WAFR).
12.
BestGFaiglJFitchR (2018) Online planning for multi-robot active perception with self-organising maps. Autonomous Robots doi: 10.1007/s10514-017-9691-4.
13.
BestGForraiMMettuRRFitchR (2018) Planning-aware communication for decentralised multi-robot coordination. In: Proceedings of IEEE International Conference on Robotics and Automation (ICRA).
14.
BestGFitchR (2016) Probabilistic maximum set cover with path constraints for informative path planning. In: Proceedings of ARAA Australasian Conference on Robotics and Automation (ACRA).
15.
BestGMartensWFitchR (2017) Path planning with spatiotemporal optimal stopping for stochastic mission monitoring. IEEE Transactions on Robotics33(3): 629–646.
16.
BinneyJSukhatmeG (2012) Branch and bound for informative path planning. In: Proceedings of IEEE International Conference on Robotics and Automation (ICRA), pp. 2147–2154.
17.
BircherAKamelMAlexisKOleynikovaHSiegwartR (2016) Receding horizon path planning for 3D exploration and surface inspection. Autonomous Robots doi: 10.1007/s10514-016-9610-0.
18.
BrowneCPowleyEWhitehouseDet al. (2012) A survey of Monte Carlo tree search methods. IEEE Transactions on Computational Intelligence and AI in Games4(1): 1–43.
19.
CharrowB (2015) Information-theoretic active perception for multi-robot teams. PhD Thesis, University of Pennsylvania.
20.
ChaslotGMJBWinandsMHMvan den HerikHJ (2008) Parallel Monte-Carlo tree search. In: Proceedings of International Conference on Computers and Games (CG), pp. 60–71.
21.
ChoudhurySKapoorARanadeGSchererSDeyD (2017) Adaptive information gathering via imitation learning. In: Proceedings of Robotics: Science and Systems.
22.
CliffOMFitchRSukkariehSSaundersDLHeinsohnR (2015) Online localization of radio-tagged wildlife with an autonomous aerial robot system. In: Proceedings of Robotics: Science and Systems.
23.
CliffOMLizierJTWangXRWangPObstOProkopenkoM (2017) Quantifying long-range interactions and coherent structure in multi-agent dynamics. Artificial Life23(1): 34–57.
24.
CoquelinPMunosR (2007) Bandit algorithms for tree search. In: Proceedings of Conference on Uncertainty in Artificial Intelligence (UAI), pp. 67–74.
25.
CorahMMichaelN (2017) Efficient online multi-robot exploration via distributed sequential greedy assignment. In: Proceedings of Robotics: Science and Systems.
26.
DiasMBZlotRKalraNStentzA (2006) Market-based multirobot coordination: A survey and analysis. Proceedings of the IEEE94(7): 1257–1270.
27.
DouillardBQuadrosAMortonPUnderwoodJPDeugeMD (2012) A 3D classifier trained without field samples. In: Proceedings of IEEE International Conference on Control, Automation, Robotics and Vision (ICARCV), pp. 805–810.
28.
DunbabinMMarquesL (2012) Robots for environmental monitoring: Significant advancements and applications. IEEE Robotics and Automation Magazine19(1): 24–39.
29.
FaiglJPěničkaRBestG (2016) Self-organizing map-based solution for the orienteering problem with neighborhoods. In: Proceedings of IEEE International Conference on Systems, Man, and Cybernetics (SMC), pp. 1315–1321.
30.
FäulhammerTAmbruşRBurbridgeCet al. (2017) Autonomous learning of object models on a mobile robot. IEEE Robotics and Automation Letters2(1): 26–33.
31.
FeldmanZDomshlakC (2014) Simple regret optimization in online planning for Markov decision processes. Journal of Artificial Intelligence Research51: 165–205.
32.
GanSKFitchRSukkariehS (2014) Online decentralized information gathering with spatial–temporal constraints. Autonomous Robots37(1): 1–25.
33.
GargSAyanianN (2014) Persistent monitoring of stochastic spatio-temporal phenomena with a small team of robots. In: Proceedings of Robotics: Science and Systems.
34.
GarivierAMoulinesE (2011) On upper-confidence bound policies for switching bandit problems. In: Proceedings of International Conference on Algorithmic Learning Theory, pp. 174–188.
35.
GellySKocsisLSchoenauerMSebagMSilverDSzepesváriCTeytaudO (2012) The grand challenge of computer Go: Monte Carlo tree search and extensions. Communications of the ACM55(3): 106–113.
36.
GunawanALauHCVansteenwegenP (2016) Orienteering problem: A survey of recent variants, solution approaches and applications. European Journal of Operational Research255(2): 315–332.
37.
HefferanBCliffOMFitchR (2016) Adversarial patrolling with reactive point processes. In: Proceedings of ARAA Australasian Conference on Robotics and Automation (ACRA).
38.
HollingerG (2015) Long-horizon robotic search and classification using sampling-based motion planning. In: Proceedings of Robotics: Science and Systems.
39.
HollingerGSinghSDjugashJKehagiasA (2009) Efficient multi-robot search for a moving target. The International Journal of Robotics Research28(2): 201–219.
40.
HollingerGASukhatmeGS (2014) Sampling-based robotic information gathering algorithms. The International Journal of Robotics Research33(9): 1271–1287.
41.
HönigWAyanianN (2016) Dynamic multi-target coverage with robotic cameras. In: Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 1871–1878.
42.
HuberMFDenckerTRoschaniMBeyererJ (2012) Bayesian active object recognition via gaussian process regression. In: Proceedings of IEEE International Conference on Information Fusion (FUSION), pp. 1718–1725.
43.
JamesSKonidarisGRosmanB (2017) An analysis of Monte Carlo tree search. In: Proceedings of AAAI Conference on Artificial Intelligence.
44.
KahnGSujanPPatilSet al. (2015) Active exploration using trajectory optimization for robotic grasping in the presence of occlusions. In: Proceedings of IEEE International Conference on Robotics and Automation (ICRA), pp. 4783–4790.
45.
KartalBGodoyJKaramouzasIGuySJ (2015) Stochastic tree search with useful cycles for patrolling problems. In: Proceedings of IEEE International Conference on Robotics and Automation (ICRA), pp. 1289–1294.
46.
KassirAFitchRSukkariehS (2015) Communication-aware information gathering with dynamic information flow. The International Journal of Robotics Research34(2): 173–200.
47.
KocsisLSzepesváriC (2006) Bandit based Monte-Carlo planning. In: Proceedings of European Conference on Machine Learning (ECML), pp. 282–293.
48.
KocsisLSzepesváriCWillemsonJ (2006) Improved Monte-Carlo search. Technical report, University of Tartu.
49.
KollerDFriedmanN (2009) Probabilistic graphical models: Principles and techniques. Cambridge, MA: MIT Press.
50.
KrauseASinghAGuestrinC (2008) Near-optimal sensor placements in Gaussian processes: Theory, efficient algorithms and empirical studies. Journal of Machine Learning Research9: 235–284.
51.
KulkarniAJTaiK (2010) Probability collectives: A multi-agent approach for solving combinatorial optimization problems. Applied Soft Computing10(3): 759–771.
52.
KumarAZilbersteinSToussaintM (2015) Probabilistic inference techniques for scalable multiagent decision making. Journal of Artificial Intelligence Research53: 223–270.
53.
LauriMAtanasovNPappasGRitalaR (2015) Active object recognition via Monte Carlo tree search. In: Proceedings of IEEE ICRA Workshop on Beyond Geometric Constraints.
54.
LauriMRitalaR (2016) Planning for robotic exploration based on forward simulation. Robotics and Autonomous Systems83: 15–31.
55.
LindhéMJohanssonKH (2013) Exploiting multipath fading with a mobile robot. The International Journal of Robotics Research32(12): 1363–1380.
56.
LiuLMichaelNShellDA (2015) Communication constrained task allocation with optimized local task swaps. Autonomous Robots39(3): 429–444.
57.
MarchantRRamosFSannerS (2014) Sequential Bayesian optimisation for spatial-temporal monitoring. In: Proceedings of Conference on Uncertainty in Artificial Intelligence (UAI).
58.
NemhauserGLWolseyLAFisherML (1978) An analysis of approximations for maximizing submodular set functions–I. Mathematical Programming14(1): 265–294.
59.
NguyenJLawranceNFitchRSukkariehS (2015) Real-time path planning for long-term information gathering with an aerial glider. Autonomous Robots40(6): 1017–1039.
60.
NoonCEBeanJC (1989) An efficient transformation of the generalized traveling salesman problem. Technical Report 89–36, Department of Industrial and Operations Engineering, University of Michigan.
61.
OliehoekFAAmatoC (2016) A Concise Introduction to Decentralized POMDPs. Dordrecht: Springer.
62.
OmidshafieiSAgha-MohammadiAAAmatoCLiuSYHowJPVianJ (2017) Decentralized control of multi-robot partially observable Markov decision processes using belief space macro-actions. The International Journal of Robotics Research36(2): 231–258.
63.
OndruskaPGurauCMarchegianiLTongCHPosnerI (2015) Scheduled perception for energy-efficient path following. In: Proceedings of IEEE International Conference on Robotics and Automation (ICRA), pp. 4799–4806.
64.
OtteMCorrellN (2013) Any-com multi-robot path-planning: Maximizing collaboration for variable bandwidth. In: Distributed Autonomous Robotic Systems: The 10th International Symposium. Berlin: Springer, pp. 161–173.
65.
PattenT (2017) Active Object Classification from 3D Range Data with Mobile Robots. PhD Thesis, The University of Sydney.
66.
PattenTFitchRSukkariehS (2013) Large-scale near-optimal decentralised information gathering with multiple mobile robots. In: Proceedings of ARAA Australasian Conference on Robotics and Automation (ACRA).
67.
PattenTKassirAMartensWDouillardBFitchRSukkariehS (2015) A Bayesian approach for time-constrained 3D outdoor object recognition. In: Proceedings of ICRA 2015 Workshop on Scaling Up Active Perception.
68.
PattenTMartensWFitchR (2017) Monte Carlo planning for active object classification. Autonomous Robots doi: 10.1007/s10514-017-9626-0.
69.
PattenTZillichMFitchRVinczeMSukkariehS (2016) Viewpoint evaluation for online 3-D active object classification. IEEE Robotics and Automation Letters1(1): 73–81.
70.
RahmattalabiAChungJJColbyMTumerK (2016) D++: Structural credit assignment in tightly coupled multiagent domains. In: Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 4424–4429.
71.
RegevTIndelmanV (2016) Multi-robot decentralized belief space planning in unknown environments via efficient re-evaluation of impacted paths. In: Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS).
72.
RezekILeslieDSReeceSet al. (2008) On similarities between inference in game theory and machine learning. Journal of Artificial Intelligence Research33: 259–283.
73.
SadeghiASmithSL (2017) Heterogeneous task allocation and sequencing via decentralized large neighborhood search. Unmanned Systems, in press.
74.
SilverDVenessJ (2010) Monte-Carlo planning in large POMDPs. In: LaffertyJDWilliamsCKIShawe-TaylorJZemelRSCulottaA (eds.) Advances in Neural Information Processing Systems23. Curran Associates, Inc., pp. 2164–2172.
75.
SinghAKrauseAGuestrinCKaiserWJ (2009) Efficient informative sensing using multiple robots. Journal of Artificial Intelligence Research34(1): 707–755.
76.
SladePCulbertsonPSunbergZKochenderferMJ (2017) Simultaneous active parameter estimation and control using sampling-based Bayesian reinforcement learning. In: Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS).
77.
SomaniAYeNHsuDLeeWS (2013) DESPOT: Online POMDP planning with regularization. In: BurgesCJCBottouLWellingMGhahramaniZWeinbergerKQ (eds.) Advances in Neural Information Processing Systems26. Curran Associates, Inc., pp. 1772–1780.
78.
SpaanMTJGordonGJVlassisN (2006) Decentralized planning under uncertainty for teams of communicating agents. In: Proceedings of International Joint Conference on Autonomous Agents and Multiagent Systems.
79.
StrandersRFarinelliARogersAJenningsN (2009) Decentralised coordination of mobile sensors using the max-sum algorithm. In: Proceedings of International Joint Conference on Artificial Intelligence (IJCAI), pp. 299–304.
80.
van HoofHKroemerOPetersJ (2014) Probabilistic segmentation and targeted exploration of objects in cluttered environments. IEEE Transactions on Robotics30(5): 1198–1209.
81.
VansteenwegenPSouffriauWOudheusdenDV (2011) The orienteering problem: A survey. European Journal of Operational Research209(1): 1–10.
82.
WaldockANicholsonD (2007) Cooperative decentralised data fusion using probability collectives. In: Proceedings of AAMAS Workshop on Agent Technology for Sensor Networks.
83.
WolpertDHBieniawskiS (2004) Distributed control by Lagrangian steepest descent. In: Proceedings of IEEE Conference on Decision and Control (CDC), pp. 1562–1567.
84.
WolpertDHBieniawskiSRRajnarayanDG (2013) Probability collectives in optimization. In Handbook of Statistics 31: Machine Learning: Theory and Applications. Amsterdam: Elsevier, pp. 61–99.
85.
WolpertDHStraussCEMRajnarayanD (2006) Advances in distributed optimization using probability collectives. Advances in Complex Systems9(4): 383–436.
86.
WuKRanasigneRDissanayakeG (2015) Active recognition and pose estimation of household objects in clutter. In: Proceedings of IEEE International Conference on Robotics and Automation (ICRA), pp. 4230–4237.
87.
XingEPJordanMIRussellS (2004) Graph partition strategies for generalized mean field inference. In: Proceedings of Conference on Uncertainty in Artificial Intelligence (UAI), pp. 602–610.
88.
XuZFitchRUnderwoodJSukkariehS (2013) Decentralized coordinated tracking with mixed discrete-continuous decisions. Journal of Field Robotics30(5): 717–740.
89.
YedidiaJSFreemanWTWeissY (2005) Constructing free-energy approximations and generalized belief propagation algorithms. IEEE Transactions on Information Theory51(7): 2282–2312.
90.
YuJSchwagerMRusD (2016) Correlated orienteering problem and its application to persistent monitoring tasks. IEEE Transactions on Robotics32(5): 1106–1118.
91.
ZlotRStentzADiasMThayerS (2002) Multi-robot exploration controlled by a market economy. In: Proceedings of IEEE International Conference on Robotics and Automation (ICRA), pp. 3016–3023.
