Skip to main content
Top

2016 | OriginalPaper | Chapter

Online Interaction of a Human Supervisor with Multi-Robot Task Allocation

Authors : Karen Kurowski, Oskar von Stryk

Published in: Intelligent Autonomous Systems 13

Publisher: Springer International Publishing

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

search-config
loading …

Abstract

In this paper, an approach is presented that allows a human supervisor to efficiently interact with task allocation in a multi-robot team (MRTA). The interaction is based on online modification of the setting of the employed MRTA optimization algorithm during its computation. For the example of a computationally expensive mixed-integer linear programming algorithm it is demonstrated how to achieve up to optimal solution quality, while simultaneously reducing the required calculation time compared to a fully autonomous optimization. The supervisor is enabled to rate feasible, intermediate solutions based on objective or subjective quality criteria and personal expertise. In that way, also suboptimal solutions can be chosen to be satisfactory, and the solver can be terminated without the need to wait for the completion of the computation of the optimal solution. An event-based communication concept with queries is used as an efficient means of implementation of the interaction. Furthermore, the supervisor can support the MRTA solver in finding good solutions by defining crucial parts of the solution structure. These intuitive commands are internally translated into constraints and are added to the problem as lazy constraints. This combination of human expertise and state-of-the-art optimization algorithms allows to achieve up to potentially optimal task allocation in much shorter time.

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!

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!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literature
1.
go back to reference S. da Costa Botelho and R. Alami. M+ : a scheme for multi-robot cooperation through negotiated task allocation and achievement. In Proc. of the IEEE Int. Conf. on Robotics and Automation (ICRA), pages 1234–1239, 1999. S. da Costa Botelho and R. Alami. M+ : a scheme for multi-robot cooperation through negotiated task allocation and achievement. In Proc. of the IEEE Int. Conf. on Robotics and Automation (ICRA), pages 1234–1239, 1999.
2.
go back to reference M. B. Dias and A. Stentz. A free market architecture for distributed control of a multirobot system. In 6th Int. Conf. on Intelligent Autonomous Systems (IAS-6), pages 115–122, 2000. M. B. Dias and A. Stentz. A free market architecture for distributed control of a multirobot system. In 6th Int. Conf. on Intelligent Autonomous Systems (IAS-6), pages 115–122, 2000.
3.
go back to reference M. B. Dias and A. T. Stentz. Opportunistic optimization for market-based multirobot control. In Proc. of the 2002 IEEE/RSJ Int.l Conf. on Intelligent Robots and Systems (IROS ’02), volume 3, pages 2714–2720, 2002. M. B. Dias and A. T. Stentz. Opportunistic optimization for market-based multirobot control. In Proc. of the 2002 IEEE/RSJ Int.l Conf. on Intelligent Robots and Systems (IROS ’02), volume 3, pages 2714–2720, 2002.
4.
go back to reference D. Gale. The theory of linear economic models. McGraw-Hill, New York, 1960. D. Gale. The theory of linear economic models. McGraw-Hill, New York, 1960.
5.
go back to reference B. P. Gerkey and M. J. Mataric. Sold!: Auction methods for multirobot coordination. IEEE Transactions on Robotics and Automation, 18(5):758–768, 2002. B. P. Gerkey and M. J. Mataric. Sold!: Auction methods for multirobot coordination. IEEE Transactions on Robotics and Automation, 18(5):758–768, 2002.
6.
go back to reference B. P. Gerkey and M. J. Mataric. A formal analysis and taxonomy of task allocation in multi-robot systems. The Int. Journal of Robotics Research, 23(9):939–954, 2004. B. P. Gerkey and M. J. Mataric. A formal analysis and taxonomy of task allocation in multi-robot systems. The Int. Journal of Robotics Research, 23(9):939–954, 2004.
8.
go back to reference B. Kalyanasundaram and K. Pruhs. Online weighted matching. Journal of Algorithms, 14(3):478–488, 1993. B. Kalyanasundaram and K. Pruhs. Online weighted matching. Journal of Algorithms, 14(3):478–488, 1993.
9.
go back to reference M. Koes, I. Nourbakhsh, and K. Sycara. Constraint optimization coordination architecture for search and rescue robotics. In Proc. of the IEEE Int. Conf. on Robotics and Automation (ICRA), pages 3977–3982, 2006. M. Koes, I. Nourbakhsh, and K. Sycara. Constraint optimization coordination architecture for search and rescue robotics. In Proc. of the IEEE Int. Conf. on Robotics and Automation (ICRA), pages 3977–3982, 2006.
10.
go back to reference C. R. Kube and H. Zhang. Collective robotics: from social insects to robots. Adapt. Behav., 2:189–218, September 1993. C. R. Kube and H. Zhang. Collective robotics: from social insects to robots. Adapt. Behav., 2:189–218, September 1993.
11.
go back to reference H. W. Kuhn. The hungarian method for the assignment problem. Naval Research Logistics Quarterly, 2:83–97, 1955. H. W. Kuhn. The hungarian method for the assignment problem. Naval Research Logistics Quarterly, 2:83–97, 1955.
12.
go back to reference E. L. Lawler, J. K. Lenstra, A. R. Kan, and D. B. Shmoys, editors. The Traveling Salesman Problem: a guided tour of combinatorial optimization. Wiley, 1985. E. L. Lawler, J. K. Lenstra, A. R. Kan, and D. B. Shmoys, editors. The Traveling Salesman Problem: a guided tour of combinatorial optimization. Wiley, 1985.
13.
go back to reference R. Parasuraman, R. Molloy, and I. L. Singh. Performance consequences of automation-induced “complacency”. The Int. Journal of Aviation Psychology, 3(1):1–23, 1993. R. Parasuraman, R. Molloy, and I. L. Singh. Performance consequences of automation-induced “complacency”. The Int. Journal of Aviation Psychology, 3(1):1–23, 1993.
14.
go back to reference L. E. Parker. Alliance: An architecture for fault tolerant multi-robot cooperation. IEEE Transactions on Robotics and Automation, 14(2):220–240, April 1998. L. E. Parker. Alliance: An architecture for fault tolerant multi-robot cooperation. IEEE Transactions on Robotics and Automation, 14(2):220–240, April 1998.
15.
go back to reference K. Petersen and O. von Stryk. An event-based communication concept for human supervision of autonomous robot teams. Int. Journal on Advances in Intelligent Systems, 4(3&4):357–369, 2011. K. Petersen and O. von Stryk. An event-based communication concept for human supervision of autonomous robot teams. Int. Journal on Advances in Intelligent Systems, 4(3&4):357–369, 2011.
16.
go back to reference K. Petersen, A. Kleiner, and O. von Stryk. Fast task-sequence allocation for heterogeneous robot teams with a human in the loop. In Proc. of the IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS), pages 1648–1655, 2013. K. Petersen, A. Kleiner, and O. von Stryk. Fast task-sequence allocation for heterogeneous robot teams with a human in the loop. In Proc. of the IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS), pages 1648–1655, 2013.
17.
go back to reference C. Reinl and O. von Stryk. Optimal control of multi-vehicle systems under communication constraints using mixed-integer linear programming. In Proc. of the First Int. Conf. on Robot Communication and Coordination (RoboComm), 2007. C. Reinl and O. von Stryk. Optimal control of multi-vehicle systems under communication constraints using mixed-integer linear programming. In Proc. of the First Int. Conf. on Robot Communication and Coordination (RoboComm), 2007.
18.
go back to reference S. Sariel, T. Balch, and N. Erdogan. Incremental multi-robot task selection for resource constrained and interrelated tasks. In Proc. of the 2007 IEEE/RSJ Int. Conf. on Intelligent Robots and Systems, 2007. S. Sariel, T. Balch, and N. Erdogan. Incremental multi-robot task selection for resource constrained and interrelated tasks. In Proc. of the 2007 IEEE/RSJ Int. Conf. on Intelligent Robots and Systems, 2007.
19.
go back to reference R. G. Smith. The contract net protocol: High-level communication and control in a distributed problem solver. IEEE Transactions on Computers, C-29(12):1104–1113, Dec. 1980. R. G. Smith. The contract net protocol: High-level communication and control in a distributed problem solver. IEEE Transactions on Computers, C-29(12):1104–1113, Dec. 1980.
20.
go back to reference M. Tambe. Towards flexible teamwork. Journal of Artificial Intelligence Research, 7:83–124, 1997. M. Tambe. Towards flexible teamwork. Journal of Artificial Intelligence Research, 7:83–124, 1997.
Metadata
Title
Online Interaction of a Human Supervisor with Multi-Robot Task Allocation
Authors
Karen Kurowski
Oskar von Stryk
Copyright Year
2016
DOI
https://doi.org/10.1007/978-3-319-08338-4_70

Premium Partner