Deadlock-free dynamic resource assignment in multi-robot systems with multiple missions: application in wireless sensor networks. (English) Zbl 1240.93241
Summary: In unstructured environments, dynamic resource assignment is required for effective cooperation of robot teams. In some scenarios, robots are in charge of executing multiple missions simultaneously. This creates risks of deadlock due to the presence of shared resources among various missions. The main contribution of this paper is the development of a novel approach that combines the one-step look-ahead deadlock avoidance policy with dynamic resource assignment. The dynamic resource assignment is achieved using greedy resource assignment for multi-mission robot teams in the framework of a matrix-based discrete event controller. Simulation results are presented in MATLAB\(^\circledR\) to discuss in detail the proposed control strategy. The paper also discusses the toolkit developed in LabVIEW\(^\circledR\) which is used to implement this control framework using a suitable example.
MSC:
| 93C65 | Discrete event control/observation systems |
| 93C85 | Automated systems (robots, etc.) in control theory |
| 93B40 | Computational methods in systems theory (MSC2010) |
Software:
MatlabReferences:
| [1] | C. Chong, S. Kumar, F. Bullo. Sensor networks: evolution, opportunities and challenges[J]. Proceedings of the IEEE. 2003, 91(8): 1247–1256. · doi:10.1109/JPROC.2003.814918 |
| [2] | D. Puccinelli, M. Haenggi. Wireless sensor networks: Applications and challenges of ubiquitous sensing[J]. IEEE Circuits and Systems Magazine, 2005, 5(3): 19–31. · doi:10.1109/MCAS.2005.1507522 |
| [3] | B. Sinopoli, C. Sharp, L. Schenato, et al. Distributed control applications within sensor networks[J]. Proceedings of the IEEE, 2003, 91(8): 1235–1246. · doi:10.1109/JPROC.2003.814926 |
| [4] | K. Dantu, M. Rahimi, H. Shah, et al. Robomote: enabling mobility in sensor networks[C]//Information Processing in Sensor Networks. New York: IEEE, 2005: 404–409. |
| [5] | Z. Butler, D. Rus. Event-based motion control for mobile sensor networks[J]. IEEE Transactions on Pervasive Computing, 2003, 2(4): 34–42. · doi:10.1109/MPRV.2003.1251167 |
| [6] | J. Cortes, S. Martinez, T. Karatas, et al. Coverage control for mobile sensing network[J]. IEEE Transactions on Robotics and Automation. New York: IEEE, 2004, 20(2): 243–255. |
| [7] | B. Gerkey, M. Mataric. Sold!: Auction methods for multirobot coordination[J]. IEEE Transactions on Robotics and Autoation, 2002, 18(5): 758–768. · doi:10.1109/TRA.2002.803462 |
| [8] | B. Gerkey, M. Mataric. A formal analysis and taxonomy of task allocation in multi-robot systems[J]. International Journal of Robotics Research, 2004, 23(9): 939–954. · doi:10.1177/0278364904045564 |
| [9] | J. King, R. Pretty, R. Gosine. Coordinated execution of tasks in multiagent environment[J]. IEEE Transactions on Systems, 2003, 33(5): 615–619. |
| [10] | J. Ezpeleta, J. M. Colom, J. Martinez. A Petri net based deadlock prevention policy for flexible manufacturing systems[J]. IEEE Transaction on Robotics and Automation, 1995, 11(2): 173–184. · doi:10.1109/70.370500 |
| [11] | T. Murata. Petri nets: properties, analysis and applications[J]. Proceedings of the IEEE, 1989, 77(4): 541–580. · doi:10.1109/5.24143 |
| [12] | V. Giordano, F. Lewis, J. Mireles, et al. Coordination control policy for mobile sensor networks with shared heterogeneous resources[C]//International Conference on Control and Automation. New York: IEEE, 2005: 191–196. |
| [13] | V. Giordano, P. Ballal, F. Lewis, et al. Supervisory control of mobile sensor networks: Math formulation, simulation, implementation[J]. IEEE Transactions on Systems, Man and Cybernetics, 2006, 36(4): 806–819. · doi:10.1109/TSMCB.2006.870647 |
| [14] | D. Tacconi, F. Lewis. A new matrix model for discrete event systems: Application to simulation[J]. IEEE Control System Magazine, 1997, 17(5): 62–71. · doi:10.1109/37.621472 |
| [15] | A. Kusiak. Intelligent scheduling of automated machining systems[M]// Intelligent Design and Manufacturing. New York: John Wiley & Sons, 1992: 421–447. |
| [16] | A. Gurel, S. Bogdan, F. Lewis. Matrix approach to deadlock-free dispatching in multi-class finite buffer flowlines[J]. IEEE Transactions on Automatic Control, 2000, 45(11): 2086–2090. · Zbl 0976.90024 · doi:10.1109/9.887631 |
| [17] | F. Lewis, A. Gurel, S. Bogdan, et al. Analysis of deadlock and circular waits using a matrix model for flexible manufacturing systems[J]. Automatica, 1998, 34(9): 1083–1100. · Zbl 0966.90028 · doi:10.1016/S0005-1098(98)00048-X |
| [18] | R. A. Wysk, N. Yang, S. Joshi. Detection of deadlocks in flexible manufacturing cells[J]. IEEE Transactions on Robotics and Automation, 1991, 7(6): 853–859. · doi:10.1109/70.105378 |
| [19] | J. Mireles, F. Lewis, A. Gurel. Implementation of a deadlock avoidance policy for multipart reentrant flow lines using a matrixbased discrete event controller[C]//Proceedings of the International Symposium on Advances in Robot Dynamics and Control. New York: ASME, 2002: 479–490. |
| [20] | T. Corman, C. Leisenson, R. Rivest. Introduction to Algorithms[M]. 2nd ed. Cambridge: MIT Press, 2001. |
| [21] | M. P. Fanti, B. Maione, S. Mascolo, et al. Event-based feedback control for deadlock avoidance in flexible production systems[J]. IEEE Transactions on Robotics and Automation, 1997, 13(3): 347–363. · doi:10.1109/70.585898 |
| [22] | M. P. Fanti, B. Maione, B. Turchiano. Comparing digraph and Petri net approaches to deadlock avoidance in FMS[J]. IEEE Transactions on Systems, 2000, 30(5): 783–798. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
