Hostname: page-component-cd9895bd7-fscjk Total loading time: 0 Render date: 2024-12-27T06:39:07.620Z Has data issue: false hasContentIssue false
  • English
  • Français

Two Adaptive Communication Methods for Multi-Robot Collision Avoidance

Published online by Cambridge University Press:  14 January 2019

Avi Rosenfeld
Avi Rosenfeld*
Affiliation:
Department of Computer Science, Jerusalem College of Technology, Jerusalem, Israel
*
*Corresponding author. E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Summary

Designers of robotic groups are faced with the formidable task of creating effective coordination architectures that can deal with collisions due to changing environment conditions and hardware failures. Communication between robots is a mechanism that can at times be helpful in such systems, but can also create a time, energy, or computation overhead that reduces performance. In dealing with this issue, different communication schemes have been proposed ranging from those without any explicit communication, localized algorithms, and centralized or global communicative methods. Finding the optimal communication act is typically an intractable problem in real-world problems. As a result, we argue that at times group designers should use computationally bounded team communication approaches. We propose two such approaches: an algorithm selection approach to communication whereby robots choose between a known group of communication schemes and a parameterized communication framework whereby robots can reason about how large a communication radius is needed for a given problem. Both solutions use a novel coordination cost measure, combined coordination costs, to find the appropriate level of communication within such groups. Robots can then use this measure to create adaptive communication approaches that select between communication approaches as needed during task execution. We validated this approach through conducting extensive experiments in a canonical robotic foraging domain and found that robotic groups using these adaptive methods were able to significantly increase their productivity compared to teams that used only one type of communication scheme.

Keywords

