Skip to main content
Erschienen in: Autonomous Agents and Multi-Agent Systems 2/2017

24.08.2016

Interacting with team oriented plans in multi-robot systems

verfasst von: Alessandro Farinelli, Masoume M. Raeissi, Nicolo’ Marchi, Nathan Brooks, Paul Scerri

Erschienen in: Autonomous Agents and Multi-Agent Systems | Ausgabe 2/2017

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Team oriented plans have become a popular tool for operators to control teams of autonomous robots to pursue complex objectives in complex environments. Such plans allow an operator to specify high level directives and allow the team to autonomously determine how to implement such directives. However, the operators will often want to interrupt the activities of individual team members to deal with particular situations, such as a danger to a robot that the robot team cannot perceive. Previously, after such interrupts, the operator would usually need to restart the team plan to ensure its success. In this paper, we present an approach to encoding how interrupts can be smoothly handled within a team plan. Building on a team plan formalism that uses Colored Petri Nets, we describe a mechanism that allows a range of interrupts to be handled smoothly, allowing the team to efficiently continue with its task after the operator intervention. We validate the approach with an application of robotic watercraft and show improved overall efficiency. In particular, we consider a situation where several platforms should travel through a set of pre-specified locations, and we identify three specific cases that require the operator to interrupt the plan execution: (i) a boat must be pulled out; (ii) all boats should stop the plan and move to a pre-specified assembly position; (iii) a set of boats must synchronize to traverse a dangerous area one after the other. Our experiments show that the use of our interrupt mechanism decreases the time to complete the plan (up to 48 % reduction) and decreases the operator load (up to 80 % reduction in number of user actions). Moreover, we performed experiments with real robotic platforms to validate the applicability of our mechanism in the actual deployment of robotic watercraft.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Fußnoten
1
See for example CPN Tools [18].
 
2
With the term proxy we refer to a software-service that connects a specific boat with the rest of the system.
 
3
Recall from Sect. 3.1 that output events are associated to places and contain commands or requests for other modules. Input events are associated to transitions and encapsulate information that should be consumed by the module that receives such event.
 
4
Since computing the minimum path cost given a sequence of visit locations is in general NP-Hard here we use a simple nearest neighbor heuristic: the path is built incrementally by always selecting the next location as the one that is closest to the current location. At the beginning the current location is the boat position.
 
5
While in our case the number of proxy / generic tokens is always finite, we might not know this number before the plan starts. Hence we use the inhibitor arc to check whether a place is empty.
 
6
To check whether results are statistically significant we run a t-test with \(\alpha = 0.05\).
 
7
According to a t-test with \(\alpha = 0.05\), the total time gain for the reassignment versions of the interrupt versus standard plan is not statistically significant, so we do not report such metric in the table.
 
10
This video was accepted to the IJCAI 2015 video competition.
 
