Abstract
The work presented here investigates the impact of certain environmental parameters on the performance of a multi-robot team conducting exploration tasks. Experiments were conducted with physical robots and simulated robots, and a diverse set of metrics was computed. The experiments were structured to highlight several factors: (a) single-robot versus multi-robot tasks; (b) independent versus dependent (or “constrained”) tasks; and (c) static versus dynamic task allocation modes. Four different task allocation mechanisms were compared, in two different exploration scenarios, with two different starting configurations for the robot team. The results highlight the distinctions between parameterised environments (characterised by the factors above, the robots’ starting positions and the exploration scenario) and the effectiveness of each task allocation mechanism, illustrating that some mechanisms perform statistically better in particular environment parameterisations.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Note that we compute distance not by looking at the shortest distances between the task locations, but is (as closely as we can establish) the actual distance travelled by the robots during task execution. We collect frequent position updates, compute the Euclidean distance between successive positions, and sum these.
- 2.
Though bidding and winner determination are managed centrally, there is no centralised control in the usual sense. The auction could also be distributed among the robots as in [4].
- 3.
References
Berhault, M., Huang, H., Keskinocak, P., Koenig, S., Elmaghraby, W., Griffin, P.M., Kleywegt, A.: Robot exploration with combinatorial auctions. In: IROS (2003)
Bonabeau, E., Dorigo, M., Théraulaz, G.: Swarm Intelligence: From Natural to Artificial Systems. Oxford University Press, New York (1999)
Dias, M.B., Zlot, R., Kalra, N., Stentz, A.: Market-based multirobot coordination: a survey and analysis. Proc. IEEE 94(7), 1257–1270 (2006)
Ezhilchelvan, P., Morgan, G.: A dependable distributed auction system: architecture and an implementation framework. In: International Symposium on Autonomous Decentralized Systems (2001)
Gerkey, B., Vaughan, R.T., Howard, A.: The player/stage project: tools for multi-robot and distributed sensor systems. In: International Conference on Advanced Robotics (2003)
Gerkey, B.P., Mataríc, M.J.: A formal analysis and taxonomy of task allocation in multi-robot systems. Int. J. Robot. Res. 23(9), 939–954 (2004)
Golfarelli, M., Maio, D., Rizzi, S.: A task-swap negotiation protocol based on the contract net paradigm. TR-005-97, DEIS/CSITE/Università di Bologna (1997)
Gombolay, M., Wilcox, R., Shah, J.A.: Fast scheduling of multi-robot teams with temporospatial constraints. In: RSS (2013)
Hart, P., Nilsson, N., Raphael, B.: A formal basis for the heuristic determination of minimal cost paths. IEEE Trans. Sys. Sci. Cybern. 4(2), 100–107 (1968)
Koenig, S., Keskinocak, P., Tovey, C.: Progress on agent coordination with cooperative auctions. In: AAAI (2010)
Koenig, S., Tovey, C., Lagoudakis, M., Kempe, D., Keskinocak, P., Kleywegt, A., Meyerson, A., Jain, S.: The power of sequential single-item auctions for agent coordination. In: AAAI (2006)
Korsah, G.A., Stentz, A., Dias, M.B.: A comprehensive taxonomy for multi-robot task allocation. Int J. Robot. Res. 32(12), 1495–1512 (2013)
Kraus, S.: Automated negotiation and decision making in multiagent environments. In: Luck, M., Mařík, V., Štěpánková, O., Trappl, R. (eds.) ACAI 2001 and EASSS 2001. LNCS (LNAI), vol. 2086, pp. 150–172. Springer, Heidelberg (2001)
Lagoudakis, M., Berhault, M., Koenig, S., Keskinocak, P., Kelywegt, A.: Simple auctions with performance guarantees for MRTA. In: IROS (2004)
Lagoudakis, M., Markakis, V., Kempe, D., Keskinocak, P., Koenig, S., Kleywegt, A., Tovey, C., Meyerson, A., Jain, S.: Auction-based multi-robot routing. In: RSS (2005)
Landén, D., Heintz, F., Doherty, P.: Complex task allocation in mixed-initiative delegation: a UAV case study. In: Desai, N., Liu, A., Winikoff, M. (eds.) PRIMA 2010. LNCS, vol. 7057, pp. 288–303. Springer, Heidelberg (2012)
Luo, L., Chakraborty, N., Sycara, K.: Multi-robot assignment algorithm for tasks with set precedence constraints. In: ICRA (2011)
Mataric, M., Sukhatme, G., Ostergaard, E.: Multi-robot task allocation in uncertain environments. Auton. Robots 14(2–3), 255–263 (2003)
Nanjanath, M., Gini, M.: Repeated auctions for robust task execution by a robot team. Robot. Auton. Syst. 58(7), 900–909 (2010)
Nunes, E., Gini, M.: Multi-robot auctions for allocation of tasks with temporal constraints. In: AAAI (2015)
Özgelen, A.T., Schneider, E., Sklar, E.I., Costantino, M., Epstein, S.L., Parsons, S.: A first step toward testing multiagent coordination mechanisms on multirobotteams. In: AAMAS Workshop: ARMS (2013)
Quigley, M., Conley, K., Gerkey, B.P., Faust, J., Foote, T., Leibs, J., Wheeler, R., Ng, A.Y.: Ros: an open-source robot operating system. In: ICRA Workshop: Open Source Software (2009)
Sariel, S., Balch, T.: Efficient bids on task allocation for multi-robot exploration. In: FLAIRS (2006)
Schneider, E., Balas, O., Özgelen, A.T., Sklar, E.I., Parsons, S.: Evaluating auction-based task allocation in multi-robot teams. In: AAMAS Workshop: ARMS (2014)
Schneider, E., Sklar, E.I., Parsons, S., Özgelen, A.T.: Auction-based task allocation for multi-robot teams in dynamic environments. In: Dixon, C., Tuyls, K. (eds.) TAROS 2015. LNCS (LNAI), vol. 9287, pp. 246–257. Springer, Switzerland (2015)
Schoenig, A., Pagnucco, M.: Evaluating sequential single-item auctions for dynamic task allocation. In: Li, J. (ed.) AI 2010. LNCS, vol. 6464, pp. 506–515. Springer, Heidelberg (2010)
Smith, R.G.: The contract net protocol: high-level communication and control in a distributed problem solver. In: Distributed Artificial Intelligence (1988)
Tovey, C., Lagoudakis, M.G., Jain, S., Koenig, S.: Generation of bidding rules for auction-based robot coordination. In: International Workshop on Multi-Robot Systems (2005)
Wellman, M.P., Wurman, P.R.: Market-aware agents for a multiagent world. Robot. Auton. Syst. 24, 115–125 (1998)
Zlot, R., Stentz, A., Dias, M.B., Thayer, S.: Multi-robot exploration controlled by a market economy. In: ICRA (2002)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
Schneider, E., Sklar, E.I., Parsons, S. (2016). Evaluating Multi-Robot Teamwork in Parameterised Environments. In: Alboul, L., Damian, D., Aitken, J. (eds) Towards Autonomous Robotic Systems. TAROS 2016. Lecture Notes in Computer Science(), vol 9716. Springer, Cham. https://doi.org/10.1007/978-3-319-40379-3_32
Download citation
DOI: https://doi.org/10.1007/978-3-319-40379-3_32
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-40378-6
Online ISBN: 978-3-319-40379-3
eBook Packages: Computer ScienceComputer Science (R0)