Control of robotic systemsMulti-robot systemsNavigationRobot dynamicsCollision avoidance
Type
Articles
Information
Robotica , Volume 37 , Issue 5 , May 2019 , pp. 851 - 867
Copyright
Copyright © Cambridge University Press 2019 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Dudek, G., Jenkin, M. and Milios, E., “A taxonomy for multi-agent robotics,” Robot Teams: From Diversity to Polymorphism (Balch, T. and Parker, L. E., eds.), vol. 3 (A K Peters, Natick, MA, 2002), pp. 3–22.Google Scholar
Goldberg, D. and Matarić, M., “Design and Evaluation of Robust Behavior-Based Controllers for Distributed Multi-robot Collection Tasks,” In: Robot Teams: From Diversity to Polymorphism (A K Peters/CRC Press, 2001) pp. 315–344.Google Scholar
Jäger, M. and Nebel, B., “Decentralized Collision Avoidance, Deadlock Detection, and Deadlock Resolution for Multiple Mobile Robots,” IROS (2001) pp. 1213–1219.Google Scholar
Hoy, M., Matveev, A. S. and Savkin, A. V., “Algorithms for collision-free navigation of mobile robots in complex cluttered environments: A survey,” Robotica 33, 463–497 (2015).CrossRefGoogle Scholar
Colby, M., Chung, J. and Tumer, K., “Implicit Adaptive Multi-robot Coordination in Dynamic Environments,” 2015 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2015) (2015) pp. 5168–5173.CrossRefGoogle Scholar
Couceiro, M. S., Figueiredo, C. M., Portugal, D., Rocha, R. P. and Ferreira, N. M. F., “Initial Deployment of a Robotic Team - A Hierarchical Approach Under Communication Constraints Verified on Low-Cost Platforms,” IROS (2012) pp. 4614–4619.Google Scholar
Liu, L., Michael, N. and Shell, D. A., “Communication constrained task allocation with optimized local task swaps,” Auton. Rob. 39(3), 429–444 (2015).CrossRefGoogle Scholar
Mezei, I., Lukic, M., Malbasa, V. and Stojmenovic, I., “Auctions and iMesh based task assignment in wireless sensor and actuator networks,” Comput. Commun. 36(9), 979–987 (2013).CrossRefGoogle Scholar
Nazarzehi, V. and Savkin, A. V., “Distributed self-deployment of mobile wireless 3D robotic sensor networks for complete sensing coverage and forming specific shapes,” Robotica 36(1), 1–18 (2018).CrossRefGoogle Scholar
Sen, S., Sekaran, M. and Hale, J., “Learning to Coordinate without Sharing Information,” Proceedings of the Twelfth National Conference on Artificial Intelligence (1994) pp. 426–431.Google Scholar
Stone, P. and Veloso, M., “Task decomposition, dynamic role assignment, and low-bandwidth communication for real-time strategic teamwork,” Artif. Intell. 110(2), 241–273 (1999).CrossRefGoogle Scholar
Tews, A., “Adaptive Multi-robot Coordination for Highly Dynamic Environments,” CIMCA (2001).Google Scholar
Yan, Y. and Mostofi, Y., “Co-optimization of communication and motion planning of a robotic operation under resource constraints and in fading environments,” IEEE Trans. Wireless Commun. 12(4), 1562–1572 (2013).CrossRefGoogle Scholar
Yan, Y. and Mostofi, Y., “To go or not to go on energy-aware and communication-aware robotic operation,” IEEE Trans. Control Netw. Syst. 1(3), 218–231 (2014).CrossRefGoogle Scholar
Zhang, K., Jr.Collins, E. G. and Shi, D., “Centralized and distributed task allocation in multi-robot teams via a stochastic clustering auction,” ACM Trans. Auton. Adapt. Syst. 7(2), 21:1–21:22 (2012).CrossRefGoogle Scholar
Goldberg, D. and Matarić, M., “Interference as a Tool for Designing and Evaluating Multi-robot Controllers,” AAAI/IAAI (1997) pp. 637–642.Google Scholar
Rosenfeld, A., Kaminka, G., Kraus, S. and Shehory, O., “A study of mechanisms for improving robotic group performance,” Artif. Intell. J. (AIJ) 172(6–7), 633–655 (2008).CrossRefGoogle Scholar
Rosenfeld, A., Kaminka, G. A. and Kraus, S., “Adaptive Robot Coordination Using Interference Metrics,” Proceedings of the European Conference on Artificial Intelligence (ECAI) (2004) pp. 910–916.Google Scholar
Anderson, M. and Papanikolopoulos, N., “Implicit cooperation strategies for multi-robot search of unknown areas,” J. Intell. Rob. Syst. 53(4), 381–397 (2008).CrossRefGoogle Scholar
Kaminka, G. A. and Glick, R., “Towards Robust Multi-robot Formations,” ICRA-06 (2006) pp. 582–588.Google Scholar
Knepper, R. A., Mavrogiannis, C. I., Proft, J. and Liang, C., “Implicit Communication in a Joint Action,” Proceedings of the 2017 ACM/IEEE International Conference on Human-Robot Interaction, HRI ’17 (2017) pp. 283–292.Google Scholar
Knezevic, A., Nguyen, Q., Tran, J. A., Ghosh, P., Sakulkar, P., Krishnamachari, B. and Annavaram, M., “CIRCE - A Runtime Scheduler for DAG-Based Dispersed Computing: DEMO,” SEC 2017 (2017) pp. 31:1–31:2.Google Scholar
Matarić, M. J., “Using Communication to Reduce Locality in Multi-robot Learning,” AAAI/IAAI (1997) pp. 643–648.Google Scholar
Prorok, A., Bahr, A. and Martinoli, A., “Low-Cost Collaborative Localization for Large-Scale Multi-robot Systems,” 2012 IEEE International Conference On Robotics And Automation (ICRA) (2012) pp. 4236–4241.CrossRefGoogle Scholar
Wellman, B. L., Dawson, S. and Anderson, M., “Multirobot Coverage Using Observation-Based Cooperation with Backtracking,” Proceedings of the Twenty-Sixth International Florida Artificial Intelligence Research Society Conference, FLAIRS (2013).Google Scholar
Yan, Z., Jouandeau, N. and Cherif, A. A., “A survey and analysis of multi-robot coordination,” Int. J. Adv. Rob. Syst. 10, 1–18 (2013).Google Scholar
Yoshida, E., Arai, T., Yamamoto, M. and Ota, J., “Local communication of multiple mobile robots: Design of optimal communication area for cooperative tasks,” J. Rob. Syst. 15(7), 407–427 (1998).3.0.CO;2-Q>CrossRefGoogle Scholar
Balch, T. and Arkin, R. C., “Behavior-based formation control for multirobot teams,” IEEE Trans. Rob. Autom. 14(6), 926–939 (1998).CrossRefGoogle Scholar
Pynadath, D. V. and Tambe, M., “The communicative multiagent team decision problem: Analyzing teamwork theories and models,” JAIR 16, 389–423 (2002).CrossRefGoogle Scholar
Lesser, V., Decker, K., Wagner, T., Carver, N., Garvey, A., Horling, B., Neiman, D., Podorozhny, R., NagendraPrasad, M., Raja, A., Vincent, R., Xuan, P. and Zhang, X.Q., “Evolution of the GPGP/TAEMS Domain-Independent Coordination Framework,” Auton. Agents Multi-Agent Syst. 9(1), 87–143 (2004).CrossRefGoogle Scholar
Excelente-Toledo, C. B. and Jennings, N. R., “The dynamic selection of coordination mechanisms,” Auton. Agents Multi-Agent Syst. 9, 55–85 (2004).CrossRefGoogle Scholar
Rosenfeld, A., A Study of Dynamic Coordination Mechanisms Ph.D. Thesis (Bar Ilan University, 2007).Google Scholar
Klien, G., Woods, D. D, Bradshaw, J. M., Hoffman, R. R. and Feltovich, P. J., “Ten challenges for making automation a “team player” in joint human-agent activity,” IEEE Intell. Syst. 19(6), 91–95 (2004).CrossRefGoogle Scholar
Shen, W.-M., Salemi, B. and Will, P., “Hormone-inspired adaptive communication and distributed control for CONTRO self-reconfigurable robots,” IEEE Trans. Rob. Autom. 18(5), 700–712 (2002).CrossRefGoogle Scholar
Yoon, K. and Hwang, C., Multiple Attribute Decision Making: An Introduction (Prentice Hall, Thousand Oaks: Sage, 1995).CrossRefGoogle Scholar
Adler, M., Sitaraman, R. K. and Venkataramani, H., “Algorithms for optimizing the bandwidth cost of content delivery,” Comput. Netw. 55(18), 4007–4020 (2011).CrossRefGoogle Scholar
Balch, T., “Reward and Diversity in Multirobot Foraging,” IJCAI-99 Workshop on Agents Learning About, From and with Other Agents (1999).Google Scholar
Balch, T., www.teambots.org (2000).Google Scholar
Watkins, C. J. C. H., Learning from Delayed Rewards Ph.D. Dissertation (Kings College, 1989).Google Scholar
Erusalimchik, D. and Kaminka, G. A., Towards Adaptive Multi-robot Coordination Based on Resource Expenditure Velocity (IOS Press, Amsterdam, Netherlands, 2008).Google Scholar
Sutton, R. S., “Reinforcement Learning: Past, Present and Future,” SEAL (1998) pp. 195–197.Google Scholar
Williams, R. J., “Simple statistical gradient-following algorithms for connectionist reinforcement learning,” Mach. Learn. 8, 229–256 (1992).CrossRefGoogle Scholar
Kohl, N. and Stone, P., “Machine Learning for Fast Quadrupedal Locomotion,” AAAI (2004) pp. 611–616.Google Scholar