No Access

ALTERNATIVE METHODS FOR MULTI-ROBOT TASK ALLOCATION

B. B. CHOUDHURY

Department of Mechanical Engineering, National Institute of Technology Rourkela, Rourkela-769008, Orissa, India

Search for more papers by this author

and

B. B. BISWAL

Department of Mechanical Engineering, National Institute of Technology Rourkela, Rourkela-769008, Orissa, India

Search for more papers by this author

https://doi.org/10.1142/S0219686709001717Cited by:8 (Source: Crossref)

Abstract

One of the most important aspects in the design of multi-robot systems (MRS) is the allocation of tasks among the robots in a productive and efficient manner. This paper presents an empirical study on task allocation strategies in multirobot environment. In general, optimal solutions are found through an exhaustive search, but because there are n × m ways in which m tasks can be assigned to n robots, an exhaustive search is often not possible with increased number of tasks. Task allocation methodologies for multirobot systems are developed by considering their capability in terms of time and space. The present work adopts a two-phase methodology to allocate tasks optimally amongst the candidate robots. The allocation cost of the robots is determined during the first phase and alternate algorithms are used in the second phase for optimizing the allocation. The work considers systems of practical sizes and the results obtained through this are helpful in recommending appropriate techniques to the users of MRS for increasing producibility and robot utilization. Three different approaches using Linear programming, Hungarian Algorithm and Knapsack Algorithm are presented and their results are analyzed for the suitability of the methods for an allocation problem. Simulation results are presented and compared for the benefit of the users.

Keywords:

References

Boyaret al., The maximum resource bin packing problem, Proceedings of the Fifteenth International Symposium on Fundamentals of Computation Theory (2005) pp. 1–19. Google Scholar
R. Cohen, L. Katzir and D. Raz, Information Processing Letters 162 (2006), DOI: 10.1016/j.ipl.2006.06.003. Google Scholar
K. A. Dowsland and W. B. Dowsland, European Journal of Operational Research 56, 2 (1992), DOI: 10.1016/0377-2217(92)90288-K. Crossref, Web of Science, Google Scholar
Cormen et al. , Introduction to Algorithms , 2nd edn. ( McGraw-Hill Publications , 2002 ) . Google Scholar
J. F. Goncalves and M. G. C. Resende, A Hybrid Heuristic for the Constrained Two-Dimensional Non-Guillotine Orthogonal Cutting Problem, AT&T Labs Research Technical Report TD-6UNQN6, 2006 . Google Scholar
Epstein et al. , Two-dimensional packing with conflicts , Proceedings of the 16th International Symposium on Fundamentals of Computation Theory ( 2007 ) . Google Scholar
Lodiet al., Discrete Applied Mathematics 379 (2002), DOI: 10.1016/S0166-218X(01)00347-X. Google Scholar
A. Amaral and A. Letchford, An Improved Upper Bound for the Two-Dimensional Nonguillotine Cutting Problem, Technical report, Lancaster University, UK, 2001 . Google Scholar
Boschettiet al., IMA Journal of Management Mathematics 13, 95 (2002), DOI: 10.1093/imaman/13.2.95. Crossref, Web of Science, Google Scholar
C. A. Bererton, Multi-Robot Coordination and Competition Using Mixed Integer and Linear Programs, The Robotics Institute, Carnegie Mellon University (2004), pp. 1–183 . Google Scholar
G. B. Dantzig, Operations Research 50(1), 42 (2002), DOI: 10.1287/opre.50.1.42.17798. Crossref, Web of Science, Google Scholar
Li-Nan Zu et al. , Algorithm of task-allocation based on realizing at the lowest cost in multi mobile robot system , Proceedings of the Third International Conference on Machine Learning and Cybernetics ( Shanghai , 2004 ) . Google Scholar
W. Jianguo, H. Peikun and C. We, Journal of Systems Engineering and Electronics 18(1), 27 (2007), DOI: 10.1016/S1004-4132(07)60131-5. Crossref, Web of Science, Google Scholar
R. P. Hernández and N. J. Dimopoulos, IEEE Transactions on Systems, Man, and Cybernetics — Part A: Systems and Humans 1 (2005). Google Scholar
S. Fujita and T. Hada, Theoretical Computer Science 939 (2002), DOI: 10.1016/S0304-3975(01)00410-8. Web of Science, Google Scholar