Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Autonomous Robots
Published in: Autonomous Robots 3/2019

07-11-2018

Real-time distributed non-myopic task selection for heterogeneous robotic teams

Authors: Andrew J. Smith, Graeme Best, Javier Yu, Geoffrey A. Hollinger

Published in: Autonomous Robots | Issue 3/2019

Log in

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

search-config
loading …

Abstract

In this paper we introduce a novel algorithm for online distributed non-myopic task-selection in heterogeneous robotic teams. Our algorithm uses a temporal probabilistic representation that allows agents to evaluate their actions in the team’s joint action space while robots individually search their own action space. We use Monte-Carlo tree search to asymmetrically search through the robot’s individual action space while accounting for the probable future actions of their team members using the condensed temporal representation. This allows a distributed team of robots to non-myopically coordinate their actions in real-time. Our developed method can be applied across a wide range of tasks, robot team compositions, and reward functions. To evaluate our coordination method, we implemented it for a series of simulated and fielded hardware trials where we found that our coordination method is able to increase the cumulative team reward by a maximum of \(47.2\%\) in the simulated trials versus a distributed auction-based coordination. We also performed several outdoor hardware trials with a team of three quadcopters that increased the maximum cumulative reward by \(24.5\%\) versus a distributed auction-based coordination.
previous article Robust connectivity maintenance for fallible 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
Footnotes
1
The hardware flight trials conducted for this research were conducted under Oregon State University’s (OSU) Federal Aviation Administration Certificate of Authorization and logged in OSU’s compliance software, Drone Complier.
 
