Hostname: page-component-586b7cd67f-t8hqh Total loading time: 0 Render date: 2024-11-22T07:14:00.708Z Has data issue: false hasContentIssue false
  • English
  • Français

Dynamic task allocation in cooperative robot teams

Published online by Cambridge University Press:  17 August 2011

Athanasios Tsalatsanis ,
Ali Yalcin  and
Kimon. P. Valavanis
Athanasios Tsalatsanis*
Affiliation:
University of South Florida, Tampa, FL, USA
Ali Yalcin
Affiliation:
Department of Industrial and Management Systems Engineering, University of South Florida, Tampa, FL, USA
Kimon. P. Valavanis
Affiliation:
Department of Electrical and Computer Engineering, University of Denver, Denver, CO, USA
*
*Corresponding author. E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Summary

In this paper, a dynamic task allocation and controller design methodology for cooperative robot teams is presented. Fuzzy-logic-based utility functions are derived to quantify each robot's ability to perform a task. These utility functions are used to allocate tasks in real time through a limited lookahead control methodology partially based on the basic principles of discrete event supervisory control theory. The proposed controller design methodology accommodates flexibility in task assignments, robot coordination, and tolerance to robot failures and repairs. Implementation details of the proposed methodology are demonstrated through a warehouse patrolling case study.

Keywords

Supervisory controlCooperative robot teamsTask allocationLimited lookahead policy
Type
Articles
Information
Robotica , Volume 30 , Issue 5 , September 2012 , pp. 721 - 730
Copyright
Copyright © Cambridge University Press 2011

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