Literatur
1.
Zurück zum Zitat Berthomieu, B., Lime, D., Roux, O. H., & Vernadat, F. (2007). Reachability problems and abstract state spaces for time petri nets with stopwatches. Discrete Event Dynamic Systems, 17(2), 133–158.MathSciNetCrossRefMATH Berthomieu, B., Lime, D., Roux, O. H., & Vernadat, F. (2007). Reachability problems and abstract state spaces for time petri nets with stopwatches. Discrete Event Dynamic Systems, 17(2), 133–158.MathSciNetCrossRefMATH
2.
Zurück zum Zitat Casper, J., & Murphy, R. R. (2003). Human-robot interactions during the robot-assisted urban search and rescue response at the world trade center. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 33(3), 367–385.CrossRef Casper, J., & Murphy, R. R. (2003). Human-robot interactions during the robot-assisted urban search and rescue response at the world trade center. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 33(3), 367–385.CrossRef
3.
Zurück zum Zitat Philip, R, Cohen., & Hector, J, Levesque. (1991) Teamwork. Special Issue in cognitive Science and Artificial Intelligence, pages 487–512. Philip, R, Cohen., & Hector, J, Levesque. (1991) Teamwork. Special Issue in cognitive Science and Artificial Intelligence, pages 487–512.
4.
Zurück zum Zitat Collins, J., Bilot, C., Gini, M., & Mobasher, B. (2000) Mixed-initiative decision support in agent-based automated contracting. In Proceedings of the Fourth International Conference on Autonomous Agents, AGENTS ’00 (pp. 247–254). New York: ACM Collins, J., Bilot, C., Gini, M., & Mobasher, B. (2000) Mixed-initiative decision support in agent-based automated contracting. In Proceedings of the Fourth International Conference on Autonomous Agents, AGENTS ’00 (pp. 247–254). New York: ACM
5.
Zurück zum Zitat Costelha, H., & Lima, P. (2012). Robot task plan representation by petri nets: modelling, identification, analysis and execution. Autonomous Robots, 33(4), 337–360.CrossRef Costelha, H., & Lima, P. (2012). Robot task plan representation by petri nets: modelling, identification, analysis and execution. Autonomous Robots, 33(4), 337–360.CrossRef
6.
Zurück zum Zitat Desel, J., Wolfgang, R., & Grzegorz, R. (2004). Lectures on concurrency and Petri nets: Advances in Petri nets (Vol. 3098). New York: Springer.MATH Desel, J., Wolfgang, R., & Grzegorz, R. (2004). Lectures on concurrency and Petri nets: Advances in Petri nets (Vol. 3098). New York: Springer.MATH
7.
Zurück zum Zitat Farinelli, A., Marchi, N., Raeissi, MM., Brooks, N. & Scerri, P. (2015) A mechanism for smoothly handling human interrupts in team oriented plans. In Proceedings of the 2015 international conference on autonomous agents and multiagent systems, AAMAS ’15 (pp. 377–385). Richland, SC: International Foundation for Autonomous Agents and Multiagent Systems. Farinelli, A., Marchi, N., Raeissi, MM., Brooks, N. & Scerri, P. (2015) A mechanism for smoothly handling human interrupts in team oriented plans. In Proceedings of the 2015 international conference on autonomous agents and multiagent systems, AAMAS ’15 (pp. 377–385). Richland, SC: International Foundation for Autonomous Agents and Multiagent Systems.
8.
Zurück zum Zitat Delle Fave, F. M., Rogers, A., Xu, Z., Sukkarieh, S. & Jennings, N. (2012) Deploying the max-sum algorithm for coordination and task allocation of unmanned aerial vehicles for live aerial imagery collection. In Proceedings of the IEEE international conference on robotics and automation (ICRA) (pp. 469–476). Delle Fave, F. M., Rogers, A., Xu, Z., Sukkarieh, S. & Jennings, N. (2012) Deploying the max-sum algorithm for coordination and task allocation of unmanned aerial vehicles for live aerial imagery collection. In Proceedings of the IEEE international conference on robotics and automation (ICRA) (pp. 469–476).
9.
Zurück zum Zitat Ani, M., Hsieh, A. C., Keller, J. F., Chaimowicz, L., Grocholsky, B., Kumar, V., et al. (2007). Adaptive teams of autonomous aerial and ground robots for situational awareness. Journal of Field Robotics, 24(11–12), 991–1014. Ani, M., Hsieh, A. C., Keller, J. F., Chaimowicz, L., Grocholsky, B., Kumar, V., et al. (2007). Adaptive teams of autonomous aerial and ground robots for situational awareness. Journal of Field Robotics, 24(11–12), 991–1014.
10.
Zurück zum Zitat Jensen, K., & Kristensen, L. M. (2009). Coloured Petri nets: Modelling and validation of concurrent systems. Berlin: Springer.CrossRefMATH Jensen, K., & Kristensen, L. M. (2009). Coloured Petri nets: Modelling and validation of concurrent systems. Berlin: Springer.CrossRefMATH
11.
Zurück zum Zitat Kaminka, G. A. & Frenkel, I. (2005) Flexible teamwork in behavior-based robots. In Proceedings, the twentieth national conference on artificial intelligence and the seventeenth innovative applications of artificial intelligence conference (pp. 108–113). Pittsburgh, July 9–13, 2005. Kaminka, G. A. & Frenkel, I. (2005) Flexible teamwork in behavior-based robots. In Proceedings, the twentieth national conference on artificial intelligence and the seventeenth innovative applications of artificial intelligence conference (pp. 108–113). Pittsburgh, July 9–13, 2005.
12.
Zurück zum Zitat King, J., Pretty, R. K., & Gosine, R. G. (2003). Coordinated execution of tasks in a multiagent environment. IEEE Transactions on Systems, Man, and Cybernetics, Part A, 33(5), 615–619.CrossRef King, J., Pretty, R. K., & Gosine, R. G. (2003). Coordinated execution of tasks in a multiagent environment. IEEE Transactions on Systems, Man, and Cybernetics, Part A, 33(5), 615–619.CrossRef
13.
Zurück zum Zitat Marciano, L. (2013). CPNP: Colored petri net representation of single-robot and multi-robot plans. Master’s thesis, Bar Ilan University. Marciano, L. (2013). CPNP: Colored petri net representation of single-robot and multi-robot plans. Master’s thesis, Bar Ilan University.
14.
Zurück zum Zitat Marzougui, B., Hassine, K., & Barkaoui, K. (2010). A new formalism for modeling a multi agent systems: Agent petri nets. JSEA, 3(12), 1118–1124.CrossRef Marzougui, B., Hassine, K., & Barkaoui, K. (2010). A new formalism for modeling a multi agent systems: Agent petri nets. JSEA, 3(12), 1118–1124.CrossRef
15.
Zurück zum Zitat Murata, T. (1989). Petri nets: Properties, analysis and applications. Proceedings of the IEEE, 77(4), 541–580.CrossRef Murata, T. (1989). Petri nets: Properties, analysis and applications. Proceedings of the IEEE, 77(4), 541–580.CrossRef
16.
Zurück zum Zitat Nourbakhsh, I. R., Sycara, K., Koes, M., Yong, M., Lewis, M., & Burion, S. (2005). Human-robot teaming for search and rescue. IEEE Pervasive Computing, 4(1), 72–78.CrossRef Nourbakhsh, I. R., Sycara, K., Koes, M., Yong, M., Lewis, M., & Burion, S. (2005). Human-robot teaming for search and rescue. IEEE Pervasive Computing, 4(1), 72–78.CrossRef
17.
Zurück zum Zitat Peterson, J. L. (1981). Petri net theory and the modeling of systems. PRENTICE-HALL, INC., ENGLEWOOD CLIFFS, NJ 07632, 1981, 290. Peterson, J. L. (1981). Petri net theory and the modeling of systems. PRENTICE-HALL, INC., ENGLEWOOD CLIFFS, NJ 07632, 1981, 290.
18.
Zurück zum Zitat Ratzer, A. V., Wells, L., Lassen, H. M., Laursen, M., Qvortrup. J. F., Stissing, M. S., Westergaard, M., Christensen, C. & Jensen, K. (2003). Cpn tools for editing, simulating, and analysing coloured petri nets. In Applications and theory of Petri nets (pp. 450–462). Berlin: Springer. Ratzer, A. V., Wells, L., Lassen, H. M., Laursen, M., Qvortrup. J. F., Stissing, M. S., Westergaard, M., Christensen, C. & Jensen, K. (2003). Cpn tools for editing, simulating, and analysing coloured petri nets. In Applications and theory of Petri nets (pp. 450–462). Berlin: Springer.
19.
Zurück zum Zitat Scerri, P., Kannan, B., Velagapudi, P., Macarthur, K., Stone, P., Taylor, M., Dolan, J., Farinelli, A., Chapman, A. & Dias, B. et al. (2012). Flood disaster mitigation: A real-world challenge problem for multi-agent unmanned surface vehicles. In Advanced agent technology (pp. 252–269). Berlin: Springer. Scerri, P., Kannan, B., Velagapudi, P., Macarthur, K., Stone, P., Taylor, M., Dolan, J., Farinelli, A., Chapman, A. & Dias, B. et al. (2012). Flood disaster mitigation: A real-world challenge problem for multi-agent unmanned surface vehicles. In Advanced agent technology (pp. 252–269). Berlin: Springer.
20.
Zurück zum Zitat Scerri, P., Pynadath, D. V., & Tambe, M. (2002). Towards adjustable autonomy for the real-world. Journal of AI Research (JAIR), 17, 171–228.MathSciNetMATH Scerri, P., Pynadath, D. V., & Tambe, M. (2002). Towards adjustable autonomy for the real-world. Journal of AI Research (JAIR), 17, 171–228.MathSciNetMATH
21.
Zurück zum Zitat Simmons, R., & Apfelbaum, D. (1998). A task description language for robot control. In Proceedings of IEEE/RSJ international conference on intelligent robots and systems (Vol. 3, pp. 1931–1937) Oct 1998. Simmons, R., & Apfelbaum, D. (1998). A task description language for robot control. In Proceedings of IEEE/RSJ international conference on intelligent robots and systems (Vol. 3, pp. 1931–1937) Oct 1998.
22.
Zurück zum Zitat Barber, K. S., Anuj, G., & Martin, C. E. (2000). Dynamic adaptive autonomy in multi-agent systems. Journal of Experimental & Theoretical Artificial Intelligence, 12(2), 129–147.CrossRefMATH Barber, K. S., Anuj, G., & Martin, C. E. (2000). Dynamic adaptive autonomy in multi-agent systems. Journal of Experimental & Theoretical Artificial Intelligence, 12(2), 129–147.CrossRefMATH
23.
Zurück zum Zitat Sycara, K., Giampapa, J. A., Langley, B. K., & Paolucci, M. (2003). The retsina mas, a case study. In A. Garcia, C. Lucena, F. Zambonelli, A. Omici, & J. Castro (Eds.), Software engineering for large-scale multi-agent systems: Research issues and practical applications (Vol. LNCS 2603, pp. 232–250). Berlin: Springer.CrossRef Sycara, K., Giampapa, J. A., Langley, B. K., & Paolucci, M. (2003). The retsina mas, a case study. In A. Garcia, C. Lucena, F. Zambonelli, A. Omici, & J. Castro (Eds.), Software engineering for large-scale multi-agent systems: Research issues and practical applications (Vol. LNCS 2603, pp. 232–250). Berlin: Springer.CrossRef
24.
Zurück zum Zitat Tambe, M. (1997). Towards flexible teamwork. Journal of Artificial Intelligence Research, 7, 83–124. Tambe, M. (1997). Towards flexible teamwork. Journal of Artificial Intelligence Research, 7, 83–124.
25.
Zurück zum Zitat Tovey, C., Lagoudakis, M., Jain, S., & Koenig, S. (2005). The generation of bidding rules for auction-based robot coordination. In F. Schneider, L. Parker, & A. Schultz (Eds.), Multi-robot systems: From swarms to intelligent automata (Vol. 3). The Netherlands: Springer. Tovey, C., Lagoudakis, M., Jain, S., & Koenig, S. (2005). The generation of bidding rules for auction-based robot coordination. In F. Schneider, L. Parker, & A. Schultz (Eds.), Multi-robot systems: From swarms to intelligent automata (Vol. 3). The Netherlands: Springer.
26.
Zurück zum Zitat Upadhyay, P. D., Acharya, S., & Dutta, A. (2013). Task petri nets for agent based computing. INFOCOMP Journal of Computer Science, 12(1), 24–35. Upadhyay, P. D., Acharya, S., & Dutta, A. (2013). Task petri nets for agent based computing. INFOCOMP Journal of Computer Science, 12(1), 24–35.
27.
Zurück zum Zitat Abhinav, V., Velagapudi, P., Kannan, B., Tomaszewski, C., Kantor, G. & Scerri, P. (2014). Development of a low cost multi-robot autonomous marine surface platform. In Field and Service Robotics (pp. 643–658). Berlin: Springer. Abhinav, V., Velagapudi, P., Kannan, B., Tomaszewski, C., Kantor, G. & Scerri, P. (2014). Development of a low cost multi-robot autonomous marine surface platform. In Field and Service Robotics (pp. 643–658). Berlin: Springer.
28.
Zurück zum Zitat Veloso, M. M., Pollack, M. E., & Cox, M. T. (1998). Rationale-based monitoring for continuous planning in dynamic environments. In Proceedings of the fourth international conference on artificial intelligence planning systems (pp. 171–179). Pittsburgh, PA, June 1998. Veloso, M. M., Pollack, M. E., & Cox, M. T. (1998). Rationale-based monitoring for continuous planning in dynamic environments. In Proceedings of the fourth international conference on artificial intelligence planning systems (pp. 171–179). Pittsburgh, PA, June 1998.
29.
Zurück zum Zitat Wang, F. Y., Kyriakopoulos, K. J., Tsolkas, A., & Saridis, G. N. (1991). A petri-net coordination model for an intelligent mobile robot. IEEE Transactions on Systems, Man and Cybernetics, 21(4), 777–789.CrossRef Wang, F. Y., Kyriakopoulos, K. J., Tsolkas, A., & Saridis, G. N. (1991). A petri-net coordination model for an intelligent mobile robot. IEEE Transactions on Systems, Man and Cybernetics, 21(4), 777–789.CrossRef
30.
Zurück zum Zitat Wang, J. & Lewis, M. (2007) Human control for cooperating robot teams. In 2007 2nd ACM/IEEE international conference on human-robot interaction (HRI) (pp. 9–16). March 2007. Wang, J. & Lewis, M. (2007) Human control for cooperating robot teams. In 2007 2nd ACM/IEEE international conference on human-robot interaction (HRI) (pp. 9–16). March 2007.
31.
Zurück zum Zitat Xu, D., Volz, R., Loerger, T. & Yen, J. (2002). Modeling and verifying multi-agent behaviors using predicate/transition nets. In Proceedings of the 14th international conference on Software engineering and knowledge engineering (pp. 193–200). ACM, 2002. Xu, D., Volz, R., Loerger, T. & Yen, J. (2002). Modeling and verifying multi-agent behaviors using predicate/transition nets. In Proceedings of the 14th international conference on Software engineering and knowledge engineering (pp. 193–200). ACM, 2002.
32.
Zurück zum Zitat Ziparo, V. A., Iocchi, L., Lima, P. U., Nardi, D., & Palamara, P. F. (2011). Petri net plans. Autonomous Agents and Multi-Agent Systems, 23(3), 344–383.CrossRef Ziparo, V. A., Iocchi, L., Lima, P. U., Nardi, D., & Palamara, P. F. (2011). Petri net plans. Autonomous Agents and Multi-Agent Systems, 23(3), 344–383.CrossRef
Metadaten
Titel
Interacting with team oriented plans in multi-robot systems
verfasst von
Alessandro Farinelli
Masoume M. Raeissi
Nicolo’ Marchi
Nathan Brooks
Paul Scerri
Publikationsdatum
24.08.2016
Verlag
Springer US
Erschienen in
Autonomous Agents and Multi-Agent Systems / Ausgabe 2/2017
Print ISSN: 1387-2532
Elektronische ISSN: 1573-7454
DOI
https://doi.org/10.1007/s10458-016-9344-6

Weitere Artikel der Ausgabe 2/2017

Autonomous Agents and Multi-Agent Systems 2/2017 Zur Ausgabe