Top

Autonomous Robots

Published in:

13-12-2017

Online planning for multi-robot active perception with self-organising maps

Authors: Graeme Best, Jan Faigl, Robert Fitch

Published in: Autonomous Robots | Issue 4/2018

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We propose a self-organising map (SOM) algorithm as a solution to a new multi-goal path planning problem for active perception and data collection tasks. We optimise paths for a multi-robot team that aims to maximally observe a set of nodes in the environment. The selected nodes are observed by visiting associated viewpoint regions defined by a sensor model. The key problem characteristics are that the viewpoint regions are overlapping polygonal continuous regions, each node has an observation reward, and the robots are constrained by travel budgets. The SOM algorithm jointly selects and allocates nodes to the robots and finds favourable sequences of sensing locations. The algorithm has a runtime complexity that is polynomial in the number of nodes to be observed and the magnitude of the relative weighting of rewards. We show empirically the runtime is sublinear in the number of robots. We demonstrate feasibility for the active perception task of observing a set of 3D objects. The viewpoint regions consider sensing ranges and self-occlusions, and the rewards are measured as discriminability in the ensemble of shape functions feature space. Exploration objectives for online tasks where the environment is only partially known in advance are modelled by introducing goal regions in unexplored space. Online replanning is performed efficiently by adapting previous solutions as new information becomes available. Simulations were performed using a 3D point-cloud dataset from a real robot in a large outdoor environment. Our results show the proposed methods enable multi-robot planning for online active perception tasks with continuous sets of candidate viewpoints and long planning horizons.

previous article Decentralized multi-robot belief space planning in unknown environments via identification and efficient re-evaluation of impacted paths

next article Searching and tracking people with cooperative mobile robots

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Available only for authorised users

Angéniol, B., de la Vaubois, C. G., & Texier, J. Y. L. (1988). Self-organizing feature maps and the travelling salesman problem. Neural Networks, 1(4), 289–293.CrossRef

Archetti, C., Hertz, A., & Speranza, M. G. (2007). Metaheuristics for the team orienteering problem. Journal of Heuristics, 13(1), 49–76.CrossRef

Atanasov, N., Ny, J. L., Daniilidis, K., & Pappas, G. J. (2015). Decentralized active information acquisition: Theory and application to multi-robot SLAM. In Proceedings of IEEE ICRA (pp. 4775–4782).

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.CrossRef

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.CrossRef

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. The International Journal of Robotics Research, 35(10), 1207–1233.CrossRef

Bektas, T. (2006). The multiple traveling salesman problem: An overview of formulations and solution procedures. Omega, 34(3), 209–219.MathSciNetCrossRef

Best, G., Cliff, O., Patten, T., Mettu, R., & Fitch, R. (2016a). Decentralised Monte Carlo tree search for active perception. In Proceedings of the WAFR.

Best, G., Faigl, J., & Fitch, R. (2016b). Multi-robot path planning for budgeted active perception with self-organising maps. In Proceedings of IEEE/RSJ IROS (pp. 3164–3171).

Best, G., & Fitch, R. (2016). Probabilistic maximum set cover with path constraints for informative path planning. In: Proceedings of ARAA ACRA.

Best, G., Martens, W., & Fitch, R. (2017). Path planning with spatiotemporal optimal stopping for stochastic mission monitoring. IEEE Transactions on Robotics, 33(3), 629–646.CrossRef

Binney, J., & Sukhatme, G. (2012). Branch and bound for informative path planning. In Proceedings of IEEE ICRA (pp. 2147–2154).

Bircher, A., Kamel, M., Alexis, K., Burri, M., Oettershagen, P., Omari, S., et al. (2016). Three-dimensional coverage path planning via viewpoint resampling and tour optimization for aerial robots. Autonomous Robots, 40(6), 1059–1078.CrossRef

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).

Cao, N., Low, K. H., & Dolan, J. M. (2013). Multi-robot informative path planning for active sensing of environmental phenomena: A tale of two algorithms. In Proceedings of AAMAS (pp. 7–14).

Charrow, B. (2015). Information-theoretic active perception for multi-robot teams. Ph.D. thesis, University of Pennsylvania.

Chekuri, C., & Pal, M. (2005). A recursive greedy algorithm for walks in directed graphs. In Proceedings of IEEE FOCS (pp. 245–253).

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

Cochrane, E. M., & Beasley, J. E. (2003). The co-adaptive neural network approach to the euclidean travelling salesman problem. Neural Networks, 16(10), 1499–1525.CrossRef

Corah, M., & Michael, N. (2017). Efficient online multi-robot exploration via distributed sequential greedy assignment. In Proceedings of robotics: science and systems.

Cunningham-Nelson, S., Moghadam, P., Roberts, J., & Elfes, A. (2015). Coverage-based next best view selection. In Proceedings of ARAA ACRA.

Dang, D. C., El-Hajj, R., & Moukrim, A. (2013a). A branch-and-cut algorithm for solving the team orienteering problem. In Proceedings of CPAIOR (pp. 332–339). Springer.