1.Kumar, V. and Sahin, F., “Cognitive Maps in Swarm Robots for the Mine Detection Application,” Proceedings of the IEEE International Conference on Systems, Man and Cybernetics, Washington, DC, USA (2003) pp. 3364–3369.Google Scholar
2.Zhang, Y., Schervish, M., Acar, E. U. and Choset, H. A., “Probabilistic Methods for Robotic Landmine Search,” Proceedings of the International Conference on Intelligent Robots and Systems, Maui, HI, USA (2001) pp. 1525–1532.Google Scholar
3.Jennings, J. S., Whelan, G. and Evans, W. F., “Cooperative Search and Rescue with a Team of Mobile Robots,” Proceedings of the International Conference on Advanced Robotics, Monterey, CA (1997) pp. 193–200.Google Scholar
4.Krishnamurthy, B. and Evans, J., “HelpMate: A Robotic Courier for Hospital Use,” Proceedings of the IEEE International Conference on Systems, Man and Cybernetics, Chicago, IL, USA (1992) pp. 1630–1634.Google Scholar
5.Ramadge, P. J. and Wonham, W. M., “Supervisory control of a class of discrete event processes,” SIAM J. Control and Optim. 18 (5), 452–462 (1987).Google Scholar
6.Parker, L. E., “ALLIANCE: An architecture for fault tolerant multirobot cooperation,” IEEE Trans. Robot. Autom. 14 (2), 220–240 (1998).CrossRefGoogle Scholar
7.Zlot, R., Stentz, A., Dias, M. B. and Thayer, S. A. T. S., “Multi-Robot Exploration Controlled by a Market Economy,” Proceedings of the International Conference on Robotics and Automation, Washington, DC, USA (2002) pp. 3016–3023.Google Scholar
8.Timofeev, A. V., Kolushev, F. A. and Bogdanov, A. A., “Hybrid Algorithms of Multi-Agent Control of Mobile Robots,” Proceedings of the International Joint Conference on Neural Networks, Washington, DC, USA (1999) pp. 4115–4118.Google Scholar
9.Liu, W., Winfield, A. F. T., Sa, J., Chen, J. and Dou, L., “Towards energy optimization: Emergent task allocation in a swarm of foraging robots,” Adapt. Behav. 15 (3), 289–305 (2007).CrossRefGoogle Scholar
10.Labella, T. H., Dorigo, M. and Deneubourg, J. L., “Self-organised task allocation in a group of robots,” Distrib. Auton. Robot. Syst. 6, 389–398 (2007).Google Scholar
11.Chen, J. and Sun, D., “Resource constrained multirobot task allocation based on leader-follower coalition methodology,” Int. J. Robot. Res. (2011) (doi:10.1177/0278364910396552).CrossRefGoogle Scholar
12.Lerman, K., Jones, C., Galstyan, A. and Matari, M. J., “Analysis of dynamic task allocation in multi-robot systems,” Int. J. Robot. Res. 25 (3), 225–241 (2006).CrossRefGoogle Scholar
13.Han, Y., Li, D., Chen, J., Yang, X. and Hu, Y., “Task Allocation Algorithm Based on Robot Ability and Relevance with Group Collaboration in a Robot Team,” Proceedings of the International Conference on Intelligent Networks and Intelligent Systems (2009) pp. 273–277.Google Scholar
14.Tsalatsanis, A., Yalcin, A. and Valavanis, K. P., “Optimized Task Allocation in Cooperative Robot Teams,” Proceedings of the 17th Mediterranean Conference on Control and Automation, Thessaloniki, Greece (2009) pp. 270–275.Google Scholar
15.Botelho, S. C. and Alami, R., “M+: A Scheme for Multi-Robot Cooperation Through Negotiated Task Allocation and Achievement”, Proceedings of the IEEE International Conference on Robotics and Automation, Detroit, MI, USA (1999) pp. 1234–1239.Google Scholar
16.Gerkey, B. P. and Mataric, M. J., “Sold!: Auction methods for multirobot coordination,” IEEE Trans. Robot. Autom. 18 (5), 758–768 (2002).CrossRefGoogle Scholar
17.Lagoudakis, M. G., Berhault, M., Koenig, S., Keskinocak, P. A. and Kleywegt, A. J., “Simple Auctions with Performance Guarantees for Multi-Robot Task Allocation,” Proceedings of the International Conference on Intelligent Robots and Systems, St. Louis, MO, USA (2004) pp. 698–705.Google Scholar
18.Morton, R. D., Bekey, G. A. and Clark, C. M., “Altruistic Task Allocation Despite Unbalanced Relationships within Multi-Robot Communities,” Proceedings of the International Conference on Intelligent Robots and Systems, St. Louis, MO, USA (2009) pp. 5849–5854.Google Scholar
19.Muralidharan, J., Gunasekaran, A., Nachiappan, S. and Kumar, A. Nivin, “Efficient mechanism development for multirobot coordination,” International Journal of Industrial and Systems Engineering, (2008) Vol. 3, No. 2, pp. 149–161.Google Scholar
20.Mezei, I., Malbasa, V. and Stojmenovic, I., “Auction aggregation protocols for wireless robot-robot coordination,” Proceedings of the International Conference on Ad-hoc Mob. Wirel. Netw. Murcia, Spain (2009) pp. 180–193.Google Scholar
21.Elango, M., Nachiappan, S. and Tiwari, M. K., “Balancing task allocation in multi-robot systems using k means clustering and auction based mechanisms,” Expert Syst. Appl. 38 (6), 6486–6491 (2010).CrossRefGoogle Scholar
22.Song, T., Yan, X., Liang, A., Chen, K. and Guan, H., “A Distributed Bidirectional Auction Algorithm for Multirobot Coordination,” Proceedings of the International Conference on Research Challenges in Computer Science, Shanghai, China (2009) pp. 145–148.Google Scholar
23.Koenig, S., Keskinocak, P. and Tovey, C., “Progress on Agent Coordination with Cooperative Auctions,” Proceedings of the AAAI Conference on Artificial Intelligence, Atlanta, GA, USA (2010).Google Scholar
24.Choi, H. L., Brunet, L. and How, J. P., “Consensus-based decentralized auctions for robust task allocation,” IEEE Trans. Robot. Autom. 25 (4), 912–926 (2009).CrossRefGoogle Scholar
25.Thomas, G. and Williams, A. B., “Sequential Auctions for Heterogeneous Task Allocation in Multiagent Routing Domains,” Proceedings of the IEEE International Conference on Systems, Man and Cybernetics, San Antonio, TX, USA (2009) pp. 1995–2000.Google Scholar
26.Viguria, A. and Howard, A. M., “An integrated approach for achieving multirobot task formations,” IEEE/ASME Trans. Mechatronics 14 (2), 176–186 (2009).CrossRefGoogle Scholar
27.Davis, R. and Smith, R. G., “Negotiation as a metaphor for distributed problem solving,” Artif. Intell. 20 (1), 63–109 (1983).CrossRefGoogle Scholar
28.Chung, S. L., Lafortune, S. and Lin, F., “Limited lookahead policies in supervisory control of discrete event systems,” IEEE Trans. Autom. Control 37 (12), 1921–1935 (1992).CrossRefGoogle Scholar
29.Kumar, R., Cheung, H. M. and Marcus, S. I., “Extension based limited lookahead supervision of discrete event systems,” Automatica 34 (11), 1327–1344 (1998).CrossRefGoogle Scholar
30.Chung, S.-L., Lafortune, S. and Lin, F., “Recursive computation of limited lookahead supervisory controls for discrete event systems,” Discrete Event Dyn. Syst. 3 (1), 71–100 (1993).CrossRefGoogle Scholar
31.Chung, S.-L., Lafortune, S. and Lin, F., “Supervisory control using variable lookahead policies,” Discrete Event Dyn. Syst. 4 (3), 237–268 (1994).CrossRefGoogle Scholar
32.Hadj-Alouane, N. B., Lafortune, S. and Feng, L., “Variable lookahead supervisory control with state information,” IEEE Trans. Autom. Control 39 (12), 2398–2410 (1994).CrossRefGoogle Scholar
33.Heymann, M. and Lin, F., “On-line control of partially observed discrete event systems,” Discrete Event Dyn. Syst. 4 (3), 221–236 (1994).CrossRefGoogle Scholar
34.Kumar, R. and Garg, V. K., “Control of stochastic discrete event systems modeled by probabilistic languages,” IEEE Trans. Autom. Control 46 (4), 593–606 (2001).CrossRefGoogle Scholar
35.Lin, F., “Robust and adaptive supervisory control of discrete event systems,” IEEE Trans. Autom. Control 38 (12), 1848–1852 (1993).Google Scholar
36.Winacott, C. and Rudie, K., “Limited Lookahead Supervisory Control of Probabilistic Discrete-Event Systems,” Proceedings of the IEEE Conference on Communication, Control, and Computing, Monticello, IL, USA (2009) pp. 660–667.Google Scholar
37.Millan, J. and O'Young, S., “On-Line Supervisory Control of Hybrid Systems Using Embedded Simulations,” Proceedings of the International Workshop on Discrete Event Systems, Berlin, Germany (2010).Google Scholar
38.Auer, A., Dingel, J. and Rudie, K., “Concurrency control generation for dynamic threads using discrete-event systems,” 47th Annual Allerton Conference on Communication, Control, and Computing, Monticello, IL, USA (2009).Google Scholar
39.Grigorov, L. and Rudie, K., “Near-optimal online control of dynamic discrete-event systems,” Discrete Event Dyn. Syst. 16 (4), 419–449 (2006).CrossRefGoogle Scholar
40.Yi-Liang, C., Laortune, S. and Feng, L., “How to Reuse Supervisors when Discrete Event System Models Evolve,” Proceedings of the IEEE Conference on Decision and Control, San Diego, CA, USA (1997) pp. 2964–2969.CrossRefGoogle Scholar
41.Gordon, D. and Kiriakidis, K., “Adaptive Supervisory Control of Interconnected Discrete Event Systems,” Proceedings of the IEEE International Conference on Control Applications, Anchorage, AK, USA (2000) pp. 935–940.Google Scholar
42.Gordon-Spears, D. and Kiriakidis, K., “Reconfigurable robot teams: Modeling and supervisory control,” IEEE Trans. Control Syst. Technol. 12 (5), 763–769 (2004).CrossRefGoogle Scholar
43.Kiriakidis, K. and Gordon, D., “Supervision of Multiple-Robot Systems,” Proceedings of the American Control Conference, Arlington, VA, USA (2001) pp. 2117–2120.Google Scholar
44.Xi, W., Lee, P., Ray, A. and Phopa, S. A. P. S., “A Behavior-Based Collaborative Multi-Agent System,” Proceedings of the IEEE International Conference on Systems, Man and Cybernetics, Washington, DC, USA (2003) pp. 4242–4248.Google Scholar
45.Jamie, K., Pretty, R. K. and Gosine, R. G., “Coordinated execution of tasks in a multiagent environment,” IEEE Trans. Syst. Man Cybern. 33 (5), 615–619 (2003).Google Scholar
46.Kimura, S., Takahashi, M., Okuyama, T., Tsuchiya, S. A. and Suzuki, Y. A., “A fault-tolerant control algorithm having a decentralized autonomous architecture for space hyper-redundant manipulators”, IEEE Trans. Syst. Man Cybern. 28 (4), 521–527 (1998).CrossRefGoogle Scholar
47.Tsalatsanis, A., Yalcin, A. and Valavanis, K. P., “Automata-Based Supervisory Controller for a Mobile Robot Team,” Proceedings of the IEEE Third Latin American Robotics Symposium, Chile (2006) pp. 53–59.Google Scholar
48.Cassandras, C. G. and Lafortune, S., Introduction to Discrete Event Systems (Kluwer Academic Publishers, Norwell, Massachesetts, USA, 1999).CrossRefGoogle Scholar
49.Mamdani, E. H., “Advances in the linguistic synthesis of fuzzy controllers,” Int. J. Man-Mach. Stud. 8 (6), 245–254 (1976).CrossRefGoogle Scholar
50.Bellman, R., “On the theory of dynamic programming” Proc. Natl. Acad. Sci. 38 (8), 716–719 (1952).CrossRefGoogle ScholarPubMed
51.Yalcin, A., Khemuka, A. and Deshpande, P., “Modelling inter-task dependencies and control of workflow managements systems based on supervisory control theory,” Int. J. Prod. Res. 43 (20), 4359–4379 (2005).CrossRefGoogle Scholar
52.Chevaleyre, Y., “Theoretical Analysis of the Multi-Agent Patrolling Problem,” Proceedings of the International Conference on Intelligent Agent Technology, Beijing, China (2004) pp. 302–308.Google Scholar
53.Blondel, V. D. and Tsitsiklis, J. N., “A survey of computational complexity results in systems and control,” Automatica 36 (9), 1249–1274 (2000).CrossRefGoogle Scholar