logo

SCIENCE CHINA Information Sciences, Volume 59, Issue 8: 080102(2016) https://doi.org/10.1007/s11432-016-5593-x

CBBR: enabling distributed shared memory-based coordination among mobile robots

More info
  • ReceivedApr 25, 2016
  • AcceptedMay 25, 2016
  • PublishedJul 18, 2016

Abstract

Coordinating mobile robots are widely used in commercial and industrial settings to fulfill various tasks. However, to program the coordination among mobile robots is challenging. A coordination framework is needed to shield the programmer from handling low-level details of robot control and communication, while supporting flexible and cost-effective coordination at the same time. The coordination framework should also be able to well coexist with the underlying robot control. To this end, we propose the Coordination-enabled Behavior-Based Robotics (CBBR) framework. CBBR employs Distributed Shared Memory (DSM) to support coordination. The shared memory illusion built by the DSM greatly simplifies the coordination logic. Moreover, the flexible access patterns of the DSM and the rich consistency semantics of the DSM reads and writes enable flexible and cost-effective coordination. With the coordination support from the DSM, CBBR naturally extends the classical Behavior-Based Robotics (BBR) for robot control. From the perspective of robot control using BBR, the shared variables in the DSM act as the logical sensors capturing the status of coordination. The coordination algorithms are encapsulated into coordination behaviors. Thus, the physical environment status and the coordination status may trigger the physical and the coordination behaviors. The scheduling of both types of behaviors integrates coordination into robot control. We conduct a case study to demonstrate the use of CBBR. The performance measurements show the cost-effectiveness of coordinating mobile robots based on CBBR, in terms of time, space, and energy consumption.


Funded by

National Natural Science Foundation of China(61321491)

"source" : null , "contract" : "2015CB352202"

National Natural Science Foundation of China(61272047)

National Basic Research Program of China(973)

National Natural Science Foundation of China(91318301)


Acknowledgment

Acknowledgments

This work was supported by National Basic Research Program of China (973) (Grant No. 2015CB352202) and National Natural Science Foundation of China (Grant Nos. 61272047, 91318301, 61321491). This work was also partially supported by Tencent, Inc.


References

[1] Antonelli G, Leonessa A. Underwater robots: motion and force control of vehicle-manipulator systems. {IEEE Control Syst Mag}, 2008, 138--139. Google Scholar

[2] Borenstein J, Koren Y. Real-time obstacle avoidance for fast mobile robots. IEEE Trans Syst Man Cybern, 1989, 19: 1179-1187 CrossRef Google Scholar

[3] Fujita M, Kageyama K. An open architecture for robot entertainment. In: {Proceedings of the 1st International Conference on Autonomous Agents}. New York: ACM, 1997. 435--442. Google Scholar

[4] Zhan G, Shi W. Lobot: Low-cost, self-contained localization of small-sized ground robotic vehicles. IEEE Trans Parall Distrib Syst, 2013, 24: 744-753 CrossRef Google Scholar

[5] Russell R A, Thiel D, Deveza R, et al. A robotic system to locate hazardous chemical leaks. In: {Proceedings of IEEE International Conference on Robotics and Automation}, Nagoya, 1995. 1: 556--561. Google Scholar

[6] Wurman P R, D'Andrea R, Mountz M. Coordinating hundreds of cooperative, autonomous vehicles in warehouses. AI Mag, 2008, 29: 9-753 Google Scholar

[7] Matari{ć} M J, Nilsson M, Simsarin K T. Cooperative multi-robot box-pushing. In: {Proceedings of 1995 IEEE/RSJ International Conference on Intelligent Robots and Systems: Human Robot Interaction and Cooperative Robots}, Pittsburgh, 1995. 3: 556--561. Google Scholar

[8] Burgard W, Moors M, Fox D, et al. Collaborative multi-robot exploration. In: {Proceedings of IEEE International Conference on Robotics and Automation}, San Francisco, 2000. 1: 476--481. Google Scholar