Dang, D. C., Guibadj, R. N., & Moukrim, A. (2013b). An effective PSO-inspired algorithm for the team orienteering problem. European Journal of Operational Research, 229(2), 332–344.CrossRefMATH

Dornhege, C., Kleiner, A., Hertle, A., & Kolling, A. (2016). Multirobot coverage search in three dimensions. Journal of Field Robotics, 33(4), 537–558.CrossRef

Faigl, J. (2010). Approximate solution of the multiple watchman routes problem with restricted visibility range. IEEE Transactions on Neural Networks, 21(10), 1668–1679.CrossRef

Faigl, J. (2016a). An application of self-organizing map for multirobot multigoal path planning with minmax objective. Computational Intelligence and Neuroscience. https://doi.org/10.1155/2016/2720630.

Faigl, J. (2016b). On self-organizing map and rapidly-exploring random graph in multi-goal planning. In Advances in self-organizing maps and learning vector quantization (pp. 143–153). Springer.

Faigl, J. (2017). On self-organizing maps for orienteering problems. In Proceedings of IJCNN (pp. 2611–2620).

Faigl, J., & Hollinger, G. (2014). Unifying multi-goal path planning for autonomous data collection. In Proceedings of IEEE/RSJ IROS (pp. 2937–2942).

Faigl, J., & Hollinger, G. A. (2017). Autonomous data collection using a self-organizing map. IEEE Transactions on Neural Networks and Learning Systems. https://doi.org/10.1109/TNNLS.2017.2678482.

Faigl, J., Kulich, M., & Přeučil, L. (2012). Goal assignment using distance cost in multi-robot exploration. In Proceedings of IEEE/RSJ IROS (pp. 3741–3746).

Faigl, J., Pěnička, R., & Best, G. (2016). Self-organizing map-based solution for the orienteering problem with neighborhoods. In Proceedings of IEEE SMC (pp. 1315–1321).

Faigl, J., & Váňa, P. (2016). Self-organizing map for data collection planning in persistent monitoring with spatial correlations. In Proceedings of IEEE SMC (pp. 3264–3269).

Galceran, E., & Carreras, M. (2013). A survey on coverage path planning for robotics. Robotics and Autonomous Systems, 61(12), 1258–1276.CrossRef

Garg, S., & Ayanian, N. (2014). Persistent monitoring of stochastic spatio-temporal phenomena with a small team of robots. In Proceedings of robotics: science and systems.

Gunawan, A., Lau, H. C., & Vansteenwegen, P. (2016). Orienteering problem: A survey of recent variants, solution approaches and applications. European Journal of Operational Research, 255(2), 315–332.MathSciNetCrossRefMATH

Helsgaun, K. (2000). An effective implementation of the Lin–Kernighan traveling salesman heuristic. European Journal of Operational Research, 126(1), 106–130.MathSciNetCrossRefMATH

Hollinger, G., Singh, S., Djugash, J., & Kehagias, A. (2009). Efficient multi-robot search for a moving target. The International Journal of Robotics Research, 28(2), 201–219.CrossRef

Hollinger, G. A., Mitra, U., & Sukhatme, G. S. (2011). Active classification: Theory and application to underwater inspection. In Proceedings of ISRR.

Hönig, W., & Ayanian, N. (2016). Dynamic multi-target coverage with robotic cameras. In Proceedings of IEEE/RSJ IROS (pp. 1871–1878).

Kassir, A., Fitch, R., & Sukkarieh, S. (2015). Communication-aware information gathering with dynamic information flow. The International Journal of Robotics Research, 34(2), 173–200.CrossRef

Kriegel, S., Brucker, M., Marton, Z. C., Bodenmuller, T., & Suppa, M. (2013). Combining object modeling and recognition for active scene exploration. In Proceedings of IEEE/RSJ IROS (pp. 2384–2391).

Kulich, M., Faigl, J., & Přeučil, L. (2011). On distance utility in the exploration task. In Proceedings of IEEE ICRA (pp. 4455–4460).

Kulich, M., Sushkov, R., & Přeučil, L. (2016). Speed-up of self-organizing networks for routing problems in a polygonal domain. In Proceedings of IEEE/RSJ IROS 10th international workshop on cognitive robotics.

Lagoudakis, M. G., Markakis, E., Kempe, D., Keskinocak, P., Kleywegt, A. J., Koenig, S., Tovey, C. A., Meyerson, A., & Jain, S. (2005). Auction-based multi-robot routing. In Proceedings of robotics: science and systems.

Likhachev, M., Ferguson, D. I., Gordon, G. J., Stentz, A., & Thrun, S. (2005). Anytime dynamic A*: An anytime, replanning algorithm. In Proceedings of ICAPS (pp. 262–271).

Martens, W., Poffet, Y., Soria, P. R., Fitch, R., & Sukkarieh, S. (2017). Geometric priors for Gaussian process implicit surfaces. IEEE Robotics and Automation Letters, 2(2), 373–380.CrossRef