Literature
Agrawal, R. (1995). Sample mean based index policies by O(log n) regret for the multi-armed bandit problem. Advances in Applied Probability, 27(4), 1054–1078.MathSciNetCrossRefMATH
Amato, C., Konidaris, G., Anders, A., Cruz, G., How, J. P., & Kaelbling, L. P. (2016). Policy search for multi-robot coordination under uncertainty. International Journal of Robotics Research, 35(14), 1760–1778.CrossRef
Arkin, R. C., & Balch, T. (1998). Cooperative multiagent robotic systems. In Artificial intelligence and mobile robots.
Ayanian, N., Fitch, R., Franchi, A., & Sabattini, L. (2017). Multirobot systems. IEEE Robotics & Automation Magazine, 24(2), 12–16.CrossRef
Beck, Z., Teacy, L., Rogers, A., & Jennings, N. R. (2016). Online planning for collaborative search and rescue by heterogeneous robot teams. In Proceedings of the international conference on autonomous agents & multiagent systems (pp. 1024–1033).
Bektas, T. (2006). The multiple traveling salesman problem: An overview of formulations and solution procedures. Omega, 34(3), 209–219.MathSciNetCrossRef
Best, G., Forrai, M., Mettu, R. R., & Fitch, R. (2018). Planning-aware communication for decentralised multi-robot coordination. In Proceedings of the IEEE International Conference on Robotics and Automation.
Best, G., Huang, S., & Fitch, R. (2018). Decentralised mission monitoring with spatiotemporal optimal stopping. In Proceedings of the IEEE/RSJ international conference on intelligent robots and systems.
Best, G., Faigl, J., & Fitch, R. (2018). Online planning for multi-robot active perception with self-organising maps. Autonomous Robots, 42(4), 715–738.CrossRef
Boddy, M., & Dean, T. L. (1989). Solving time-dependent planning problems. Providence: Department of Computer Science, Brown University.MATH
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.CrossRef
Chang, H. S., Fu, M. C., Hu, J., & Marcus, S. I. (2005). An adaptive sampling algorithm for solving Markov decision processes. Operations Research, 53(1), 126–139.MathSciNetCrossRefMATH
Choi, H., Brunet, L., & How, J. P. (2009). Consensus-based decentralized auctions for robust task allocation. IEEE Transactions on Robotics, 25(4), 912–926.CrossRef
Chopra, S., Notarstefano, G., Rice, M., & Egerstedt, M. (2017). Distributed version of the Hungarian method for a multirobot assignment. IEEE Transactions on Robotics, 33(4), 932–947.CrossRef
Deng, Q., Yu, J., & Wang, N. (2013). Cooperative task assignment of multiple heterogeneous unmanned aerial vehicles using a modified genetic algorithm with multi-type genes. Chinese Journal of Aeronautics, 26(5), 1238–1250.CrossRef
Desrosiers, J., Dumas, Y., Solomon, M. M., & Soumis, F. (1995). Chapter 2: Time constrained routing and scheduling. In M. O. Ball, T. L. Magnanti, C. L. Monma, & G. L. Nemhauser (Eds.), Handbooks in operations research and management science (Vol. 8, pp. 35–139). Elsevier
Faigl, J., Kulich, M., & Preucil, L. (2012). Goal assignment using distance cost in multi-robot exploration. In: Proceedings of the IEEE International Conference on Intelligent Robots and Systems (pp. 3741–3746).
Fukuda, T., Nakagawa, S., Kawauchi, Y., & Buss, M. (1989). Structure decision for self organising robots based on cell structures. In Proceedings of the IEEE international conference on robotics and automation.
Garivier, A., & Moulines, E. (2011). On upper-confidence bound policies for switching bandit problems. In Proceedings of the international conference on algorithmic learning theory (pp. 174–188). Berlin: Springer.
Gerkey, B. P., & Mataric, M. J. (2002). Sold!: Auction methods for multirobot coordination. IEEE Transactions on Robotics and Automation, 18(5), 758–768.CrossRef
Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE transactions on Systems Science and Cybernetics, 4(2), 100–107.CrossRef
Karp, R.M. (1992). On-line algorithms versus off-line algorithms: How much is it worth to know the future? In IFIP Congress (1) (Vol. 12, pp. 416–429).
Kartal, B., Godoy, J., Karamouzas, I., & Guy, S. J. (2015). Stochastic tree search with useful cycles for patrolling problems. In Proceedings of the IEEE international conference on robotics and automation (ICRA) (pp. 1289–1294).
Kocsis, L., & Szepesvári, C. (2006). Bandit based Monte-Carlo planning. In Proceedings of the European conference on machine learning (pp. 282–293).
Labbé, M., & Michaud, F. (2014). Online global loop closure detection for large-scale multi-session graph-based SLAM. In Proceedings of the IEEE/RSJ international conference on intelligent robots and systems (pp. 2661–2666).
Lan, X., & Schwager, M. (2016). Rapidly exploring random cycles: Persistent estimation of spatiotemporal fields with multiple sensing robots. IEEE Transactions on Robotics, 32(5), 1230–1244.CrossRef
Liu, Y., & Chopra, N. (2009). Controlled synchronization of robotic manipulators in the task space. In Proceedings of the ASME dynamic systems and control conference (pp. 443–450).
Liu, L., Michael, N., & Shell, D. A. (2015). Communication constrained task allocation with optimized local task swaps. Autonomous Robots, 39(3), 429–444.CrossRef
Liu, L., & Shell, D. A. (2012). Large-scale multi-robot task allocation via dynamic partitioning and distribution. Autonomous Robots, 33(3), 291–307.CrossRef
Luo, L., Chakraborty, N., & Sycara, K. (2012). Competitive analysis of repeated greedy auction algorithm for online multi-robot task assignment. In Proceedings of the IEEE international conference on robotics and automation (pp. 4792–4799).
Mathew, N., Smith, S., & Waslander, S. (2015). Multirobot rendezvous planning for recharging in persistent tasks. IEEE Transactions on Robotics, 31(1), 128–142.CrossRef
Meyer, J., Sendobry, A., Kohlbrecher, S., Klingauf, U., & von Stryk, O. (2012). Comprehensive simulation of quadrotor UAVs using ROS and Gazebo. In Proceedings of the international conference on simulation, modeling and programming for autonomous robots (SIMPAR).
Mills-Tettey, G. A., Stentz, A., & Dias, M. B. (2007). The dynamic Hungarian algorithm for the assignment problem with changing costs. Technical Report, Carnegie Mellon University.
Mitrović-Minić, S., Krishnamurti, R., & Laporte, G. (2004). Double-horizon based heuristics for the dynamic pickup and delivery problem with time windows. Transportation Research Part B: Methodological, 38(8), 669–685.CrossRef
Omidshafiei, S., Agha-Mohammadi, A., Amato, C., Liu, S., How, J. P., & Vian, J. (2017). Decentralized control of multi-robot partially observable Markov decision processes using belief space macro-actions. International Journal of Robotics Research, 36(2), 231–258.CrossRef
Petersen, K., Kleiner, A., & von Stryk, O. (2013). Fast task-sequence allocation for heterogeneous robot teams with a human in the loop. In Proceedings of the international conference on intelligent robots and systems (pp. 1648–1655).
Schaefers, L., & Platzner, M. (2015). Distributed Monte Carlo tree search: A novel technique and its application to computer Go. IEEE Transactions on Computational Intelligence and AI in Games, 7(4), 361–374.CrossRef
Shin, K. G., & Ramanathan, P. (1994). Real-time computing: A new discipline of computer science and engineering. Proceedings of the IEEE, 82(1), 6–24.CrossRef
Smith, R. N., Das, E. C., Heidarsson, H., Pereira, A. M., Arrichiello, F., Cetnic, I., et al. (2010). Usc CINAPS builds bridges. IEEE Robotics & Automation Magazine, 17(1), 20–30.CrossRef
Tumer, K., & Agogino, A. (2009). Multiagent learning for black box system reward functions. Advances in Complex Systems, 12(04n05), 475–492.CrossRefMATH
Yoshizoe, K., Kishimoto, A., Kaneko, T., Yoshimoto, H., & Ishikawa, Y. (2011). Scalable distributed Monte-Carlo tree search. In Proceedings of the fourth annual symposium on combinatorial search.
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
Zavlanos, M. M., Spesivtsev, L., & Pappas, G. J. (2008). A distributed auction algorithm for the assignment problem. In Proceedings of the IEEE conference on decision and control (pp. 1212–1217).
Zheng, X., & Koenig, S. (2009). K-swaps: Cooperative negotiation for solving task-allocation problems. In: Proceedings of the international joint conference on artificial intelligence (Vol. 9, pp. 373–378).
Zlot, R., Stentz, A., Dias, M. B., & Thayer, S. (2002). Multi-robot exploration controlled by a market economy. In Proceedings of the IEEE international conference on robotics and automation (Vol. 3, pp. 3016–3023).
Metadata
Title
Real-time distributed non-myopic task selection for heterogeneous robotic teams
Authors
Andrew J. Smith
Graeme Best
Javier Yu
Geoffrey A. Hollinger
Publication date
07-11-2018
Publisher
Springer US
Published in
Autonomous Robots / Issue 3/2019
Print ISSN: 0929-5593
Electronic ISSN: 1573-7527
DOI
https://doi.org/10.1007/s10514-018-9811-9

Other articles of this Issue 3/2019

Autonomous Robots 3/2019 Go to the issue

OriginalPaper

Coordination of multiple AGVs: a quadratic optimization method

OriginalPaper

Multi-robot grasp planning for sequential assembly operations

OriginalPaper

Attractor dynamics approach to joint transportation by autonomous robots: theory, implementation and validation on the factory floor

OriginalPaper

Robust proprioceptive grasping with a soft robot hand

OriginalPaper

Resilient distributed state estimation with mobile agents: overcoming Byzantine adversaries, communication losses, and intermittent measurements

EditorialNotes

Guest Editorial: Special section on “Foundations of resilience for networked robotic systems”