[9] Wawerla J, Vaughan R T. A fast and frugal method for team-task allocation in a multi-robot transportation system. In: {Proceedings of IEEE International Conference on Robotics and Automation}, Anchorage, 2010. 1432--1437. Google Scholar

[10] Brooks R A. A robust layered control system for a mobile robot. IEEE J Robotic Autom, 1986, 2: 14-23 CrossRef Google Scholar

[11] Gelernter D. Generative communication in Linda. ACM Trans Program Lang Syst, 1985, 7: 80-112 CrossRef Google Scholar

[12] Attiya H. Robust simulation of shared memory: 20 years after. Bull Eur Assoc Theor Comput Sci, 2010, 100: 99-113 Google Scholar

[13] Lamport L. On interprocess communication. Distrib Comput, 1986, 1: 86-101 CrossRef Google Scholar

[14] Ahamad M, Neiger G, Burns J E, et al. Causal memory: definitions, implementation, and programming. Distrib Comput, 1995, 9: 37-49 CrossRef Google Scholar

[15] Lynch N A. {Distributed Algorithms}. San Francisco: Morgan Kaufmann, 1996. Google Scholar

[16] Lamport L. A new solution of Dijkstra's concurrent programming problem. Commun ACM, 1974, 17: 453-455 CrossRef Google Scholar

[17] Arkin R C. {Behavior-Based Robotics}. Cambridge: MIT Press, 1998. Google Scholar

[18] Mottola L, Moretta M, Whitehouse K, et al. Team-level programming of drone sensor networks. In: {Proceedings of the 12th ACM Conference on Embedded Network Sensor Systems}. New York: ACM, 2014. 177--190. Google Scholar

[19] Marcolino L S, Chaimowicz L. No robot left behind: Coordination to overcome local minima in swarm navigation. In: {Proceedings of IEEE International Conference on Robotics and Automation}, Pasadena, 2008. 1904--1909. Google Scholar

[20] J{ä}ger M, Nebel B. Decentralized collision avoidance, deadlock detection, and deadlock resolution for multiple mobile robots. In: {Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems}, Maui, 2001. 3: 1213--1219. Google Scholar

[21] Kube C R, Bonabeau E. Cooperative transport by ants and robots. Robot Auton Syst, 2000, 30: 85-101 CrossRef Google Scholar

[22] Klotzb{ü}cher M, Bruyninckx H. A lightweight real-time executable finite state machine model for coordination in robotic systems. Technical Report, 2007. Google Scholar

[23] Dijkstra E W. Solution of a problem in concurrent programming control. Commun ACM, 1965, 8: 569-101 CrossRef Google Scholar

[24] Peterson G L. An $o (n \log n)$ unidirectional algorithm for the circular extrema problem. ACM Trans Program Lang Syst, 1982, 4: 758-762 CrossRef Google Scholar

[25] Chang E, Roberts R. An improved algorithm for decentralized extrema-finding in circular configurations of processes. Commun ACM, 1979, 22: 281-283 CrossRef Google Scholar

[26] Hirschberg D S, Sinclair J B. Decentralized extrema-finding in circular configurations of processors. Commun ACM, 1980, 23: 627-628 CrossRef Google Scholar

[27] Fischer M J, Lynch N A, Paterson M S. Impossibility of distributed consensus with one faulty process. J ACM, 1985, 32: 374-382 CrossRef Google Scholar

[28] Dolev D, Lynch N A, Pinter S S, et al. Reaching approximate agreement in the presence of faults. J ACM, 1986, 33: 499-516 CrossRef Google Scholar

[29] Dijkstra E W. Hierarchical ordering of sequential processes. Acta Inform, 1971, 1: 115-138 CrossRef Google Scholar

[30] Lynch N A. Upper bounds for static resource allocation in a distributed system. J Comput Syst Sci, 1981, 23: 254-278 CrossRef Google Scholar

Copyright 2019 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备18024590号-1