Mathew, N., Smith, S., & Waslander, S. (2013). A graph-based approach to multi-robot rendezvous for recharging in persistent tasks. In Proceedings of IEEE ICRA (pp. 3497–3502).

McMahon, J., & Plaku, E. (2017). Autonomous data collection with limited time for underwater vehicles. IEEE Robotics and Automation Letters, 2(1), 112–119.CrossRef

Noon, C. E., & Bean, J. C. (1989). An efficient transformation of the generalized traveling salesman problem. Technical report 89-36, Department of Industrial and Operations Engineering, University of Michigan.

Patten, T. (2017). Active object classification from 3D range data with mobile robots. Ph.D. thesis, The University of Sydney.

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., Martens, W., & Fitch, R. (2017). Monte Carlo planning for active object classification. Autonomous Robots. https://doi.org/10.1007/s10514-017-9626-0.

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.CrossRef

Peng, C., Roy, P., Luby, J., & Isler, V. (2016). Semantic mapping of orchards. IFAC-PapersOnLine, 49(16), 85–89.CrossRef

Quattrini Li, A., Cipolleschi, R., Giusto, M., & Amigoni, F. (2016). A semantically-informed multirobot system for exploration of relevant areas in search and rescue settings. Autonomous Robots, 40(4), 581–597.CrossRef

Robin, C., & Lacroix, S. (2015). Multi-robot target detection and tracking: Taxonomy and survey. Autonomous Robots, 40(4), 729–760.CrossRef

Singh, A., Krause, A., Guestrin, C., & Kaiser, W. J. (2009). Efficient informative sensing using multiple robots. Journal of Artificial Intelligence Research, 34(2), 707.MathSciNetMATH

Smith, S. L., & Imeson, F. (2017). GLNS: An effective large neighborhood search heuristic for the generalized traveling salesman problem. Computers and Operations Research, 87, 1–19.MathSciNetCrossRef

Somhom, S., Modares, A., & Enkawa, T. (1997). A self-organising model for the travelling salesman problem. Journal of the Operational Research Society, 48(9), 919–928.CrossRefMATH

Somhom, S., Modares, A., & Enkawa, T. (1999). Competition-based neural network for the multiple travelling salesmen problem with minmax objective. Computers and Operations Research, 26(4), 395–407.MathSciNetCrossRefMATH

Toth, P., & Vigo, D. (2001). The vehicle routing problem. New Delhi: SIAM.MATH

Tucci, M., & Raugi, M. (2010). Stability analysis of self-organizing maps and vector quantization algorithms. In Proceedings of IJCNN (pp. 1–5).

van Hoof, H., Kroemer, O., & Peters, J. (2014). Probabilistic segmentation and targeted exploration of objects in cluttered environments. IEEE Transactions on Robotics, 30(5), 1198–1209.CrossRef

Vansteenwegen, P., Souffriau, W., & Oudheusden, D. V. (2011). The orienteering problem: A survey. European Journal of Operational Research, 209(1), 1–10.MathSciNetCrossRefMATH

Wohlkinger, W., Aldoma, A., Rusu, R. B., & Vincze, M. (2012). 3DNet: Large-scale object class recognition from CAD models. In Proceedings of IEEE ICRA (pp. 5384–5391).

Wohlkinger, W., & Vincze, M. (2011). Ensemble of shape functions for 3D object classification. In Proceedings of IEEE ROBIO (pp. 2987–2992).

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

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.CrossRef

Yu, J., Schwager, M., & Rus, D. (2016). Correlated orienteering problem and its application to persistent monitoring tasks. IEEE Transactions on Robotics, 32(5), 1106–1118.CrossRef

Zhang, W. D., Bai, Y. P., & Hu, H. P. (2006). The incorporation of an efficient initialization method and parameter adaptation using self-organizing maps to solve the TSP. Applied Mathematics and Computation, 172(1), 603–623.MathSciNetCrossRefMATH

Zlot, R., Stentz, A., Dias, M., & Thayer, S. (2002). Multi-robot exploration controlled by a market economy. In Proceedings of IEEE ICRA (Vol. 3, pp. 3016–3023).

Title: Online planning for multi-robot active perception with self-organising maps
Authors: Graeme Best
Jan Faigl
Robert Fitch
Publication date: 13-12-2017
Publisher: Springer US
Published in: Autonomous Robots / Issue 4/2018
Print ISSN: 0929-5593
Electronic ISSN: 1573-7527
DOI: https://doi.org/10.1007/s10514-017-9691-4

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Other articles of this Issue 4/2018

Multiple-place swarm foraging with dynamic depots

Decentralized multi-robot belief space planning in unknown environments via identification and efficient re-evaluation of impacted paths

Locally-optimal multi-robot navigation under delaying disturbances using homotopy constraints

Reconfigurable multi-robot coordination with guaranteed convergence in obstacle cluttered environments under local communication

Reactive mission and motion planning with deadlock resolution avoiding dynamic obstacles

The Team Surviving Orienteers problem: routing teams of robots in uncertain environments with survival constraints